抽象语法树和具体语法树有什么区别？

我一直在读关于解释器/编译器是如何工作的，而且我感到困惑的一个领域是AST和CST之间的区别。我的理解是，parsing器创build一个CST，把它交给语义分析器，把它变成一个AST。不过，我的理解是，语义分析器只是确保遵循规则。我真的不明白为什么它会做任何改变，使其抽象而不是具体。

有什么我错过了关于语义分析器的东西，还是AST和CST之间的区别有些人造？

一个具体的语法树完全以parsing的forms表示源文本。一般来说，它符合定义源语言的上下文无关语法。

然而，具体的语法和树有很多东西是必要的，使源文本明确可parsing，但没有实际意义的贡献。例如，为了实现运算符优先级，CFG通常具有几个expression组件（词，因子等）的级别，运算符将它们连接到不同的级别（您添加条件以获取expression式，条款由可select的多个因子组成等）。然而，为了实际解释或编译语言，你不需要这个; 你只需要有运算符和操作数的expression式节点。抽象语法树是将具体语法树简化为实际上需要表示程序含义的结果。这棵树有一个更简单的定义，因此在执行的后期更容易处理。

您通常不需要实际构build具体的语法树。在你的YACC（或者Antlr，或者Menhir，或者其他…）语法中的动作例程可以直接构build抽象语法树，所以具体语法树只能作为代表源文本parsing结构的概念实体存在。

一个具体的语法树匹配语法规则所说的语法。 抽象语法树的目的是对“语法树”中必不可less的“简单”表示。

AST恕我直言，真正的价值是它比CST 小，因此需要更less的时间来处理。（你可能会说，谁在乎呢？但是我使用了一个工具，在那里我们有数千万个节点同时存在！）。

大多数支持构build语法树的parsing器生成器都坚持认为，如果你的树节点比CST“更简单”，那么你就亲自指定了它们的构build方式（因为程序员很漂亮懒）。可以说，这意味着你必须编写更less的树访问函数，这也是有价值的，因为它最大限度地减less了工程能量。当你有3500条规则（例如COBOL）时，这就很重要。而这个“更简单”导致了“小”的好处。

但是有这样的AST会产生一个不存在的问题：它不符合语法，现在你必须精神跟踪这两个问题。而当3500规则文法有1500个AST节点时，这个问题就很重要了。如果语法发展（他们总是这样做！），现在你有两套巨大的东西要保持同步。

另一个解决scheme是让parsing器为你简单地构buildCST节点并使用它们。构build语法时，这是一个巨大的优势：不需要创build1500个特殊的AST节点来模拟3500条语法规则。试想一下，树是与文法同构的。从语法工程师的angular度来看，这是完全没有意义的，这让他专注于获得正确的语法，并将其转化为自己的内容。可以说，你必须编写更多的节点访问规则，但是可以进行pipe理。稍后再说。

我们用DMS软件再工程工具来做什么，是根据（GLR）parsing过程的结果自动build立一个CST。然后，DMS通过消除非价值承载terminal（关键词，标点符号），语义上无用的一元制作以及形成如下列表的语法规则对的列表来自动构build“压缩”CST：空间效率原因，

L = e ; L = L e ; L2 = e2 ; L2 = L2 ',' e2 ;

和这种forms的各种各样的变化。你用语法规则和虚拟CST来思考; 该工具在压缩表示上运行。轻松在你的大脑，在运行时更快/更小。

值得注意的是，以这种方式构build的压缩CST看起来很像您可能手动devise的一个AST（请参阅示例链接）。特别是，压缩的CST没有携带任何只是具体语法的节点。有一些小小的尴尬：例如，当在expression式子语法中经典地find的'（'和'）'的具体节点不在树中时，在压缩的CST 中出现“括号节点”并且必须被处理。一个真正的AST不会有这个。这似乎是一个非常小的代价来支付方便，而不必指定AST构造。并且树的文档始终可用且正确：语法是文档。

