将AST编译回源代码

#1 楼

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

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

完成AST的基本方法是通过遍历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在不同类型的标识符中具有有趣的字符（例如“ $”），但是您会发现它并不总是存在（请参阅文字字符串中的$变量）。人们通常希望使用其原始布局格式；为此，您必须在列号信息中存储具体令牌，并具有关于何时打印的漂亮打印规则。使用该列号数据将漂亮打印的文本放置在同一列中的可能位置，以及如果该行之前填充了漂亮打印的行怎么办。
评论：大多数标准解析器（包括您自己的解析器）使用Zend解析器实现，我敢肯定）将评论完全丢弃。再次，人们讨厌这一点，并且会拒绝打印出漂亮的答案，而答案会丢失。这是一些prettyprinters尝试通过使用原始文本来重新生成代码的主要原因（
（如果您没有捕获列号信息，则另一个方法是复制原始代码布局以进行保真打印）。恕我直言，正确的技巧是在AST中捕获注释，以便AST转换也可以检查/生成注释，但每个人都可以自己设计选择。

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

更加原则化的方法将目的是好的格式化的prettyprint与有意重新生成文本以匹配的保真打印区分开来。原始来源在最大程度上。应该清楚的是，在终端机级别上，您几乎想要保真打印。根据您的目的，您可以用漂亮的格式打印或保真打印。我们使用的一种策略是在未更改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（....）表示垂直框
I（...）表示缩进框）

直接使用语法规则，使我们可以简洁地表达语法（解析器）， 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是同时内置的少数几个。]