100

我一直在阅读一些关于解释器/编译器如何工作的内容，而我感到困惑的一个领域是 AST 和 CST 之间的区别。我的理解是解析器生成一个 CST，将其交给语义分析器，语义分析器将其转换为 AST。但是，我的理解是语义分析器只是确保遵循规则。我真的不明白为什么它实际上会进行任何更改以使其抽象而不是具体。

关于语义分析器，我是否缺少某些东西，或者 AST 和 CST 之间的区别是否有些人为？

4

9 回答 9

76

具体的语法树以解析的形式准确地表示源文本。一般来说，它符合定义源语言的上下文无关文法。

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

您通常不需要实际构建具体的语法树。您的 YACC（或 Antlr、或 Menhir 或其他...）语法中的动作例程可以直接构建抽象语法树，因此具体语法树仅作为表示源文本解析结构的概念实体存在。

于 2009-12-11T15:52:31.347 回答
40

具体的语法树匹配语法规则所说的语法。抽象语法树的目的是对“语法树”中的基本内容进行“简单”表示。

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

大多数支持构建语法树的解析器生成器都坚持要求您在假设您的树节点将比 CST“更简单”的情况下亲自指定它们是如何构建的（并且在这一点上，它们通常是正确的，因为程序员很漂亮懒惰的）。可以说，这意味着您必须编写更少的树访问函数，这也很有价值，因为它可以最大限度地减少工程能量。当您有 3500 条规则时（例如，对于 COBOL），这很重要。而这种“简单”导致了“小”的良好特性。

但是拥有这样的 AST 会产生一个不存在的问题：它与语法不匹配，现在您必须在心理上跟踪它们。当 3500 个规则语法有 1500 个 AST 节点时，这很重要。如果语法不断发展（他们总是这样！），现在你有两套巨大的东西要保持同步。

另一种解决方案是让解析器简单地为您构建 CST 节点并使用它们。这在构建语法时是一个巨大的优势：无需发明 1500 个特殊的 AST 节点来建模 3500 个语法规则。想想这棵树与语法同构。从语法工程师的角度来看，这完全是无脑的，这让他可以专注于正确地编写语法并尽情发挥。可以说您必须编写更多节点访问者规则，但这可以管理。稍后再谈。

我们使用DMS Software Reengineering Toolkit所做的是根据 (GLR) 解析过程的结果自动构建 CST。然后 DMS 出于空间效率的原因自动构造一个“压缩的”CST，通过消除非值携带终端（关键字、标点符号）、语义上无用的一元产生式，并为语法规则对形成可直接索引的列表，如下所示：

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

以及这种形式的各种变体。您根据语法规则和虚拟 CST 进行思考；该工具对压缩表示进行操作。让您的大脑轻松，运行时更快/更小。

值得注意的是，以这种方式构建的压缩 CST 看起来很像您可能手动设计的 AST（参见示例末尾的链接）。特别是，压缩的 CST 不携带任何只是具体语法的节点。有一点点尴尬：例如，虽然在表达式子语法中经典地发现的 '(' 和 ')' 的具体节点不在树中，但“括号节点”确实出现在压缩 CST 中并且必须处理。真正的 AST 不会有这个。对于不必指定 AST 构造的便利性，这似乎是一个很小的代价。树的文档始终可用且正确：语法就是文档。

我们如何避免“额外访客”？我们不完全是，但 DMS 提供了一个 AST 库，它遍历 AST 并透明地处理 CST 和 AST 之间的差异。DMS 还提供了一个“属性语法”评估器 (AGE)，它是一种将计算出的值在树上和下层传递的方法；AGE 处理所有的树表示问题，因此工具工程师只担心直接在语法规则本身上有效地编写计算。最后，DMS 还提供了“表面语法”模式，它允许语法中的代码片段用于查找特定类型的子树，而无需了解所涉及的大多数节点类型。

其他答案之一观察到，如果您想构建可以重新生成源的工具，您的 AST 必须与 CST 匹配。这不太对，但如果您有 CST 节点，则重新生成源要容易得多。 DMS 会自动生成大部分漂亮打印机，因为它可以访问两者：-}

底线：AST 适合小型的，无论是物理的还是概念的。来自 CST 的自动 AST 构造提供了这两者，并让您避免跟踪两个不同集合的问题。

编辑 2015 年 3 月： 链接到 CST 与以这种方式构建的“AST”的示例

于 2009-12-16T18:33:07.867 回答
30

这是基于 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 中不存在括号，因为关联是从树结构派生的。

AST

编辑

有关更详细的解释，请参阅编译器和编译器生成器pg。23

于 2012-04-16T15:08:05.167 回答
21

这篇博文可能会有所帮助。

在我看来，AST“丢弃”了许多对语义没有贡献的中间语法/结构信息。例如，你不在乎 3 是一个原子是一个项是一个因子是一个......你只关心它是3在你实现求幂表达式或其他什么的时候。

于 2009-12-11T15:41:25.350 回答
11

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

  • expression_list 可以是：表达式
  • 表达式列表可以是：表达式、表达式列表

从字面上看，这两个规则为出现在程序中的任何表达式列表提供了一个梳子形状。

抽象语法树的形式便于进一步操作。它以一种对理解程序含义的人有意义的方式表示事物，而不仅仅是它们的编写方式。上面的表达式列表可能是函数的参数列表，可以方便地表示为表达式的向量，因为静态分析最好让表达式的总数显式可用并且能够通过其访问每个表达式指数。

于 2009-12-11T15:46:59.410 回答
6

简单地说，AST 只包含代码的语义，Parse tree/CST 还包含有关如何准确编写代码的信息。

于 2016-04-25T05:43:36.277 回答
2

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

 

注意：有趣的是，当您实现重构引擎时，您的 AST 将再次包含所有具体信息，但您将继续将其称为 AST，因为这已成为该领域的标准术语（因此可以说它已经很久了ago 失去了原来的意义）。

于 2009-12-12T16:55:25.313 回答
2

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

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

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

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

不能一开始就在语法中引入这些规则吗？当然。您可以通过将其分解为用于模仿上述 AST 节点的更具体的规则来重写上述紧凑和抽象的规则：

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

现在，当您考虑自顶向下解析时，第二项会在mul_rule和div_rule之间引入 FIRST/FIRST 冲突，这是 LL(1) 解析器无法处理的。第一个规则形式是第二个规则形式的左因子版本，它有效地消除了结构。你必须为在这里使用 LL(1) 付出一些代价。

因此 AST 是一种临时补充，用于修复语法和解析器的缺陷。CST -> AST 转换是一种重构举措。当额外的逗号或冒号存储在语法树中时，没有人会担心。相反，一些作者将它们改造成 AST，因为他们喜欢使用 AST 进行重构，而不是同时维护各种树或编写额外的推理引擎。程序员懒惰是有原因的。实际上，它们甚至将通过词法分析收集的行和列信息存储在 AST 中以用于错误报告。确实很抽象。

于 2012-02-22T16:02:34.627 回答
2

CST（具体语法树）是语法（程序应该如何编写的规则）的树表示。根据编译器架构，解析器可以使用它来生成 AST。

AST（抽象语法树）是 Parsed 源代码的树表示，由编译器的 Parser 部分生成。它存储有关标记+语法的信息。

根据编译器的体系结构，CST 可用于生成 AST。可以公平地说，CST 演变成 AST。或者，AST 是更丰富的 CST。

更多解释可以在这个链接上找到： http: //eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6

于 2017-04-05T21:15:48.387 回答