1

我正在开发一个使用 OCaml 和 Menhir 作为解析器和词法分析器的编译器。当我编写像语法这样的 JavaScript 时，(a, b) => a + b像 lambda 函数定义以及(a + b) * c带有括号优先子表达式的算术一样，我写

expr
: x = ID { EId(x) }
...
| LPAREN; e = expr; RPAREN; { e }
...
| LPAREN; args = separated_list(COMMA, ID); RPAREN; ARROW; body = expr; { EFunction(args, body) }

在parser.mly.

只需添加更多上下文，我就有lexer.mll这样的：

let letter = ['a'-'z' 'A'-'Z']
let lud = ['a'-'z' 'A'-'Z' '_' '0'-'9']
let id = letter lud*

rule read = parse
    ...
    | "(" { LPAREN }
    | ")" { RPAREN }
    | "," { COMMA }
    | "=>" { ARROW }
    ...
    | id { ID (Lexing.lexeme lexbuf) }
    ...

但这会在编译时出现reduce/reduce错误：

Error: do not know how to resolve a reduce/reduce conflict between the following two productions:
expr -> ID
separated_nonempty_list(COMMA,ID) -> ID

我知道问题可能是由这两者之间的歧义引起的：(a)和(a) => a（one-arg-function）。但我仍然不明白为什么它仍然会产生这个错误，因为对我来说非常清楚，后面跟着一个粗箭头的括号=>将成为一个函数......

有人可以帮助我吗？

4

1 回答 1

1

但我仍然不明白为什么它仍然会产生这个错误，因为对我来说非常清楚，后面跟着一个粗箭头的括号=>将成为一个函数......

是的，超级清晰。语法是完全明确的。但是您不限于一次查看输入一个标记，而 LR( 1 ) 解析器则可以。在解析器试图决定如何处理ain的那一刻(a)，它还看不到胖箭头，它必须在它之前做出决定。也就是说，在使用 之前)，解析器需要确定它之前的内容是 anexpr还是 a separated_nonempty_list。

可能值得注意的是，语法实际上是 LR(2)：多了一个前瞻标记，并且可以解决冲突。这并不是什么安慰，因为 Menhir 没有提供任何增加前瞻的机制，但这确实意味着存在解决方案，因为一种语言的 LR(k) 语法的存在意味着相同语言的 LR(1) 语法的存在语; 甚至还有一种生成 LR(1) 语法的机械算法。

除了转换整个语法之外，一个稍微有点混乱的解决方案是隔离 '(a)' 情况，这可以通过一对明显冗余的规则来完成：

expr: LPAREN ID RPAREN ARROW expr
    | LPAREN ID RPAREN

第二个生产显然与 冲突LPAREN expr RPAREN，但它是一个转移/减少冲突而不是一个减少/减少冲突，它可以通过给予RPAREN更高的优先级来解决，而不是ID为了强制解决有利于转移RPAREN。

这是对优先级声明的完全颠倒，而且随着您的语法变得更加复杂，它很可能会出现问题。一个理论上更合理的解决方案是定义expr_other_than_identifier. 您可以在此处找到一个示例，这是一个非常相似的语法，并且在其他一些类似问题的 SO 答案中。

:特别是，Yacc 自己的语法是 LR(2)（直到您看到启动下一条规则的非终结符之后，您才能判断一条规则已经结束）。该语法存在类似的解决方案，但大多数类似 yacc 的解析器生成器通过将额外的前瞻推入词法分析器来解决问题。例如，您可以将其识别) =>为单个标记（包括内部空格），或者如果下一个标记是粗箭头，则可以发出不同的右括号标记。

于 2018-07-06T07:32:45.273 回答