解析树和抽象语法树 (AST) 有什么区别? [英] What's the difference between parse trees and abstract syntax trees (ASTs)?

问题描述

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

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

推荐答案

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

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

本例的语法:

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 : '
'? '
' ;
WS      : ( ' ' | '	' )+ { skip(); } ;

输入

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

解析树

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

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 是输入的抽象表示.请注意，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.

有关详细说明，请参阅 编译器和编译器生成器 pg.23
或 抽象语法树 on pg.21 in 编程语言的语法和语义

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

这篇关于解析树和抽象语法树 (AST) 有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！