Presentacion

Universidad de Oviedo - Departamento de Informática

Escuela Politécnica Superior de Ingeniería

ANÁLISIS SINTÁCTICO EN PROCESADORES DE LENGUAJE

TEMA 5
ANÁLISIS SINTÁCTICO DESCENDENTE

Página 1

Objetivos

• Conocer el análisis descendente con / sin retroceso
• Estudiar la técnica de análisis descendente
• Establecer las condiciones LL(1)
• Transformar gramáticas que no cumplenla condición LL(1)
• Construir analizadores predictivos
• Tratar los errores sintácticos

Página 2

Contenido
• Introducción
• El problema del retroceso
• Análisis sintáctico descendente con retroceso
• Análisis sintáctico descendente sin retroceso
• Construcción de analizadores sintácticos descendentes
• Tratamiento de errores sintácticos.
Página 3

Introducción

Clasificaciónmétodos análisis sintáctico
A. Descendentes
No Direccionales

Algoritmo de Unger

A. Ascendentes
Algoritmo CYK

No deterministas

Direccionales

Predice / Concuerda
1º Profundidad
1º Anchura

Desplaza / Reduce
1º Profundidad
1º Anchura

Deterministas
Predice / Concuerda
Gramática LL(k) - LL(1)

Desplaza / Reduce
Gramática LR(k)
LR(0), SLR(1), LALR(1)
Página 4Introducción

A. Sintáctico Descendente: Características
Los analizadores sintácticos descendentes son llamados predictivos y
orientados hacia un fin, debido a la forma en que trabajan y construyen el
árbol sintáctico.
Construyen el árbol sintáctico de la sentencia a reconocer de una forma
descendente, comenzando por el símbolo inicial o raíz, hasta llegar a los
símbolos terminales que forman lasentencia.
Los algoritmos de análisis descendente deben de cumplir al menos dos
condiciones: saber en todo momento dónde se encuentra dentro del árbol
sintáctico y debe poder elegir la regla de producción que aplicará.
Página 5

Introducción

A. Sintáctico Descendente: Características
Los compiladores dirigidos por sintaxis, en la forma de análisis descendente
recursivo fue propuestapor Lucas (1961), para describir un compilador
simplificado de ALGOL 60 mediante un conjunto de subrutinas recursivas.
Problema: La elegancia y comodidad de la escritura de compiladores
dirigidos por sintaxis fue pagada en tiempo de compilación por el usuario.
El análisis sintáctico descendente sin retroceso, por medio del uso de
gramáticas LL(1), obtenidas por Foster (1965) y Knuth (1967).Generalizadas
posteriormente por Lewis, Rosenkrantz y Stearns en 1969, dando lugar a las
gramáticas LL(k).
Página 6

El problema del retroceso

Análisis Sintáctico con retroceso
El problema se presenta cuando a partir del nodo raíz, el analizador
sintáctico no elige las producciones adecuadas para alcanzar la
sentencia a reconocer.
Se tienen que deshacer las producciones aplicadas hastaencontrar otras
producciones alternativas, volviendo a tener que reconstruir parte del
árbol sintáctico (backtracking) .
El retroceso puede afectar a otros módulos del compilador tales como
tabla de símbolos, código generado, etc. teniendo que deshacerse
también los procesos desarrollados en estos módulos.
Página 7

El problema del retroceso

Análisis Sintáctico con retroceso: EjemploVN={, , }
VT={module, d, p, ;, end}
S=

Las reglas de producción:
::= module ;
end
::= d | d;
::= p | p;

Analizar la cadena de entrada: module d ; d ; p ; p end
Página 8

El problema del retroceso

Análisis Sintáctico con retroceso: Ejemplo
1. Se parte del símbolo inicial


2. Aplicando la primera regla de producción de la gramática se obtiene


module



;end

3. Aplicando las derivaciones más a la izquierda, se tiene que:


module


d

;

end

p

Página 9

El problema del retroceso

Análisis Sintáctico con retroceso: Ejemplo
Se deriva con la segunda alternativa


module



;

d

p

;

end



Se debe volver atrás


module


d

;

;



end

p

d

Página 10

El problema del retroceso...