Analisis sintactico descendente

Páginas: 5 (1119 palabras) Publicado: 15 de diciembre de 2014
UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA
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)...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • ANALISIS SINTACTICO
  • Analisis Sintactico
  • analisis sintactico
  • Análisis Sintáctico
  • Analisis sintactico
  • Análisis Sintáctico
  • Análisis sintáctico
  • Analisis Sintactico

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS