何时使用抽象语法树或具体语法树？

Question

何时使用抽象语法树或具体语法树？

compiler-constructionabstract-syntax-treeconcrete-syntax-tree

5

我一直在研究编译器。词法分析器似乎非常直接：将一个“句子”分解成单词（或令牌）。为确保正确的语法，需要使用解析器。解析器通常会取出令牌并构建一棵树，结果是一个根节点（将单词组成句子、段落、页面等）。

从这个问题来看，解析器会构建抽象语法树（AST）。AST仅包含执行代码所需的内容，因此括号之类的东西是不必要的，因为运算符优先级已经内置到AST中。AST可能是编译器所需的全部内容。

但是，如何将代码从一种语言转换为另一种语言呢？以一个虚构的语言（语法）或现有的语法为例，并将其转换为另一种语言，在该语言中，运算符优先规则可能与原语言不同。CST中也内置了运算符优先级吗？

例如，假设我编写了一种语言，并希望将其翻译成PHP代码。大多数语言中的三元运算符具有从右到左的结合性。PHP错误地使用了从左到右的结合性（在此处了解更多）。我希望“我的语言”使用从右到左，但是生成的PHP代码必须应用括号才能在PHP中得到正确的结果（在维基百科上，结果应为“train”，而不是“horse”）。

因此，对于语言翻译，CST是否更好？运算符优先级通常内置于CST中吗？是否有介于两者之间的东西？是否有任何比较简单代数方程的示例来比较两种树？是否有说明三元运算符的示例？

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

我的问题是：什么时候使用一种方法比另一种方法更合适？

- Luke

1

我不明白为什么在语言转换中需要具体语法树。具体语法往往是最容易出现差异的地方。你只需要原始程序的语义和AST即可在另一种语言中创建具有类似语义的程序，而AST可以提供更少的混乱。 - user395760

1

啊，我明白你的意思了。那么何时使用具体树比抽象树更合适，并且具体树是否关心优先级？ - Luke

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

一个模拟源语言所有语义细节的AST就是你所需要的。根据定义，如果它确实正确地模拟了语义，并且你的语言包括三元运算符，那么它也将正确地模拟运算符应用的特定顺序（例如，优先级模数覆盖，如括号）。

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

这是代码生成中的一个古老问题：目标的运算符与源的运算符不完全相同，因此输出不能一对一对应。在你的情况下，你应该能够通过在PHP三元运算符周围加上括号来控制顺序从而实现原始语义，因此这不是一个大问题。

通常，生成实现所需结果的代码序列可能会非常复杂，有很多方法可以做到这一点。这就是为什么编译器书籍比较厚而不是薄的原因。你似乎已经默认选择了“获取AST，遍历AST，生成代码”；这几乎是一个即时代码生成器。如果你不关心生成的代码是否特别好，而且目标语言与源语言相当接近，那么这种方法是足够有效的。

如果代码生成问题更加复杂，通常会使用AST生成计算的数据流模型，包括产生结果的运算符和消耗前面运算符结果的运算符，并在“运算符”中获取变量值和常量。然后遍历数据流表示以生成代码；这样做的好处是可以选择数据流表示中的运算符，在目标语言中找到匹配的代码序列，生成代码，然后再考虑如何收集操作数。更好的方案是将数据流子图（表示等效的复合目标语言结构）与生成的数据流图匹配；这可以产生明显更好的代码。通常，可以在原始代码生成之后应用特定于目标语言的优化来产生更好的代码。在两种情况下，都必须考虑管理运算符结果的问题；它们是否可以直接传递给下一个目标语言运算符，或者必须进入某种临时存储（对于机器代码，这可以是另一个寄存器或内存位置）。做所有这些并不容易；这也是为什么编译器书籍不薄的原因。

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

底线：除非您的翻译真正简单，否则拥有AST并不足够。您可以在此SO答案中阅读更多信息https://dev59.com/anA75IYBdhLWcg3wJFYL#3460977 警告：以下是强烈的观点。

关于“Transcoder”：我更喜欢术语“编译”，“翻译”或“源到源”的编译器。我已经构建了近40年的程序分析和操作工具。在遇到这个 SO 问题之前，我从未听说过“transcoder”这个术语：体验将传统的 Cobol/PL1 迁移到 Java和一个描述 IMHO 真正糟糕的代码转换方案 NACA 的响应。我后来听说这个术语正在得到推广；我不明白为什么我们必须发明另一个术语，当我们已经有完全足够的术语时。通常这是某人发明高级祭司的迹象；“让我们发明一个闪亮的新术语，这样人们就不会真正理解我们在做什么”。我很高兴把这个术语留给那些真正糟糕的翻译。