Comment surmonter le conflit de décalage-réduction dans la grammaire LALR

Question

J'essaye d'analyser des nombres décimaux positifs et négatifs.

number(N) ::= pnumber(N1). 

number(N) ::= nnumber(N1). 

number(N) ::= pnumber(N1) DOT pnumber(N2). 

number(N) ::= nnumber(N1) DOT pnumber(N2). 

pnumber(N) ::= NUMBER(N1). 

nnumber(N) ::= MINUS NUMBER(N1). 

L'inclusion des deux premières règles donne un changement/réduire les conflits, mais je ne sais pas comment je peux écrire la grammaire telle que le conflit ne se produit jamais. J'utilise l'analyseur de citron.

Edit: les conflits de .out

State 79: 
    (56) number ::= nnumber * 
      number ::= nnumber * DOT pnumber 

          DOT shift  39 
          DOT reduce  56  ** Parsing conflict ** 
        {default} reduce  56  number ::= nnumber 

State 80: 
    (55) number ::= pnumber * 
      number ::= pnumber * DOT pnumber 

          DOT shift  40 
          DOT reduce  55  ** Parsing conflict ** 
        {default} reduce  55  number ::= pnumber 
State 39: 
      number ::= nnumber DOT * pnumber 
      pnumber ::= * NUMBER 

         NUMBER shift-reduce 59  pnumber ::= NUMBER 
         pnumber shift-reduce 58  number ::= nnumber DOT pnumber 

State 40: 
      number ::= pnumber DOT * pnumber 
      pnumber ::= * NUMBER 

         NUMBER shift-reduce 59  pnumber ::= NUMBER 
         pnumber shift-reduce 57  number ::= pnumber DOT pnumber 

Edit 2: grammaire minimale qui cause problème

start ::= prog. 
prog ::= rule. 
rule ::= REVERSE_IMPLICATION body DOT. 
body ::= bodydef. 
body ::= body CONJUNCTION bodydef. 
bodydef ::= literal. 
literal ::= variable. 
variable ::= number. 
number ::= pnumber. 
number ::= nnumber. 
number ::= pnumber DOT pnumber. 
number ::= nnumber DOT pnumber. 
pnumber ::= NUMBER. 
nnumber ::= MINUS NUMBER. 

Answer 1

Les conflits vous montrent indiquer un problème avec la façon dont le non-terminal number est il utilisé, pas avec number lui-même.

Le problème de base est que, après avoir vu un pnumber ou nnumber, lorsque le prochain jeton de test avant est un DOT, il ne peut pas décider si cela devrait être la fin de la number (réduire, si DOT fait partie d'un autre non terminal après du number), ou si le DOT doit être traité dans le cadre du number (déplacé de sorte qu'il peut ensuite réduire l'un des p/nNombre règles DOT de pNuméro.)

Ainsi, afin de diagnostiquer la problème, vous devrez montrer toutes les règles qui utilisent number n'importe où sur le côté droit (et se répète toutes les autres règles qui utilisent les non-terminaux de ces règles sur la droite).

Notez qu'il est rarement utile pour poster juste un fragment d'une grammaire, comme le processus de construction de l'analyseur LR dépend fortement du contexte où les règles sont utilisées ailleurs dans la grammaire ...

---

Donc, le problème ici est que vous avez besoin de lookahead à deux jetons pour faire la différence entre un DOT dans un (réel) literal et un DOT à la fin d'un rule.

La solution facile est de laisser l'affaire lexer avec elle - lexers peuvent faire de petites quantités de préanalyse assez facilement, de sorte que vous pouvez reconnaître REAL_NUMBER comme un non-terminal distinct de NUMBER (probablement encore sans -, de sorte que vous » d finir avec

number ::= NUMBER | MINUS NUMBER | REAL_NUMBER | MINUS REAL_NUMBER 

est beaucoup plus difficile à éliminer le conflit par affacturage la grammaire, mais il peut être fait.

---

en général, pour factoriser une grammaire pour supprimer un conflit d'anticipation, vous devez trouver les règles qui manifestent le conflit (rule et number ici) et refactoriser les choses pour les rassembler dans des règles qui ont des préfixes communs jusqu'à ce que vous soyez assez loin pour désambiguïser. Tout d'abord, je vais supposer qu'il existe d'autres règles que number qui peuvent apparaître ici, sinon nous pourrions simplement éliminer toutes les règles intermédiaires.

variable ::= number | name 

Nous voulons déplacer la règle number « up » dans la grammaire pour l'obtenir dans le même endroit que rule avec DOT. Nous avons donc besoin de diviser les règles contenant à un cas particulier quand ils se terminent par un number. Nous ajoutons un suffixe pour désigner les règles qui correspondent à la règle d'origine avec toutes les versions qui se terminent par un number séparé

variable ::= number | variable_n 
variable_n ::= name 

... et ProGate que « up »

literal ::= number | literal_n 
literal_n ::= variable_n 

... et agin

bodydef ::= number | bodydef_n 
bodydef_n := literal_n 

... et encore

body ::= number | body_n 
body := body CONUNCTION number 
body_n ::= bodydef_n 
body_n ::= body CONJUNCTION bodydef_n 

Notez que lorsque vous le déplacez vers le haut, vous devez diviser de plus en plus de règles, ce processus peut donc faire exploser la grammaire. Cependant, les règles qui sont utilisées seulement à la fin d'un rhs que vous refactoring finira par avoir seulement besoin de la version _n, donc vous n'avez pas nécessairement à doubler le nombre de règles.

... dernière étape

rule ::= REVERSE_IMPLICATION body_n DOT 
rule ::= REVERSE_IMPLICATION number DOT 
rule ::= REVERSE_IMPLICATION body CONJUNCTION number DOT 

Vous avez maintenant les points dans les mêmes endroits, donc élargir les règles number:

rule ::= REVERSE_IMPLICATION body_n DOT 
rule ::= REVERSE_IMPLICATION integer DOT 
rule ::= REVERSE_IMPLICATION integer DOT pnumber DOT 
rule ::= REVERSE_IMPLICATION body CONJUNCTION integer DOT 
rule ::= REVERSE_IMPLICATION body CONJUNCTION integer DOT pnumber DOT 

et les conflits décalage réduire ces risques sont partis, parce que les règles ont des préfixes communs jusqu'à la fin de l'anticipation nécessaire pour déterminer lequel utiliser. J'ai réduit le nombre de règles dans cette expansion finale en ajoutant

integer ::= pnumber | nnumber 

Answer 2

Vous devez déclarer l'associativité du jeton opérateur DOT avec %left ou %right.

Ou, une autre idée consiste à abandonner cette réduction intermédiaire. La caractéristique évidente de votre grammaire est que les nombres augmentent de DOT suivi d'un nombre. Cela peut être capturé avec une seule règle:

number : number DOT NUMBER 

Un nombre suivi d'un DOT suivi d'un jeton NUMBER est encore un certain nombre.

Cette règle n'exige pas DOT qu'une associativité soit déclarée, car il n'y a pas d'ambiguïté; la règle est purement récursive à gauche, et la main droite de DOT est un jeton de terminal. L'analyseur doit réduire le haut de la pile à number lorsque la machine d'état est à ce point, puis passer DOT:

number : number DOT NUMBER 

La langue que vous analysez ici est régulier; il peut être analysé par des expressions régulières sans aucune récursion. C'est pourquoi les règles qui ont à la fois une récursion gauche et une récursion droite et qui exigent que l'associativité soit déclarée sont en quelque sorte un "gros marteau".