将AST编译回源代码

我目前正在构build一个用PHP编写的PHPparsing器,因为在我之前的问题中没有parsing器出现。 parsing器本身工作得很好。

现在很明显,parsing器本身没有什么好处(除了静态分析)。 我想将转换应用到AST,然后将其编译回源代码。 应用转换不是一个问题,一个正常的访问者模式应该做的。

我现在的问题是如何将AST编译回源代码。 基本上有两种可能性:

  1. 使用一些预定义的scheme编译代码
  2. 保持原始代码的格式,并仅在已更改的节点上应用1.。

现在我想把注意力集中于1,因为2似乎很难完成(但如果你有关于这方面的技巧,我想听听他们)。

但是我不确定哪个devise模式可以用来编译代码。 我看到实现这个最简单的方法是将->compile方法添加到所有节点。 我在这里看到的缺点是要改变生成输出的格式是相当困难的。 为了做到这一点,需要改变节点本身。 因此我正在寻找一个不同的解决scheme。

我听说访问者模式也可以用于这个,但我不能想象这是如何工作的。 正如我所了解的访问者模式,你有一些NodeTraverserrecursion遍历所有节点,并调用Visitor ->visit方法。 对于节点操作来说,这听起来很有希望, Visitor->visit方法可以简单地改变它所传递的Node,但是我不知道如何将它用于编译。 一个明显的想法是迭代节点树从叶到根,并用源代码replace访问过的节点。 但是,这似乎不是一个很干净的解决scheme?

将AST转换回源代码的问题通常称为“漂亮打印”。 有两个微妙的变化:尽可能重新生成匹配原始文本(我称之为“保真度打印”),和(漂亮)漂亮的打印,这将生成很好的格式文本。 而且,如何根据编码人员是否正在处理重新生成的代码(他们通常需要高保真打印)来打印问题,或者您的唯一目的是编译它(此时任何合法的漂亮打印都可以)。

要做好漂亮的打印需要的信息通常比经典的parsing器收集的信息要多,而且大多数parsing器生成器不支持这种额外的信息收集。 我打电话给parsing器,收集足够的信息,做好这个“重新deviseparsing器”。 下面更多细节。

漂亮的基本方法是通过走AST(你把它放在“访问者模式”),并根据AST节点内容生成文本。 基本的技巧是:从左到右调用子节点(假定这是原始文本的顺序)来生成它们所代表的文本,散布其他文本以适合此AST节点types。 要打印一个语句块,你可能需要下面的伪码:

  PrettyPrintBlock: Print("{"}; PrintNewline(); Call PrettyPrint(Node.children[1]); // prints out statements in block Print("}"); PrintNewline(); return; PrettyPrintStatements: do i=1,number_of_children Call PrettyPrint(Node.children[i]); Print(";"); PrintNewline(); // print one statement endo return; 

请注意,当您访问树时,这会飞出文本。

有很多你需要pipe理的细节:

  • 对于代表文字的AST节点,您必须重新生成文字值。 如果你想要的答案是准确的,这比看起来更难。 在不损失任何精度的情况下打印浮点数比看起来难得多(科学家在损害Pi的值时讨厌它)。 对于string文字,您必须重新生成引号和string文字内容; 你必须小心重新生成转义序列的字符必须逃脱。 PHP双引号string文字可能有点困难,因为它们不是由AST中的单个标记表示的。 (我们的PHP前端 (一个reengineeringparsing器/ prettyprinter表示它们基本上是一个连接string片段的expression式,可以在string“literal”中应用转换)。

  • 间距:某些语言在关键位置需要空格。 令牌ABC17 42最好不要打印为ABC1742,但可以将令牌(ABC17)打印为(ABC17)。 解决这个问题的一个办法是在合法的地方放一个空间,但是人们不会喜欢这个结果:太多的空白。 如果您只编译结果,则不是问题。

  • 换行符:允许任意空格的语言在技术上可以作为一行文本重新生成。 人们讨厌这个,即使你要编译结果, 有时你必须看看生成的代码,这使得它不可能。 所以你需要一种方法来引入代表主要语言元素(语句,块,方法,类等)的AST节点的换行符。 这通常不难; 当访问一个表示这样的构造的节点时,打印构造并附加一个换行符。

  • 你会发现,如果你想让用户接受你的结果,你将不得不保留一些你通常不会想到的源文本属性。对于文字,你可能需要重新生成文字的基数; 编码器input一个hex文字的数字,当你重新生成十进制等价物时,并不高兴,即使它意味着完全一样的东西。 同样,string也必须有“原始”引号。 大多数语言都允许使用“或”作为string引号字符,而人们也想要它们原来使用的字符。对于使用引号的PHP,确定string中的哪些字符必须被转义,有些语言允许使用大写或小写字符。甚至是缩写),大写和小写variables名称意味着相同的variables;同样,原作者通常希望他们的原始封套返回PHP中有不同types的标识符(例如“$”)的有趣的字符,但是你会发现它并不总是存在的(参见string中的$variables)通常人们希望它们的原始布局格式化;为此,您必须存储具体令牌的列号信息,并且具有关于何时使用该列的相当详细的规则 – 数字数据,以便在可能的情况下在同一列中放置已打印的文本,以及如果在该列之后填充了迄今为止相当多的打印行,该如何处理。

  • 评论:大多数标准parsing器(包括你使用Zendparsing器实现的parsing器,我敢肯定)完全抛弃了注释。 人们再次讨厌这个问题,并且会拒绝一个评论丢失的印刷精美的答案。 这是一些漂亮打印机试图通过使用原始文本重新生成代码的主要原因(另一种是复制原始代码布局以进行高保真打印,如果没有捕获到列号信息)。 恕我直言,正确的诀窍是捕获在AST的意见,所以AST转换也可以检查/产生的意见,但每个人都有自己的deviseselect。

