Analizador Sintáctico

El análisis sintáctico 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. Este proceso es similar a determinar la estructura de una frase en Castellano, determinando quien es el sujeto, predicado, el verbo y los complementos. 

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. El analizador sintáctico o parser 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 (operaciones). Por ejemplo el análisis sintáctico de la siguiente expresión

La estructura de la gramática anterior refleja la prioridad de los operadores, así los operadores “+” y “-” tienen la prioridad más baja, mientras que “*” y “/” tienen una prioridad superior. Se evaluaran en primer lugar las constantes, variables y expresiones entre paréntesis. Los árboles sintácticos se construyen con un conjunto de reglas conocidas como gramática, y que definen con total precisión el lenguaje fuente. Al proceso de reconocer la estructura del lenguaje fuente se conoce con el nombre de análisis sintáctico (parsing). Hay distintas clases de analizadores o reconocedores sintácticos, pero en general se clasifican en 2 grandes grupos: A.S. Ascendentes y A.S. Descendentes.

Caracteristicas 

• Lee componentes léxicos (tokens)

• Comprueba que el orden de estos corresponde a la sintaxis predeterminada

 • Genera errores en caso de que el flujo de tokens no responda a la sintaxis

 • Genera árboles de análisis sintáctico

 • Se suele conocer como “Parser”

• El análisis sintáctico desarrolla el esqueleto de toda la fase de análisis

• Utiliza el analizador léxico como una rutina dentro del análisis sintáctico ( getNextToken() )

 • Integra el análisis semántico como un conjunto de rutinas a ejecutar durante la comprobación de la sintaxis.

• Aunque el objetivo teórico es construir un árbol de análisis sintáctico, este raramente se construye como tal, sino que las rutinas semánticas integradas van generando el árbol de sintaxis abstracta.

• El análisis sintáctico se especifica mediante una gramática libre de contexto

• El análisis sintáctico se implementa mediante un autómata de pila

Analizador sintáctico ascendente: Intenta construir un árbol de análisis sintáctico, empezando desde la raíz y descendiendo hacia las hojas. Lo que es lo mismo que intentar obtener una derivación por la izquierda para una cadena de entrada, comenzando desde la raíz y creando los nodos del árbol en orden previo.

 Analizador sintáctico descendente: Intenta construir un árbol de análisis sintáctico, empezando desde las hojas (la cadena) y ascendiendo hacia la raíz. Lo que es lo mismo que intentar obtener una reducción desde una cadena hasta llegar al axioma. El analizador sintáctico tanto ascendente como descendente puede representarse de dos formas: mediante tabla de análisis sintáctico o mediante autómata de pilas.

Elminacion de re cursiva de izquierda

Una gramática es recursiva por la izquierda si tiene un no terminal A tal que existe una derivación A           Aα  para alguna cadena  α. Los métodos de análisis sintáctico descendente no pueden manejar gramáticas  recursivas por la izquierda, así que se necesita una transformación que elimine la recursión por la izquierda.

Recursión por la izquierda inmediata simple  (Eliminación de la recursividad izquierda de las producciones)

En este caso la recursión por la izquierda se presenta solo en las reglas gramaticales

A → A α | β

Donde α y β son cadenas de terminales y no terminales y  β no comienza en A. Esta regla genera todas las cadenas de la forma β, β α, β α α…Todas las cadenas comienzan con una β, seguida por     (0 o mas α). Esta regla gramatical es equivalente a la expresión regular β αⁿ

Para eliminar  la recursión por la izquierda  volvemos a escribir estas reglas gramaticales divididas en dos: una para que primero genere β y otra que genere  las repeticiones de α utilizando recursión por la derecha en vez de recursión por la izquierda:

A → β A´

A´→ α A´|є

Ejemplo Considere de nueva cuenta la regla recursiva izquierda de la gramática de expresión simple:

exp → exp opsuma term | term

La forma de esta regla es  A → A α | β, con A= exp,  α=opsuma term y β=term. Al volverla a escribir para eliminar la recursividad por la izquierda obtenemos que

exp → term exp´