parsing - 分析没有固定/静态语义的树？

Question

我正在尝试分析一种可以有多种翻译的动态语言，具体取决于概率。我在我的语言中定义了一些类型，例如数字、向量等...

例如，如果我们看到表达式“a+b”，那么它可能是两个数字的加法，也可能是两个向量的加法。数字更有可能，因此我们认为“最佳”表示是两个数字的总和。然而它们有可能是向量，所以我仍然想保留这种“不太可能”的表示。

如果后来我看到“a/b”，那么我就知道它们不能是向量，因为向量除法是未定义的。因此，我会丢弃“矢量”表示形式，并以正确的表示形式为准。

我想通过分析 AST 来做到这一点。问题是，由于类型和运算符有多种可能的组合，我们出现了组合爆炸。

关于我可以使用的合适策略或模式有什么想法吗？我正在考虑一种不同组合的访问者类型，它们并行运行以赋予结构最好的含义。有点像在自然语言处理中分析句子。

我使用 ANTLR 的树遍历机制进行分析，因此任何特定于该系统的引用，或实现动态语言的语义将不胜感激。

Answer 1

从我的角度来看，你本质上需要的是一个类型推断系统，它是编程语言中表达式类型的自动推导。您可以从the wikipedia page about type inference开始，然后花一些时间去理解the Hindley–Milner algorithm .

AST 只是编译器的开始，因此您应该尝试习惯构建 AST 的具体数据结构并编写访问者多次遍历树。语义部分只有在构建了整个 AST 之后才开始。