野牛/ 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和一個不 - 並在每個地方使用適當的一個以避免模糊。