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

Question

抽象语法树和具体语法树有什么区别？我一直在阅读有关解释器/编译器如何工作的一些内容，而我感到困惑的一个领域是AST和CST之间的区别。我的理解是解析器生成一个CST，将它交给语义分析器，将其转换为AST。但是，我的理解是语义分析器只是确保遵循规则。我真的不明白为什么它会实际做出任何改变，使其变得抽象而不是具体。有没有关于语义分析器的东西，或者AST和CST之间的差异有点人为？

Answer 1

具体语法树以完全解析的形式表示源文本。通常，它符合定义源语言的无上下文语法。

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

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

Answer 2

这是基于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=1y=23*(x+y)

解析树

解析树是输入的具体表示。解析树保留输入的所有信息。空框表示空格，即行尾。

AST

AST是输入的抽象表示。请注意，AST中不存在parens，因为关联可以从树结构中派生。

编辑

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