0

给定一个语法和附加的动作代码，是否有任何标准解决方案来推断每个产生式需要产生什么类型（因此，调用产生式应该期望从中得到什么类型）？

我正在考虑使用类似于 c#var语法的 OO 程序和操作代码（但我不是在寻找特定于 c# 的东西）。

如果不是函数重载和递归语法，这将是相当简单的。

像这样的情况会出现问题：

Foo ::= 
    Bar Baz { return Fig(Bar, Baz); }
    Foo Pit { return Pop(Foo, Pit); } // typeof(foo) = fn(typeof(Foo))
4

2 回答 2

4

如果您使用函数式语言编写代码，这很容易；标准的 Hindley-Milner 类型推断效果很好。 不要这样做。在我的支持 Icon、c 和标准 ML 的 EBNF 解析器生成器（从未发布，但可根据要求提供源代码）中，我实际上实现了您所询问的标准 ML 后端的想法：所有类型都被推断出来。 由此产生的语法几乎无法调试。

如果您将重载混入其中，结果只会更难调试。（没错！这就是！比不可能更难！比无穷大！超过我的就寝时间！）如果你真的想自己尝试，欢迎使用我的代码。（你没有；我从未发布它是有原因的。）

于 2008-12-17T05:19:47.170 回答
1

语法动作的返回值实际上与局部变量没有什么不同，因此您应该能够使用 C# 类型推断来完成这项工作。有关如何实现 C# 类型推断的一些见解，请参阅本文。

进行类型推断的标准方法是Hindley-Milner 算法，但它不能处理开箱即用的重载。

请注意，即使是类型推断语言的解析器生成器通常也不会推断语法动作的类型。例如，ocamlyacc需要类型注释。Haskell的Happy解析器生成器可以推断类型，但似乎不鼓励这种做法。这可能表明推断语法中的类型很困难，或者是一个坏主意，或者两者兼而有之。

[更新] Norman Ramsey 非常喜欢，他受益于痛苦的经历。

于 2008-12-17T05:24:00.080 回答