我们如何避免“额外访客”？我们并不完全，但是DMS提供了一个AST库，它可以在AST中进行操作，并透明地处理CST和AST之间的差异。 DMS还提供了一个“属性语法”评估器（AGE），它是一种在树上向上和向下传递节点值的方法。 AGE处理所有的树形表示问题，所以工具工程师只是担心直接对语法规则本身进行有效的计算。最后，DMS还提供了“表面语法”模式，它允许语法中的代码片段用于查找特定types的子树，而不需要知道大多数涉及的节点types。

其他的答案之一，观察到，如果你想build立工具，可以重新生成源，你的AST将不得不匹配CST。这是不正确的，但如果您有CST节点，则重新生成源代码要容易得多。 DMS自动生成绝大多数的打印机，因为它可以同时访问： – }

底线：ASTs适合小型的，包括物理和概念。 CST提供的自动化的AST结构可以提供这两种function，并且可以避免跟踪两套不同的问题。

编辑2015年3月：链接到CST与“AST”的例子build成这种方式

这个博客文章可能会有所帮助。

在我看来，AST“扔掉”了大量不会促成语义的中间语法/结构信息。例如，你不关心3是一个primefaces是一个术语是一个因素是一个….你只是在意它是3当你实现指数expression式或任何其他。

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

input

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

parsing树

分析树是input的具体表示。 parsing树保留了input的所有信息。空框表示空白，即行结束。

解析树

AST

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

AST

编辑

有关更多的解释，请参见编译器和编译器生成器页。 23

具体的语法树遵循语言的语法规则。在语法中，“expression式列表”通常用两个规则来定义

expression_list可以是：expression式
expression_list可以是：expression，expression_list

从字面上看，这两个规则给出了程序中出现的任何expression式列表的梳形。

抽象语法树的forms是便于进一步操作的。它以一种对理解程序意义的人有意义的方式来表示事物，而不仅仅是它们被写的方式。上面的expression式列表（可以是函数的参数列表）可以方便地表示为expression式的向量，因为对于静态分析来说，明确可用的expression式总数并且能够通过其指数。

具体的语法树包含了多余的括号，空白和注释等所有信息，抽象语法树从这些信息中抽象出来。

注意：足够有趣的是，当你实现一个重构引擎时，你的AST将再次包含所有的具体信息，但是你会一直把它称为AST，因为它已经成为了这个领域的标准术语（所以人们可以说它很长以前失去了原来的意思）。

这是一个没有区别的差异。

AST通常被解释为通过丢弃词法内容来逼近编程语言expression式的语义的一种方式。例如，在上下文无关语法中，您可以编写以下EBNF规则

 term: atom (('*' | '/') term )*

而在AST情况下，您只能使用mul_rule和div_rule来表示正确的算术运算。

这些规则不能在语法中首先引入？当然。你可以重写上面的紧凑和抽象的规则，把它分成更模拟所提到的AST节点的更具体的规则：

 term: mul_rule | div_rule mul_rule: atom ('*' term)* div_rule: atom ('/' term)*

现在，当你用自顶向下的parsing方式思考的时候，第二个术语介绍了mul_rule和div_rule之间的一个LL（1）parsing器无法处理的第一个/第一个冲突。第一个规则forms是第二个左边的因式分解法，它有效地消除了结构。您必须在这里使用LL（1）支付一定的奖金。

所以AST是一个临时补充，用于解决语法和parsing器的缺陷。 CST – > AST转换是一个重构的过程。在语法树中存储额外的逗号或冒号时，从来没有人打扰过。相反，有些作者将它们改装成AST，因为它们喜欢使用AST进行重构，而不是同时维护各种树或者编写额外的推理引擎。程序员因为很好的理由而懒惰。实际上，他们甚至可以在AST中存储通过词法分析收集的行和列信息，以便进行错误报告。确实非常抽象。

简单地说，AST只包含代码的语义，Parse树/ CST也包含了如何编写代码的信息。

AST是CST的简化版本。它们都可以由您的parsing器构build。如果有人需要明确的解释： http : //eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6