Compiladores: Analizador Sintáctico
El análizador sintactico (AS) recibe una serie de secuencias de tokens desde el analizador léxico (AL) y ha de comprobar si ese orden es correcto. Tiene que informar y repararse de los errores sintácticos que ocurren frecuentemente pero no solucionarlos. La salida suele ser un árbol sintáctico. Realiza otras tareas para recoger la informacion sobre tokens y la tabla de simbolos, realizar el analisis semántico y generar codigo intermedio.
La mayoría de errores son sintácticos y se pueden solucionar muy facilmente, pero siempre han de seguir el mismo patrón:
Informar con claridad y exactitud.
Recuperarse con rapidez (generalmente con modo pánico).
No retrasar el procesamiento de programas correctos.
GRAMÁTICA LIBRE DE CONTEXTO Y ARBOL DE DERIVACION.
El AS se basa en una gramatica que se define como una serie de reglas que derivan finalmente en una serie de nodos terminales (o símbolos de la gramatica). Al final se genera un arbol de derivación segun si tomamos la mano izquierda o la derecha.
E-> E+E
E-> E*E
E-> -E
E-> (E)
E-> id
Donde podriamos representar -(id+id) como una serie de normas: E -> -E -> -(E -> -(E+E) -> -(id+E) -> -(id+id).
Una GLC puede ser ambigua si hay mas de un arbol de derivaciónd istinto o si una sentencia por la mano izquierda y la derecha es diferente. Decimos además que la derivacion acaba en una forma sentencial segun si tomamos primero los simbolos mas a la izquierda o mas a la derecha.
El pivote se utiliza generalmente en un análisis descendente (mano derecha), donde tomamos el simbolo no terminal mas a la derecha que haya y aplicmaos reglas con él hasta que desaparezca.
S => zABz => zAbBbz => zAbbbz => zaAabbbz => zaaabbbz.
En el siguiente ejemplo puede verse como además el pivote puede no ser unico en una misma forma sentencial.
Con el analizador sintáctico necesitamos el uso de automatas con pila pues el AS recibe una gramatica libre de contexto (GLC). Donde un automata con pila para un simbolo de la entrada, con un simbolo en el tope de la pila puede pasar a una serie de estados. El automata podrá terminar correctamente o bien en un estado final o bien agotando la entrada segun el modelo que se considere.
Suponiendo un automata con pila con la siguiente gramatica podriamos llegar a comprobar la cadena a+a*a.
(q,λ,S) -> (q,λ,S+A) -> (q,λ,A+A) -> (q,λ,B+A) -> (q,λ,a+A) -> (q,λ,+A) -> (q,λ,A) -> (q,λ,A+B) -> (q,λ,a+B) -> (q,λ,+B) -> (q,λ,B) -> (q,λ,a) -> (q,λ,λ)
Hay muchas otras combinaciones pero no verifican dicha cadena y por eso mismo, porque se hacen calculos paralelos no merece la pena usarlos para simular. Además hay otros problemas segun hagamos una derivacion por la izquierda o por la derecha, por ejemplo con la siguiente gramatica, el calculo a+a*a se realiza ambigüamente:
Aplicaremos la regla para nuestra gramatica: suma, resta, division empiezan por asociatividad izquierda, el resto de operadores por la derecha.
En cuanto a problemas con la ambiguedad el caso mas importante será la sentencia if-else. Los lenguajes son sensibles al contexto y por tanto no podremos representar todos los lenguajes con este analizar sintáctico.
ANALISIS ASCENDENTE Y DESCENDENTE
El análisis descendente parte del simbolo inicial (raiz) y hace todas las operaciones que puede con el simbolo no terminal mas a la izquierda, seguidamente pasara al segundo mas a la izquierda y así sucesivamente. Al final llegará a todos los nodos hoja (simbolos terminales) de la gramatica.
El análisis ascendente hace lo opuesto. Partiendo de los nodos hoja (simbolos terminales) se intenta construir hacia arriba el arbol hasta llegar al simbolo inicial (raiz) de la gramatica.
Los metodos ascendentes y descendentes suelen ser generales y los mas eficientes son:
LL (análisis descendente): Devuelve un conjunto de dereivaciones por la izquierda.
LR (análisis ascendente): Devuelve un conjunto de derivaciones por la derecha.
ALGORITMOS DE LA TRANSFORMACION DE GRAMÁTICAS
Para utilizar una gramática propia, primero tenemos que asegurarnos que es una gramática λ-libre, luego se quitan los ciclos (S->A y A->S), luego eliminamos las variables improductivas (aquellas que no llevan a simbolos terminales) y los simbolos inaccesibles (simbolos no terminales a los que no puedo llegar nunca) y tendría una gramatica propia.
Con una gramática propia podemos eliminar la recursividad por la izquierda, lo que nos devuelve una gramatica no recursiva (algo que neceistamos pues los bucles infinitos son muy malos). Aparte podríamos hacer la factorización que no es necesaria pero suele aliviar problemas.
ELIMINACION DE LA RECURSIVIDAD INMEDIATA IZQUIERDA
La recursividad inmediata sucede cuando un simbolo no terminal se descompone en él mismo y otra cosa mas, asi que podrian hacerse bucles infinitos sobre sí mismo:
La recursividad: E -> E+T -> E+T+T -> ...
Comprobar que es una gramatica al menos λ-libre.
Analizar cada símbolo y ver si tiene recursividad.
Si tiene tendremos dos tipos de variables α (aquellos simbolos que acompañan al no-terminal que provoca la recursividad) y β (cualquier otro numero que no provoque recursividad).
El recursivo ahora será cada una de las variables β ó cada una de las variables β concatenadas con un estado K'.
El nuevo estado K' tiene de nuevo cada una de las variables α ó cada una de las variables α concatenadas con el estado K'.
E-> E+T | T
(α1=+T)(β1=T)
E-> T | TE'
E'-> +T | +TE'
ELIMINACION DE LA RECURSIVIDAD IZQUIERDA
La recursividad izquierda es la recursividad inmediata más la que se produce al intentar solucionar la inmediata. Las variables se ordenan con un valor creciente y hay que evitar que se produzcan transiciones a estados de menor valor. Se divide en varios pasos:
Ordenar todos los simbolos no terminales.
Para i=1 hasta n: Eliminar la recursividad inmediata izquierda.
Para i=1 hasta i: Fijandonos en el siguiente, si hay recursividad en las anteriores se soluciona.
Eliminar recursividad inmediata izquierda.
Reglas que transiten de i=2 a i<2 (T->E)
No existen, paso abortado.
Eliminar recursividad inmediata izquierda.
Reglas que transiten de i=3 a i<3 (F->E)
F = a | Ea -> F = a | Ta | TE'a
Reglas que transiten de i=3 a i<3 (F->T)
F = a | Fa | FT'a | FE'a | F'E'a | FT'E'a
Eliminar recursividad inmediata izquierda.
F' = a | T'a | E'a | T'E'a | aF' | T'aF' | E'aF' | T'E'aF'
La factorizacion izquierda reside en coger la parte diferente en un simbolo no terminal y sustituirlo por un simbolo nuevo que contenga las diferencias. Como ya hemos visto no es necesario que sea λ-libre por lo que puede hacerse en cada momento.
Si recibo id, ¿espero un parentesis o no?
En el siguiente ejemplo veremos como si usamos una gramatica que no es propia (lambda-libre, sin simbolos innecesarios y sin ciclos) el algoritmo de eliminación de la recursividad izquierda no funciona. Nuestro ejemplo es una gramatica con ciclos:
A -> B|a
B -> C|b
C -> A|c
Eliminacion de la recursividad inmediata en A (A->A_)
No tiene.
Combinaciones de i=2 que generen recursion (B->A)
No tiene
Eliminacion de la recursividad inmediata en B (B->B_)
No tiene
Combinaciones de i=3 que generen recursion (C->A)
C = B|a|c
Combinaciones de i=3 que generen recursion (C->B)
C = C|b|a|c
Eliminacion de la recursividad inmediata en C (C->C_)
C = b|a|c|bC'|aC'|cC'
C'= C' //ERROR.
El metodo LL es un analisis descendente de derivaciones izquierdas. Que se aplica sobre autómatas con pilas. Ya vimos como se derivaba en un automata con pila, sin embargo volveremos a verlo para el problema de la indeterminacion de caminos.
Supongamos una gramatica que verifique la cadena 'cabd' con las siguientes reglas de produccion:
Automata: un solo estado q, que se verifica con la cadena vacía. Tiene una serie de funciones de transiciones δ, y el simbolo de la pila es el inicial de la gramatica S.
M={{q},{a,b,c,d},{a,b,c,d,A,S},δ,q,S,λ}
Las funciones de transición serían:
(q,cabd,S) -R.1-> (q,cabd,cAd) -R.6-> (q,abd,Ad) -R.4-> (q,abd,abd) -R.4-> (q,bd,bd) -R.5-> (q,d,d) -R.7-> (q,λ,λ)
Pero podriamos haber tomado otras decisiones. El metodo LL busca hacer un solo camino que no cometa errores, por lo que tiene que tener la capacidad de saber mirando lo que hay en la pila, lo que hay en la entrada y las reglas que tiene, cual ha de coger. Por lo que nunca ha de poder dudar entre dos o mas opciones.
En nuestro ejemplo la regla A->ab|a es la que nos permite tomar varios caminos, pero, ¿que pasa si sacamos factor comun?
Dado el simbolo de la entrada, lo que hay en la pila y un unico siguiente token podemos tener la LL(1) donde solo hay una eleccion posible. Aunque haga la eliminacion de la recursividad por la izquierda, la factorización y elimine la ambigüedad NO ES SEGURO que genere un lenguaje LL(1).
El conjunto primero(x) se define con las reglas:
Si x es un simbolo terminal, es él mismo: primero(a) -> a.
Si x es λ entonces se añade a primero(x).
Si x deriva en algo como (y1y2y3...) su primero será primero(y1) y si este puede ser λ en algun momento, entonces será primero(y2) y asi hasta que alguno no sea λ.
Calculo de primero para la siguiente gramática libre de contexto
El conjunto siguiente(x) solo se calcula para los no terminales. Son todos los siguientes tokens que me permitirian escoger entre un camino y otro. De forma pre-definida, para el primer simbolo no terminal $ (marcador de final) pertenece siempre.
Si una regla de produccion encontramos una lambda, NO se añade, se hace el primero del termino que lo invoca sin lambda.
El siguinte de una regla de produccion es el ultimo terminal, o, si es un no-terminal, las reglas donde E aparezca a la derecha y tomamos el símbolo que tenga a su derecha, terminal o no.
TABLA DE ANALISIS CON PREDICT
Para realizar una tabla de análisis necesitamos la funcion predict, esta consiste en una matriz de simbolos terminales y simbolos no terminales y su construccion es la siguiente:
Numeramos las reglas: 1(E->TE'), 2(E'->+TE), 3(E'->λ)...
Aplicamos Primero(regla1), Primero(regla2)...
Rellenamos la tabla con los predicts, donde en caso de toparnos con un lambda, invocamos al siguiente del simbolo no-terminal sobre el que estamos:
Predict(1)=primero(TE') = Primero(T) = Primero(F) = {(,id}
Predict(2)=primero(+TE') = {+}
Predict(3)=primero(λ) -> Siguiente(E')={$,)}
Predict(4)=primero(FT') = {(,id
Predict(5)=primero(*FT') = {*}
Predict(6)=primero(λ) -> Siguiente(T')={),$,+}
Predict(7)=primero((E)) -> {(}
Predict(8)=primero(id) -> {id}
