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

Question

我一直在研究编译器。这个词法分析器似乎很简单:采用“句子”并将其分解为单词(或标记)。为了确保正确的语法，需要一个解析器。解析器通常获取 token 并构建一棵树，该树导致一个根节点(单词成句子，段落，页面等)。

从this question看来，解析器将构建AST。 AST仅包含执行代码所必需的内容，因此不需要括号之类的东西，因为AST中内置了运算符优先级。 AST可能是编译器所需的全部。

但是，如何将代码从一种语言转换为另一种语言呢？采用一种组合语言(语法)或现有语法并将其转换为另一种运算符优先规则可能不同的地方？ CST是否也“内置”了运营商优先级？

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

那么对于语言翻译，CST会更好吗？通常将运算符(operator)优先级内置到CST中吗？之间有什么吗？有没有将两个树与一个简单的代数方程进行比较的示例？举例说明三元运算符吗？

(“转码”是“编程语言翻译”的正确术语吗？Google搜索带来了转换媒体。)

我要弄清楚的是:什么时候更合适地使用一个？

Answer 1

您只需要对源语言的所有语义细节进行建模的AST。根据定义，如果它确实正确地对语义建模，并且您的语言包含三元运算符，那么它将也正确地对运算符的应用顺序进行建模(例如，优先级取模的结果(例如括号))。

因此，您的问题不在AST中。它使用优先级不同的类似(三元)运算符生成另一种语言。

这是代码生成中的一个古老问题:目标运算符与源运算符不太匹配，因此输出不能一对一。对于您的情况，您应该能够通过生成带有括号的PHP三元运算符来控制顺序，以实现原始语义，从而解决该问题，所以这不是一个大问题。

通常，生成实现所需结果的代码序列可能非常复杂，并且有很多方法可以实现。这就是为什么编译器书籍比较厚而不是比较薄的原因。您似乎已经隐式地决定“获取AST，浏览AST，输入代码”；这几乎是即时代码生成器。如果您不在乎生成的代码是否特别好，并且目标语言与源语言非常接近，则此方法就足够了。

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

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

底线:除非您的翻译真的很琐碎，否则仅拥有AST还是不够的。
您可以在以下SO答案中了解更多有关您需要做什么的信息:https://stackoverflow.com/a/3460977/120163

警告:大声的意见随之而来。

关于“代码转换器”:我更喜欢术语“编译”，“翻译”或“源到源”编译器。我从事程序分析和操作工具的开发已有近40年的历史了。直到我遇到这个SO问题:Experience migrating legacy Cobol/PL1 to Java和描述IMHO的响应(一种称为NACA的真正糟糕的代码转换方案)之前，我从未听说过“代码转换器”一词。从那以后，我听说这个词正越来越受到人们的欢迎。我不知道为什么在我们有足够的术语时为什么还要发明另一个术语。通常，这表明有人发明了圣职； “让我们发明一个 Shiny 的新名词，这样人们就不会真正了解我们在做什么”。我很乐意将这个术语留给如此糟糕的翻译。