Comment est cette grammaire LL (1)?

12

Ceci est une question du Dragon Book. Voici la grammaire:

SAaAbBbBa
Aε
Bε

La question demande comment montrer qu'il s'agit de LL (1) mais pas de SLR (1).

Pour prouver qu'il s'agit de LL (1), j'ai essayé de construire sa table d'analyse, mais j'obtiens plusieurs productions dans une cellule, ce qui est contradictoire.

Veuillez dire comment est ce LL (1) et comment le prouver?

Vinayak Garg
la source
6
Je ne suis pas très familier avec les grammaires, mais il semble que le langage de cette grammaire soit fini. L={ab,ba}
Nejc
@Nejc: Oui, ça ressemble à ça!
Vinayak Garg

Réponses:

11

Tout d'abord, donnons un numéro à vos productions.

1 2 3 4S B b B a A ε B εSAaAb
SBbBa
Aε
Bε

Calculons le premier et suivons les ensembles en premier. Pour de petits exemples comme ceux-ci, l'utilisation de l'intuition sur ces ensembles est suffisante.

FIRST(S)={a,b}FIRST(A)={}FIRST(B)={}FOLLOW(A)={a,b}FOLLOW(B)={a,b}

Calculons maintenant la table . Par définition, si nous n'obtenons pas de conflits, la grammaire est .L L ( 1 )LL(1)LL(1)

    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

Comme il n'y a pas de conflits, la grammaire est .LL(1)

Maintenant pour la table . Tout d'abord, l' automate .L R ( 0 )SLR(1)LR(0)

state 0SAaAbSBbBaABA1B5
state 1SAaAba2
state 2SAaAbAA3
state 3SAaAbb4
state 4SAaAbb
state 5SBbBab6
state 6SBbBaBB7
state 7SBbBaa8
state 8SBbBa

Et puis la table (je suppose que peut être suivi de n'importe quoi).SSLR(1)S

    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

Il y a des conflits dans l'état 0, donc la grammaire n'est pas . Notez que si était utilisé à la place, alors les deux conflits seraient résolus correctement: dans l'état 0 sur la tête de lecture, prendrait R3 et sur la tête de lecture il prendrait R4.L A L R ( 1 ) a L A L R ( 1 ) bSLR(1)LALR(1)a LALR(1)b

Cela soulève la question intéressante de savoir s'il existe une grammaire qui est mais pas , ce qui est le cas mais pas facile à trouver un exemple.L A L R ( 1 )LL(1)LALR(1)

Alex ten Brink
la source
Merci! J'avais construit correctement le First & Follow, mais j'ai fait une erreur en construisant la table.
Vinayak Garg
10

Si on ne vous le demande pas, vous n'avez pas à construire la table LL (1) pour prouver qu'il s'agit d'une grammaire LL (1). Vous calculez simplement les ensembles FIRST / FOLLOW comme l'a fait Alex:

FIRST(S)=a,bFIRST(A)=εFIRST(B)=εFOLLOW(A)=a,bFOLLOW(B)=a,b

Et puis, par définition, une grammaire LL (1) doit:

  1. Si et sont deux règles différentes de la grammaire, alors ce devrait être . Par conséquent, les deux ensembles n'ont aucun élément commun.A b PREMIER ( a ) PREMIER ( b ) = AaAbFIRST(a)FIRST(b)=
  2. Si pour tout symbole non terminal vous avez , alors il doit s'agir de . Par conséquent, s'il y a une production nulle pour un symbole non terminal, les ensembles FIRST et FOLLOW ne peuvent avoir aucun élément commun.AΑεFIRST(A)FOLLOW(A)=

Donc, pour la grammaire donnée:

  1. Nous avons depuis tandis que et ils n'ont aucun élément commun.FIRST(AaAb)FIRST(BbBa)=FIRST(AaAb)={a}FIRST(BbBa)={b}
  2. PREMIER ( A ) = { a , b } SUIVRE ( A ) = PREMIER ( B ) SUIVRE ( B ) = PREMIER ( B ) = { ε } SUIVRE ( B ) = { a , b }FIRST(A)FOLLOWA)= since while , et maintenant depuis while .FIRST(A)={a,b}FOLLOW(A)=FIRST(B)FOLLOW(B)=FIRST(B)={ε}FOLLOW(B)={a,b}

Quant à l'analyse SLR (1) je pense qu'elle est sans faille!

Ethan
la source
Bienvenue! Afin d'améliorer cette réponse, pourquoi n'appliquez-vous pas ce que vous dites à la grammaire en question?
Raphael
Heureux d'être ici!! J'ai répondu à votre demande et je pense avoir donné une explication approfondie!
Ethan
Merci! Notez que nous pouvons utiliser LaTeX ici, comme je l'ai fait pour votre calcul.
Raphael
Ouah merci! c'est une excellente explication. Mais je pense qu'il y a une erreur dans l'application. N'est-ce pas d'abord (A) = {epsilon}? Je pense que vous avez échangé le PREMIER et le SUIVI.
Vinayak Garg
FIRST (A) est en effet epsilon mais puisque vous cherchez à calculer le PREMIER ensemble du membre de droite, A -> ε montre simplement que nous avons une production vide et le premier symbole de terminal que vous voyez (et donc le PREMIER ensemble) est symbole du terminal a. J'espère que cela vous a aidé!
Ethan
0

Recherchez une condition suffisante qui fait une grammaire LL (1) (indice: regardez les PREMIERS ensembles).

Recherchez une condition nécessaire à laquelle toutes les grammaires SLR (1) doivent répondre (indice: regardez les ensembles SUIVANTS).

AProgrammer
la source