如何解决LR(1)语法定义中的歧义？

Question

我在OCaml中编写Golang编译器,参数列表让我有点头疼.在Go中,您可以按以下方式对相同类型的连续参数名称进行分组:

func f(a, b, c int)  ===  func f(a int, b int, c int)

您还可以拥有一个类型列表,不带参数名称:

func g(int, string, int)

这两种风格不能混合搭配; 要么所有参数都被命名,要么都没有.

我的问题是,当解析器看到一个逗号时,它不知道该怎么做.在第一个例子中,是a一个类型的名称或一个变量的名称,有更多的变量出现？逗号有双重角色,我不知道如何解决这个问题.

我正在为OCaml使用Menhir解析器生成器工具.

编辑:目前,我的Menhir语法完全遵循http://golang.org/ref/spec#Function_types中规定的规则

Answer 1

正如所写，go 语法不是LALR(1). 事实上，它不LR(k)适合任何k. 然而，它是明确的，所以你可以用GLR解析器成功解析它，如果你能找到一个（我很确定有几个用于 OCAML 的 GLR 解析器生成器，但我对它们中的任何一个都不太了解推荐一个）。

如果您不想（或不能）使用GLR解析器，您可以像 Russ Cox 在gccgo编译器中所做的那样，使用bison. （bison可以生成 GLR 解析器，但 Cox 不使用该功能。）他的技术不依赖于扫描器区分类型名称和非类型名称。

相反，它只接受其元素为name_or_typeor 的参数列表name name_or_type（实际上，由于...语法的原因，有更多的可能性，但它不会改变一般原则。）这很简单，明确和LALR(1)，但它过于接受--func foo(a, b int, c)例如，它将接受-- 并且它不会生成正确的抽象语法树，因为它不会将类型附加到正在声明的参数列表。

这意味着一旦参数列表被完全解析并即将插入到附加到某个函数声明的 AST 中（例如），将执行语义扫描以修复它，并在必要时生成错误消息。该扫描是在声明元素列表上从右到左完成的，以便指定的类型可以传播到左侧。

值得注意的是，参考手册中的语法也过于接受，因为它没有表达“所有参数都命名或都不命名”的约束。这个约束可以用 LR(1) 语法来表达——我将把它留给读者作为练习——但由此产生的语法会更难以理解。