PDF de programación - Procesadores de Lenguajes - Tema 3.II. Analisis Sintactico descendente

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

Escuela Técnica Superior de Ingeniería Informática

Procesadores de Lenguajes

Tema 3
Tema 3
Parte II
Parte II

Análisis Sintáctico Descendente
Análisis Sintáctico Descendente

Javier Vélez Reyes
[email protected]

Javier Vélez Reyes [email protected]

Objetivos del Tema
Objetivos del Tema

Entender la técnica de análisis descendente
(cid:132)(cid:132) Entender la técnica de análisis descendente
Presentar los analizadores con retroceso
(cid:132)(cid:132) Presentar los analizadores con retroceso
Aprender el cálculo de los conjuntos de predicción
(cid:132)(cid:132) Aprender el cálculo de los conjuntos de predicción
Presentar las condiciones LL(1)
(cid:132)(cid:132) Presentar las condiciones LL(1)
Aprender la modificación de gramáticas no LL(1)
(cid:132)(cid:132) Aprender la modificación de gramáticas no LL(1)
Presentar los analizadores predictivos
(cid:132)(cid:132) Presentar los analizadores predictivos
Recursivos
(cid:132)(cid:132) Recursivos
Dirigidos por tabla
(cid:132)(cid:132) Dirigidos por tabla

1

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Analizador con retroceso
(cid:132)(cid:132) Analizador con retroceso
Técnica de análisis predictivo
(cid:132)(cid:132) Técnica de análisis predictivo
Analizadores predictivos
(cid:132)(cid:132) Analizadores predictivos

Javier Vélez Reyes [email protected]

Introducción
Introducción

Análisis sintáctico descendente
(cid:132)(cid:132) Análisis sintáctico descendente
Partir del axioma de la gramática
(cid:132)(cid:132) Partir del axioma de la gramática
Escoger reglas gramaticales
(cid:132)(cid:132) Escoger reglas gramaticales
Hacer derivaciones por la izquierda
(cid:132)(cid:132) Hacer derivaciones por la izquierda
Procesar la entrada de izquierda a derecha
(cid:132)(cid:132) Procesar la entrada de izquierda a derecha
Obtener el árbol de análisis sintáctico o error
(cid:132)(cid:132) Obtener el árbol de análisis sintáctico o error

R1. E := E + E
R2. E := E * E
R3. E := n
R4. E := (E)

2 + 3 * 5

E (R1)1

E (R3)2

+

E (R2)3

E (R3)4

*

E (R3)5

2

3

5

2

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Analizador con retroceso
(cid:132)(cid:132) Analizador con retroceso
Técnica de análisis predictivo
(cid:132)(cid:132) Técnica de análisis predictivo
Analizadores predictivos
(cid:132)(cid:132) Analizadores predictivos

Javier Vélez Reyes [email protected]

Analizador con retroceso
Analizador con retroceso

Analizador con retroceso
(cid:132)(cid:132) Analizador con retroceso
Usa retroceso para resolver la incertidumbre
(cid:132)(cid:132) Usa retroceso para resolver la incertidumbre
Sencillo de implementar
(cid:132)(cid:132) Sencillo de implementar
Muy ineficiente
(cid:132)(cid:132) Muy ineficiente
R1

c A d

S

S

R1. S := c A d
R2. A := a b
R3. A := a

S

S

R2

c A d

c a d
S

c A d

a

b

c a d

c A d

c a d
S

R3

c A d

a

c a d

a

b

c a d
S

c A d

a

c a d

(cid:57)

3

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Analizador con retroceso
(cid:132)(cid:132) Analizador con retroceso
Técnica de análisis predictivo
(cid:132)(cid:132) Técnica de análisis predictivo
Cálculo de los conjuntos de predicción
(cid:132)(cid:132) Cálculo de los conjuntos de predicción
Conjunto Primero
(cid:132)(cid:132) Conjunto Primero
Conjunto Siguiente
(cid:132)(cid:132) Conjunto Siguiente
Conjunto Predicción
(cid:132)(cid:132) Conjunto Predicción
Condiciones LL(1)
(cid:132)(cid:132) Condiciones LL(1)
Modificación de gramáticas no LL(1)
(cid:132)(cid:132) Modificación de gramáticas no LL(1)
Eliminación de ambigüedad
(cid:132)(cid:132) Eliminación de ambigüedad
Factorización por la izquierda
(cid:132)(cid:132) Factorización por la izquierda
Eliminación de la recursividad
(cid:132)(cid:132) Eliminación de la recursividad

