Pourquoi ces conflits apparaissent-ils dans la grammaire yacc suivante pour XML?

J’ai la grammaire XML suivante qui fonctionne bien:

program : '' root ; root : '' node_list '' ; node_list : node_s | node_list node_s ; node_s : node | u_node | ID ; node : '' ; u_node :'' node_list '' |'' '' ; atsortingbute_list : atsortingbutes | ; atsortingbutes : atsortingbute | atsortingbutes atsortingbute ; atsortingbute : ID ASSIGNOP '"' ID '"' | ID ASSIGNOP '"' NUM '"' | ID ASSIGNOP '"' NUM ID'"' | ID ASSIGNOP '"' WEB '"' ; 

Je n’aime pas l’instruction supplémentaire relative à node_list vide. J’ai donc ajouté une règle vide à node_s |

mais ce faisant, j’obtiens les conflits suivants

 conflicts: 8 shift/reduce prog1.y:40.10: warning: rule useless in parser due to conflicts: node_s: /* empty */ 

Je ne sais pas pourquoi, toute aide serait appréciée.

L’exécution de bison --verbose ay imprimer des informations dans le fichier a.output . Le fichier contient des informations telles que:

 State 27 conflicts: 2 shift/reduce Grammar 3 node_list: node_s 4 | node_list node_s 5 node_s: node 6 | u_node 7 | ID 8 | /* empty */ ... state 27 2 root: '<' ID attribute_list '>' . node_list '<' '/' ID '>' ID shift, and go to state 28 '<' shift, and go to state 29 ID [reduce using rule 8 (node_s)] '<' [reduce using rule 8 (node_s)] node_list go to state 30 node_s go to state 31 node go to state 32 u_node go to state 33 state 28 7 node_s: ID . 

Nous pouvons voir ici que dans l'état 27, il y a 2 conflits de décalage / changement. Je vais décrire le premier décalage / réduire les conflits: lorsque la machine à états est à l'état 27 et que l'entrée est ID , la machine peut effectuer deux actions:

 shift, and go to state 28 [reduce using rule 8 (node_s)] 

La première action a été générée par la règle 7 node_s:ID , la deuxième action a été générée par la règle 8 node_s:/*empty*/ . L'action à choisir est ambiguë.

node_list est la liste de node_s . Dans l'état 27, l' ID entrée peut être analysé comme

  ID node_list = node_s:/*empty*/, node_s:ID 

ou comme

 ID node_list = node_s:ID 

En d'autres termes, il est impossible de décider si la liste de nœuds doit commencer par un nœud vide.

Pour résoudre ce problème, la grammaire doit être modifiée comme suit:

 node_list : /*empty*/ | node_list node_s ; node_s : node | u_node | ID ; u_node :'<' ID attribute_list '>' node_list '<''/'ID'>' ; 

Désormais, lors de l'parsing de la node_list '<''/'ID'>' , l'entrée déterminera sans ambiguïté si la liste de nœuds est vide ou non:

 INPUT ACTION < / empty node list < ID non-empty node list ID non-empty node list