décider si la grammaire est LR(0) ou non

Question

Je suis nouveau dans le domaine de la compilation et je viens de commencer un exercice d'analyse ascendante.

Je suis bloqué sur le problème suivant.

construire une table d'analyse LR(0) pour la grammaire suivante :

1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id


I0 :

   E' –> .E
   E –> .E + T
   E –> .T
   T –> .(E)
   T –> .id

sur E, l'état suivant dans le DFA serait :

 I1:

    E' -> E.
    E  -> E. + T

d'après ce que j'ai appris jusqu'à présent, n'est-ce pas un conflit S-R ?Parce que l'analyseur ne saurait pas s'il doit réduire ou se déplacer car il n'a pas de variable de look-ahead?donc cela ne devrait pas être la grammaire LR(0) ?

mais le PDF que je lis a construit la table LR(0).Alors, y a-t-il une erreur dans le PDF ou ai-je mal compris le concept ?

Answer 1

C'est en effet un conflit de changement / réduit.Cette grammaire n'est pas lr (0).Vous pouvez également voir cela car ce n'est pas sans préfixe ;La grammaire contient plusieurs chaînes qui sont des préfixes les unes des autres, de sorte qu'il ne peut pas être LR (0).

Cela dit, vous pouvez toujours construire tous les ensembles de configuration LR (0) et rendre l'automate LR (0).Cela ne sera tout simplement pas déterministe en raison du changement de vitesse / réduisant le conflit.Il est donc possible que vous ayez raison et que le document a raison.

J'espère que cela vous aidera!

Answer 2

Vous avez augmenté la grammaire avec E' -> E.Normalement, vous augmenteriez avec une production comme E' -> E $, où $ est un symbole (terminal) qui n'apparaît pas autrement dans la grammaire et indique la fin de l'entrée.

Donc I1 serait en fait

E' -> E. $
E  -> E. + T

et il n'y a pas de conflit.(Et je crois que la grammaire est LR(0).)