什么时候使用抽象或具体的语法树？

Question

我一直在研究编译器。词法分析器似乎非常简单:取一个“句子”，并将其分解为单词(或标记)。为了确保语法正确，需要一个解析器。解析器通常接受令牌并构建一棵树，该树产生一个根节点(将单词转换为句子、段落、页面等)。

从this question上看，解析器似乎会构建一个AST。AST只包含执行代码所需的内容，所以括号之类的东西是不必要的，因为运算符的优先级是内置在AST中的。一个AST可能就是编译器所需要的全部。

但是如何将代码从一种语言转换为另一种语言呢？采用一种虚构的语言(语法)或现有的语法，并将其转换为另一种语言(语法)，其中操作符优先规则可能不同，也可能不同？运算符优先级是否也“内置”到CST中？

例如，假设我编写了一种语言，并希望将其转换为PHP代码。大多数语言中的三元运算符具有从右到左的结合性。PHP错误地使用了从左到右的关联性(see more about this here)。我希望“我的语言”使用从右到左，但是生成的PHP代码必须应用括号才能在PHP中获得正确的结果(对于link to Wikipedia，结果需要是“训练”而不是“马”)。

那么对于语言翻译来说，CST会更好吗？运算符优先级通常内置于CST中吗？中间有什么吗？有没有用一个简单的代数方程比较这两棵树的例子？有没有三元运算符的例子？

(“代码转换”是“编程语言翻译”的正确术语吗？谷歌搜索会显示媒体转换。)

我试图弄清楚的是:什么时候使用一种比另一种更合适？

Answer 1

您所需要的就是对源语言的所有语义细节进行建模的AST。根据定义，如果它确实正确地对语义进行了建模，并且您的langauge包含一个三元运算符，那么它也会正确地对运算符应用的特定顺序进行建模(例如，前置模覆盖的结果，如括号)。

所以你的问题不在AST中。它正在使用类似的(三元)运算符生成另一种语言，这些运算符的优先级不同。

这是代码生成中的一个古老问题:目标的运算符与源的运算符不完全匹配，因此输出不能一对一。在您的例子中，您应该能够通过生成PHP三元运算符并将它们括起来来控制顺序来实现原始语义，因此这不是一个大问题。

一般来说，生成代码序列以达到期望的结果可能是相当复杂的，而且有很多方法可以做到这一点。这就是为什么编译器的书是厚的而不是薄的。您似乎已经隐含地选择了"get AST，walk AST，spit code"；这几乎是一个即时的代码生成器。如果您不关心生成的代码是否特别好，并且目标语言非常接近源语言，那么这种方法就可以很好地工作。

如果代码生成问题更加复杂，通常会发生的情况是，AST用于生成相当于计算的数据流模型，由生成结果的运算符组成，并使用先前运算符的结果，从而根植于获取变量值和常量的“运算符”。然后遍历数据流表示以生成代码；这样做的好处是，您可以在数据流表示中选择一个运算符，在目标语言中找到匹配的代码序列，生成该序列，然后再考虑如何收集操作数。更好的方案将数据流子图(表示等效的复合目标语言构造)与生成的数据流图相匹配；这可以生成明显更好的代码。通常，可以在原始代码生成后应用特定于目标语言的优化，以生成更好的代码。在这两种情况下，您都必须考虑运算符结果的管理；它们是直接提供给下一个目标语言运算符，还是必须放入某种临时存储中(对于机器码，这可以是另一个寄存器或内存位置)。做这一切并不容易；这也是为什么编译器书籍并不薄的原因。

这种想法的一种变体是源到源程序转换。这将源代码中的构造“直接”映射到目标代码中的构造，尽管这通常是通过在AST上操作在幕后完成的，因为未解析的编程语言文本很难匹配。我们的DMS Software Reengineering Toolkit就是这种系统的一个例子。使用这样的工具，您可以用源语言编写模式(隐式匹配解析树)，并用目标语言编写相应的模式(隐式生成目标语言AST)。您可以编写复杂的源或目标构造，从而提供上述数据流图匹配的大部分效果。后生成优化包括更多将目标代码转换为目标代码的重写规则。

底线:拥有一个AST是不够的，除非你的翻译是真正琐碎的。你可以在这里阅读更多关于你需要什么的信息，所以回答：https://stackoverflow.com/a/3460977/120163

警告:大声疾呼紧随其后。

Re“代码转换器”：我更喜欢术语“编译”、“翻译”或“源到源”编译器。近40年来，我一直在构建程序分析和操作工具。我从来没有听说过“代码转换器”这个词，直到我遇到了这样一个问题：Experience migrating legacy Cobol/PL1 to Java和一个描述我一个非常糟糕的代码转换方案的回复。从那以后，我就听说这个术语越来越有吸引力；我不明白为什么我们必须在已经有足够的术语的情况下发明另一个术语。通常，这是有人发明了高级祭司的标志；“让我们创造一个闪亮的新术语，这样人们就不会真正理解我们在做什么”。我很高兴把这个词留给这样糟糕的翻译。