Analisis Sintactico Ascendente

Procesadores de Lenguajes
Ingeniería Técnica superior de Ingeniería Informática
Departamento de Lenguajes y Sistemas informáticos

Análisis sintáctico
Analizadores ascendentes
Javier Vélez Reyes jvelez@lsi.uned.es Departamento de Lenguajes Y Sistemas Informáticos UNED

Análisis sintáctico. Analizadores ascendentes
Objetivos

Objetivos
› › › › Comprender el análisis ascendente porreducción desplazamiento Aprender el algoritmo general de análisis ascendente Conocer la arquitectura general de un analizador sintáctico ascendente Aprender a construir analizadores ascendentes en complejidad creciente › › › › › Analizadores LR (0) Analizadores SLR Analizadores LALR Analizadores LR (1)

Entender cómo los analizadores sintácticos realizan la gestión de errores › › Entender losconflictos reducción – reducción Entender los conflictos reducción – desplazamiento

›

Entender la clasificación de gramáticas inducida en virtud de los métodos de análisis empleados

Javier Vélez Reyes jvelez@lsi.uned.es

Análisis sintáctico. Analizadores ascendentes
Índice

Índice
› › Introducción Análisis sintáctico ascendente › › › › Análisis ascendente por reducción – desplazamientoArquitectura general de análisis sintáctico ascendente Algoritmo general de análisis sintáctico ascendente

Analizadores sintácticos ascendentes › › › › Analizadores LR (0) Analizadores LR (1) Analizadores LALR Analizadores LR (1)

› ›

Gestión de errores en analizadores ascendentes Tipos de gramáticas y análisis ascendente › › Interpretación de conflictos en los tipos de analizadoresClasificación de gramáticas por tipos de analizadores

Javier Vélez Reyes jvelez@lsi.uned.es

Análisis sintáctico. Analizadores ascendentes
Índice

Índice
› Constricción de analizadores sintácticos en la práctica › › › › › › ¿Qué es Cup? ¿Cómo funciona Cup? ¿Cómo se usa Cup? Gestión de errores en Cup Desarrollo paso a paso

Bibliografía

Javier Vélez Reyes jvelez@lsi.uned.es

Análisissintáctico. Analizadores ascendentes
Introducción

¿Qué es el análisis ascendente?
El análisis sintáctico ascendente es una técnica de análisis sintáctico que intenta comprobar si una cadena x pertenece al lenguaje definido por una gramática L (G) aplicando los siguientes criterios › › › › › Partir de los elementos terminales de la frase x Escoger reglas gramaticales estratégicamente Aplicar ala inversa derivaciones por la derecha (Right Most Derivation) Procesar la cadena de izquierda a derecha Intentar alcanzar el axioma para obtener el árbol de análisis sintáctico o error R1: E ::= E + E R2: E ::= E - E R3: E ::= E * E R4: E ::= E / E R5: E ::= ( E ) R6: E ::= n

Cadena de derivación
El análisis ascendente genera una cadena de derivación por la derecha leída en sentido inversoÁrbol de análisis sintáctico
Se parte la cadena de entrada leída de izquierda a derecha y se aplican reglas a la inversa para intentar alcanzar el axioma E 
R1

n+n*n← E+n*n← E+E*n← E+E*E← E+E← E

 R6 E

+ E n
(3)

E *

R3



n R6 (2) 

E n
(5)

R6 

Javier Vélez Reyes jvelez@lsi.uned.es

Análisis sintáctico. Analizadores ascendentes
Introducción

Analizadoressintácticos ascendentes
¿Como se selecciona el siguiente no terminal a derivar? ¿Como se selecciona la regla de producción en cada paso de derivación inversa?

Analizadores descendentes Se parte del axioma y se aplica una cadena de derivaciones para construir un árbol sintáctico





LR (0) Determinan la regla que hay que aplicar sin consultar terminales a la entrada SLR Determinan laregla a aplicar consultado el primer terminal a la entrada

Analizadores deterministas Son analizadores que imponen ciertas restricciones sobre la naturaleza de los lenguajes que soportan

LALR Analizadores ascendentes Se parte de los terminales y se construye la inversa de una derivación para intentar alcanzar el axioma LR (1) LR (k)

Determinan la regla a aplicar consultando los k primeros...