解析树和AST有什么区别?

Are they generated by different phases of a compiling process? Or are they just different names for the same thing?

它们是由编译过程的不同阶段生成的吗?或者它们只是同一个东西的不同名称?

5 个解决方案

#1

This is based on the Expression Evaluator grammar by Terrence Parr.

这是基于Terrence Parr的表达式求值语法。

The grammar for this example:

这个例子的语法:

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(); } ;

Input

输入

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

Parse Tree

解析树

The parse tree is a concrete representation of the input. The parse tree retains all of the information of the input. The empty boxes represent whitespace, i.e. end of line.

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

AST

AST

The AST is an abstract representation of the input. Notice that parens are not present in the AST because the associations are derivable from the tree structure.

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

For a more through explanation see Compilers and Compiler Generators pg. 23
or Abstract Syntax Trees on pg. 21 in Syntax and Semantics of Programming Languages

对于更多的解释，请参阅编译器和编译器生成器。23或抽象语法树在pg. 21的语法和语义的编程语言。

#2

From what I understand, the AST focuses more on the abstract relationships between the components of source code, while the parse tree focuses on the actual implementation of the grammar utilized by the language, including the nitpicky details. They are definitely not the same, since another term for "parse tree" is "concrete syntax tree".

从我的理解来看，AST更关注源代码组件之间的抽象关系，而解析树则侧重于语言使用的语法的实际实现，包括细节。它们肯定不是相同的，因为“解析树”的另一个术语是“具体语法树”。

I found this page which attempts to resolve this exact question.

我发现这一页试图解决这个问题。

#3

The DSL book from Martin Fowler explains this nicely. The AST only contains all 'useful' elements that will be used for further processing, while the parse tree contains all the artifacts (spaces, brackets, ...) from the original document you parse

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

#4

Take the pascal assignment Age:= 42;

以pascal作业年龄为例:= 42;

The syntax tree would look just like the source code. Below I am putting brackets around the nodes. [Age][:=][42][;]

语法树看起来就像源代码一样。下面我把括号括起来。[时代][:=][42][;]

An abstract tree would look like this [=][Age][42]

一棵抽象的树看起来像这样[=][42]

The assignment becomes a node with 2 elements, Age and 42. The idea is that you can execute the assignment.

赋值成为一个节点，包含两个元素，年龄和42。想法是你可以执行任务。

Also note that the pascal syntax disappears. Thus it is possible to have more than one language generate the same AST. This is useful for cross language script engines.

还要注意，pascal语法消失了。因此，有多种语言生成相同的AST是可能的，这对于跨语言脚本引擎非常有用。

#5

In parse tree interior nodes are non terminal, leaves are terminal. In syntax tree interior nodes are operator, leaves are operands.

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