LR (1) BNF-Grammatik für Funktionsparameter mit Elipsis nachlauf

Question

Ich mag würde eine LR (1) Grammatik in BNF Form für die Sprache, die von diesen beiden Regeln von The Complete Syntax of Lua beschrieben schreiben:

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

I versucht habe, die folgenden Grammatiken, sondern nach dem Werkzeug ich verwende, sind beide "nicht LR (1) aufgrund shift-reduce conflict":

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> 

Gibt es eine LR (1) Grammatik in BNF-Form für diese Sprache?

Answer 1

Hier ist einfach:

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

Hier ist ein etwas weniger einfach eines, das den Vorteil, dass linksrekursive hat:

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

Die eher künstliche Verzerrung der Grammatik ein künstliches mit namelist1 Nicht-Terminal, das aussieht, als wäre es aus einer LL-Grammatik herausgenommen, verursacht nur Probleme. (Es macht auch nicht die Grammatik LL (1), obwohl das leicht durch Links-Factoring der ersten Alternative oben gemacht werden könnte.)

Answer 2

Hier ist eine Bison-Grammatik ohne Konflikte. Es ist LALR (1), die es macht auch LR (1):

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