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

12

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

SAaAbBbBa
B εAε
Bε

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.

Vinayak Garg
fuente
66
No estoy muy familiarizado con las gramáticas, pero parece que el lenguaje de esta gramática es finito. L={ab,ba}
Nejc
@Nejc: ¡Sí, parece que sí!
Vinayak Garg

Respuestas:

11

Primero, demos un número a tus producciones.

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

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

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

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

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)

Alex ten Brink
fuente
¡Gracias! Había construido el Primero y Seguir correctamente, pero cometí un error al construir la tabla.
Vinayak Garg
10

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:

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

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.AaAbFIRST(a)FIRST(b)=
  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ΑεFIRST(A)FOLLOW(A)=

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.FIRST(AaAb)FIRST(BbBa)=FIRST(AaAb)={a}FIRST(BbBa)={b}
  2. desde FIRST ( A ) = { a , b } mientras SIGUE ( A ) = , y ahora FIRST ( B ) SIGUE ( B ) = desde FIRST ( B ) = { ε } mientras SIGUE ( B ) = {FIRST(A)FOLLOWA)=FIRST(A)={a,b}FOLLOW(A)=PRIMERO(si)SEGUIR(si)=PRIMERO(si)={ε} .SEGUIR(si)={una,si}

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

Ethan
fuente
¡Bienvenidos! Para mejorar esta respuesta, ¿por qué no aplica lo que dice a la gramática en cuestión?
Raphael
¡¡Feliz de estar aqui!! Respondí tu solicitud y creo que di una explicación completa.
Ethan
¡Gracias! Tenga en cuenta que podemos usar LaTeX aquí, ya que edité para sus matemáticas.
Raphael
¡Wow gracias! Esta es una gran explicación. Pero creo que hay algún error en la aplicación. ¿No es primero (A) = {epsilon}? Creo que intercambiaste PRIMERO y SIGUE.
Vinayak Garg
FIRST (A) es de hecho épsilon, pero dado que está buscando calcular el PRIMER conjunto del miembro derecho completo, A -> ε solo muestra que tenemos una producción vacía y el primer símbolo de terminal que ve (y, por lo tanto, el PRIMER conjunto) símbolo de terminal a. Espero que esto haya ayudado!
Ethan
0

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

Un programador
fuente