Construcción De Tablas De Análisis Sintáctico

Construcción de tablas de análisis sintáctico

.

1) Dada la siguiente gramatica:

Lexp → Atom | List
Atom → num| id
List → (Lexp-seq)
Lexp-seq → Lexp, Lexp-seq | Lexp
a) Factorizar la gramática. (NOTA: la gramática no se factoriza porque es recursiva, lo que se hace es quitarle la recursividad.)

Lexp → Atom | List
Atom → num| id
List → (Lexp-seq)
Lexp-seq→ Lexp Lexp-seq’
Lexp-seq’ → , Lexp-seq Lexp-seq’ | ε

b) Construir el conjunto PRIMEROS Y SIGUIENTES para los no-terminales de la gramática resultante.

1. Conjuntos PRIMEROS

PRIMERO (Lexp) = { num, id, ( }
PRIMERO (Atom) = { num, id }
PRIMERO (List) = { ( }
PRIMERO (Lexp-seq) = { num, id, ( }
PRIMERO (Lexp-seq’) = { , , ε }

2. Conjuntos SIGUIENTES

SIGUIENTE(Lexp) = { $ }
SIGUIENTE (Lexp) = SIGUIENTE (Lexp) ∪ { )} = { $, )}
SIGUIENTE (Atom) = SIGUIENTE (Lexp) = { $, ) }
SIGUIENTE (List) = PRIMERO (Atom) ∪ SIGUIENTE (Atom) = { num, id, $, ) }
SIGUIENTE (Lexp-seq) = SIGUIENTE (List) = {num, id, $, ) }
SIGUIENTE (Lexp-seq’) = PRIMERO (Lexp-seq) ∪ SIGUIENTE (Lexp-seq) = {num, id, (, $, ) }

c) Construir la tabla de análisis sintáctico.

| Num |Id | ( | ) | , | $ |
Lexp | Lexp → Atom | Lexp → Atom | Lexp → List | | | |
Atom | Atom → num | Atom → id | | | | |
List | | | List → (Lexp-seq) | | | |
Lexp-seq | Lexp-seq → Lexp Lexp-seq’ | Lexp-seq → Lexp Lexp-seq’ | Lexp-seq → Lexp Lexp-seq’ | | | |
Lexp-seq’ | Lexp-seq’ → ε | Lexp-seq’ → ε | Lexp-seq’ → ε | Lexp-seq’ → ε | Lexp-seq’ → , Lexp-seqLexp-seq’ | Lexp-seq’ → ε |

d) Mostrar el Contenido de la pila, la entrada y las producciones aplicadas para la entrada: (a, (b, (2)), (c))

PILA | ENTRADA | SALIDA | ECUACION |
$ Lexp-seq | ( a , ( b , ( 2 ) ), ( c ) ) $ | | M[Lexp-seq, ( ] |
$ Lexp-seq’ Lexp | ( a , ( b , ( 2 ) ), ( c ) ) $ | Lexp-seq → Lexp Lexp-seq’ | M[Lexp, ( ] |
$ Lexp-seq’ List | ( a , ( b , ( 2 ) ), ( c) ) $ | Lexp → List | M[List, ( ] |
$ Lexp-seq’ ) Lexp-seq ( | ( a , ( b , ( 2 ) ), ( c ) ) $ | List → (Lexp-seq) | M[ (, ( ] |
$ Lexp-seq’ ) Lexp-seq | a , ( b , ( 2 ) ), ( c ) ) $ | | M[Lexp-seq, a ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp | a , ( b , ( 2 ) ), ( c ) ) $ | Lexp-seq → Lexp Lexp-seq’ | M[Lexp, a ] |
$ Lexp-seq’ ) Lexp-seq’ Atom | a , ( b , ( 2 ) ), ( c ) ) $ | Lexp →Atom | M[Atom, a ] |
$ Lexp-seq’ ) Lexp-seq’ id | a , ( b , ( 2 ) ), ( c ) ) $ | Atom → id | M[id, a ] |
$ Lexp-seq’ ) Lexp-seq’ | , ( b , ( 2 ) ), ( c ) ) $ | | M[Lexp-seq’, , ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq , | , ( b , ( 2 ) ), ( c ) ) $ | Lexp-seq’ → , Lexp-seq Lexp-seq’ | M[, , ,] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq | ( b , ( 2 ) ), ( c ) ) $ | | M[Lexp-seq, ( ]|
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ Lexp | ( b , ( 2 ) ), ( c ) ) $ | Lexp-seq → Lexp Lexp-seq’ | M[Lexp, ( ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ List | ( b , ( 2 ) ), ( c ) ) $ | Lexp → List | M[List, ( ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq ( | ( b , ( 2 ) ), ( c ) ) $ | List → (Lexp-seq) | M[(, ( ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq |b , ( 2 ) ), ( c ) ) $ | | M[Lexp-seq, b ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq’ Lexp | b , ( 2 ) ), ( c ) ) $ | Lexp-seq → Lexp Lexp-seq’ | M[Lexp, b ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq’ Atom | b , ( 2 ) ), ( c ) ) $ | Lexp → Atom | M[Atom, b ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq’ id | b , ( 2 ) ), ( c ) ) $ | Atom → id| M[id, b ] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq’ | , ( 2 ) ), ( c ) ) $ | | M[Lexp-seq, ,] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq’ Lexp-seq , | , ( 2 ) ), ( c ) ) $ | Lexp-seq’ → , Lexp-seq Lexp-seq’ | M[ , , ,] |
$ Lexp-seq’ ) Lexp-seq’ Lexp-seq’ ) Lexp-seq’ Lexp-seq | ( 2 ) ), ( c ) ) $ | | M[Lexp seq, ( ] |
$ Lexp-seq’ )...