Comment est cette grammaire LL (1)?

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

$S \to AaAb \mid BbBa$
$A \to \varepsilon$
$B \to \varepsilon$

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?

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

1 2 3 4S → B b B a A → ε B → $S \to AaAb$
$S \to BbBa$
$A \to \varepsilon$
$B \to \varepsilon$

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.

$$\mathsf{FIRST}(S) = \{a, b\}\\ \mathsf{FIRST}(A) = \{\}\\ \mathsf{FIRST}(B) = \{\}\\ \mathsf{FOLLOW}(A) = \{a, b\}\\ \mathsf{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)$

$$\mbox{state 0}\\ S \to \bullet AaAb\\ S \to \bullet BbBa\\ A \to \bullet\\ B \to \bullet\\ A \implies 1\\ B \implies 5\\ $$ $$\mbox{state 1}\\ S \to A \bullet aAb\\ a \implies 2\\ $$ $$\mbox{state 2}\\ S \to Aa \bullet Ab\\ A \to \bullet\\ A \implies 3\\ $$ $$\mbox{state 3}\\ S \to AaA \bullet b\\ b \implies 4\\ $$ $$\mbox{state 4}\\ S \to AaAb \bullet b\\ $$ $$\mbox{state 5}\\ S \to B \bullet bBa\\ b \implies 6\\ $$ $$\mbox{state 6}\\ S \to Bb \bullet Ba\\ B \to \bullet\\ B \implies 7\\ $$ $$\mbox{state 7}\\ S \to BbB \bullet a \\ a \implies 8\\ $$ $$\mbox{state 8}\\ S \to BbBa \bullet \\ $$

Et puis la table (je suppose que peut être suivi de n'importe quoi).$SLR(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 ) $SLR(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)$

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:

$\qquad \begin{align} \operatorname{FIRST}(S)&={a,b} \\ \operatorname{FIRST}(A)&={ε} \\ \operatorname{FIRST}(B)&={ε} \\ \operatorname{FOLLOW}(A)&={a,b} \\ \operatorname{FOLLOW}(B)&={a,b} \end{align}$

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 ) = $A \Rightarrow a$$A \Rightarrow b$$\operatorname{FIRST}(a) \cap \operatorname{FIRST}(b) = \emptyset$
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$$Α \Rightarrow^* ε$$\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}(A) = \emptyset$

Donc, pour la grammaire donnée:

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

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

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).