解析器：像文法一样区分JavaScript中的括号和函数声明

Question

我正在开发一个使用 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（单参数函数）。但我仍然不明白为什么它仍然产生这个错误，因为对我来说非常清楚括号后跟一个粗箭头 => 将成为一个函数......

有人可以帮我解决这个问题吗？

Answer 1

But I still couldn't understand why it is still producing this error since to me it is super clear that the parenthesis followed by a fat arrow => is going to be a function...

是的，超级清晰。语法完全没有歧义。但是您不限于一次查看输入的一个标记，而 LR(1) 解析器是。当解析器试图决定如何处理 (a) 中的 a 时，它还不能看到粗箭头，它必须在它看到之前做出决定。也就是说，在使用 ) 之前，解析器需要决定在它之前出现的是 expr 还是 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冲突，但它是shift/reduce冲突而不是reduce/reduce冲突，可以通过给予RPAREN更高的优先级来解决比 ID 来强制解决方案有利于移动 RPAREN。

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

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

解析器：像文法一样区分JavaScript中的括号和函数声明

Parser: Distinguish parenthesis and function declaration in JavaScript like grammar

grammar

parsing

ocaml

menhir