當規則覆蓋另一個子集時，消除語法歧義

Question

我正在嘗試構建一個小型的野牛語法，但是在定義的一部分時遇到問題。函數可以用右邊的任何合法表達式（語法中的expression_list）作爲參數來調用。

問題的出現是因爲左側，功能可以通過分配給他們（標識符後跟標識符列表 - assignment_expression和identifier_list在語法）定義

我的問題是如何能夠消除因爲左側的合法聲明是右側合法聲明的子集，所以我的語法中含糊不清。

語法被寫入野牛（訴2.4.1）

從命令的輸出是：

2 shift/reduce, 2 reduce/reduce 
warning: rule useless in parser due to conflicts: assignment_expression: IDENTIFIER LPAREN RPAREN 

下面是完整的語法：

expression: 
    assignment_expression 
    | expression DECORATOR IDENTIFIER 

value: 
    IDENTIFIER 
    | HEX 
    | BIN 
    | OCT 
    | SCI 
    | FLOAT 
    | INT 
    ; 

constant_expression: 
    value 
    | LPAREN constant_expression RPAREN 
    | constant_expression OR constant_expression 
    | constant_expression XOR constant_expression 
    | constant_expression AND constant_expression 
    | constant_expression LSHIFT constant_expression 
    | constant_expression RSHIFT constant_expression 
    | constant_expression PLUS constant_expression 
    | constant_expression MINUS constant_expression 
    | constant_expression MUL constant_expression 
    | constant_expression DIV constant_expression 
    | constant_expression MOD constant_expression 
    | constant_expression POW constant_expression 
    | constant_expression FACTORIAL 
    | NOT constant_expression 
    | IDENTIFIER LPAREN RPAREN 
    | IDENTIFIER LPAREN constant_expression RPAREN 
    | IDENTIFIER LPAREN expression_list RPAREN 
    ; 

expression_list: 
    constant_expression COMMA constant_expression 
    | expression_list COMMA constant_expression 
    ; 

assignment_expression: 
    constant_expression 
    | IDENTIFIER EQUAL assignment_expression 
    | IDENTIFIER LPAREN RPAREN 
    | IDENTIFIER LPAREN IDENTIFIER RPAREN 
    | IDENTIFIER LPAREN identifier_list RPAREN 
    ; 

identifier_list: 
    IDENTIFIER COMMA IDENTIFIER 
    | identifier_list COMMA IDENTIFIER 
    ; 

以下是野牛輸出詳細模式（-v）的相關部分：

State 34 conflicts: 2 shift/reduce 
State 35 conflicts: 2 reduce/reduce 

state 34 

3 value: IDENTIFIER . 
25 constant_expression: IDENTIFIER . LPAREN RPAREN 
26     | IDENTIFIER . LPAREN constant_expression RPAREN 
27     | IDENTIFIER . LPAREN expression_list RPAREN 
33 assignment_expression: IDENTIFIER LPAREN IDENTIFIER . RPAREN 
35 identifier_list: IDENTIFIER . COMMA IDENTIFIER 

COMMA shift, and go to state 53 
LPAREN shift, and go to state 39 
RPAREN shift, and go to state 54 

COMMA  [reduce using rule 3 (value)] 
RPAREN [reduce using rule 3 (value)] 
$default reduce using rule 3 (value) 


state 35 

25 constant_expression: IDENTIFIER LPAREN RPAREN . 
32 assignment_expression: IDENTIFIER LPAREN RPAREN . 

$end  reduce using rule 25 (constant_expression) 
$end  [reduce using rule 32 (assignment_expression)] 
DECORATOR reduce using rule 25 (constant_expression) 
DECORATOR [reduce using rule 32 (assignment_expression)] 
$default reduce using rule 25 (constant_expression) 

根據要求在這裏是一個很小的語法有問題：

assignment_expression: 
    constant_expression 
    | IDENTIFIER LPAREN identifier_list RPAREN 
    ; 

value: 
    IDENTIFIER 
    | INT 
    ; 

constant_expression: 
    value 
    | IDENTIFIER LPAREN expression_list RPAREN 
    ; 

expression_list: 
    constant_expression COMMA constant_expression 
    | expression_list COMMA constant_expression 
    ; 

