Compiladores e interpretes: Clase 7

Clase # 07

Analizador sintáctico: introducción, conceptos, características

Objetivos

Complementar conceptos teóricos del análisis Léxico y Sintáctico.

Estudiar el código fuente de un programa prototipo de análisis Léxico y Sintáctico desarrollado.

Desarrollo temático

La mayor parte de este tema está dedicada a los métodos de análisis sintáctico de uso típico en compiladores. Primero se introducen los conceptos básicos, después las técnicas adecuadas para la aplicación manual. Además como los programas pueden contener errores sintácticos, los métodos de análisis sintáctico se pueden ampliar para que se recuperen de los errores sintácticos más frecuentes.

¿QUÉ ES EL ANALIZADOR SINTÁCTICO?

Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce.

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.

En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico.

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:

(A+B)*(C+D)

Con las reglas de la gramática que se presenta a continuación dará lugar al árbol sintáctico EJEMPLO

<expresión> ::= <término> <más términos>

<más términos>::= +<término> <más términos>| - <término> <más términos> | <vacío>

<término> ::= <factor> <más factores>

<más factores>::= * <factor> <más factores>|/ <factor> <más factores> | <vacío>

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).

La principal tarea del analizador sintáctico no es comprobar que la sintaxis del programa fuente sea correcta, sino construir una representación interna de ese programa y en el caso en que sea un programa incorrecto, dar un mensaje de error.

EL ANALIZADOR SINTÁCTICO (ASN) comprueba que el orden en que el analizador léxico le va entregando los tokens es válido. Si esto es así significará que la sucesión de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje del código fuente.

La forma más habitual de representar la sintaxis de un programa es el árbol de análisis sintáctico, y lo que hacen los analizadores sintácticos es construir una derivación por la izquierda o por la derecha del programa fuente, que en realidad son dos recorridos determinados del árbol de análisis sintáctico. A partir de ese recorrido el analizador sintáctico debe construir una representación intermedia de ese programa fuente: un árbol sintáctico abstracto o bien un programa en un lenguaje intermedio; por este motivo, es muy importante que la gramática esté bien diseñada, e incluso es frecuente rediseñar la gramática original para facilitar la tarea de obtener la representación intermedia mediante un analizador sintáctico concreto.

El ASN constituye el esqueleto principal del compilador. Habitualmente el analizador léxico se implementa como una rutina dentro del sintáctico, al que devuelve el siguiente token que encuentre en el buffer de entrada cada vez que éste se lo pide. Así mismo, gran parte del resto de etapas de un programa traductor están integradas de una u otra forma en el analizador sintáctico.

LAS PRINCIPALES FUNCIONES SON:

Identificar cada tipo de instrucción y sus componentes.

– Completar la Tabla de Símbolo s.

– Realizar comprobaciones estáticas:

• Se realizan durante la compilación del programa.

• Ejemplos: comp. de tipos, unicidad de etiquetas e identificadores, etc.

– Realizar comprobaciones dinámicas:

• Aquellas que el compilador incorpora al programa traducido.

• Hacen referencia a aspectos que sólo pueden ser conocidos en tiempo de ejecución

• Dependientes del estado de la máquina en la ejecución o del propio programa.

– Validar las declaraciones de identificadores: en muchos lenguajes no se puede usar una variable si no ha sido declarada con anterioridad.

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.

TIPOS DE ANÁLISIS SINTÁCTICOS

Desde el punto de vista de la teoría de Análisis Sintáctico, hay dos estrategias para construir el árbol sintáctico:

Análisis descendente: partimos de la raíz del árbol (donde estará situado el axioma o símbolo inicial de la gramática) y se van aplicando reglas por la izquierda de forma que se obtiene una derivación por la izquierda de la cadena de entrada. Para decidir qué regla aplicar, se lee un token de la entrada. Recorriendo el árbol de análisis sintáctico resultante, en profundidad de izquierda a derecha, encontraremos en las hojas del árbol los tokens que nos devuelve el Analizador Léxico (A.L.) en ese mismo orden.

Análisis ascendente: partiendo de la cadena de entrada, se construye el árbol de análisis sintáctico empezando por las hojas (donde están los tokens) y se van creando nodos intermedios hasta llegar a la raíz (hasta el símbolo inicial), construyendo así el árbol de abajo a arriba. El recorrido del árbol se hará desde las hojas hasta la raíz. El orden en el que se van encontrando las producciones corresponde a la inversa de una derivación por la derecha.

Las dos estrategias recorren la cadena de entrada de izquierda a derecha una sola vez, y necesitan (para que el análisis sea eficiente) que la gramática no sea ambigua.

Para ello, el analizador sintáctico (A.S.) comprueba que el orden en que el analizador léxico le va entregando los tokens es válido. Si esto es así significará que la sucesión de símbolos que representan dichos tokens puede ser generada por la gramática correspondiente al lenguaje del código fuente.

MANEJO DE ERRORES SINTÁCTICOS

Si un compilador tuviera que procesar sólo programas correctos, su diseño e implantación se simplificarían mucho. Pero los programadores a menudo escriben programas incorrectos, y un buen compilador debería ayudar al programador a identificar y localizar errores. Es más, considerar desde el principio el manejo de errores puede simplificar la estructura de un compilador y mejorar su respuesta a los errores.

Los errores en la programación pueden ser de los siguientes tipos:

• Léxicos, producidos al escribir mal un identificador, una palabra clave o un operador.

• Sintácticos, por una expresión aritmética o paréntesis no equilibrados.

• Semánticos, como un operador aplicado a un operando incompatible.

• Lógicos, puede ser una llamada infinitamente recursiva.

El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores.

Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos:

• Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localización.

• Recuperarse del error, para poder seguir examinando la entrada.

• No ralentizar significativamente la compilación.

Un buen compilador debe hacerse siempre teniendo también en mente los errores que se pueden producir; con ello se consigue:

• Simplificar la estructura del compilador.

• Mejorar la respuesta ante los errores.

Tenemos varias estrategias para corregir errores, una vez detectados:

• Ignorar el problema (Panic mode ): Consiste en ignorar el resto de la entrada hasta llegar a una condición de seguridad. Una condición tal se produce cuando nos encontramos un token especial (por ejemplo un ‘;’o un ‘END’).A partir de este punto se sigue analizando normalmente.

• Recuperación a nivel de frase: Intenta recuperar el error una vez descubierto. En el caso anterior, por ejemplo, podría haber sido lo suficientemente inteligente como para insertar el token ‘;’. Hay que tener cuidado con este método, pues puede dar lugar a recuperaciones infinitas.

GRAMÁTICAS DE ATRIBUTOS. Una gramática de atributos es una gramática libre de contexto cuyos símbolos pueden tener asociados atributos y las producciones pueden tener asociadas reglas de evaluación de los atributos. En la creación de compiladores se utilizan ecuaciones de atributos o reglas semánticas como método para expresar la relación entre el cálculo de los atributos y las reglas del lenguaje. Cada producción (regla sintáctica) tiene asociada una acción semántica que se aplica cuando se realiza una reducción en el análisis sintáctico ascendente.

Atributo: propiedad de una construcción de un lenguaje. Pueden variar mucho en cuanto a información que contienen o tiempo que tardan en determinarse durante la traducción/ejecución. Cada símbolo (terminal o no terminal) puede tener asociado un número finito de atributos. Ejemplos de atributos:

– Tipo de una variable

– Valor de una expresión

– Ubicación en memoria de una variable

– Código objeto de un procedimiento

– Número de dígitos significativos en un número