精华内容
下载资源
问答
  • 基于后缀语法树的代码抄袭检测研究 研究代码抄袭监测的文档
  • Atitti 语法树AST 后缀表达式 DAG 三地址代码
                   

    Atitti. 语法树AST、后缀表达式、DAG、三地址代码

     

     

    抽象语法树的观点认为任何复杂的语句嵌套情况都可以借助于树的形式加以描述。确实,不得不承认应用抽象语法树可以使语句翻译变得相对容易,它很好地描述了语句、表达式之间的联系。不过,由于Neo Pascal并不会显式构造抽象语法树,所以不得不借助于其他数据结构实现。根据先前的经验,栈结构就是不二之选

     

    DAG(有向无环图)

     

    后缀表达式:也称为逆波兰表达式,这种形式简单明晰,便于存储。在处理表达式翻译时,后缀表达式有着其他形式无法比拟的优势。不过,由于后缀表达式的应用领域比较单一,所以很少独立作为一个实际编译器的IR存在。

    1. 后缀表达式

     编辑

    不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *

    作者::  ★(attilax)>>>   绰号:老哇的爪子 ( 全名::Attilax Akbar Al Rapanui 阿提拉克斯 阿克巴 阿尔 拉帕努伊 ) 汉字名:艾龙,  EMAIL:1466519819@qq.com

    转载请注明来源: http://blog.csdn.net/attilax

     

    1.1. 前缀记法、中缀记法和后缀记法

    它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。

    举例:
    (3 + 4) × 5 - 6就是中缀表达式
    - × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式

     

    中缀表达式(中缀记法)
    中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
    虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。

     

     

    三地址代码:也称为"四元组",即操作符和三个操作数地址。这是一种最为常见的IR。甚至有些书籍认为IR就是中间代码(即三地址代码

     

     

    所谓的三地址,指的就是每一行代码通常包含三个地址信息,即操作数1、操作数2、结果操作数。例如,(ADD  A,1,C )这行三地址代码的含义就是A+1→C。这种形式初看与汇编语言有点类似

    当然,三地址代码也不是完美的,由于它是相对离散的,在分析源程序结构方面,它就不及语法树便捷

     

     

     三地址代码的理由如下:三地址代码是一种线性IR。由于输入源程序及输出目标程序都是线性的,因此,线性IR有着其他形式无法比拟的优势。另外,相对于其他表示形式而言,程序员对于线性表示形式通常会有一种莫名的亲切感,编译器设计者当然也不例外。早期编译器设计者往往都是汇编语言程序设计的高手,可以非常自然、流畅地阅读线性的三地址代码形式。同时,线性表示形式也会降低输入输出的实现难度。随着编译器"端"、"遍"等概念的出现,IR已经不仅仅是一种存储在内存中的数据结构。有时它也需要以文件形式转存输出,作为接口供其他系统读取使用。

     

    为什么将其设计为"三地址"的形式呢?实际上,这是计算机科学家经过多年实践探索后才得到共识的。三地址代码并不是唯一的线性IR,只能说是最为常见的而已。在编译技术领域,二地址代码、单地址代码(即栈式机代码)都曾出现过,也曾在某些应用领域盛行一时,尤其是单地址代码。

     

    然而,单地址代码的情况则截然不同了,在现代编译器设计中,单地址代码也是应用比较广泛的一种IR。尤其是近年随着混合语言的日渐壮大,单地址代码也重新进入了人们的视野。由于执行单地址代码程序的栈式机架构相对比较简单,可以非常方便地构造相关的解释器或虚拟机,所以单地址代码深受混合语言设计者的欢迎。读者熟悉的Java字节码、.NET的IL都是单地址代码

     

    三地址代码是在二地址代码的基础上发展而来的。二地址代码的不足之处在于它通常会给其中一个源操作分量带来一定副作用。当然,这种设计的灵感最初是来源于x86指令系统的,但是却忘了一个重要的区别:x86指令中往往都是以寄存器作为暂存空间的。而暂存空间对于二地址代码却是一个棘手的问题。为了解决二地址代码的不足,人们提出了一个对源操作分量不产生任何副作用的形式,那就是三地址代码。也就是说,在一行三地址代码中,任何运算都不会改变两个源操作分量。这是三地址代码与二地址代码的主要区别。这个特性是非常重要的,它将使得编译器更自由地复用名字与值,不必考虑代码带来的副作用。

     

    最后,再来谈谈IR的级别,即IR依赖于目标机的程度。按级别分类,可将IR分成三类:高级形式(HIR)、中级形式(MIR)、低级形式(LIR),也可称为高级中间语言、中级中间语言、低级中间语言。

    高级形式(HIR)是一种尽可能保持了源语言程序结构的IR,这种形式能较好地保留源程序的原始语义信息。由于高级形式太接近源语言程序结构,所以很少有编译器将其独立作为IR传递给后端。

    中级形式(MIR)既要以一种与语言无关的方式在一定程度上反映源语言的特性,又要能够适应多种体系结构的IR。中级形式是一种比较常用的IR,它兼顾了源语言、目标机的特性,又能适用于大多数优化算法。当一个编译器仅设计一种IR时,中级形式是较理想的选择。

    低级形式(LIR)就是在一定程度上包含某些目标机特性的IR,比目标语言稍高级,常作为一些机器相关的优化算法的输入。不过,实际上,除了一些较大型的编译器需要使用低级形式之外,低级形式并不是很常见。因为更多编译器设计者更愿意直接基于目标语言作优化。

     

     

    表5-6  if语句的翻译方案

    if语句

    翻 译 方 案

    if <表达式> then

       <语句1>

    else

       <语句2>

    <表达式翻译>

    (JNT                   , <表达式结果> , null , __L1 )

    <语句1>

    (JMP                   , __L2 , null , null )

    (LABEL              , __L1 , null , null )

    <语句2>

    (LABEL              , __L2 , null , null )

    如果省略了else部分,那么只需将翻译方案中第4~6行语句省略,并将第7行的"__L2"替换为"__L1"即可。semantic068、semantic069、semantic070主要的功能就是根据翻译方案翻译输入的if语句。也就是说,试图依靠这三个语义子程序,完成翻译方案中黑体语句的生成。在上述翻译方案中,可以暂且将"__L1"称为"假分支标号",而将"__L2"称为"出口标号"。另外,需注意一点,当输入语句是if-then结构时,第7行语句的标号不应该取出口标号,而应该取假分支标号,因为此时并不存在真正意义的假分支,因此,可以将假分支标号当作出口标号使用。

     

    while语句的翻译方案

    while语句

    翻译方案

    while <表达式> do

          <语句>

    (LABEL ,__L1,null,null)

    <表达式翻译>

    (JNT               ,<表达式结果>,null,__L0)

    <语句>

    (JMP               ,__L1,null,null)

    (LABEL ,__L0,null,null)

     

     

    5.1.2 IR设计及其级别 - 51CTO.COM.html

               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • Atitti. 语法树AST、后缀表达式、DAG、三地址代码.pdf
  • 语法树AST、后缀表达式、DAG、三地址代码 抽象语法树的观点认为任何复杂的语句嵌套情况都可以借助于树的形式加以描述。确实,不得不承认应用抽象语法树可以使语句翻译变得相对容易,它很好地描述了语句、...

    Atitti. 语法树AST、后缀表达式、DAG、三地址代码

     

     

    抽象语法树的观点认为任何复杂的语句嵌套情况都可以借助于树的形式加以描述。确实,不得不承认应用抽象语法树可以使语句翻译变得相对容易,它很好地描述了语句、表达式之间的联系。不过,由于Neo Pascal并不会显式构造抽象语法树,所以不得不借助于其他数据结构实现。根据先前的经验,栈结构就是不二之选。

     

    DAG(有向无环图)

     

    后缀表达式:也称为逆波兰表达式,这种形式简单明晰,便于存储。在处理表达式翻译时,后缀表达式有着其他形式无法比拟的优势。不过,由于后缀表达式的应用领域比较单一,所以很少独立作为一个实际编译器的IR存在。

    1. 后缀表达式

     编辑

    不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *

    作者::  ★(attilax)>>>   绰号:老哇的爪子  全名::Attilax Akbar Al Rapanui 阿提拉克斯 阿克巴 阿尔 拉帕努伊  汉字名:艾龙,  EMAIL:1466519819@qq.com

    转载请注明来源: http://blog.csdn.net/attilax

     

    1.1. 前缀记法、中缀记法和后缀记法

    它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。

    举例:
    (3 + 4) × 5 - 6 就是中缀表达式
    - × + 3 4 5 6 前缀表达式
    3 4 + 5 × 6 - 后缀表达式

     

    中缀表达式(中缀记法)
    中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
    虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。

     

     

    三地址代码:也称为"四元组",即操作符和三个操作数地址。这是一种最为常见的IR。甚至有些书籍认为IR就是中间代码(即三地址代码

     

     

    所谓的三地址,指的就是每一行代码通常包含三个地址信息,即操作数1、操作数2、结果操作数。例如,(ADD  A,1,C )这行三地址代码的含义就是A+1→C。这种形式初看与汇编语言有点类似

    当然,三地址代码也不是完美的,由于它是相对离散的,在分析源程序结构方面,它就不及语法树便捷

     

     

     三地址代码的理由如下:三地址代码是一种线性IR。由于输入源程序及输出目标程序都是线性的,因此,线性IR有着其他形式无法比拟的优势。另外,相对于其他表示形式而言,程序员对于线性表示形式通常会有一种莫名的亲切感,编译器设计者当然也不例外。早期编译器设计者往往都是汇编语言程序设计的高手,可以非常自然、流畅地阅读线性的三地址代码形式。同时,线性表示形式也会降低输入输出的实现难度。随着编译器"端"、"遍"等概念的出现,IR已经不仅仅是一种存储在内存中的数据结构。有时它也需要以文件形式转存输出,作为接口供其他系统读取使用。

     

    为什么将其设计为"三地址"的形式呢?实际上,这是计算机科学家经过多年实践探索后才得到共识的。三地址代码并不是唯一的线性IR,只能说是最为常见的而已。在编译技术领域,二地址代码、单地址代码(即栈式机代码)都曾出现过,也曾在某些应用领域盛行一时,尤其是单地址代码。

     

    然而,单地址代码的情况则截然不同了,在现代编译器设计中,单地址代码也是应用比较广泛的一种IR。尤其是近年随着混合语言的日渐壮大,单地址代码也重新进入了人们的视野。由于执行单地址代码程序的栈式机架构相对比较简单,可以非常方便地构造相关的解释器或虚拟机,所以单地址代码深受混合语言设计者的欢迎。读者熟悉的Java字节码、.NET的IL都是单地址代码

     

    三地址代码是在二地址代码的基础上发展而来的。二地址代码的不足之处在于它通常会给其中一个源操作分量带来一定副作用。当然,这种设计的灵感最初是来源于x86指令系统的,但是却忘了一个重要的区别:x86指令中往往都是以寄存器作为暂存空间的。而暂存空间对于二地址代码却是一个棘手的问题。为了解决二地址代码的不足,人们提出了一个对源操作分量不产生任何副作用的形式,那就是三地址代码。也就是说,在一行三地址代码中,任何运算都不会改变两个源操作分量。这是三地址代码与二地址代码的主要区别。这个特性是非常重要的,它将使得编译器更自由地复用名字与值,不必考虑代码带来的副作用。

     

    最后,再来谈谈IR的级别,即IR依赖于目标机的程度。按级别分类,可将IR分成三类:高级形式(HIR)、中级形式(MIR)、低级形式(LIR),也可称为高级中间语言、中级中间语言、低级中间语言。

    高级形式(HIR)是一种尽可能保持了源语言程序结构的IR,这种形式能较好地保留源程序的原始语义信息。由于高级形式太接近源语言程序结构,所以很少有编译器将其独立作为IR传递给后端。

    中级形式(MIR)既要以一种与语言无关的方式在一定程度上反映源语言的特性,又要能够适应多种体系结构的IR。中级形式是一种比较常用的IR,它兼顾了源语言、目标机的特性,又能适用于大多数优化算法。当一个编译器仅设计一种IR时,中级形式是较理想的选择。

    低级形式(LIR)就是在一定程度上包含某些目标机特性的IR,比目标语言稍高级,常作为一些机器相关的优化算法的输入。不过,实际上,除了一些较大型的编译器需要使用低级形式之外,低级形式并不是很常见。因为更多编译器设计者更愿意直接基于目标语言作优化。

     

     

    表5-6  if语句的翻译方案

    if语句

       

    if <表达式> then

       <语句1>

    else

       <语句2>

    <表达式翻译>

    (JNT                   , <表达式结果> , null , __L1 )

    <语句1>

    (JMP                   , __L2 , null , null )

    (LABEL              , __L1 , null , null )

    <语句2>

    (LABEL              , __L2 , null , null )

    如果省略了else部分,那么只需将翻译方案中第4~6行语句省略,并将第7行的"__L2"替换为"__L1"即可。semantic068、semantic069、semantic070主要的功能就是根据翻译方案翻译输入的if语句。也就是说,试图依靠这三个语义子程序,完成翻译方案中黑体语句的生成。在上述翻译方案中,可以暂且将"__L1"称为"假分支标号",而将"__L2"称为"出口标号"。另外,需注意一点,当输入语句是if-then结构时,第7行语句的标号不应该取出口标号,而应该取假分支标号,因为此时并不存在真正意义的假分支,因此,可以将假分支标号当作出口标号使用。

     

    while语句的翻译方案

    while语句

    翻译方案

    while <表达式> do

          <语句>

    (LABEL ,__L1,null,null)

    <表达式翻译>

    (JNT               ,<表达式结果>,null,__L0)

    <语句>

    (JMP               ,__L1,null,null)

    (LABEL ,__L0,null,null)

     

     

    5.1.2 IR设计及其级别 - 51CTO.COM.html

    转载于:https://www.cnblogs.com/attilax/p/5963361.html

    展开全文
  • 语法树

    2021-05-12 01:18:45
    何为语法树 什么是语法树? 你是否曾想过,这个世界存在这么多语言的意义。 假如现在你面前有一个物体,它是一个不规则的圆体,整个身体通红,头部还有一根细长稍微弯曲偏右呈棕色的圆柱体。 在中文我们称之为...
    下图为一个表达式的语法,该表达式的后缀形式为 ( A)

     
     
      A.  x5y+*a/b-
     
      B.  x5yab*+/-
     
      C.  -/*x+5yab
     
      D.  x5*y+a/b-

    何为语法树

    什么是语法树?

    你是否曾想过,这个世界存在这么多语言的意义。

    假如现在你面前有一个物体,它是一个不规则的圆体,整个身体通红,头部还有一根细长稍微弯曲偏右呈棕色的圆柱体。
    在中文我们称之为「苹果」,
    在英文我们称之为「Apple」,
    在日文中我们称之为「アップル」,
    在法语中我们称之为「pomme」,
    在德语中我们称之为「Apfel」,
    无论用不同的语言,针对这个物体在文字上、发音上都完全不一样,但这个物体确确实实的存在这个时空上,颜色、气味、形状都不曾因为语言而改变过。

    无论这个世界存在多少语言,它们所描述的真理都不曾改变过。

    或者说,真理就存在那里,可以用不同的语言的不同表达方式描述出来。那么计算机的世界,这么多编程的语言,C、C++、Java、C#、JavaScript、Python、Go、Ruby等等等,它们共同所描述的真理是什么?

    我们知道人类语言上,无论什么语种,都会有「主语」「动词」「宾语」「标点符号」来描述一个现实世界所发生的事件。
    而在计算机编程语言上,无论什么语种,都会有「类型」「运算符」「流程语句」「函数」「对象」等概念来表达计算机中存在内存中的0和1,以及背后运算与逻辑。

    语法树,计算机描述世界真理的树状结构。

    不同的语言,都会配之不同的语法分析器,而语法分析器是把源代码作为字符串读入、解析,并建立语法树的程序。语法的设计和语法分析器的实现是决定语言外在表现的重要因素。
    什么是语法树?摘自Wiki一段:

    在计算机科学中,抽象语法树(abstract syntax tree 或者缩写为 AST),或者语法树(syntax tree),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。之所以说语法是「抽象」的,是因为这里的语法并不会表示出真实语法中出现的每个细节。

    一则简单的例子

    如果我们需要让计算机帮忙算一下 「1加2再乘以3」 的结果,该怎么表达呢?
    现在我们大多数的现代编程语言,都是使用「中缀表达式」的方式来编写运算,比如JavaScript:

     

    而FORTH语言则使用「后缀表达式」,这基本上与日语中的语序是一致的:

     

    LISP语言使用的「前缀表达式」:

     

    我们再看一下这三种表达式的语法树:

    表达式语法树比较.png

    可以看出,对于这三种简单的语言,它们只是在这个语法树上按不同的规则遍历而已。三者的代码看起来差别很大,但实际上所用的树结构是相同的。

    先来看看Python的语法树

    通过Python语言自带的库文件ast,我们可以查看特定的代码被转换成怎样的语法树。

    BinOp op = Mult()表示乘法运算,与*相对应;
    BinOp op = Add()表示加法运算,与+相对应;
    Num n = 1既为数值1。

    Python语法树.png

    再窥视一下JavaScript的语法树

    在语法复杂的语言中,语法树是包含很多细节的语法结果表达式,我们需要靠语法树把这种形式以更简洁的形式表达出来。

    Javascript 有不少工具可以把代码构造出清晰的语法树,比如esprimav8SpiderMonkeyUglifyJSAST explorer等。

    这里,我使用「esprima」来探讨一下JavaScript运算(1 + 2) * 3的语法树。

    body表示程序体,而程序体中包含了一则表达式ExpressionStatement, 表达式体里包含了操作符 *,以及左右两边表达式,其中右边是数字3,而左边表达式还包含一层表达式,里面是一个+ 操作符,以及左右两边分别为12的数字。

    javascript语法树.png

    如果还没有看懂,你可以到这里看一下这段代码所生成的语法树:AST for (1 + 2)* 3;

    我们可以利用语法树做些什么?

    看到这里你可能会问,知道语法是又有什么用呢?跟我日常编写代码貌似半毛钱关系都没有。其实语法树还是很有用的,想一下如果想做「语法高亮」、「关键字匹配」、「作用域判断」、「语言转换」以及「代码压缩」等等,都是最好把代码解构成语法树之后再去各种操作,当然仅仅解构还不够,还需要提供各种函数去遍历与修改语法树。

    另一方面,去研究、去探讨计算机真实的世界不是一个很精彩很刺激的过程么?

    展开全文
  • 何为语法树

    2018-03-01 15:03:35
    何为语法树2016-03-15 | JerryC | 搬砖码农什么是语法树?你是否曾想过,这个世界存在这么多语言的意义。假如现在你面前有一个物体,它是一个不规则的圆体,整个身体通红,头部还有一根细长稍微弯曲偏右呈棕...

    原文链接:http://huang-jerryc.com/2016/03/15/%E4%BD%95%E4%B8%BA%E8%AF%AD%E6%B3%95%E6%A0%91/

    转载学习之用。

    何为语法树

    什么是语法树?

    你是否曾想过,这个世界存在这么多语言的意义。

    假如现在你面前有一个物体,它是一个不规则的圆体,整个身体通红,头部还有一根细长稍微弯曲偏右呈棕色的圆柱体。
    在中文我们称之为「苹果」,
    在英文我们称之为「Apple」,
    在日文中我们称之为「アップル」,
    在法语中我们称之为「pomme」,
    在德语中我们称之为「Apfel」,
    无论用不同的语言,针对这个物体在文字上、发音上都完全不一样,但这个物体确确实实的存在这个时空上,颜色、气味、形状都不曾因为语言而改变过。

    无论这个世界存在多少语言,它们所描述的真理都不曾改变过。

    或者说,真理就存在那里,可以用不同的语言的不同表达方式描述出来。那么计算机的世界,这么多编程的语言,C、C++、Java、C#、JavaScript、Python、Go、Ruby等等等,它们共同所描述的真理是什么?

    我们知道人类语言上,无论什么语种,都会有「主语」「动词」「宾语」「标点符号」来描述一个现实世界所发生的事件。
    而在计算机编程语言上,无论什么语种,都会有「类型」「运算符」「流程语句」「函数」「对象」等概念来表达计算机中存在内存中的0和1,以及背后运算与逻辑。

    语法树,计算机描述世界真理的树状结构。

    不同的语言,都会配之不同的语法分析器,而语法分析器是把源代码作为字符串读入、解析,并建立语法树的程序。语法的设计和语法分析器的实现是决定语言外在表现的重要因素。
    什么是语法树?摘自Wiki一段:

    在计算机科学中,抽象语法树(abstract syntax tree 或者缩写为 AST),或者语法树(syntax tree),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。之所以说语法是「抽象」的,是因为这里的语法并不会表示出真实语法中出现的每个细节。

    一则简单的例子

    如果我们需要让计算机帮忙算一下 「1加2再乘以3」的结果,该怎么表达呢?
    现在我们大多数的现代编程语言,都是使用「中缀表达式」的方式来编写运算,比如JavaScript:

    
         
    1
    
         
    (1 + 2) * 3

    而FORTH语言则使用「后缀表达式」,这基本上与日语中的语序是一致的:

    
         
    1
    
         
    1 2 + 3 *

    LISP语言使用的「前缀表达式」:

    
         
    1
    
         
    ( * (+ 1 2) 3)

    我们再看一下这三种表达式的语法树:

    表达式语法树比较

    可以看出,对于这三种简单的语言,它们只是在这个语法树上按不同的规则遍历而已。三者的代码看起来差别很大,但实际上所用的树结构是相同的。

    先来看看Python的语法树

    通过Python语言自带的库文件ast,我们可以查看特定的代码被转换成怎样的语法树。

    
         
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    
         
    >>> import ast
    >>> ast.dump(ast.parse("(1 + 2) * 3"))
    'Module(
    body=[
    Expr(
    value=BinOp(
    left=BinOp(
    left=Num(n=1),
    op=Add(),
    right=Num(n=2)
    ),
    op=Mult(),
    right=Num(n=3)
    )
    )
    ]
    )'

    BinOp op = Mult()表示乘法运算,与*相对应;
    BinOp op = Add()表示加法运算,与+相对应;
    Num n = 1既为数值1。

    Python语法树

    再窥视一下JavaScript的语法树

    在语法复杂的语言中,语法树是包含很多细节的语法结果表达式,我们需要靠语法树把这种形式以更简洁的形式表达出来。

    Javascript 有不少工具可以把代码构造出清晰的语法树,比如 esprimav8SpiderMonkeyUglifyJSAST explorer等。

    这里,我使用「esprima」来探讨一下JavaScript运算(1 + 2) * 3的语法树。

    javascript code:

    
         
    1
    
         
    (1 + 2)* 3;

    ast for json:

    
         
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    
         
    {
    "type": "Program",
    "body": [
    {
    "type": "ExpressionStatement",
    "expression": {
    "type": "BinaryExpression",
    "operator": "*",
    "left": {
    "type": "BinaryExpression",
    "operator": "+",
    "left": {
    "type": "Literal",
    "value": 1,
    "raw": "1"
    },
    "right": {
    "type": "Literal",
    "value": 2,
    "raw": "2"
    }
    },
    "right": {
    "type": "Literal",
    "value": 3,
    "raw": "3"
    }
    }
    }
    ],
    "sourceType": "script"
    }

    body表示程序体,而程序体中包含了一则表达式ExpressionStatement, 表达式体里包含了操作符 *,以及左右两边表达式,其中右边是数字3,而左边表达式还包含一层表达式,里面是一个+ 操作符,以及左右两边分别为12的数字。

    javascript语法树

    如果还没有看懂,你可以到这里看一下这段代码所生成的语法树:AST for (1 + 2)* 3;*%203%0A)

    我们可以利用语法树做些什么?

    看到这里你可能会问,知道语法是又有什么用呢?跟我日常编写代码貌似半毛钱关系都没有。其实语法树还是很有用的,想一下如果想做「语法高亮」、「关键字匹配」、「作用域判断」、以及「代码压缩」等等,都是最好把代码解构成语法树之后再去各种操作,当然仅仅解构还不够,还需要提供各种函数去遍历与修改语法树。

    另一方面,去研究、去探讨计算机真实的世界不是一个很精彩很刺激的过程么?


    展开全文
  • 构建 语法树 来解析 数学表达式

    千次阅读 2018-11-30 12:53:04
    构建 语法树 来解析 数学表达式 本文主要讲如何把一个数学表达式转化成语法树,并通过语法树来解出结果。 引入 这个主要是用来学习语法树的构建,数学表达式只是一个引子,本项目可以引申到 HTTP 请求报文解析,SQL...
  • 后缀表达式

    2015-09-01 12:56:34
    构造表达式后用中序遍历输出结果。 #include #include #include #include #include using namespace std; const int MAX =100; struct node {  char data;  struct node *l;  
  • 【SQL】SQL语法树

    万次阅读 2018-04-08 22:32:57
    1. 为什么会出现SQL语法树? 假设有一个SQL语句 select name,age,count(name) as count_name, count(id) as count_id from mytable where id = ? and name = ? 这是一条sql语句,如果你想运行这个语句(下面写...
  • 实现了中缀式变后缀,语法树的生成,可以进行简单的计算
  • ANTLR语法树与树的遍历

    千次阅读 2014-05-15 15:44:01
    ANTLR中抽象语法树(AST)的生成和使用 直接在语法文件中嵌入求值处理代码的方式在ANTLR中称为嵌入式动作。复杂情况下需要基于语法树遍历生成目标代码。前者语法复杂时使语法文件臃肿。另外,语法可能经常需要修改...
  • ANTLR4 解析语法树 以及IDEA相关插件使用 前言 首先,写这篇博文主要是为了记录下我在用antlr+idea开发时遇到的坑点来帮助大家,希望大家不要走我的弯路,同时也是记录自己的一个写编译器历程。 ANTLR简介 在这就给...
  • 四则运算--语法树、中缀表达式、波兰表达式、逆波兰表达式中缀表达式和语法树中缀表达式语法树前缀表达式(波兰式)中缀表达式生成前缀表达式根据前缀表达式计算结果后缀表达式(逆波兰式)中缀表达式生成后缀表达式...
  • AST语法树自己写代码解析的话就比较麻烦,有现成的库可以解析PHP,就像webpack就是自己解析js的语法代码,编译成各种版本的可用代码 githubhttps://github.com/josdejong/mathjs ExtensionDescription ...
  • iOS逆向:【代码混淆】1、基于编译器混淆静态库(StaticLib)2、字符串加密:使用clang-c接口将源代码转换成抽象语法树,并对抽象语法树进行遍历和分析,分析代码中的字符串,并进行加密处理。
  • 输入中缀表达式 输出后缀表达式 VC6.0
  • 上篇笔记介绍了语法分析相关的一些基础概念,本篇笔记根据龙书第2.5节的内容实现一个针对简单表达式的后缀语法翻译器Demo。 备注:原书中的demo是java实例,我给出的将是逻辑一致的Python版本的实现。 在简单后缀...
  • 何为抽象语法树(AST)

    2018-03-19 21:23:00
    其实语法树还是很有用的,想一下如果想做「语法高亮」、「关键字匹配」、「作用域判断」、以及「代码压缩」等等,都是最好把代码解构成语法树之后再去各种操作,当然仅仅解构还不够,还需要提供各种函数去遍历与修改...
  • ANTLR中抽象语法树(AST)的生成和使用 直接在语法文件中嵌入求值处理代码的方式在ANTLR中称为嵌入式动作。复杂情况下需要基于语法树遍历生成目标代码。前者语法复杂时使语法文件臃肿。另外,语法可能经常需要...
  • 联想一:前缀记法、中缀记法和后缀记法 根据前缀表达式的定义去写出答案 前缀记法、中缀记法和后缀记法都是对表达式的记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的...
  • 针对后缀树聚类选取基类时,基类短语出现信息不规范、重复和冗余的问题,提出了一种改进后缀树聚类算法。该算法首先以短语互信息算法改进基类的选取,选出遵守维吾尔语语法规则的基类短语;然后,利用短语归并算法对...
  • AST(Abstract syntax tree)即为“抽象语法树”,简称语法树,指代码在计算机内存的一种树状数据结构,便于计算机理解和阅读。 一般只有语言的编译器开发人员或者从事语言设计的人员才涉及到语法树的提取和处理...
  • 表达式与前中后缀表达式

    万次阅读 多人点赞 2018-10-11 21:09:03
    计算机科学中,除了栈以外,二叉树也是处理表达式的常用工具,为了处理表达式而遵循相应规则构造的被称为表达式。 表达式 算数表达式是分层的递归结构,一个运算符作用于相应的运算对象,其运算对象又可以是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,148
精华内容 8,059
关键字:

后缀语法树