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

问题描述

我在编译器设计书中找到了这两个术语，我想知道它们分别代表什么以及它们之间的区别。

我搜索了互联网，并发现解析树也称为具体语法树（CST）。

解决方案

这是基于特里（Terry） 23.另请参见作者首页了解更多内容，例如源代码

I found the two terms in a compiler design book, and I'd like to know what each stands for, and how they are different.

I searched on the internet and found that parse trees are also called concrete syntax trees (CSTs).

解决方案

This is based on the Expression Evaluator grammar by 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

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.

EDIT

For a more through explanation see Compilers and Compiler Generators by P.D. Terry pg. 23. Also see the authors home page for more items such as source code.

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