UNIDAD III.- Analizador sintáctico.

3.1.-Función del análisis sintáctico.

El análisis sintáctico tiene como función principal generar un árbol de análisis sintáctico a partir de los componentes léxicos obtenidos en la etapa anterior.

El análisis sintáctico (en inglés parser) es un análisis a nivel de sentencias, y es mucho más complejo que el análisis léxico. Su función es tomar el programa fuente en forma de tokens, que recibe del analizador léxico y determinar la estructura de las sentencias del programa.

El análisis sintáctico agrupa a los tokens en clases sintácticas (denominadas no terminales en la definición de la gramática), tales como expresiones, procedimientos, etc., y obtiene un árbol sintáctico (u otra estructura equivalente) en la cual las hojas son los tokens y cualquier nodo, que no sea una hoja, representa un tipo de clase sintáctica.

         

Tipos de analizadores sintácticos.

Hay distintas clases de analizadores o reconocedores sintácticos, en general se clasifican en dos grandes grupos: analizadores sintácticos ascendentes y analizadores sintácticos descendentes.

Análisis sintáctico descendente: construyen el árbol sintáctico a partir del símbolo inicial de la gramática, hasta llegar a los distintos tokens, que constituyen la sentencia a analizar. Es decir, se parte del símbolo inicial de la gramática y se van aplicando las distintas producciones hasta llegar a formar la sentencia.  El orden de derivación es importante, siempre se deriva primero el no terminal situado más a la izquierda según se mira el árbol (derivaciones más a la izquierda).

Los principales problemas que se plantean en el análisis sintáctico descendente son dos: el retroceso (en inglés backtracking) y la recursividad a izquierdas.

Análisis sintáctico con retroceso: el retroceso, se produce cuando se eligen mal las producciones para alcanzar la sentencia a analizar, y debe de darse marcha atrás en el proceso de análisis, para elegir otra alternativa. El retroceso se repite hasta que se ha elegido la alternativa correcta; evidentemente esto ralentiza enormemente el proceso de análisis.

Análisis sintáctico LL: son usados para evitar  el retroceso y  la recursividad a izquierda, se deriva de que en general se elige el criterio de tomar siempre en primera opción la alternativa más a la izquierda.  Para ello, las gramáticas deben de cumplir unas determinadas propiedades, dando lugar a una clasificación de las gramáticas. Los lenguajes de programación que se pueden describir mediante uno de estos tipos de gramáticas, llamadas LL (Libres de contexto)(k), aquí  se realiza el análisis descendente determinista, por medio del reconocimiento de la cadena de entrada de izquierda a derecha (Left to right) y que va tomando las derivaciones más a la izquierda con sólo mirar los k tokens situados a continuación de donde se halla.

Análisis sintáctico ascendente: construyen el árbol sintáctico a partir de las hojas, paso a paso hasta llegar a la raíz. Es decir parten de los distintos tokens de la sentencia a analizar, y por medio de reducciones llegan al símbolo inicial de la gramática. Se llaman reducciones, para indicar que se efectúan en sentido contrario a las producciones de la gramática.

Análisis ascendente con retroceso: El principal problema que se plantea en el análisis ascendente es el del retroceso, que se traduce en la elección de un pivote para realizar la reducción.

Análisis sintáctico LR: Para evitar el problema del retroceso,  se definieron distintos tipos de gramáticas entre las cuales las más utilizadas son las LR (k). Los analizadores sintácticos ascendentes que reconocen lenguajes descritos por gramáticas LR (k), toman sus decisiones en función de los k tokens inspeccionados por delante  de cada vez en la cadena de entrada, tomados de izquierda a derecha, realizándose el análisis por derivaciones más a la derecha en sentido inverso . Las gramáticas LR (k) describen la mayor parte de los lenguajes libres de contexto, y son mucho menos restrictivas que las gramáticas LL (k).

Análisis sintáctico por precedencia de operadores: se utilizan para una pequeña clase de operadores y sus gramáticas, las cuales  tienen la propiedad de que ningún lado derecho de las producciones es vacío ni tienen 2 terminales adyacentes.

3.2.- Gramáticas independientes de contexto.

También llamadas gramáticas libres de contexto, según la jerarquía de Chomsky, es un tipo de gramática formal que  generalmente engloba a los lenguajes de programación y cuyas normas de producción son:

                Exp.àx

Donde: Exp es un símbolo no terminal, x es una cadena de terminales y/o no terminales. El término independiente del contexto se refiere al hecho de que el no terminal Exp puede siempre ser sustituido por x sin tener en cuenta el contexto en el que ocurra.

Una gramática de este tipo, consta de 4 elementos básicos:

Símbolos terminales: elementos que no generan nada, son los símbolos con los que puede terminar una cadena o producción.

No terminales: elementos del lado izquierdo de una producción, antes de la flecha "->"

Producciones: sentencias que se escriben en la gramática, especifican las reglas para de la gramática para obtener un resultado, cada producción consta de un no terminal seguido de una flecha y una cadena de terminales y no terminales.

Símbolo inicial: primer elemento de la gramática, es un no terminal.

3.3.- Escritura de una gramática.

Toda construcción que se pueda describir mediante una expresión regular también se puede describir por medio de una gramática, por lo tanto todo conjunto regular es un lenguaje independiente de contexto.

Las reglas de sintaxis de un lenguaje a menudo son bastante sencillas, y para describirlas no se necesita una notación tan poderosa como las gramáticas, por ello se utilizan reglas de sintaxis de gramáticas para que se proporcione una notación más concisa y más fácil de entender para los componentes léxicos y al mismo tiempo separar la estructura sintáctica de un lenguaje en partes léxicas y no léxicas proporciona una forma conveniente de modular la etapa inicial de un compilador en dos componentes de tamaño razonable y además describir estructuras anidadas, estructuras de control, etc.

3.4.- Gramáticas ambiguas.

Una gramática es ambigua si permite construir dos o más árboles de derivación distintos para  la misma cadena. Por lo tanto, para demostrar que una gramática es ambigua lo único que se necesita es encontrar una cadena que tenga más de un árbol de derivación.

Una gramática en la cual, para toda cadena generada w, todas las derivaciones de w tienen el mismo árbol de derivación es no ambigua.

En algunos casos, dada una gramática ambigua, se puede encontrar otra gramática que produzca el mismo lenguaje pero que no sea ambigua.

Si todas las gramáticas independientes del contexto para un lenguaje son ambiguas, se dice que el lenguaje es un lenguaje independiente del contexto inherentemente ambiguo.