野牛/ yacc语法消歧

Question

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

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

，其描述了含有标识符，常量以及与模式匹配，它看起来像这样λ-函数的表达式：

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

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

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

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

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

Answer 1

如果你总是希望|绑定到最接近LAMBDA，基本上只是意味着你只能在最后|子句match_block中有一个LAMBDA：

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分成两个版本 - 一个允许lambdas和一个不 - 并在每个地方使用适当的一个以避免模糊。