解析树和抽象语法树之间有什么区别？

Question

我在编译器设计书中找到了这两个术语,我想知道每个术语代表什么,以及它们是如何不同的.

我在互联网上搜索,发现解析树也称为具体语法树(CST).

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,因为关联可以从树结构中派生.

编辑

有关详细说明,请参阅PD Terry的编译器和编译器生成器.23.另请参阅作者主页以获取更多项目,例如源代码.

Answer 2

以下是在编译器构造的上下文中对解析树(具体语法树,CST)和抽象语法树(AST)的解释.它们是类似的数据结构,但它们的构造方式不同,用于不同的任务.

解析树木

解析树通常在词法分析之后作为下一步生成(它将源代码转换为一系列令牌,可以被视为有意义的单位,而不仅仅是一系列字符).

它们是树状数据结构,显示了如何通过所讨论的语言的语法生成输入的终端字符串(源代码令牌).解析树的根是语法的最通用符号 - 起始符号(例如,语句),内部节点表示起始符号扩展到的非终结符号(可以包括起始符号本身),例如表达式,声明,术语,函数调用.叶子是语法中的端子,其显示为标识符,关键字,和常量中的语言/输入字符串,例如,实际的符号为,9,如果等

解析编译器时也会执行各种检查以确保语法的正确性 - 并且语法错误报告可以嵌入到解析器代码中.

它们可以通过语法导向定义或转换方案用于语法导向转换,用于简单的任务,例如将中缀表达式转换为后缀表达式.

下面是表达式的解析树的图形表示9 - 5 + 2(注意树中终端的位置和表达式字符串中的实际符号):

抽象语法树

AST表示某些代码的语法结构.编程结构的树,如表达式,流控制语句等 - 分为运算符(内部节点)和操作数(叶子).例如,表达式的语法树i + 9将操作符设置+为root,将变量设置i为运算符的左子项,将数字设置9为右子项.

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

请注意,运算符本身是给定语言的编程结构,并且不必是实际的计算运算符(如+is):for循环也将以这种方式处理.例如,您可以使用语法树,例如for [ expr, expr, expr, stmnt ](表示为内联),其中for是运算符,方括号内的元素是其子元素(表示C的for语法) - 也由运算符等组成.

AST通常由语法分析(解析)阶段的编译器生成,稍后用于语义分析,中间表示,代码生成等.

这是AST的图形表示:

Answer 3

AST在概念上描述了源代码,它不需要包含解析某些源代码(花括号,关键字,括号等)所需的所有语法元素.

Parse树更紧密地表示源代码.

在AST中,IF语句的节点只能包含三个子节点:

• 条件
• 如果是案例
• 其他案例

对于类C语言,Parse Tree需要包含'if'关键字,括号,花括号的节点.