Métodos Formales de descripción semantica

Universidad Autónoma de Yucatán

Facultad de matemáticas

Teoría de Lenguajes de programación.

Tarea 1: Analizadores Léxicos y Sintácticos














Técnicas de análisis sintáctico
El análisis sintáctico se puede considerar como una función que toma como entrada la secuencia de componentes léxicos producida por el análisis léxico y produce como salida el árbolsintáctico. En la realidad, el análisis sintáctico hace una petición al análisis léxico del componente léxico siguiente en la entrada (los símbolos terminales) conforme lo va necesitando en el proceso de análisis, conforme se mueve a lo largo de la gramática.
Dependiendo de la forma en la que se construyen los árboles de análisis sintáctico los métodos se clasifican en descendentes y ascendentes.

i.Método de análisis sintáctico descendente.

El análisis sintáctico descendente 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:
Parte del axioma inicial.
Va efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia.
Escogereglas gramaticales estratégicamente.
Obtienen el árbol de análisis sintáctico o en su defecto el error.
En cada paso del proceso de derivación de la cadena de entrada se realiza una predicción de la posible producción a aplicar y se comprueba si existe una concordancia entre el símbolo actual en la entrada con el primer terminal que se puede generar a partir de esa regla de producción, si existeesta concordancia se avanza en la entrada y en el árbol de derivación, en caso contrario se vuelve hacia atrás y se elige una nueva regla de derivación.
Parten del símbolo de inicio de la gramática que se coloca en la raíz y se va construyendo el árbol desde arriba hacia abajo hasta las hojas, eligiendo la derivación que da lugar a una concordancia con la cadena de entrada. Se basa en la idea depredice una derivación y establece una concordancia con el símbolo de la entrada (predict/match). El análisis sintáctico descendente corresponde con un recorrido prefijo del árbol de análisis sintáctico (primero expandimos el nodo que visitamos y luego procesamos los hijos).
samos los hijos).
El método descendente puede ser de tres tipos diferentes con retroceso, con funciones recursivas y degramáticas LL(1).
a) Con retroceso.
En el análisis sintáctico con retroceso se van probando uno por una todas las reglas candidatas a ser aplicadas para construir el arbol de analisis sintáctico. Cuando una de las reglas seleccionadas falla se retrocede y se prueba con la regla siguiente.

El análisis sintáctico descendente con retroceso intenta encontrar entre las producciones de lagramática la derivación por la izquierda del símbolo inicial para una cadena de entrada.

Ejemplo:

Analizar la cadena de entrada “cad” dada la gramática siguiente:

S → c A d
A → ab│a

“cad”, se toma la primera producción






cad”, se toma la segunda producción.
siguiente hoja del árbol A → cabd







“cad” se compara con la siguiente hoja del árboletiquetada con “b”. Como no concuerda, se indica el error y se vuelve a A para ver si hay otra alternativa no intentada.






“cad”, se toma la siguiente alternativa que comienza por a.
siguiente hoja del árbol A, → cad






“cad”, coincide d con d → análisis exitoso








Forma de implementación en algún Lenguaje de Programación
procedure factor;
begin
casetoken of
(: match ( “(“);
exp;
match (“)”);
num: match (num);
else error
endCase
end
procedure match(expecToken)
begin
if token=expecTok then
getToken;
else
error
end

b) Con funciones recursivas

Para dar soporte a la pila se utilizan las capacidades de recursión del lenguaje. La gramática queda expresada a través de llamadas explicitas a distintas funciones asociadas a...