将AST编译回源代码

Question

将AST编译回源代码

Nik*_*kiC 30 php compiler-construction abstract-syntax-tree

我目前正在构建一个用PHP编写的PHP解析器,因为在我之前的问题中没有出现现有的解析器.该分析器本身运作得相当好.

现在很明显,解析器本身没什么用(除了静态分析).我想将转换应用于AST,然后将其编译回源代码.应用转换不是一个问题,普通的访客模式应该这样做.

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

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

现在我想专注于1.因为2.似乎很难完成(但如果你有相关的提示,我想听听它们).

但我不确定哪种设计模式可用于编译代码.我看到实现这一点的最简单方法是->compile向所有节点添加一个方法.我在这里看到的缺点是,更改生成的输出的格式非常困难.人们需要更改节点本身才能做到这一点.因此,我正在寻找一个不同的解决方案.

我听说访客模式也可以用于此,但我无法想象它应该如何工作.据我了解访问者模式,你有一些NodeTraverser在所有节点上递归迭代并调用一个->visit方法Visitor.对于节点操作来说这听起来非常有前景,其中该Visitor->visit方法可以简单地更改它传递的Node,但我不知道它如何用于编译.一个显而易见的想法是将节点树从叶子迭代到根,并用源代码替换访问的节点.但这在某种程度上似乎不是一个非常干净的解决方案？

Answer 1

Ira*_*ter 62

将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;

Run Code Online (Sandbox Code Playgroud)

请注意,当您访问树时,这会立即吐出文本.

您需要管理许多细节:

对于表示文字的AST节点,您必须重新生成文字值.如果您希望答案准确,这比看起来更难.在不损失任何精度的情况下打印浮点数比看起来要难得多(科学家在损害Pi值时讨厌它).对于字符串文字,您必须重新生成引号和字符串文字内容; 您必须小心为必须转义的字符重新生成转义序列.PHP双引号字符串文字可能有点困难,因为它们不是由AST中的单个标记表示的.(我们的PHP前端(一个重新设计的解析器/ prettyprinter)基本上将它们表示为连接字符串片段的表达式,使转换能够应用于字符串"literal"中.
间距:某些语言在关键位置需要空格.最好不要将标记ABC17 42打印为ABC1742,但可以将标记(ABC17)打印为(ABC17).解决这个问题的一种方法是在任何合法的地方放置一个空格,但是人们不会喜欢这样的结果:太多的空白.如果您只是编译结果,那不是问题.
换行符:允许任意空格的语言在技术上可以作为单行文本重新生成.人们讨厌这个,即使你要编译结果; 有时您必须查看生成的代码,这使得它变得不可能.因此,您需要一种方法来为代表主要语言元素(语句,块,方法,类等)的AST节点引入换行符.这通常不难; 在访问表示此类构造的节点时,打印出构造并附加换行符.
您会发现,如果您希望用户接受您的结果,您将不得不保留源文本的一些属性,而这些属性通常不会存储.对于文字,您可能必须重新生成文字的基数; 输入数字作为十六进制文字的编码器在重新生成十进制等值时不满意,即使它意味着完全相同的事情.同样,字符串必须具有"原始"引号; 大多数语言允许"或"作为字符串引号字符,人们想要他们最初使用的东西.对于PHP,你使用哪个引用很重要,并确定字符串文字中的哪些字符必须被转义.有些语言允许大写或小写的关键字(或者甚至是缩写),大写和小写变量名称意思相同的变量;原作者通常也想要原来的套管.PHP在不同类型的标识符中有滑稽的字符(例如"$"),但你会发现它并不总是存在(参见文字字符串中的$ variables).通常人们想要他们原始的布局格式;要做到这一点,你必须存储具体标记的列号信息,并且有关于何时使用该列的漂亮的打印规则 - 编号数据,以便在可能的情况下将相同列的文本定位在同一列中,以及如果在该列之后填充了迄今为止相当复杂的行,该怎么办.
评论:大多数标准解析器(包括你使用Zend解析器实现的解析器,我很确定)完全抛出注释.同样,人们讨厌这一点,并且会拒绝一个评论丢失的漂亮答案.这是一些漂亮的打印机尝试使用原始文本重新生成代码的主要原因(另一种是复制原始代码布局以进行保真打印,如果您没有捕获列号信息).恕我直言,正确的诀窍是捕获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;

Run Code Online (Sandbox Code Playgroud)

其中的真正价值在于,任何节点都可以使用任意插入文本以任意顺序组合其子节点生成的文本框.您可以通过这种方式重新排列大块文本(想象一下VBox以方法名称顺序排列类的方法).遇到没有文字吐出; 仅当到达根时,或者某些AST节点,其中已知所有子框已正确生成.

我们的DMS软件再造工具包使用这种方法来绘制它可以解析的所有语言(包括PHP,Java,C#等).我们不是通过访问者将盒子计算附加到AST节点,而是将盒子计算附加到特定于域的文本框表示法中

H(...)表示水平框
垂直方框的V(....)
我(...)为缩进框)

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

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

Run Code Online (Sandbox Code Playgroud)

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

进行漂亮打印的一种更复杂的方法是构建一个语法导向的翻译器(意思是,以树的顺序遍历树和构建文本或其他数据结构)以在特殊的文本框AST中生成文本框.然后,文本框AST由另一个树步行打印,但它的操作基本上是微不足道的:打印文本框.请参阅此技术文章:用于软件重新设计的漂亮打印

还有一点:您当然可以自己构建所有这些机器.但是你选择使用解析器生成器的原因相同(它有很多工作要做一个,而且这项工作并没有以一种有趣的方式为你的目标做出贡献),这与你想要选择一个非常重要的原因相同.货架prettyprinter发电机.周围有很多解析器生成器.没有多少漂亮的打印机生成器.[DMS是为数不多的内置之一.]

归档时间：	14 年，6 月前
查看次数：	9053 次
最近记录：	10 年，8 月前