identifier_list: 
    IDENTIFIER COMMA IDENTIFIER 
    | identifier_list COMMA IDENTIFIER 
    ; 

Answer 1

你的文字和你的語法不太排隊。或者，也許我沒有正確理解你的文字。你說：

左側，功能可以通過分配給他們（標識符後跟標識符列表 - assignment_expression和identifier_list在語法）來定義

在我的頭上，我想象這樣的例子是這樣的：

comb(n, r) = n!/(r! * (n-r)!) 

但你的語法如下：

assignment_expression: 
    constant_expression 
    | IDENTIFIER EQUAL assignment_expression 
    | IDENTIFIER LPAREN RPAREN 
    | IDENTIFIER LPAREN IDENTIFIER RPAREN 
    | IDENTIFIER LPAREN identifier_list RPAREN 

這不會解析上面的定義，因爲EQUAL左邊可能出現的唯一東西是IDENTIFIER。右遞歸允許在賦值表達式之前任意重複IDENTIFIER =，但最後一項必須是constant_expression或三個原型生成中的一個。因此，這將匹配：

c = r = f(a,b) 

但這樣會這樣：

c = r = f(2, 7) 

我說，讓你的語法本身模棱兩可，但它可能是一個錯誤。你大概的意思是：

assignment_expression: rvalue 
        | lvalue '=' assignment_expression 

rvalue: constant_expression 

lvalue: IDENTIFIER 
     | IDENTIFIER '(' ')' 
     | IDENTIFIER '(' identifier_list ')' 

我順便指出你的identifier_list定義需要至少兩個標識符是過於複雜，所以我上面假設的identifier_list實際的定義是：

identifier_list: IDENTIFIER | identifier_list ',' IDENTIFIER 

雖然這並不足以解決問題。它仍有不知道解析器是否：

comb(n  | lookahead ',' 

是

comb(n, r) = ... 

開始或只是一個函數調用

comb(n, 4) 

因此，要解決這個問題，我們需要拉一些重型火炮。

---

我們可以從簡單的解決方案開始。這個語法並不含糊，因爲lvalue必須跟着=。當我們最終到達=時，即使它們看起來完全相同，我們也可以判斷到目前爲止我們所擁有的是rvalue還是lvalue。 （例如，comb(n, r)）。唯一的問題是，=可能與我們碰巧所處的位置有無限的距離。

對於野牛，如果我們有一個明確的語法，並且我們不能解決前瞻性問題，我們可以要求一個GLR解析器。 GLR解析器的效率稍低，因爲它需要並行保留所有可能的解析，但對於大多數不含糊的語法來說，它仍然是線性複雜的。 （GLR分析器可以在O解析甚至模棱兩可的語法（N ），但野牛實現不容忍的模糊性。它的設計解析編程語言，畢竟。）

因此，要做到這一點，你只需要添加

%glr-parser 

和讀取野牛手冊中有關如何語義動作受影響的部分。 （總結：它們被存儲起來，直到解析被消除歧義，所以它們可能沒有在解析過程中，早，因爲它們會在一個LALR（1）解析器發生）

---

的第二簡單的解決方案，這是相當在實踐中很常見的是讓解析器接受所需語言的超集，然後在語義動作中添加可以說是句法檢查的東西。因此，您可以編寫語法以允許看起來像call_expression的任何內容位於作業的左側，但是當您實際上爲作業/定義構建AST節點時，請驗證該調用的參數列表實際上是一個簡單的標識符列表。

這不僅可以簡化您的語法，而且不需要太多的實施成本，它可以生成準確的錯誤消息來描述語法錯誤，這對於標準的LALR（1）解析器來說是不容易的。

---

儘管如此，仍有是的LALR（1）語法您的語言（或者說，什麼我想，你的語言是）。爲了生成它，我們需要避免強制減少，以區分lvalue和rvalue，直到我們知道它是哪一個。

所以問題是IDENTIFIER可能是expression_list的一部分或identifier_list的一部分。而且我們不知道哪一個，即使我們看到)。因此，我們需要特殊情況IDENTIFIER '(' identifier_list ')'，以使其成爲lvalue和rvalue的一部分。換句話說，我們需要的是這樣的：

