bison/yacc 语法消歧

Question

我有以下野牛语法（作为更复杂语法的一部分）： <代码>

expression:
    IDENTIFIER
    | CONST
    | LAMBDA match_block
;
match_block:
    pattern '=' expression
    | match_block '|' pattern '=' expression
;
pattern:
    IDENTIFIER
    | CONST
;

which describe expressions containing identifiers, constants and lambda-functions with pattern matching, which looks like this:

lambda 0 = 1
     | 1 = 2
     | x = x

Problem is 1 shift/reduce conflict caused by ambiguity with nested matches, as in following example:

lambda 0 = 1
     | x = lambda 1 = 2
                | y = 4

Rule is that match block relate to closest function, as shown with indentation in example above.

我的问题是 - 如何重写这个语法来消除这种歧义（不使用 %left %right yacc 指令）？

Answer 1

如果您始终希望 | 绑定到最近的 LAMBDA，那基本上意味着您只能在 LAST 中拥有 LAMBDA match_block 的 >| 子句：

non_lambda_expression:
    IDENTIFIER
    | CONST
;
expression:
    non_lambda_expression
    | LAMBDA match_block
;
non_lambda_match_block:
    pattern '=' non_lambda_expression
    | non_lambda_match_block '|' pattern '=' non_lambda_expression
;
match_block:
    pattern '=' expression
    | non_lambda_match_block '|' pattern '=' expression
;
pattern:
    IDENTIFIER
    | CONST
;

基本上，您将 expression 和 match_block 分成两个版本 - 一个允许 lambda，另一个允许 lambda不是这样的——并在每个地方使用适当的一个以避免歧义。