我在一本编译器设计书中找到了这两个术语，我想知道它们各自代表什么，以及它们有何不同。解析树和抽象语法树有什么区别？

我在网上搜索，发现解析树也被称为具体语法树（CST）。

2011-05-11 Shashi Bhushan

查看此SO问题的答案：http://stackoverflow.com/questions/1888854/what-is-the-difference-between-an-abstract-syntax-tree-and-a-concrete-syntax-树 – 2011-05-14 09:57:15

这是基于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)

解析树

的语法分析树是输入的具体表示。分析树保留了输入的所有信息。空框表示空白，即行尾。

Parse Tree

AST

AST是输入的抽象表示。请注意，parens不存在于AST中，因为这些关联可以从树结构中推导出来。

AST

编辑

对于通过解释更见Compilers and Compiler Generators通过P.D.特里pg。 23.另请参阅作者home page了解更多项目，例如源代码。

来源

2012-04-16 15:47:17

给定的URL“编译器和编译器生成器”需要认证。这个资源是否有不同的URL或者是否有某种匿名访问？ – rexford 2016-01-05 14:11:06

@rexford当我第一次发布它时，链接是免费的。显然这已经改变了。你有具体的问题吗？ – 2016-01-05 14:30:45

本书可在本书作者的主页上找到，截至2017年11月。http://www.cs.ru.ac.za/compilers/index.html – uxp 2017-11-08 23:25:29

AST从概念上描述了源代码，它不需要包含解析某些源代码（花括号，关键字，括号等）所需的所有语法元素。

解析树更接近地表示源代码。

在AST为IF语句的节点可以只包含三个孩子：

条件
如果案例
否则案例

对于类似C语言的解析树需要包含'if'关键字，圆括号和花括号的节点。

来源

2011-05-11 17:54:57 jjwchoy

这里是解析树（具体语法树，国家支助组）和抽象语法树（AST的）的解释，在编译器构造的情况下。它们是相似的数据结构，但它们构造不同，并用于不同的任务。

解析树

解析树通常为词法分析之后的下一步骤（其转动源代码转换成一系列令牌可以被看作是有意义的单位，而不是仅仅一个字符的序列）产生的。

它们是树型数据结构，它显示了输入的终端字符串（源代码标记）是如何由相关语言的语法生成的。解析树的根是语法的最一般符号 - 起始符号（例如，语句），并且内部节点表示开始符号扩展到的非终止符号（可以包括开始符号本身），例如as expression，statement，term，函数调用。叶子是语法的终端，在语言/输入字符串中显示为标识符，关键字和常量的实际符号，例如为，，如果等

在解析编译器还执行各种检查，以确保语法的正确性 - 和和语法错误报告可以嵌入到解析器代码。

对于简单的任务（如将中缀表达式转换为后缀表达式），它们可以用于通过语法指导的定义或转换方案进行语法指导的转换。

这里的一个分析树的用于表达9 - 5 + 2的图形表示（注意在树的端子和从表达式串的实际的符号的位置）：

enter image description here

抽象语法树

AST表示一些代码的句法结构。编程树的结构，如表达式，流控制语句等 - 分组成运算符（内部节点）和操作数（叶）。例如，表达式i + 9的语法树将以运算符+为根，变量i作为操作员的左孩子，编号9作为右孩子。

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

请注意，操作符本身是给定语言的程序设计结构，并不一定是实际的计算操作符（如+就是）：for循环也将以这种方式处理。例如，可以有一个语法树，如for [ expr, expr, expr, stmnt ]（内联），其中for是运算符，方括号内的元素是它的子元素（表示C的for语法） - 也由操作员等组成。

AST通常由语法分析（解析）阶段的编译器生成，稍后用于语义分析，中间表示，代码生成等。

下面是一个AST的图形表示：

来源

2014-10-12 22:23:53 corazza

我希望你的答案是可以接受的。它更详细，更好地解释。 – Salil 2017-09-05 04:00:26

@Salil谢谢！:)我在博客上也写过关于这些内容的内容：http://flowing.systems/tag/mcd – corazza 2017-09-05 12:56:51

我发现这个在网络上，也许有帮助：

解析树是规则（和令牌）的纪录用于匹配一些输入文本，而语法树记录输入的结构，并且对产生它的文法不敏感。请注意，对于任何单一语言都是无限数量的语法，因此对于给定的输入句子，每个语法都会导致不同的语法树形式，因为所有不同的中间规则都是如此。一个抽象语法树是一个非常优越的中间形式，正是因为这种不敏感性，并且因为它强调了语言而不是语法的结构。

来源

2015-01-30 13:51:53 Khatri

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

回答

解析树

抽象语法树

相关问题