Procesadores de Lenguaje - II26 - Universitat Jaume I

Tema 3: Análisis sintáctico - Ejercicios de análisis LL(1) y RLL(1)

Solución del ejercicio A3

Producciones <A> -> Anulable() Primeros() Siguientes(<A>)

1. <X> -> a <Y> <Z> no a $ d e

2. <X> -> b no b

3. <X> -> sí

4. <Y> -> c <X> no c $ d e

5. <Y> -> <X> sí a b

6. <Z> -> d no d $ d e f

7. <Z> -> e <Z> f no e

8. <Z> -> sí

Tabla de análisis $ a b c d e f

<X> 3 1 2
3 3

<Y> 5 5 5 4 5 5

<Z> 8

6, 8 7, 8 8

Producciones `<A> ->`	Anulable()	Primeros()	Siguientes(`<A>`)
1. `<X> -> a <Y> <Z>`	no	`a`	`$ d e`
2. `<X> -> b`	no	`b`
3. `<X> ->`	sí
4. `<Y> -> c <X>`	no	`c`	`$ d e`
5. `<Y> -> <X>`	sí	`a b`
6. `<Z> -> d`	no	`d`	`$ d e f`
7. `<Z> -> e <Z> f`	no	`e`
8. `<Z> ->`	sí

Tabla de análisis	`$`	`a`	`b`	`c`	`d`	`e`	`f`
`<X>`	3	1	2		3	3
`<Y>`	5	5	5	4	5	5
`<Z>`	8				6, 8	7, 8	8

Podemos observar que hay dos conflictos que indican que la gramática no es LL(1): al analizar <Z>, si el símbolo de anticipación fuese d no sabríamos si aplicar la producción 6 o la producción 8, y si el símbolo de anticipación fuese e no sabríamos si aplicar la producción 7 o la producción 8.

Observa también que las partes derechas anulables no son solamente aquellas que valen , son también aquellas que se pueden reescribir (directa o indirectamente) como , y eso se puede acabar reflejando en la tabla de análisis.