解析树和AST有什么区别？

Question

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

Answer 1

这是基于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中不存在parens,因为关联可以从树结构中派生.

有关更多解释,请参阅编译器和编译器生成器.23
或抽象语法树上的pg.21 编程语言的语法和语义

Answer 2

根据我的理解,AST更多地关注源代码组件之间的抽象关系,而解析树则侧重于语言使用的语法的实际实现,包括挑剔的细节.它们肯定不一样,因为"解析树"的另一个术语是"具体语法树".

我发现此页面试图解决这个确切的问题.

Answer 3

Martin Fowler 的DSL书很好地解释了这一点.AST仅包含将用于进一步处理的所有"有用"元素,而解析树包含您解析的原始文档中的所有工件(空格,括号,...)

Answer 4

Wikipedia says

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

Quora 上的一个回答说

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

结合以上两个定义，

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

Answer 5

进行帕斯卡赋值 Age:= 42;

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

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

该作业成为一个包含 2 个元素（Age 和 42）的节点。其想法是您可以执行该作业。

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