我正在从事一个包含小型 DSL 的项目。用这种语言对字符串进行词法分析和解析会生成一个解析树，实现为一个名为 Expr 的抽象类，然后它有许多常见的派生类，如 AssignmentExpr、InvokeExpr、AdditionExpr 等，对应于解析树节点，这些节点是赋值、函数调用、添加等。该项目是用 C# 实现的。
我目前正在考虑为这个 DSL 实现类型推断。这意味着我希望能够获取 Expr 类的实例并返回一些关于树中不同节点类型的编码信息。此类型信息取决于符号表(变量类型)和函数表(函数签名)。因此，我想做类似的事情:
TypedExpr typedExpr = inferTypes(expr, symbolTable, functionTable)
在这里，TypedExpr 理想情况下与 Expr 类似，只是具有给出表达式类型的 Type 属性。然而，这会带来以下设计问题:
TypedExpr 继承自 Expr 并简单地实现一个附加属性 Type 是有意义的。但是，这会创建两个并行的继承层次结构，一个用于 TypedExpr(TypedAssignmentExpr、TypedInvokeExpr 等)，另一个用于 Expr(AssignmentExpr、InvokeExpr 等)。这不便于维护，如果需要进一步扩展解析树，问题就会扩大。我不确定如何减轻这种情况。一种可能是桥梁设计模式，但我认为这不能完全解决问题。
或者，Expr 可以简单地实现一个 Type 属性，然后在解析器构造时该属性为 null，然后由类型推断算法填充。但是，传递具有空字段的对象会引发 NullReferenceExceptions。 TypedExpr 的想法可以缓解这种情况。此外，考虑到 Expr 类的想法是表达解析树，类型信息实际上并不是树的一部分:类型是上下文相关的，需要特定的符号和函数表。
第三，类型推断方法还可以简单地返回一个 Dictionary
我对上面给出的三个解决方案中的任何一个都不完全满意。
我的问题是:解决这个问题的各种方法有哪些优点和缺点？类型信息应该直接在解析树中编码，还是应该使用并行树类？还是字典解决方案是最好的？是否有公认的“最佳实践”解决方案？
最佳答案
继续选项二。这可以被视为“最佳实践”。
原因是一个编译器通常在很多pass(阶段，阶段)中工作。解析是第一个，类型解析是另一个。您可以稍后添加优化 channel 、代码生成 channel 等。通常，在所有这些 channel 中维护单个数据结构、抽象语法树(AST；或解析树)。
“传递具有 null 字段的对象会引发 NullReferenceExceptions” 的想法只是错误的担忧。您必须处理无效情况并引入反制措施以无论如何验证输入/输出。编译器(包括简单的表达式处理器)是由复杂规则驱动的相当复杂的事物，其中涉及高度复杂的数据结构和您无法简单避免的应用程序逻辑。
AST 具有未初始化的数据是非常正常的。每个编译过程，除了解析器对 AST 的初始构造之外，然后操作 AST，计算更多信息(如类型解析阶段)。 AST 甚至可能发生重大变化，即由于优化过程。
旁注:现代编译器(例如最新的 C# 编译器)对 AST 和其他内部数据结构采用了非可变性策略。在那种情况下，每个 channel 都会构建自己的新数据结构。然后，您可以为每次传递设计一组新的数据结构，但这可能会变成需要维护的过于复杂的代码。 C# 编译器团队的某个人可以详细说明这个主题。
关于c# - 类型信息应该在解析树中编码吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23265473/