Análisis sintáctico: Análisis descendente por tabla
Introducción
¡Hola!
¡Qué emoción volvernos a encontrar! Espero que sigas desarrollando tus habilidades y conocimientos en este proceso académico, por lo tanto te doy la bienvenida a la décima clase del curso.
En esta sesión aprenderemos sobre
No se diga más. ¡Iniciemos nuestro aprendizaje!
¡Éxito!
Desarrollo del tema
Factorización Izquierda:
- Se utiliza para transformar una gramática en LL(1)
- Aunque algunas veces no es posible
Para cada símbolo no terminal A
encontrar el prefijo más largo que ocurra en dos o más partes derechas de Asi α≠ε entonces reemplazar todas las producciones de A,
- Aunque algunas veces no es posible
con
donde Z es un nuevo símbolo no terminal
Repetir hasta que no queden prefijos comunes
- Gramática que no es LL(1):
Las tres formas inician con el mismo token
- Gramática factorizada que es LL(0):
Las cuatro formas inician con diferente token
Gramática que no es LL(1):
Múltiples opciones con ID
Difícil escoger opción correcta
Gramática que es LL(1):
Siguiente token determina opción
Fácil escoger opción correcta
Conjunto FIRST:
- Dado α∈T∪NT, un símbolo terminal o no terminal
- FIRST(α)
Es el conjunto de tokens que aparecen como primer símbolo en alguna cadena derivada de α
x∈FIRST si hay una producción
para algún
∈FIRST(α) si →*ε
- Ejemplo:
Conjunto FOLLOW
- Dado
- α∈NT, un símbolo no terminal
- FOLLOW(α)
Se define como el conjunto de tokens que aparecen inmediatamente enseguida de en una regla válida
FOLLOW(S) = {EOF} donde S es el símbolo inicial
- Ejemplo:
Conjunto PREDICT:
- Es el conjunto de tokens que podrían aparecer enseguida en una cadena de tokens o forma derecha
PREDICTA(A→α) = {FIRST(α)\{ε}⋃FOLLOW(A) si ε∈FIRST (α) FIRST(α) otro caso
- Permite decidir qué forma derecha escoger con base al token de entrada
- Gramática LL(1):
program → stmt_list EOF
stmt_list → stmt stmt_list | ε
stmt → ID := expr | READ ID | WRITE expr
expr → term term_tail
term_tail → add_op term term_tail | ε
term → factor factor_tail
factor_tail → mult_op factor factor_tail | ε
factor → ‘(‘ expr ‘)’ | ID | NUMBER
add_op → ‘+’ | ‘–’
mult_op → ‘*’ | ‘/’
Calcular los conjuntos PREDICT para aplicar el método descendente predictivo
Conjuntos FIRST de Calculadora:
Conjuntos FOLLOW de Calculadora:
Conjuntos PREDICT de Calculadora:
Ejemplo: Análisis Descendente Predictivo
- Código: x ≔3
write x
- Código Tokenizado:
ID ≔NUMBER
WRITE ID
El analizador descendente predictivo por tabla utiliza un stack.
Utiliza una tabla que contiene la información de los conjuntos PREDICT
Utiliza un stack para hacer las sustituciones (derivaciones)
No requiere hacer llamadas recursivas
Construcción de Tabla de Análisis
Hay un renglón por cada símbolo no terminal A∈NT
Hay una columna por cada símbolo terminal a∈T incluyendo EOF (fin de entrada)
M(A,a) es la forma a utilizar cuando el tope del stack contenga A y el siguiente símbolo de entrada sea a
El diseño del analizador descendente por tabla es más difícil que el de un analizador descendente recursivo
Existen herramientas en línea para calcular los conjuntos PREDICT y las tablas de análisis.
Conclusión
Para recordar:
Hemos llegado al final de nuestra sesión. ¡Muchas felicidades por tu dedicación y tenacidad! Resuelve la consigna formulada para este tema; te invito a esforzarte para cumplir con este compromiso en tiempo y forma. ¡Sigue adelante con entusiasmo! Te encuentro próximamente.