Analizadores predictivos
(cid:132)(cid:132) Analizadores predictivos

Javier Vélez Reyes [email protected]

Técnicas de análisis predictivo
Técnicas de análisis predictivo

Propósito
(cid:132)(cid:132) Propósito
Crear un analizador descendente O(n)
(cid:132)(cid:132) Crear un analizador descendente O(n)
Debe decidir qué regla aplicar según token
(cid:132)(cid:132) Debe decidir qué regla aplicar según token
La gramática debe ser LL(1)
(cid:132)(cid:132) La gramática debe ser LL(1)
L. Análisis de izquierda a derecha
(cid:132)(cid:132) L. Análisis de izquierda a derecha
L. Derivaciones por la izquierda
(cid:132)(cid:132) L. Derivaciones por la izquierda
1. Un token permite decidir la regla de producción
(cid:132)(cid:132) 1. Un token permite decidir la regla de producción
Se elimina la recursividad
(cid:132)(cid:132) Se elimina la recursividad

4

Javier Vélez Reyes [email protected]

Conjuntos de predicción
Conjuntos de predicción

Ayudan a decidir quéqué regla utilizar en cada paso
regla utilizar en cada paso

Conjuntos de predicción
(cid:132)(cid:132) Conjuntos de predicción
(cid:132)(cid:132) Ayudan a decidir
Construcción
(cid:132)(cid:132) Construcción
Conjunto Primero
(cid:132)(cid:132) Conjunto Primero
Conjunto Siguiente
(cid:132)(cid:132) Conjunto Siguiente
Regla
(cid:132)(cid:132) Regla

