术语解析树和派生树之间的任何差异？

Question

当引用符合语法的文本的解析结果时,术语AST(抽象语法树),解析树和派生树由不同的人围绕.假设我们正在谈论解析计算机语言,他们的差异是否足够小,我们可以互换使用这些术语？如果没有,我们如何正确使用这些条款？

Answer 1

AFAIK,"派生树"和"解析树"是相同的.

抽象语法树

在计算机科学中,抽象语法树(AST)或语法树是用编程语言编写的源代码的抽象语法结构的树表示.树的每个节点表示在源代码中出现的构造.语法是"抽象的",因为它不代表真实语法中出现的每个细节.

解析树

具体的语法树或解析树或解析树是(有序的,有根的)树,它根据某种形式语法表示字符串的句法结构.在解析树中,内部节点由语法的非终端标记,而叶节点由语法的终端标记.

以源a = (1 + 2) * 3;为例.该解析树看起来是这样:

    ASSIGNMENT
   / / |      \
  / /  |       \ 
 a = expression ;
       /   \
 expression \ 
   / | \     \
  (  +  )     *
    / \        \
   1   2        3

而抽象语法树可能看起来像:

ASSIGNMENT
  /    \
 a   expression 
      /     \
 expression  *
     |        \ 
     +         3 
    / \
   1   2

Answer 2

解析/派生/具体语法树都是同一个概念的同义词。

这样的树通常只用于理论讨论，因为它们包含许多对于进行语言处理似乎没有必要的细节；在表达式树中，你真的需要一个节点来表示“(”，另一个节点来表示“)”？

“抽象语法”树的概念是一种将程序结构表示到足以在实践中处理的详细程度的概念；您通常不会找到“(...)”的节点。

一个有趣的问题：AST 是否可以直接从 CST 计算？答案应该是肯定的，但人们几乎从不这样做。他们倾向于在解析器运行时构建“抽象语法”节点，并使用 ad hoc（规则缩减程序附件）将来自子解析的节点与父节点的粘合节点组装在一起。恕我直言，他们这样做是因为我们都在 YACC 上长大，这就是传统上的做法。（我们过去也用燧石生火。）还有一个较小的借口；这样做可以让编译器构建者完全控制 AST 的结构，并且他可以生成一个在额外细节方面非常少的结构。这种临时树不能从 CST 计算，除非通过嵌入在解析器操作中的相同临时计算。

我使用了一种不同的方法：我的工具直接从 CST 计算 AST，实际上是通过删除不相关的细节，例如，省略代表无价值标记的节点（例如，那些毫无意义的 '(' ')' 标记以及关键字)，压缩出一元产生式的字符串，并将等价于列表的右倾或左倾树转换为真正的列表节点。这样做的好处是解析器可以直接从语法规则计算 AST。无需摆弄程序附件。没有弄错。不再担心我们的 COBOL 语法有 3500 条规则，否则我将需要为每个规则添加程序性粘液，而且我必须数百次更改语法以使其正确并每次都摆弄粘液。而且我们的工具就像直接在 CST 上操作一样工作，这使得考虑树操作变得容易，尤其是当您直接关注语法规则时。（这也使得使用表面语法的模式匹配更加容易：对于任何模式片段，都有一个可直接计算的 AST 对应）。

因此，就实用性而言，AST 和 CST 之间的区别是真实的。但我认为它们应该被视为只是同构表示。