优雅AST模型

Question

我正在用scala编写一个玩具编译器。目标语言本身看起来像scala，但它是一个开放的实验领域。

经过几次大的重构之后，我找不到一种很好的方法来建模我的抽象语法树。我想使用scala的模式匹配工具，问题是树在编译过程中携带移动信息(如类型、符号)。

我可以看到几种解决方案，但我不喜欢：

• 带有可变字段的case类(我相信scala编译器会这样做)：问题是，这些字段不是编译的每个阶段，因此必须为空(或选项d)，调试/编写代码变得非常困难。此外，如果举个例子，在输入阶段之后，我会找到一个空类型的节点，我很难找到错误的原因。
• 巨大的特征/案例类层次结构:类似Node，NodeWithSymbol，NodeWithType，.似乎写作和工作都很痛苦
• 用萃取器精心手工制作的东西

我也不确定使用完全不变的AST是否是一个好做法，特别是在scala中，那里没有隐式共享(因为编译器不知道不可变)，而且总是复制树可能会损害性能。

您能想到一个优雅的模式来使用scala强大的类型系统来建模我的树吗？

Answer 1

TL;DR我更喜欢将AST保持不变，并在单独的结构(例如Map )中携带类型信息，这些信息可以由存储在AST中的ID引用。但没有完美的答案。

你绝不是第一个回答这个问题的人。让我列举一些选择：

1)在每个阶段更新的可变结构。你提到的所有优点和缺点。

2)性状/饼型。可行，但昂贵(没有分享)，有点丑陋。

( 3)每个阶段都有一个新的树型。在某些方面，这是理论上最干净的。每个阶段只能处理上一阶段为其生成的结构。另外，同样的方法从前端一直到后端。例如，您可能会在某个时候"desugar“，并且有一个新的树类型意味着下游阶段甚至不需要考虑节点类型被取消的可能性。此外，低级别优化通常需要比原始AST低得多的IRs。但是这也是大量的代码，因为几乎所有的东西都必须在每一步重新创建。这种方法也可能很慢，因为在各个阶段之间几乎没有数据共享。

4)用ID标记AST中的每个节点，并使用该ID引用其他数据结构(映射和向量等)中的信息，这些结构保存着为每个阶段计算的信息。在很多方面，这是我的最爱。它保持不变，最大限度地共享和最小化您必须编写的“多余”代码。但是，您仍然需要处理“丢失”信息的可能性，这些信息很难调试。它也没有可变选项那么快，尽管比在每个阶段都需要生成一个新树的任何选项都快。

Answer 2

最近，我开始为一种小型语言编写一个玩具验证器，我正在为解析器、解析器和类型检查器阶段使用基亚马库。

Kiama是一个用于语言处理的Scala库。它可以方便地分析和转换结构化数据。库支持的编程样式基于众所周知的正式语言处理范式，包括属性文法、树重写、抽象状态机和漂亮印刷。

我将尝试总结我(相当有限的)经验：

• + Kiama提供了几个示例，主要贡献者通常会快速回答邮件列表中的问题
• +属性语法范式允许很好地分离为节点的“不可变组件”，例如名称和子节点，以及“可变组件”(例如，类型信息)。
• +这个库附带了一个通用的重写系统，到目前为止它涵盖了我所有的用例。
• +库，例如漂亮的打印机，可以很好地展示DSL和各种功能模式/方法/想法。
• -学习曲线绝对陡峭，即使有例子和邮件列表
• -以“纯功能”的方式实现解决阶段(参见( 我的问题)看起来很棘手，但混合方法(我还没有尝试过)似乎是可能的
• -属性语法范例和由此产生的关注点分离并不能清楚地说明如何记录节点最终拥有的属性(cf )。我的问题)
• - Rumour说，属性语法范式不能产生最快的实现

总结一下我的总结，我非常喜欢使用Kiama，我强烈建议您尝试一下，或者至少看一下示例。

(PS. )我没有隶属于Kiama)