CLASE#07: ANALIZADOR SINTÁCTICO

1

UNIVERSIDAD “GERARDO BARRIOS”

COMPILADORES E INTÉRPRETES

CICLO I – 2016

DOCENTE: ING. MARVIN OSMARO PARADA

CLASE # 07

UNIDAD 3 ANALIZADOR SINTACTICO: INTRODUCION, CONCEPTOS, CARACTERISTICAS

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 TEMATICO

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>

<factor> ::= ( <expresión> ) | <variable> | <constante>

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.

CLASE#07: ANALIZADOR SINTÁCTICO

2

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.

CLASE#07: ANALIZADOR SINTÁCTICO

3

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

CLASE#07: ANALIZADOR SINTÁCTICO

4

UNIVERSIDAD “GERARDO BARRIOS”

COMPILADORES E INTÉRPRETES

CICLO I – 2016

DOCENTE: ING. MARVIN OSMARO PARADA

LABORATORIO 2 COMPUTO II – TEÓRICO 50%

ALUMNO FIRMA

INDICACIÓN. REUNIRSE EN GRUPO DE TRES INTEGRANTES y RESPONDER A LAS SIGUIENTES

PREGUNTAS, ENTREGAR EL INFORME AL DOCENTE

1. Que es un árbol sintáctico

2. Cuál es la salida del analizar sintáctico

3. En que cosiste la gramáticas de atributos

4. Cuál es la principal tarea del analizador sintáctico

5. Que son los atributos, menciona algunos ejemplos

6. Cuál es la función principal del analizador sintáctico

7. Cuáles son los tipos de análisis sintáctico, explica cada uno

8. Como interactúa el manejo de errores en la fase de análisis sintáctico

9. Define con tus propias palabras en que consiste un analizador sintáctico

10.Cuáles suelen será los errores más comunes en la programación de esta fase