Analisis Sintactico Predictivo
-
Upload
leonel-morales -
Category
Education
-
view
3.409 -
download
0
description
Transcript of Analisis Sintactico Predictivo
![Page 1: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/1.jpg)
Análisis Sintáctico Predictivo
Optimización del Análisis Sintáctico Descendente
Leonel Morales Dí[email protected]
Copyright 2008 by Leonel Morales Díaz – Ingeniería Simple.Derechos reservados
Disponible en: http://www.ingenieriasimple.com/compiladores
![Page 2: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/2.jpg)
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
![Page 3: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/3.jpg)
Ejemplo
• Gramática de tipos en Pascal
Tipo -> Simple | ^id |array [ Simple ] of Tipo
Simple -> integer | char |núm puntopunto núm
![Page 4: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/4.jpg)
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
![Page 5: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/5.jpg)
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
![Page 6: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/6.jpg)
Optimizaciones
• Probar con todas las producciones– Recursividad puede tomar tiempo
• Escoger la más acertada anticipadamente
• Implementación de Primero(β)
![Page 7: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/7.jpg)
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)
![Page 8: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/8.jpg)
• 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(β)
![Page 9: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/9.jpg)
Casos especiales
• ¿Primero(β) = Primero(δ)?• ¿Primero(β) = nil?
![Page 10: Analisis Sintactico Predictivo](https://reader036.fdocumento.com/reader036/viewer/2022082809/557b9dc6d8b42aa0758b50ff/html5/thumbnails/10.jpg)
Gramática infijo corregida
Expr -> Término RestoResto -> + Expr | - Expr | nilTérmino -> 0Término -> 1Término -> 2....Término -> 9