所有这些“额外的”信息都是由一个好的重新编译parsing器收集的。 传统的parsing器通常不会收集任何信息,这使得打印可接受的AST变得困难。

一个更原则的方法区分打印的目的是漂亮的格式,从保真打印,其目的是重新生成文本,以最大限度地匹配原始来源。 应该清楚,在terminal级别,你几乎要保真度打印。 根据你的目的,你可以打印漂亮的格式,或保真度打印。 我们使用的策略是当AST没有被改变时默认打印保真度打印,并且在打印的地方有漂亮的打印(因为改变机器经常没有关于列号或数字基数的任何信息等等)。 这些转换会将新生成的AST节点标记为“不存在保真度数据”。

一个有组织的漂亮的打印方法就是要理解,几乎所有基于文本的编程语言都是以矩形的文本块来表示的。 (Knuth的TeX文档生成器也有这个想法)。 如果您有一些文本框代表重新生成的代码片段(例如,直接为terminal令牌生成的原始框),您可以想象操作员编写这些框:水平合成(在另一个框右边堆叠一个框),垂直(堆叠在彼此之上;这实际上取代了打印换行符),缩进(水平合成和一盒空白)等等。然后你可以构build你的漂亮的打印机,通过构build和编写文本框:

  PrettyPrintBlock: Box1=PrimitiveBox("{"); Box2=PrimitiveBox("}"); ChildBox=PrettyPrint(Node.children[1]); // gets box for statements in block ResultBox=VerticalBox(Box1,Indent(3,ChildBox),Box2); return ResultBox; PrettyPrintStatements: ResultBox=EmptyBox(); do i=1,number_of_children ResultBox=VerticalBox(ResultBox,HorizontalBox(PrettyPrint(Node.children[i]); PrimitiveBox(";") endo return; 

真正的价值在于任何节点都可以用任意的顺序和任意的中间文本组成由其子节点产生的文本框。 你可以用这种方法重新排列巨大的文本块(想象一下VBox在方法名顺序中的类的方法)。 没有文字被吐出来遇到; 只有到达根时,或者某个已知所有子项目框已经正确生成的AST节点。

我们的DMS Software Reengineering Toolkit使用这种方法来打印所有可以parsing的语言(包括PHP,Java,C#等)。 我们没有通过访问者将框计算附加到AST节点,而是将框计算附加到域特定的文本框符号中

  • H(…)为水平框
  • V(….)为垂直框
  • 我(…)为缩进框)

直接到语法规则,使我们能够在一个地方简洁地expression语法(parsing器)和美丽的打印机(“反分析器”)。 漂亮的打印机规则由DMS自动编译到访问者中。 漂亮的打印机必须足够聪明才能理解评论如何发挥作用,坦率地说,这有点神秘,但你只需要做一次。 一个DMS示例:

 block = '{' statements '}' ; -- grammar rule to recognize block of statements <<PrettyPrinter>>: { V('{',I(statements),'}'); }; 

你可以看到一个更大的例子,说明如何完成Wirth的Oberon编程语言PrettyPrinter,显示语法规则和漂亮打印规则是如何组合的。 PHP前端看起来像这样,但它显然更大。

一个更复杂的方法来做一个漂亮的打印是build立一个语法导向的翻译(意味着,走树,并build立文本或其他数据结构以树的顺序),以产生一个特殊的文本框中的文本框AST。 文本框AST然后被另一棵树行走打印,但其行为基本上是微不足道的:打印文本框。 看到这个技术文件: 漂亮的打印软件再造

另一点:你当然可以自己build立所有这些机器。 但是,你select使用parsing器生成器的原因是相同的,因为你需要使用parsing器生成器来完成一个非常有用的工作,货架prettyprinter发电机。 周围有很多parsing器生成器。 没有很多漂亮的打印机。 [DMS是less数两个内置的。]