parsing - bison/yacc 语法消歧

Question

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

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

它描述了包含标识符、常量和具有模式匹配的 lambda 函数的表达式，如下所示：

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

问题是 1 移位/减少冲突，由嵌套匹配的歧义引起，如下例所示：

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

规则是匹配块与最近的函数相关，如在上面的示例中显示为缩进。

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

Answer 1

如果您总是希望将a|绑定到最接近的LAMBDA，那基本上意味着您只能在 aLAMBDA的最后|一个子句中有 a 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，另一个不允许——并在每个位置使用适当的版本来避免歧义。