我正在用 scala 编写一个玩具编译器。目标语言本身看起来像 scala，但它是一个开放的实验领域。
经过几次大型重构后，我找不到一个很好的方法来为我的抽象语法树建模。我想使用 scala 的模式匹配工具，问题是树在编译过程中携带移动信息（如类型、符号）。
我可以看到几个解决方案，我都不喜欢：
具有可变字段的案例类（我相信 scala 编译器会这样做）：问题是这些字段在编译的每个阶段都不存在，因此必须为空（或 Option'd）并且调试/写代码。此外，例如，如果我在输入阶段之后找到了一个 null 类型的节点，我很难找到错误的原因。
巨大的 trait/case 类层次结构：像 Node、NodeWithSymbol、NodeWithType 之类的东西……似乎很难编写和使用
用提取器完全手工制作的东西
我也不确定使用完全不可变的 AST 是否是一种好习惯，尤其是在没有隐式共享的 scala 中（因为编译器不知道不可变性），并且一直复制树可能会损害性能.
你能想出一个优雅的模式来使用 scala 强大的类型系统来模拟我的树吗？
TL;DR 我更喜欢保持 AST 不可变，并在单独的结构（例如 Map）中携带类型信息之类的东西，可以由存储在 AST 中的 ID 引用。但没有完美的答案。
你绝不是第一个为这个问题而苦苦挣扎的人。让我列出一些选项：
1) 在每个阶段更新的可变结构。你提到的所有优点和缺点。
2）特征/蛋糕图案。可行，但昂贵（没有共享）而且有点丑陋。
3) 每个阶段都有一个新的树类型。在某些方面，这是理论上最干净的。每个阶段只能处理前一阶段为其生成的结构。加上同样的方法从前端一直到后端。例如，您可能在某个时候“脱糖”，并且拥有新的树类型意味着下游阶段甚至不必考虑通过脱糖消除的节点类型的可能性。此外，低级优化通常需要比原始 AST 低得多的 IR。但这也是很多代码，因为几乎所有内容都必须在每一步重新创建。这种方法也可能很慢，因为阶段之间几乎没有数据共享。
4) 用 ID 标记 AST 中的每个节点，并使用该 ID 来引用其他数据结构（地图和向量等）中的信息，这些数据结构包含为每个阶段计算的信息。在很多方面，这是我最喜欢的。它保持不变性，最大化共享并最小化您必须编写的“多余”代码。但是您仍然必须处理可能难以调试的“丢失”信息。它也没有 mutable 选项快，但比任何需要在每个阶段生成新树的选项都快。
我最近开始为一种小型语言编写一个玩具验证器，并且我正在使用Kiama库进行解析器、解析器和类型检查器阶段。
Kiama 是一个用于语言处理的 Scala 库。它可以方便地分析和转换结构化数据。该库支持的编程风格基于众所周知的形式语言处理范例，包括属性语法、树重写、抽象状态机和漂亮的打印。
我将尝试总结我的（相当有限的）经验：
[+] Kiama 提供了几个示例，主要贡献者通常会快速回复邮件列表中提出的问题
[+] 属性文法范式允许将节点的“不可变组件”（例如名称和子节点）和“可变组件”（例如类型信息）很好地分离
[+] 该库带有一个通用的重写系统，到目前为止，它涵盖了我所有的用例
[+] 该库，例如漂亮的打印机，为 DSL 和各种功能模式/方法/想法提供了很好的示例
[-] 学习曲线绝对陡峭，即使有示例和手头的邮件列表
[-] 以“纯功能”风格（参见我的问题）实现解析阶段似乎很棘手，但混合方法（我还没有尝试过）似乎是可能的
[-] 属性语法范式和由此产生的关注点分离并没有使如何记录节点最终具有的属性变得明显（参见我的问题）
[-] 有传言说，属性语法范式不会产生最快的实现
总结一下我的总结，我非常喜欢使用 Kiama，我强烈建议您尝试一下，或者至少看看示例。
（PS.我不隶属于Kiama）