LR (1) grammaire BNF pour les paramètres de fonction avec elipsis arrière

Question

Je voudrais écrire une grammaire LR (1) sous forme BNF pour la langue décrite par ces deux règles de The Complete Syntax of Lua:

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

J'ai essayé le suivant grammaires, mais selon l'outil que je me sers, les deux sont « non LR (1) en raison de la touche Maj enfoncée réduire les conflits »:

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> 

Existe-t-il une grammaire LR (1), sous forme BNF, pour cette langue?

Answer 1

est ici simple:

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

est ici un peu moins simple qui a l'avantage d'être à gauche récursive:

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

La distorsion assez artificielle de la grammaire en utilisant un artificielle namelist1 Non-terminal, qui semble être sorti d'une grammaire LL, ne fait que causer des problèmes. (Cela ne fait pas non plus la grammaire LL (1), bien que cela puisse facilement être fait en factorisant la première alternative ci-dessus.)

Answer 2

Voici une grammaire de bison sans conflits. Il est LALR (1), ce qui le rend aussi LR (1):

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