Jaka jest ta gramatyka LL (1)?

To pytanie z Dragon Book. Oto gramatyka:

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

Pytanie dotyczy tego, jak pokazać, że jest to LL (1), ale nie SLR (1).

Aby udowodnić, że jest to LL (1), próbowałem zbudować jego tabelę analizującą, ale otrzymuję wiele produkcji w komórce, co jest sprzecznością.

Powiedz, jak to jest LL (1) i jak to udowodnić?

Po pierwsze, dajmy swoim produkcjom numer.

1 2 3 4$S \to AaAb$
$S \to BbBa$
$A \to \varepsilon$
$B \to \varepsilon$

Obliczmy pierwszy i najpierw wykonajmy zestawy. W przypadku takich małych przykładów wystarczy intuicyjna obsługa tych zestawów.

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

Teraz obliczmy tabelę . Z definicji, jeśli nie dostaniemy konfliktów, gramatyka to .$LL(1)$$LL(1)$

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

Ponieważ nie ma konfliktów, gramatyka to .$LL(1)$

Teraz tabela . Po pierwsze, automat .$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 \\ $$

And then the $SLR(1)$ table (I assume $S$ can be followed by anything).

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

There are conflicts in state 0, so the grammar is not $SLR(1)$. Note that if $LALR(1)$ was used instead, then both conflicts would be resolved correctly: in state 0 on lookahead $a$ $LALR(1)$ would take R3 and on lookahead $b$ it would take R4.

This gives rise to the interesting question whether there is a grammar that is $LL(1)$ but not $LALR(1)$, which is the case but not easy to find an example of.

If you are not asked, you don't have to construct the LL(1) table to prove that it is an LL(1) grammar. You just compute the FIRST/FOLLOW sets as Alex did:

$\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}$

And then, by definition an LL(1) grammar has to:

1. If $A \Rightarrow a$ and $A \Rightarrow b$ are two different rules of the grammar, then it should be that $\operatorname{FIRST}(a) \cap \operatorname{FIRST}(b) = \emptyset$. Hence, the two sets haven't any common element.
2. If for any non-terminal symbol $A$ you have $Α \Rightarrow^* ε$, then it should be that $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}(A) = \emptyset$. Hence, if there is a zero production for a non-terminal symbol, then the FIRST and FOLLOW sets can't have any common element.

So, for the given grammar:

1. We have $\operatorname{FIRST}(AaAb) \cap \operatorname{FIRST}(BbBa) = \emptyset$ since $\operatorname{FIRST}(AaAb) = \{a\}$ while $\operatorname{FIRST}(BbBa) = \{b\}$ and they don't have any common elements.
2. $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}A) = \emptyset$ since $\operatorname{FIRST}(A) = \{a,b\}$ while $\operatorname{FOLLOW}(A) = \emptyset$, and now $\operatorname{FIRST}(B) \cap \operatorname{FOLLOW}(B) = \emptyset$ since $\operatorname{FIRST}(B) = \{ε\}$ while $\operatorname{FOLLOW}(B) = \{a,b\}$.

As for the SLR(1) analysis I think it is flawless!

Search for a sufficient condition which makes a grammar LL(1) (hint: look at the FIRST sets).

Search for a needed condition which all SLR(1) grammars must meet (hint: look at the FOLLOW sets).