Analisis sintactico descendente
Escuela Técnica Superior de Ingeniería Informática
Procesadores de Lenguajes
Tema 3
Parte II
Análisis Sintáctico Descendente
Javier Vélez Reyes
jvelez@lsi.uned.es
Javier Vélez Reyes jvelez@lsi.uned.es
Objetivos del Tema
Entender la técnica de análisis descendente
Presentar los analizadores con retroceso
Aprenderel cálculo de los conjuntos de predicción
Presentar las condiciones LL(1)
Aprender la modificación de gramáticas no LL(1)
Presentar los analizadores predictivos
Recursivos
Dirigidos por tabla
1
Javier Vélez Reyes jvelez@lsi.uned.es
Índice General
Introducción
Analizador con retroceso
Técnica de análisis predictivo
Analizadores predictivos
Javier VélezReyes jvelez@lsi.uned.es
Introducción
Análisis sintáctico descendente
Partir del axioma de la gramática
Escoger reglas gramaticales
Hacer derivaciones por la izquierda
Procesar la entrada de izquierda a derecha
Obtener el árbol de análisis sintáctico o error
R1.
R2.
R3.
R4.
E := E + E
E := E * E
E := n
E := (E)
E (R1)1
E (R3)2 +
E (R2)3
E (R3)4 *2+3*5
2
3
E (R3)5
5
2
Javier Vélez Reyes jvelez@lsi.uned.es
Índice General
Introducción
Analizador con retroceso
Técnica de análisis predictivo
Analizadores predictivos
Javier Vélez Reyes jvelez@lsi.uned.es
Analizador con retroceso
Analizador con retroceso
Usa retroceso para resolver la incertidumbre
Sencillo de implementar
R1. S := c A d
SR2. A := a b
Muy ineficiente
R3. A := a
S
S
c Ad
R1
R2
S
c Ad
c Ad
a
cad
cad
cad
S
c Ad
a
b
cad
R3
b
S
S
c Ad
c Ad
a
a
cad
cad
9
3
Javier Vélez Reyes jvelez@lsi.uned.es
Índice General
Introducción
Analizador con retroceso
Técnica de análisis predictivo
Cálculo de los conjuntos de predicción
Condiciones LL(1)
Modificación de gramáticas no LL(1)
Conjunto Primero
Conjunto Siguiente
Conjunto Predicción
Eliminación de ambigüedad
Factorización por la izquierda
Eliminación de la recursividad
Analizadores predictivos
Javier Vélez Reyes jvelez@lsi.uned.es
Técnicas de análisis predictivo
Propósito
Crear un analizadordescendente O(n)
Debe decidir qué regla aplicar según token
La gramática debe ser LL(1)
L. Análisis de izquierda a derecha
L. Derivaciones por la izquierda
1. Un token permite decidir la regla de producción
Se elimina la recursividad
4
Javier Vélez Reyes jvelez@lsi.uned.es
Conjuntos de predicción
Conjuntos de predicción
Ayudan a decidir qué reglautilizar en cada paso
Construcción
Conjunto Primero
Conjunto Siguiente
Regla
PRIM (α)
SIG (A)
PRED ( A := α ) =
SI ε є PRIM ( α ) ENTONCES = PRIM ( α ) – { ε } ∪ SIG ( A)
= PRIM ( α )
SINO
Javier Vélez Reyes jvelez@lsi.uned.es
Conjunto Primero
Definición
Si α es una forma sentencial compuesta por una
concatenación de símbolos PRIM (α) es el conjuntode
terminales (o ε) que pueden aparecer iniciando las
cadenas que pueden derivar de α
Construcción
PRIM
PRIM
PRIM
PRIM
(ε) = {ε}
(a) = {a}
(A) = ∪ PRIM (αi) Para todo A := αi
(Aα) = PRIM (A) – {ε} ∪ PRIMε (α)
5
Javier Vélez Reyes jvelez@lsi.uned.es
Conjunto Siguiente
Definición
Si A es un símbolo no terminal de la gramática SIG (A)
es el conjunto determinales (y $) que pueden aparecer
a continuación de A en alguna forma sentencial derivada
del axioma
Construcción
1.Inicialmente
SIG (A) = { }
2. Si A es el axioma
SIG (A) = SIG (A) ∪ {$}
3. Para cada regla B := αAβ
SIG (A) = SIG (A) ∪ {PRIM (β) - ε}
4. Para cada regla B := αA o B:= αAβ con ε є PRIM (β)
SIG (A) = SIG (A) ∪ SIG (B)
5. Repetir 3 y 4 hasta que no se aumentar SIG (A)...
Regístrate para leer el documento completo.