Luk*_*uke 5 compiler-construction abstract-syntax-tree concrete-syntax-tree
我一直在研究编译器.词法分析器似乎非常直接:取一个"句子"并将其分解为单词(或标记).为了确保正确的语法,需要一个解析器.解析器通常采用令牌并构建一个树,从而产生根节点(将单词分为句子,段落,页面等等).
从这个问题来看,似乎解析器会构建一个AST.AST只包含执行代码所需的内容,所以括号之类的内容是不必要的,因为运算符优先级内置在AST中.AST可能都是编译器需要的.
但是如何将代码从一种语言转换为另一种语言？采用一种伪造的语言(语法)或现有的语法并将其转换为另一种语言,其中运算符优先级规则可能会有所不同？运营商优先还是"内置"到CST吗？
举个例子,假设我编写了一种语言,并希望将其翻译成PHP代码.大多数语言的三元运算符具有从右到左的关联性.PHP错误地使用从左到右的关联性(请在此处查看更多相关信息).我希望"我的语言"从右到左使用,但生成的PHP代码必须应用括号才能在PHP中获得正确的结果(通过指向Wikipedia的链接,结果需要是"train"而不是"horse").
因此,对于语言翻译,CST会更好吗？运营商优先级通常是否构建在CST中？介于两者之间吗？有没有例子比较两个树和一个简单的代数方程？任何说明三元运算符的例子？
("转码"是"编程语言翻译"的正确术语吗？谷歌搜索会带来转换媒体.)
我想弄清楚的是:什么时候使用一个比另一个更合适？
只需要一个模拟源语言所有语义细节的AST.根据定义,如果它确实对语义进行了正确建模,并且您的语言包含三元运算符,那么它将正确地模拟应用运算符的特定顺序(例如,先验模的覆盖结果,例如括号).
所以你的问题不在AST中.它使用优先级不同的类似(三元)运算符生成另一种语言.
这在代码生成中是一个古老的问题:目标的运算符与源的运算符不完全匹配,因此输出不能是一对一的.在您的情况下,您应该能够通过生成带有括号的PHP三元运算符来控制顺序以实现原始语义,从而解决问题,因此这不是一个大问题.
通常,生成实现期望结果的代码序列可能非常复杂,并且有很多方法可以实现.这就是编译器书籍厚而不是薄的原因.你似乎已经隐含地决定"获取AST,走AST,吐代码"; 这几乎是一个动态代码生成器.如果你不关心生成的代码是否特别好,并且目标语言非常接近源语言,那么这种方法就足够了.
如果代码生成问题更复杂,通常会发生的是AST用于生成计算的数据流模型,包括生成结果的运算符,并消耗先前运算符的结果,在"运算符"中基础获取变量值和常量.然后遍历数据流表示以生成代码; 其优点是,你可以选择在数据流表示运营商,发现在目标语言的匹配代码序列,生成,然后担心操作数是如何收集的.更好的方案将数据流子图(表示等效的复合目标语言结构)与生成的数据流图进行匹配; 这可以产生明显更好的代码.通常,可以在生成原始代码之后应用特定于目标语言的优化,以生成更好的代码.在这两种情况下,您都必须担心管理运营商的结果; 它们可以直接送到下一个目标语言操作符,还是必须进入某种临时存储(对于机器代码,这可以是另一个寄存器或内存位置).做这一切并不容易; 再次,这就是编译器书籍不薄的原因.
这个想法的变体是源到源程序转换.这将源代码中的构造"直接"映射到目标代码中的构造,尽管这通常是在后台通过操作AST来完成的,因为未解析的编程语言文本很难匹配.我们的DMS软件再造工具包就是这种系统的一个例子.有了这样一个工具,你写的源语言(其中隐含对阵解析树)模式,以及相应的模式在目标的langauge(隐式生产目标语言的AST).您可以编写复杂的源或目标构造,从而提供上面匹配的数据流图的大部分效果.后代优化包含更多重写规则,可将目标代码转换为目标代码.
一句话:除非你的翻译真的微不足道,否则有一个AST是不够的.您可以在此SO答案中详细了解您的需求:https://stackoverflow.com/a/3460977/120163
警告:大声的意见如下.
Re"Transcoder":我更喜欢术语"编译","翻译"或"源到源"编译器.近40年来,我一直在构建程序分析和操作工具.在我遇到这个问题之前,我从未听过"transcoder"一词:将遗留Cobol/PL1迁移到Java的经验 和描述IMHO的响应是一个真正糟糕的代码转换方案,称为NACA.从那以后我听说这个词正在获得牵引力; 我不明白为什么当我们有完全适当的术语时,我们必须发明另一个术语.通常这是某人发明高级祭司的标志; "让我们发明一个闪亮的新术语,这样人们就不会真正理解我们正在做的事情".我很高兴将这个词留给真正糟糕的翻译.