Análisis Sintáctico Predictivo

Optimización del Análisis Sintáctico Descendente

Leonel Morales Díazleonel@ingenieriasimple.com

Copyright 2008 by Leonel Morales Díaz – Ingeniería Simple.Derechos reservados

Disponible en: http://www.ingenieriasimple.com/compiladores

Analizador descendente

• Algoritmo1. Seleccione una producción y construya

los hijos2. Encuentre el siguiente nodo (no

terminal)3. Si hay otro nodo aplicar recursivamente4. Si no hay más nodos

1. Si la cadena coincide entonces ACEPTAR2. Si no coincide, probar recursivamente

Ejemplo

• Gramática de tipos en Pascal

Tipo -> Simple | ^id |array [ Simple ] of Tipo

Simple -> integer | char |núm puntopunto núm

Descendente (símbolo inicial)Function Tipo()

Resu = Simple()If Not Resu Then

Resu = Match(“^”) And Match(“id”)If Not Resu Then

Resu = Match(“Array”) And Match(“[”)And Simple() And Match(“]”)And Match(“of”) And Tipo()

EndEndTipo = Resu

End Function

Descendente (nodo)Function Simple()

Resu = Match(“integer”)If Not Resu Then

Resu = Match(“char”)If Not Resu Then

Resu = Match(“núm”)And Match(“puntopunto”)And Match(“núm”)

EndEndSimple = Resu

End Function

Optimizaciones

• Probar con todas las producciones– Recursividad puede tomar tiempo

• Escoger la más acertada anticipadamente

• Implementación de Primero(β)

Primero(β)

• Dice cuál es el primer lexema– De cada lado derecho

• Ejemplo:Tipo -> Simple | ^id |

array [ Simple ] of Tipo• Primero(Simple)• Primero(^id)• Primero(array [ Simple ] of Tipo)

• Antes de usar cualquier producción– Chequear primer símbolo– Compararlo contra Primero(β)– Encontrar la producción correcta

• Análisis Sintáctico Predictivo

Uso de Primero(β)

Casos especiales

• ¿Primero(β) = Primero(δ)?• ¿Primero(β) = nil?

Gramática infijo corregida

Expr -> Término RestoResto -> + Expr | - Expr | nilTérmino -> 0Término -> 1Término -> 2....Término -> 9