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 A2

Apartado A2.1

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

1. <H> -> d <L> d no d $

2. <L> -> <X> <Y> c <L> no a b c d

3. <L> -> sí

4. <X> -> a no a b c

5. <X> -> sí

6. <Y> -> b no b c

7. <Y> -> sí

Tabla de análisis $ a b c d

<H>

1

<L>
2 2 2 3

<X>
4 5 5

<Y>

6 7

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

Tabla de análisis	`a`	`b`	`c`	`d`
`<H>`				1
`<L>`	2	2	2	3
`<X>`	4	5	5
`<Y>`		6	7

Podemos observar que no hay conflictos en la tabla y por tanto la gramática es LL(1).

Apartado A2.2

Un analizador LL(1), aplicando la información de la tabla de análisis anterior, obtendría la siguiente derivación canónica por la izquierda, y concluiría por tanto que la cadena pertenece al lenguaje generado por la gramática:

<H> => d <L> d
=> d <X> <Y> c <L> d
=> d a <Y> c <L> d
=> d a b c <L> d
=> d a b c <X> <Y> c <L> d
=> d a b c <Y> c <L> d
=> d a b c c <L> d
=> d a b c c <X> <Y> c <L> d
=> d a b c c <Y> c <L> d
=> d a b c c b c <L> d
=> d a b c c b c d

En este ejercicio se puede apreciar la importancia de tener en cuenta los siguientes, no sólo los primeros, cuando hay partes derechas anulables.

Como ejercicio adicional, dibuja el correspondiente árbol de derivación, y encuentra y analiza ejemplos de cadenas que no pertenezcan al lenguaje generado por la gramática (solución en clase).