110

它们是由编译过程的不同阶段生成的吗？还是它们只是同一事物的不同名称？

4

8 回答 8

110

这是基于 Terrence Parr 的Expression Evaluator语法。

此示例的语法：

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

输入

x=1
y=2
3*(x+y)

解析树

解析树是输入的具体表示。解析树保留了输入的所有信息。空框代表空白，即行尾。

解析树

AST

AST 是输入的抽象表示。请注意，AST 中不存在括号，因为关联是从树结构派生的。

AST

有关更详细的解释，请参阅编译器和编译器生成器pg。23
或pg 上的抽象语法树。21 在编程语言的语法和语义

于 2012-03-25T22:14:09.030 回答
34

这是在编译器构造的上下文中对解析树（具体语法树，CST）和抽象语法树（AST）的解释。它们是相似的数据结构，但它们的构造不同并用于不同的任务。

解析树

解析树通常是在词法分析之后生成的（它将源代码转换为一系列可以被视为有意义的单元的标记，而不仅仅是一个字符序列）。

它们是树状数据结构，显示了输入的终端字符串（源代码标记）是如何由相关语言的语法生成的。解析树的根是语法中最通用的符号——起始符号（例如statement），内部节点表示起始符号扩展为的非终结符号（可以包括起始符号本身），例如表达式,语句,术语,函数调用。叶子是语法的终端，在语言/输入字符串中作为标识符、关键字和常量出现的实际符号，例如for、9、if等。

在解析的同时，编译器还执行各种检查以确保语法的正确性——并且语法错误报告可以嵌入到解析器代码中。

它们可用于通过语法导向定义或翻译方案进行语法导向翻译，用于简单的任务，例如将中缀表达式转换为后缀表达式。

这是表达式的解析树的图形表示9 - 5 + 2（注意树中终端的位置以及表达式字符串中的实际符号）：

在此处输入图像描述

抽象语法树

AST 代表一些代码的句法结构。诸如表达式、流控制语句等编程结构的树 - 分组为运算符（内部节点）和操作数（叶子）。例如，表达式的语法树i + 9将运算符+作为根，变量i作为运算符的左孩子，数字9作为右孩子。

这里的区别在于非终结符和终结符不发挥作用，因为 AST 不处理语法和字符串生成，而是编程构造，因此它们表示这些构造之间的关系，而不是它们由语法生成的方式.

请注意，运算符本身是给定语言的编程结构，不必是实际的计算运算符（如+is）：for循环也将以这种方式处理。例如，您可以有一个语法树，例如for [ expr, expr, expr, stmnt ]（表示为内联），其中for是一个运算符，方括号内的元素是它的子元素（表示 C 的for语法）——也由运算符等组成。

AST 通常也由编译器在语法分析（解析）阶段生成，稍后用于语义分析、中间表示、代码生成等。

这是 AST 的图形表示：

在此处输入图像描述

于 2014-10-12T22:23:53.987 回答
17

据我了解，AST 更侧重于源代码组件之间的抽象关系，而解析树侧重于语言使用的语法的实际实现，包括挑剔的细节。它们绝对不一样，因为“解析树”的另一个术语是“具体语法树”。

于 2011-02-17T08:30:45.393 回答
11

Martin Fowler的DSL 书很好地解释了这一点。AST 仅包含将用于进一步处理的所有“有用”元素，而解析树包含您解析的原始文档中的所有工件（空格、括号等）

于 2011-02-17T08:36:15.547 回答
11

AST 从概念上描述源代码，它不需要包含解析某些源代码所需的所有语法元素（大括号、关键字、括号等）。

解析树更紧密地表示源代码。

在 AST 中，IF 语句的节点可能只包含三个子节点：

  • 健康）状况
  • 如果案例
  • 其他情况

对于类 C 语言，解析树需要包含“if”关键字、括号、花括号的节点。

于 2011-05-11T17:54:57.673 回答
5

取帕斯卡赋值 Age:= 42;

语法树看起来就像源代码。下面我在节点周围加上括号。[年龄][:=][42][;]

抽象树看起来像这样 [=][Age][42]

分配成为具有 2 个元素的节点，即 Age 和 42。想法是您可以执行分配。

另请注意，pascal 语法消失了。因此，可能有不止一种语言生成相同的 AST。这对于跨语言脚本引擎很有用。

于 2015-08-04T14:26:59.917 回答
5

维基百科说

解析树具体反映了输入语言的语法，使其不同于计算机编程中使用的抽象语法树。

Quora上的一个回答说

解析树是用于匹配某些输入文本的规则（和标记）的记录，而语法树记录输入的结构并且对产生它的语法不敏感。

结合以上两个定义，

AnAbstract Syntax Tree从逻辑上描述解析树。它不需要包含解析某些源代码所需的所有语法结构（空格、大括号、关键字、括号等）。这就是为什么Parse Tree在调用Concrete Syntax TreeAST 时也调用Syntax Tree. 因此，语法分析器的输出实际上是语法树。

于 2018-05-19T11:16:40.690 回答
3

在解析树中，内部节点是非终端的，叶子是终端的。在语法树中，内部节点是运算符，叶子是操作数。

于 2014-11-25T12:56:48.257 回答