将AST编译回源代码

Question

现在显然，解析器本身并没有什么用（除了静态分析）。我想将转换应用于AST，然后将其编译回源代码。应用转换不是什么大问题，普通的Visitor模式应该可以。

我目前的问题是如何将AST编译回源代码。我基本上看到两种可能性：

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

现在，我想专注于1.，因为2.似乎很难完成（但是，如果您有关于此的提示，我想听听他们）。

但是我不太确定可以使用哪种设计模式来编译代码。我看到的最简单的实现->compile方法是向所有节点添加一个方法。我在这里看到的缺点是，很难更改生成的输出的格式。为此，需要更改节点本身。因此，我正在寻找其他解决方案。

我曾经听说过，访问者模式也可以用于此目的，但是我真的无法想象它应该如何工作。据我了解，访问者模式有一些NodeTraverser可以在所有Node上递归迭代，并调用a的->visit方法Visitor。对于节点操纵来说，这听起来很有希望，因为该Visitor->visit方法可以简单地更改它传递的Node，但是我不知道如何将其用于编译。一个明显的想法是将节点树从叶迭代到根，然后用源代码替换访问的节点。但这似乎不是一个很干净的解决方案？

Answer 1

将AST转换回源代码的问题通常称为“prettyprinting”。有两个细微的变化：尽可能多地重新生成与原始文本匹配的文本（我称之为“保真打印”），以及（漂亮的）prettyprinting，可以生成格式正确的文本。以及您的打印方式很重要，这取决于编码人员是要处理重新生成的代码（他们通常想要保真打印）还是您唯一的意图是编译它（此时可以进行任何合法的漂亮打印都可以）。

要做好漂亮的打印，通常需要比经典解析器收集更多的信息，而大多数解析器生成器不支持此额外信息收集这一事实使情况更加恶化。我将收集足够信息以完成此工作的解析器称为“重新设计解析器”。下面有更多详细信息。

完成漂亮打印的基本方法是通过遍历AST（如您所说的“访客模式”），并基于AST节点内容生成文本。基本技巧是：从左到右调用子节点（假设这是原始文本的顺序）以生成它们表示的文本，并在此AST节点类型的适当位置插入其他文本。要漂亮地打印语句块，您可能具有以下伪代码：

 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;

请注意，这在您访问树时会即时弹出文本。

您需要管理许多细节：

• 对于表示文字的AST节点，您必须重新生成文字值。如果您想要准确的答案，这比看起来要难。在不损失精度的情况下打印浮点数比看起来 要 困难得多（科学家会在破坏Pi的值时讨厌它）。对于字符串文字，您必须重新生成引号和字符串文字内容。您必须小心重新生成必须转义的字符的转义序列。PHP用双引号括起来的字符串文字可能会有点困难，因为它们在AST中没有用单个标记表示。（我们的PHP前端（重新设计的解析器/ prettyprinter本质上将它们表示为连接字符串片段的表达式，从而可以在字符串“ literal”内部应用转换）。

• 间距：某些语言在关键位置需要空格。最好不要将令牌ABC17 42打印为ABC1742，但是可以将令牌（ABC17）打印为（ABC17）。解决此问题的一种方法是在合法的地方放置一个空格，但是人们不喜欢结果：太多的空格。如果仅编译结果，这不是问题。

• 换行符：允许任意空格的语言可以从技术上重新生成为一行文本。即使您要编译结果，人们也讨厌这样做。有时您 必须 查看生成的代码，这使它变得不可能。因此，您需要一种方法来为代表主要语言元素（语句，块，方法，类等）的AST节点引入换行符。通常这并不难；当访问表示这种构造的节点时，请打印出该构造并添加换行符。

