有沒有辦法在保持LALR（1）的同時減少這種減少的替代方案的數量？

Question

我目前在野牛減少其目的是要與幾個可選不同規則匹配一個逗號分隔的列表：

arg_list 
    : 
    | expr_list 
    | assignment_list 
    | expr_list ',' assignment_list 
    | varargs 
    | expr_list ',' varargs 
    | assignment_list ',' varargs 
    | expr_list ',' assignment_list ',' varargs 
    | varkwdargs 
    | expr_list ',' varkwdargs 
    | assignment_list ',' varkwdargs 
    | expr_list ',' assignment_list ',' varkwdargs 
    | varargs ',' varkwdargs 
    | expr_list ',' varargs ',' varkwdargs 
    | assignment_list ',' varargs ',' varkwdargs 
    | expr_list ',' assignment_list ',' varargs ',' varkwdargs 
    ; 

如果現在還不清楚，這是爲了實現（在僞代碼）：

arg_list 
    : 
    | expr_list [',' assignment_list] [',' varargs] [',' varkwdargs] 
    | assignment_list [',' varargs] [',' varkwdargs] 
    | varargs [',' varkwdargs] 
    | varkwdargs 
    ; 

要做到這一點是執行，例如方式：

optional_assignment_list: 
    : 
    | ',' assignment_list 
    ; 

然而，後一種表述不是LALR（1），因爲在Bison看到逗號的每一步中，都必須決定是否轉移並查找* assignment_list *或減少空白* optional_assignment_list *並移動在尋找一個* optional_varargs *。

我試圖找到是否有更好的方式來表示這一點。我已經能夠通過引入* optional_varkwdargs *降低替代品的數量，但仍有9個替代的減少，這是我的猜測是比16好：

optional_varkwdargs 
    : 
    | ',' varkwdargs 
    ; 

arg_list 
    : 
    | expr_list optional_varkwdargs 
    | assignment_list optional_varkwdargs 
    | expr_list ',' assignment_list optional_varkwdargs 
    | varargs optional_varkwdargs 
    | expr_list ',' varargs optional_varkwdargs 
    | assignment_list ',' varargs optional_varkwdargs 
    | expr_list ',' assignment_list ',' varargs optional_varkwdargs 
    | varkwdargs 
    ; 

任何想法，將不勝感激。

Answer 1

嘛，一個可能性是有一個更一般的arglist分析器，它允許這些事情列表以任意順序：

arg_list: arg_item 
      { $$ = CreateSingletonArgList($1); } 
     | arg_list ',' arg_item 
      { if (CheckArgListOrdering($1, $3)) 
       $$ = AppendArgList($1, $3); 
      else 
       $$ = $1; } 
     ; 

arg_item: expr 
     | assignment 
     | vararg 
     | varkwarg 
     ; 

然後，您有一個分析後檢查的arg_list以確保事情不要錯誤的順序。這樣做的好處是可以提供更好的錯誤消息，對於這些情況（「kwarg必須是可變參數後」或類似），而不僅僅是一個普通的「語法錯誤」

編輯

通過上述行動在規則中，CheckArgListOrdering函數進行檢查以確保arg_item可以在現有arg_list中的所有這些之後，如果不是，則發出適當的錯誤消息。返回值告訴解析器是否接受新的arg_item或將其丟棄。 Create/Append函數只是將arg_lists作爲任何種類的有序集合數據結構（可能是鏈接列表，數組或其他任何適當的東西）來管理。