¿Cómo es esta gramática LL (1)?

Esta es una pregunta del Libro del Dragón. Esta es la gramática:

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

La pregunta pregunta cómo mostrar que es LL (1) pero no SLR (1).

Para demostrar que es LL (1), intenté construir su tabla de análisis, pero obtengo múltiples producciones en una celda, lo cual es una contradicción.

Indique cómo es este LL (1) y cómo demostrarlo.

Primero, demos un número a tus producciones.

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

Calculemos el primero y sigamos primero los conjuntos. Para pequeños ejemplos como estos, usar la intuición sobre estos conjuntos es suficiente.

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

Ahora calculemos la tabla . Por definición, si no tenemos conflictos, la gramática es L L ( 1 ) .$LL(1)$$LL(1)$

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

Como no hay conflictos, la gramática es .$LL(1)$

Ahora para la tabla . Primero, el autómata 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 \\ $$

Y luego la tabla (supongo que S puede ser seguido por cualquier cosa).$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    |   |   |

Hay conflictos en el estado 0, por lo que la gramática no es . Tenga en cuenta que si se utilizara L A L R ( 1 ) , ambos conflictos se resolverían correctamente: en el estado 0 en la búsqueda anticipada a L A L R ( 1 ) tomaría R3 y en la búsqueda anticipada b tomaría R4.$SLR(1)$$LALR(1)$$a$ $LALR(1)$$b$

Esto da lugar a la interesante pregunta de si hay una gramática que es pero no L A L R ( 1 ) , que es el caso pero no es fácil encontrar un ejemplo.$LL(1)$$LALR(1)$

Si no se le pregunta, no tiene que construir la tabla LL (1) para demostrar que es una gramática LL (1). Simplemente calcula los conjuntos PRIMERO / SEGUIR como lo hizo 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}$

Y luego, por definición, una gramática LL (1) tiene que:

1. Si y A ⇒ b son dos reglas diferentes de la gramática, entonces debería ser que PRIMERO ( a ) ∩ PRIMERO ( b ) = ∅ . Por lo tanto, los dos conjuntos no tienen ningún elemento común.$A \Rightarrow a$$A \Rightarrow b$$\operatorname{FIRST}(a) \cap \operatorname{FIRST}(b) = \emptyset$
2. Si para cualquier símbolo no terminal tiene Α ⇒ ∗ ε , entonces debería ser que PRIMERO ( A ) ∩ SEGUIR ( A ) = ∅ . Por lo tanto, si hay una producción cero para un símbolo no terminal, entonces los conjuntos FIRST y FOLLOW no pueden tener ningún elemento común.$A$$Α \Rightarrow^* ε$$\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}(A) = \emptyset$

Entonces, para la gramática dada:

1. Tenemos desde FIRST ( A a A b ) = { a } mientras FIRST ( B b B a ) = { b } y no tienen ninguno elementos comunes.$\operatorname{FIRST}(AaAb) \cap \operatorname{FIRST}(BbBa) = \emptyset$$\operatorname{FIRST}(AaAb) = \{a\}$$\operatorname{FIRST}(BbBa) = \{b\}$
2. desde FIRST ( A ) = { a , b } mientras SIGUE ( A ) = ∅ , y ahora FIRST ( B ) ∩ SIGUE ( B ) = ∅ desde FIRST ( B ) = { ε } mientras SIGUE ( B ) = $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}A) = \emptyset$$\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\}$

En cuanto al análisis SLR (1), creo que es perfecto.

Busque una condición suficiente que haga una gramática LL (1) (sugerencia: observe los PRIMEROS conjuntos).

Busque una condición necesaria que todas las gramáticas SLR (1) deben cumplir (pista: mire los conjuntos SIGUIENTE).