抽象语法树和具体语法树有什么区别? [英] What is the difference between an Abstract Syntax Tree and a Concrete Syntax Tree?

问题描述

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

我是否遗漏了语义分析器的某些内容，或者 AST 和 CST 之间的区别是否有些人为?

解决方案

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

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

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

I've been reading a bit about how interpreters/compilers work, and one area where I'm getting confused is the difference between an AST and a CST. My understanding is that the parser makes a CST, hands it to the semantic analyzer which turns it into an AST. However, my understanding is that the semantic analyzer simply ensures that rules are followed. I don't really understand why it would actually make any changes to make it abstract rather than concrete.

Is there something that I'm missing about the semantic analyzer, or is the difference between an AST and CST somewhat artificial?

解决方案

A concrete syntax tree represents the source text exactly in parsed form. In general, it conforms to the context-free grammar defining the source language.

However, the concrete grammar and tree have a lot of things that are necessary to make source text unambiguously parseable, but do not contribute to actual meaning. For example, to implement operator precedence, your CFG usually has several levels of expression components (term, factor, etc.), with the operators connecting them at the different levels (you add terms to get expressions, terms are composed of factors optionally multipled, etc.). To actually interpret or compile the language, however, you don't need this; you just need Expression nodes that have operators and operands. The abstract syntax tree is the result of simplifying the concrete syntax tree down to the things actually needed to represent the meaning of the program. This tree has a much simpler definition and is thus easier to process in the later stages of execution.

You usually don't need to actually build a concrete syntax tree. The action routines in your YACC (or Antlr, or Menhir, or whatever...) grammar can directly build the abstract syntax tree, so the concrete syntax tree only exists as a conceptual entity representing the parse structure of your source text.

这篇关于抽象语法树和具体语法树有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！