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

Question

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

Jas*_*ker 74 parsing terminology abstract-syntax-tree semantic-analysis concrete-syntax-tree

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

有没有关于语义分析器的东西,或者AST和CST之间的差异有点人为？

Answer 1

Mic*_*and 58

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

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

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

补充：Python解释器先构建一个CST，然后再转换成AST。 (3认同)
@EricAuld 这是一个重大变化；AST 通常也更简单（例如，在 CST -> AST 翻译中删除括号等分组结构，因为分组是隐含在 AST 结构中的；它们只是如何从源文本构建正确的树的说明）。 (2认同)

Answer 2

Ira*_*ter 30

一个具体的语法树匹配什么样的语法规则,说是语法.抽象语法树的目的是"简单"表示"语法树"中必不可少的内容.

AST恕我直言的实际价值在于它小于 CST,因此处理时间更短.(你可能会说,谁在乎？但是我使用的工具可以同时存在数千万个节点!).

大多数支持构建语法树的解析器生成器坚持要求你个人指定它们是如何构建的,假设你的树节点比CST"更简单"(并且,它们通常是正确的,因为程序员很漂亮懒).可以说,这意味着你必须编写更少的树访问者函数,这也是有价值的,因为它最大限度地减少了工程能量.当你有3500条规则(例如,对于COBOL)时,这很重要.而这种"简单"的过程导致了"小"的良好属性.

但是有这样的AST会产生一个不存在的问题:它与语法不匹配,现在你必须在心理上跟踪它们.当3500规则语法有1500个AST节点时,这很重要.如果语法发展(他们总是这样做!),现在你有两套巨大的东西要保持同步.

另一个解决方案是让解析器只为您构建CST节点并使用它们.构建语法时这是一个巨大的优势:没有必要发明1500个特殊的AST节点来模拟3500语法规则.试想一下树与语法同构.从语法工程师的角度来看,这是完全无脑的,这使他能够专注于正确理解语法,并将其扼杀在心中.可以说,您必须编写更多节点访问者规则,但这可以进行管理.稍后会详细介绍.

我们使用DMS Software Reengineering Toolkit做的是根据(GLR)解析过程的结果自动构建CST.DMS然后自动构建了空间效率的原因的"压缩" CST,通过消除非价值携带有像列表端子(关键字,punctation),语义无用一元制作,以及形成列出了语法规则对:

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

Run Code Online (Sandbox Code Playgroud)

以及这些形式的各种变化.您可以根据语法规则和虚拟CST来考虑; 该工具在压缩表示上运行.在您的大脑上轻松,在运行时更快/更小.

值得注意的是,以这种方式构建的压缩CST看起来很像您可能手工设计的AST(参见示例末尾的链接).特别是,压缩的CST不携带任何只是具体语法的节点.有一些尴尬的小问题:例如,当表达式子文件中经典地找到的'('和')'的具体节点不在树中时,"括号节点" 确实出现在压缩的CST中并且必须被处理.一个真正的AST不会有这个.这似乎是一个相当小的代价,为了方便而无需指定AST结构.并且树的文档始终可用且正确:语法是文档.

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

其中一个答案观察到,如果您想构建可以重新生成源的工具,那么您的AST必须与CST匹配.这不太对,但如果你有CST节点,重新生成源要容易得多. DMS自动生成大部分的prettyprinter,因为它可以同时访问: - }

底线:ASTs适用于小型,包括物理和概念.来自CST的自动AST构造提供了两者,并且可以避免跟踪两个不同集合的问题.

编辑2015年3月: 通过这种方式链接到CST与"AST"的示例

Answer 3

Jon*_*erg 20

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

在我看来,AST"抛弃"了许多不会对语义有贡献的中间语法/结构信息.例如,你不关心3是一个原子是一个术语是一个因素是......你只关心它是3在你实现取幂表达式时或者其他什么.

Answer 4

Guy*_*der 19

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

Run Code Online (Sandbox Code Playgroud)

输入