lvalue: IDENTIFIER | prototype 
rvalue: expression_other_than_lvalue | lvalue 

就剩下我們如何定義expression_other_than_lvalue的問題。大多數情況下，解決方案很簡單：常量，運算符表達式，帶括號的表達式;這些都不是左值。包含expression_other_than_identifier的帶圓括號的列表的呼叫也是expression_other_than_identifier。唯一不計算的東西就是IDENTIFIER(IDENTIFIER,IDENTIFIER,...)

所以讓我們儘可能地重寫語法。 （我已經改變了constant_expression到lvalue，因爲它是更短的打字。而對於實際的符號，我覺得這更易讀取代許多標記名稱，但以下大部分的是一樣的原件。）

value_not_identifier: HEX | BIN | OCT | SCI | FLOAT | INT 

expr_not_lvalue: 
    value_not_identifier 
    | '(' rvalue ')' 
    | rvalue OR rvalue 
    | ... 
    | IDENTIFIER '(' list_not_id_list ')' 

lvalue: 
    IDENTIFIER 
    | IDENTIFIER '(' ')' 
    | IDENTIFIER '(' identifier_list ')' 

identifier_list: 
    IDENTIFIER | identifier_list ',' IDENTIFIER 

現在，除了我們尚未定義的細節list_not_id_list之外，一切都將落實到位。 lvalue和expr_not_lvalue是不相交的，所以我們可以完成了：

rvalue: 
    lvalue 
    | expr_not_lvalue 

assignment_expression: 
    rvalue 
    | lvalue '=' assignment_expression 

，我們只需要處理未標識表表達式列表。如上所述，這是一樣的東西：

expr_not_identifier: 
    expr_not_lvalue 
    lvalue_not_identifier 

list_not_id_list: 
    expr_not_identifier 
    | list_not_id_list ',' rvalue 
    | identifier_list ',' expr_not_identifier 

所以在解析列表，我們第一次發現的東西是不是標識符，我們從identifier_list生產刪除列表。如果我們通過了整個列表，那麼當需要rvalue時，如果我們看到=或語句終止符，那麼我們仍然會發現自己的lvalue可以做出決定（最終）。

所以正確的（我希望）完整的語法是：

expression: 
    assignment_expression 
    | expression DECORATOR IDENTIFIER 

assignment_expression: 
    rvalue 
    | lvalue '=' assignment_expression 

value_not_identifier: HEX | BIN | OCT | SCI | FLOAT | INT 

expr_not_lvalue: 
    value_not_identifier 
    | '(' rvalue ')' 
    | rvalue OR rvalue 
    | rvalue XOR rvalue 
    | rvalue AND rvalue 
    | rvalue LSHIFT rvalue 
    | rvalue RSHIFT rvalue 
    | rvalue '+' rvalue 
    | rvalue '-' rvalue 
    | rvalue '*' rvalue 
    | rvalue '/' rvalue 
    | rvalue '%' rvalue 
    | rvalue POW rvalue 
    | rvalue '!' 
    | NOT rvalue 
    | IDENTIFIER '(' list_not_id_list')' 

lvalue_not_identifier: 
    IDENTIFIER '(' ')' 
    | IDENTIFIER '(' identifier_list ')' 

lvalue: 
    lvalue_not_identifier 
    | IDENTIFIER 

rvalue: 
    lvalue 
    | expr_not_lvalue 

identifier_list: 
    IDENTIFIER | identifier_list ',' IDENTIFIER 

list_not_id_list: 
    expr_not_identifier 
    | list_not_id_list ',' rvalue 
    | identifier_list ',' expr_not_identifier 

expr_not_identifier: 
    expr_not_lvalue 
    lvalue_not_identifier 

鑑於簡單的解決方案的可用性，並實現精確的語法要求變革的inelegance，這是毫不奇怪，你很少看到這種結構。但是，您會發現它在ECMA-262標準（它定義了ECMAScript又名Javascript）中廣泛使用。該報告中使用的語法形式包括一種簡化上述轉換的宏特性，但它不會使語法更容易閱讀（imho），而我不知道實現該特性的解析器生成器。