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 
     ;