5

我一直在研究编译器。词法分析器似乎非常直截了当：取一个“句子”并将其分解为单词（或标记）。为了确保语法正确，需要一个解析器。解析器通常获取标记并构建一个树，该树会产生一个根节点（单词到句子、段落、页面等......）。

从这个问题来看，解析器似乎会构建一个 AST。AST 仅包含执行代码所必需的内容，因此不需要括号之类的内容，因为运算符优先级内置于 AST 中。AST 可能是编译器所需要的。

但是如何将代码从一种语言转换为另一种语言呢？将一种组合语言（语法）或现有语法转换为另一种运算符优先级规则可能不同也可能不同的语法？运算符优先级是否也“内置”到 CST 中？

例如，假设我创建了一种语言并想将其翻译成 PHP 代码。大多数语言的三元运算符具有从右到左的结合性。PHP 错误地使用了从左到右的关联性（在此处查看更多信息）。我希望“我的语言”从右到左使用，但生成的 PHP 代码必须应用括号才能在 PHP 中获得正确的结果（通过Wikipedia 的链接，结果需要是“train”而不是“horse”）。

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

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

我想弄清楚的是：什么时候使用一个比另一个更合适？

4

1 回答 1

7

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

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

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

通常，生成实现预期结果的代码序列可能非常复杂，并且有很多方法可以做到这一点。这就是编译器书籍厚而不是薄的原因。您似乎已经隐含地选择了“获取 AST，步行 AST，吐出代码”；这几乎是一个即时代码生成器。如果您不关心生成的代码是否特别好，并且目标语言与源语言非常接近，那么这种方法就足够了。

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

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

底线：除非您的翻译真的很琐碎，否则拥有 AST 是不够的。您可以在这个 SO 答案中阅读更多关于您需要什么的信息：https ://stackoverflow.com/a/3460977/120163

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

关于“转码器”：我更喜欢术语“编译”、“翻译”或“源到源”编译器。近 40 年来，我一直在构建程序分析和操作工具。在遇到这个 SO 问题之前，我从未听说过“转码器”一词：体验将遗留 Cobol/PL1 迁移到 Java 以及描述恕我直言的一个真正糟糕的代码翻译方案，称为 NACA。我听说这个词越来越受欢迎。我不明白为什么当我们有完全合适的术语时我们必须发明另一个术语。通常这是有人发明大祭司的标志；“让我们发明一个闪亮的新术语，这样人们就不会真正理解我们在做什么”。一世'

于 2012-02-26T20:29:14.700 回答