Comment éviter un décalage réduire le conflit dans une grammaire LALR pour l'analyse des listes imbriquées?

Question

Je voudrais créer une grammaire LALR pour analyser les listes imbriquées, mais je reçois toujours un changement/réduit le conflit.

je le list1 qui est une liste d'articles de type1 et liste2:

<list1> ::= <type1> | <type1> <list1> ; 
<type1> ::= A | B | <list2> ; 

Et j'ai un liste2 qui est une liste d'articles de type2:

<list2> ::= <type2> | <type2> <list2> ; 
<type2> ::= X | Y ; 

Cette grammaire produit un changement/Réduire l'erreur. Comment puis-je l'éviter?

C'est le béton Bigloo source:

(lalr-grammar 
    (comment 
    new-line 
    text-chunk 
    white-space) 
    (input 
    (()    '()) 
    ((node-list)  node-list)) 
    (node-list 
    ((node)   (cons node '())) 
    ((node node-list) (cons node node-list))) 
    (node 
    ((comment)   (cons 'comment comment)) 
    ((new-line)  (cons 'new-line new-line)) 
    ((text)   (cons 'text text)) 
    ((white-space)  (cons 'white-space white-space))) 
    (text 
    ((text-chunk)  (cons 'text text-chunk)) 
    ((text-chunk text) (cons 'text (string-append text-chunk text))))) 

Les terminaux sont: commentaire, nouvelle ligne, le texte-morceau et espace blanc. Les non terminaux sont: entrée, liste de nœuds, nœud et texte.

Bigloo se plaint de la règle pour réduire le texte à texte morceau:

*** WARNING:bigloo:lalr-grammar 
** Shift/Reduce conflict: 
- shift to state 2 
- reduce rule (text --> text-chunk) 
on token `text-chunk' 

Mais je ne pense pas que ce soit un problème Bigloo. Cela ressemble à un problème de grammaire.

Answer 1

La grammaire est en fait ambiguë, car une séquence de type2 instances peut être accumulée au niveau list2, mais elle peut également être vue comme une séquence de type1 instances.

E.g. cette entrée

X X 

peut être analysé comme

list1(
    type1(
    list2(
     type2(
     X) 
     list2(
     type2(
      X))))) 

mais aussi

list1(
    type1(
    list2(
     type2(
     X))) 
    list1(
    type1(
     list2(
     type2(
      X))))) 

Qu'en est l'introduction d'un séparateur au niveau list1? Cela résoudrait le problème.