• 您会发现，如果希望用户接受结果，则必须保留通常不认为要存储的源文本的某些属性。对于文字，您可能必须重新生成文字的基数。当您重新生成十进制等效项时，即使输入的内容完全相同，但以十六进制文字形式输入数字的编码人员也不满意。同样，字符串必须带有“原始”引号。大多数语言都允许使用“或’作为字符串引号字符，而人们希望使用它们最初使用的字符。对于PHP，用引号引起来的事情很重要，并确定必须将字符串文字中的哪些字符转义。某些语言允许使用大写或小写关键字（甚至缩写），大小写变量名表示同一个变量；再次，原作者通常希望将原件归还。PHP在不同类型的标识符中具有有趣的字符（例如，“ $”），但是您会发现它并不总是存在（请参阅文字字符串中的$变量）。人们通常希望其原始布局格式；为此，您必须在列号信息中存储具体令牌，并具有关于何时使用该列号数据将漂亮字体的文本放置在同一列中的可能位置的漂亮打印规则，以及到目前为止该怎么做。 -prettyprinted行填充到该列之后。

• 注释：大多数标准解析器（包括我非常确定的使用Zend解析器实现的解析器）都会完全丢弃注释。同样，人们讨厌这一点，并且会拒绝打印出漂亮的答案，而这些评论会丢失评论。这是一些prettyprinters尝试通过使用原始文本来重新生成代码的主要原因（另一个原因是，如果您没有捕获列号信息，则复制原始代码布局以进行保真打印）。恕我直言，正确的技巧是在AST中捕获注释，以便AST转换也可以检查/生成注释，但是每个人都可以自己设计。

所有这些“额外”信息都是由良好的重新设计解析器收集的。传统的解析器通常不收集任何信息，这使得打印可接受的AST变得很困难。

一种更原则化的方法将目的是好的格式化的漂亮打印与目的是重新生成文本以最大程度地匹配原始源的保真打印区分开。应该清楚的是，在终端机级别，您几乎要保真打印。根据您的目的，您可以使用漂亮的格式打印或保真打印。我们使用的策略是在未更改AST的情况下默认使用保真打印，并在其中进行漂亮的打印（因为更改机制通常没有有关列号或数字基数的任何信息）。转换将新生成的AST节点标记为“不存在保真度数据”。

很好地进行漂亮打印的一种有组织的方法是要理解，实际上所有基于文本的编程语言都可以用 矩形
文本块很好地呈现。（Knuth的TeX文档生成器也有这个想法）。如果您有一些表示重新生成的代码的文本框集（例如，直接为终端令牌生成的原始框），则可以想象用于组合这些框的运算符：水平构图（将一个框堆叠在另一个框的右边），垂直（堆叠框彼此叠​​放；实际上替代了打印换行符），缩进（水平组合带空白框）等。然后，您可以通过构建和组合文本框来构建prettyprinter：

 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软件再造工具包使用这种方法来打印所有可以解析的语言（包括PHP，Java，C＃等）。我们不是通过访问者将框计算附加到AST节点上，而是将框计算附加到特定于域的文本框符号中

• H（…）用于卧式包装箱
• V（....）垂直盒
• 我（…）缩进框）

直接遵循语法规则，使我们可以在一个地方简洁地表达语法（解析器）和prettyprinter（“反解析器”）。prettyprinter框规则由DMS自动编译为访问者。prettyprinter机器必须足够聪明，才能理解评论是如何发挥作用的，坦率地说，这有点不可思议，但您只需要执行一次即可。DMS示例：

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

您可以看到一个更大的示例，说明如何使用Wirth的Oberon编程语言PrettyPrinter完成语法规则和prettyprinting规则的组合。PHP前端看起来像这样，但是显然要大得多。

进行漂亮打印的一种更复杂的方法是构建语法导向的转换器（即，按树的顺序走树并构建文本或其他数据结构），以在特殊的文本框AST中生成文本框。文本框AST然后通过另一棵树走动进行漂亮的打印，但是它的操作基本上是微不足道的：打印文本框。

还有一点：您当然可以自己构建所有这些机器。但是，您选择使用解析器生成器的原因（创建一个解析器需要进行大量工作，并且该工作不会以有趣的方式对您的目标有所贡献）与您选择现成的原因相同。架子prettyprinter生成器。周围有很多解析器生成器。prettyprinter生成器并不多。[DMS是内置的少数几个。]