PRIM (αα))
PRIM (
SIG (A)
SIG (A)

PRED ( A := α ) =
PRED ( A := α ) =

SI ε є PRIM ( α ) ENTONCES = PRIM ( α ) – { ε } ∪ SIG ( A)
SI ε є PRIM ( α ) ENTONCES = PRIM ( α ) – { ε } ∪ SIG ( A)
SINO
SINO

= PRIM ( α )
= PRIM ( α )

Javier Vélez Reyes [email protected]

Conjunto Primero
Conjunto Primero

Definición
(cid:132)(cid:132) Definición
(cid:132)(cid:132) Si Si αα es una forma sentencial compuesta por una
es una forma sentencial compuesta por una

n de síímbolos PRIM (

concatenacióón de s
concatenaci
terminales (o εε) que pueden aparecer iniciando las
) que pueden aparecer iniciando las
terminales (o
cadenas que pueden derivar de αα
cadenas que pueden derivar de

mbolos PRIM (αα) es el conjunto de
) es el conjunto de

(cid:132)(cid:132) Construcci

Construccióónn

PRIM (ε) = {ε}
PRIM (ε) = {ε}
PRIM (a) = {a}
PRIM (a) = {a}
PRIM (A) = ∪ PRIM (αi) Para todo A := αi
PRIM (A) = ∪ PRIM (αi) Para todo A := αi
PRIM (Aα) = PRIM (A) – {ε} ∪ PRIMε (α)
PRIM (Aα) = PRIM (A) – {ε} ∪ PRIMε (α)

5

Javier Vélez Reyes [email protected]

Conjunto Siguiente
Conjunto Siguiente

Definición
(cid:132)(cid:132) Definición
Si A es un símbolo no terminal de la gramática SIG (A)
(cid:132)(cid:132) Si A es un símbolo no terminal de la gramática SIG (A)
es el conjunto de terminales (y $) que pueden aparecer
es el conjunto de terminales (y $) que pueden aparecer
a continuación de A en alguna forma sentencial derivada
a continuación de A en alguna forma sentencial derivada
del axioma
del axioma
Construccióónn
1.Inicialmente
1.Inicialmente

(cid:132)(cid:132) Construcci

SIG (A) = { }
SIG (A) = { }

2. Si A es el axioma
2. Si A es el axioma

SIG (A) = SIG (A) ∪ {$}
SIG (A) = SIG (A) ∪ {$}
3. Para cada regla B := αAβ
3. Para cada regla B := αAβ

SIG (A) = SIG (A) ∪ {PRIM (β) - ε}
SIG (A) = SIG (A) ∪ {PRIM (β) - ε}

4. Para cada regla B := αA o B:= αAβ con ε є PRIM (β)
4. Para cada regla B := αA o B:= αAβ con ε є PRIM (β)

SIG (A) = SIG (A) ∪ SIG (B)
SIG (A) = SIG (A) ∪ SIG (B)

5. Repetir 3 y 4 hasta que no se aumentar SIG (A)
5. Repetir 3 y 4 hasta que no se aumentar SIG (A)

Javier Vélez Reyes [email protected]

Condiciones LL(1)
Condiciones LL(1)

Determinación de la condición LL(1)
(cid:132)(cid:132) Determinación de la condición LL(1)
Se determina a partir de los conjuntos de predicción
(cid:132)(cid:132) Se determina a partir de los conjuntos de predicción
Permite distinguir siempre la regla a aplicar
(cid:132)(cid:132) Permite distinguir siempre la regla a aplicar

Los conjuntos de predicción de las reglas de
Los conjuntos de predicción de las reglas de
producción de cada no terminal deben ser disjuntos
producción de cada no terminal deben ser disjuntos
entre sí
entre sí

Ejemplo
(cid:132)(cid:132) Ejemplo

A := a b B
A := B b
B := b
B := c

{a}
{b, c}
{b}
{c}

6

Javier Vélez Reyes [email protected]

Modificación de gramáticas no LL(1)
Modificación de gramáticas no LL(1)
Condiciones necesarias
(cid:132)(cid:132) Condiciones
No ambigua
(cid:132)(cid:132) No ambigua
Factorizada por la izquierda
(cid:132)(cid:132) Factorizada por la izquierda
No recursiva a izquierdas
(cid:132)(cid:132) No recursiva a izquierdas

necesarias para

para serser LL(1)
LL(1)

E := E + E
E := E - E
E := E * E
E := E / E
E := n
E := (E)

E := TE’
E’ := +TE’ | -TE’ | ε
T := FT’
T’ := *FT’ | /FT’ | ε
F := n | ( E )

Javier Vélez Reyes [email protected]

Factorización por la izquierda
Factorización por la izquierda

Objetivo
(cid:132)(cid:132) Objetivo
Se trata de rescribir las producciones de la gramática
(cid:132)(cid:132) Se trata de rescribir las producciones de la gramática
con igual comienzo para retrasar la decisión hasta haber
con igual comienzo para retrasar la decisión hasta haber
visto lo suficiente de la entrada como para elegir la
visto lo suficiente de la entrada como para elegir la
opción correcta
opción correcta

Procedimiento
(cid:132)(cid:132) Procedimiento

A := αβ1 |αβ2 | … | αβn | δi
A := αβ1 |αβ2 | … | αβn | δi

A := αA’ | δi
A := αA’ | δi
A’ := β1 | β2 | … | βn
A’ := β1 | β2 | … | βn

7

Javier Vélez Reyes [email protected]

Eliminación de la recursividad
Eliminación de la recursividad

Tipos de recursividad
(cid:132)(cid:132) Tipos de recursividad
Directa. Una gramática G es recursiva si tiene alguna
(cid:132)(cid:132) Directa. Una gramática G es recursiva si tiene alguna
regla de producción que sea recursiva por la izquierda
regla de producción que sea recursiva por la izquierda

A := Aα
A := Aα

Indirecta. Si, a partir de una forma sentencial que
(cid:132)(cid:132) Indirecta. Si, a partir de una forma sentencial que
empieza por un no terminal se puede derivar una nueva
empi