语义规则/抽象语法树规则

Question

首先，语义规则和抽象语法树规则是否相同？

如果我有一种语言规范，并且有CFG，则该如何构建抽象语法树规则。任何来源都可以接受。谢谢。

- Kraken

Answer 1

“抽象语法树规则”（这是奇怪的术语）可以解释为在解析过程中塑造抽象语法结构的规则。通常，它们被写成非终端T的语法规则中，它们是由解析T的子短语生成的抽象语法树的构造函数。如果……

 T = '(' A ';' B ')' ;

这是一条语法规则，T的抽象语法树构造器可能会用到它。

   T(A,B)

意味着构建一个T节点，其子节点是为A和B子解析构建的AST。

语义规则是程序必须满足的合法性约束，不仅仅是语法。因此，可以从“规则”中构建抽象语法树；这样做只能证明程序在语法上是正确的。但是抽象语法可以表达一些在语义上毫无意义的东西，例如：

  "declare s as function; ...  s=7; ..."

通常来说，检查这个问题的唯一方式是遍历抽象语法树，在本地收集事实（例如，“s是一个函数”是从声明语句中提取的事实；“s被赋予整数”是从赋值语句中收集的），然后传播这些事实直到它们相遇并且被证明是（不）兼容。

- Ira Baxter

Answer 2

回答你的第二个问题，这里有一篇文章将语法和语法树的概念联系在一起，并探讨了一些解析算法。

http://www.cs.purdue.edu/homes/xyzhang/spring11/notes/ast.pdf

从这篇文章中：

The resulting grammar is called the concrete grammar.  
The corresponding derivation tree is called the parse tree.

具体语法树或解析树是一棵树，根据某些形式化语法表示字符串的句法结构。

这里有一个从语法中推导解析树的示例链接：

http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsetrees.html

这也突显了处理模糊语法的问题。

- prelic