LR（1）BNF語法功能參數與後省略號

Question

我想寫入BNF形式的LR（1）的語法用於通過這兩個規則從The Complete Syntax of Lua描述的語言：

parlist ::= namelist [`,´ `...´] | `...´ 
namelist ::= Name {`,´ Name} 

我試圖下面的語法，但根據我使用的工具，兩者都是 「不LR（1）由於SHIFT-減少衝突」：

parlist ::= namelist 
parlist ::= namelist , ... 
parlist ::= ... 

namelist ::= Name namelist1 
namelist1 ::= , Name namelist1 
namelist1 ::= <epsilon> 

---

parlist ::= namelist 
parlist ::= namelist , ... 
parlist ::= ... 

namelist ::= namelist1 Name 
namelist1 ::= namelist1 Name , 
namelist1 ::= <epsilon> 

對於這種語言，是否有BN（BNF）形式的LR（1）語法？

Answer 1

下面是一個簡單之一：

parlist ::= Name 
parlist ::= ... 
parlist ::= Name , parlist 

這裏的一個略小於簡單其中一個具有被左遞歸的優點：

parlist ::= namelist 
parlist ::= namelist , ... 
parlist ::= ... 
namelist ::= Name 
namelist ::= namelist , Name 

使用人工namelist1的語法的相當人爲失真非終端，看起來像是從LL語法中刪除，只是造成問題。 （雖然這可以通過將上面的第一個替代方案留在左邊來容易地完成，但它並沒有使語法LL（1）成爲可能。）

Answer 2

這是一個沒有衝突的野牛語法。它是LALR（1），這也使LR（1）：

%token ELIPSES COMMA NAME 
%% 
parlist : namelist parlistsuffix 
     | ELIPSES 
     ; 
parlistsuffix: COMMA ELIPSES 
     | /* epsilon */ 
     ; 
namelist: namelist COMMA NAME 
     | NAME 
     ;