• Author / Uploaded
• Guille Paredes

Citation preview

Apuntes de Compiladores I

Compiladores I Introducción Desde el punto de vista de un informático, prácticamente todas las acciones que se va a ver obligado a desarrollar en el transcurso de su carrera profesional, tendrá que ver con traductores: la programación, la creación de ficheros batch, la utilización de un intérprete de comando, etc.

Por ejemplo ¿ Que ocurre si nos dan un documento de Word que procede de una fusión con una base de datos y se quiere, a partir de él, obtener la B.D. original?. Pues se puede: a) Convertirla a texto. b) Procesarla con un traductor para quitar el texto superfluo y dar como resultado un texto en el que cada campo está entre comillas. c) El texto anterior se importa con cualquier SGBD. Otro ejemplo Creación de preprocesadores para lenguajes que no lo tienen . Por ejemplo para trabajar fácilmente con SQL en C, se puede hacer un preprocesador para meter SQL inmerso.

¿Qué es un traductor? Un traductor es un programa que traduce o convierte desde un texto o programa escrito en un lenguaje fuente hasta un texto o programa escrito en un lenguaje destino produciendo, si cabe, mensajes de error. * Los traductores engloban tanto al compilador como al intérprete. * Esquema inicial para un traductor

Programa Fuente escrito en Lenguaje Fuente

TRADUCTORES

Programa Destino escrito en Lenguaje Destino

Mensajes de Error

* Es importante destacar la velocidad en la que hoy en día se hacen. En la década de 1950, se consideró a los traductores como programas notablemente difíciles de escribir. El primer compilador de FORTRAN, por ejemplo, necesitó para su implementación 18 años de trabajo en grupo. Hasta que apareció la teoría de autómatas no se pudo acelerar ni formalizar la creación de traductores.

Tipos de Traductores Traductores del idioma : Traducen de un idioma dado a otro, por ejemplo, un traductor de Inglés a Español.. * Problemas: Inteligencia Artificial y problemas de las frases hechas: El problema de la inteligencia artificial es que tiene mucho de artificial y poco de inteligencia. Por ejemplo una vez se tradujo del Ingles al Ruso (por lo de la guerra fría) : “El espíritu es fuerte pero la carne es débil” que, de nuevo, se pasó al Inglés, y dio: “El vino está bueno pero la carne está podrida” ( En inglés spirit significa tanto espíritu como alcohol ). Falta de formalización en la especificación del significado de las palabras. Cambio del sentido de las palabras según el contexto. Ej: “Por decir aquello, se llevó una galleta”. Sólo un subconjunto del lenguaje.

Preparado por Prof. Julio Suárez

1

Apuntes de Compiladores I

Compiladores : Es aquel traductor que tiene como entrada una sentencia en lenguaje formal y como salida tiene un fichero ejecutable, es decir, hace una traducción de alto nivel a código máquina. Intérpretes : Es como un compilador, solo que la salida es una ejecución. El programa de entrada se interpreta y ejecuta a la vez. * Hay lenguajes que solo pueden ser interpretados. Ej: SNOBOL (StriNg Oriented SimBOlyc Language), LISP (LISt Processing) BASIC (Beginner’s All ...) La principal ventaja es que permiten una fácil depuración. Los inconvenientes son, en primer lugar la lentitud de ejecución , ya que si uno ejecuta a la vez que traduce no puede aplicarse mucha optimización, además si el programa entra en un bucle tiene que interpretar y ejecutar todas las veces que se realice el bucle. Otro inconveniente es que durante la ejecución, es necesario el intérprete en memoria por lo que consumen más recursos. Preprocesadores : Permiten modificar el programa fuente antes de la verdadera compilación. Hacen uso de macroinstrucciones y directivas. Ej:

//Uno.c #include “Dos.c” Void main( ) { xxxx xxxxxxx }

PREPROCESADOR

//Dos.c yyy yyyy

//Uno.c yyy yyyy void main( ) { xxxx xxxxxxx }

COMPILADOR

El preprocesador sustituye la instrucción “#include Uno.c” por el código que tiene “Uno.c”, cuando el compilador empieza se encuentra con el código ya incluido en el programa fuente. Ejemplos de algunas directivas de procesador (Clipper, C): #fi, #ifdef, #define, #ifndef, #define, #include ... que permiten compilar trozos de códigos opcionales.

Intérpretes de comandos : Lo que hace es traducir sentencias simples a llamadas a programas de una biblioteca. Son especialmente utilizados por Sistemas Operativos. Ej: El shell del DOS o del UNIX. Desencadenan la ejecución de programas que pueden estar residentes en memoria o encontrarse en disco. Por ejemplo, si ponemos en MS-DOS el comando “copy” se ejecuta la función “copy” del sistema operativo. Ensambladores y Macroensambladores : Son los pioneros de los compiladores, ya que en los albores de la informática, los programas se escribían directamente en código máquina, y los ensambladores establecen una relación biunívoca entre cada instrucción y una palabra nemotécnica, de manera que el usuario escribe los programas haciendo uso de los mnemotécnicos, y el ensamblador se encarga de traducirlo al código máquina puro. Preparado por Prof. Julio Suárez

2

Apuntes de Compiladores I

El lenguaje que utiliza se llama lenguaje ensamblador y tiene una correspondencia uno a uno entre sus instrucciones y el código máquina. Ej: Código máquina 65h.00h.01h Ensamblador LD HL, #0100 - Macroensamblador : Hay ensambladores que tienen macroinstrucciones que se suelen traducir a varias instrucciones máquinas, pues bien, un macroensamblador es un ensamblador con un preprocesador delante. Conversores fuente - fuente : Pasan un lenguaje de alto nivel a otro lenguaje de alto nivel, para conseguir mayor portabilidad. Por ejemplo en un ordenador sólo hay un compilador de PASCAL, y queremos ejecutar un programa escrito en COBOL; Un conversor COBOL –> PASCAL nos solucionaría el problema. Compilador cruzado : Es un compilador que obtiene código para ejecutar en otra máquina. Se utilizan en la fase de desarrollo de nuevos ordenadores.

Otros Conceptos Referido a Traductores Compilar-linkar-ejecuta : Estas son las tres fases básicas de un computador. Nosotros nos centraremos en la primera fase a lo largo de la asignatura. * El compilador obtiene un código objeto, junto con una tabla de símbolos.

Archivo.fue

Archivo.obj

COMPILAR

* ¿Porqué no hace directamente un fichero ejecutable? Para permitir la compilación separada, de manera que puedan fusionarse diversos ficheros OBJ en un solo ejecutable. * Un fichero OBJ es un fichero que posee una estructura de registros. Estos registros tienen longitudes diferentes. Unos de estos registros tienen código máquina, otros registros van a tener información. También incluye información sobre los objetos externos. P.ej: Variables que están en otros ficheros declaradas (EXTERN)

* El enlazador resuelve las referencias cruzadas, o externas, que pueden estar o en otros OBJ, o en librerías LIB, y se encarga de generar el ejecutable final. * Se obtiene un código reubicable, es decir, un código que en su momento se podrá ejecutar en diferentes posiciones de memoria, según la situación de la misma en el momento de la ejecución.

Pasadas de compilación : Es el número de veces que se lee el programa fuente. Hay algunas situaciones en las que, para realizar la compilación, no es suficiente con leer el fichero fuente una sola vez. Por ejemplo: ¿Que ocurre si tenemos una recursión indirecta? A llama a B B llama a A Preparado por Prof. Julio Suárez

3

Apuntes de Compiladores I

Cuando se lee el cuerpo de A, no se sabe si B va a existir o no, y no se sabe su dirección de comienzo, luego en una pasada posterior hay que rellenar estos datos. * Para solucionar el problema 1.- Hacer dos pasadas de compilación. 2.- Hacer una sola pasada de compilación utilizando la palabra reservada FORWARD. FORWARD B( ) A( ) * Algunos compiladores dan por implícito el FORWARD. Si no encuentra aquello a que se hace referencia, continúan, esperando que el linkador resuelva el problema, o emita el mensaje de error. Compilación incremental: Es aquella que compila un programa en el que si después se descubren errores, en vez de corregir el programa fuente y compilarlo por completo, se compilan solo las modificaciones. Lo ideal es que solo se recompilen aquellas partes que contenían los errores, y que el código generado se reinserte con cuidado en el OBJ generado cuando se encontraron los errores. Sin embargo esto es muy difícil.

Autocompilador: Es un compilador escrito en el mismo lenguaje que compila. * Cuando se extiende entre muchas máquinas diferentes el uso de un compilador, y éste se desea mejorar, el nuevo compilador se escribe con el antiguo, de manera que pueda ser compilado por todas esas máquinas diferentes, y dé como resultado un compilador más potente de ese mismo lenguaje.

Metacompilador: Es un programa que acepta la descripción de un lenguaje y obtiene el compilador de dicho lenguaje, es decir, acepta como entrada una gramática de un lenguaje y genera un autómata que reconoce cualquier sentencia del lenguaje . A este autómata podemos añadirle código para realizar el compilador. * Por ejemplo LEX y YACC, FLEX, Bison, JavaCC, PCCTS, MEDISE, etc. * Unos metacompiladores pueden trabajar con gramáticas de contexto libre y otros trabajan con gramática regular. Los que trabajan con gramáticas de contexto libre se dedican a reconocer la sintaxis del lenguaje y los de gramática regular trocean la entrada y la dividen en palabras. * El PCLEX es un metacompilador cuya función es generar un programa que es la parte del compilador que reconoce las palabras reservadas y otros componentes léxicos. * El PCYACC es un metacompilador cuya función es generar un programa que es la parte del compilador que indica si una sentencia del lenguaje es válida o no (análisis sintáctico). Descompilador: Pasa de un código máquina (o programa de salida) al lenguaje que lo generó ( o programa fuente). Cada descompilador trabaja con un lenguaje de alto nivel concreto. * Es una operación casi imposible, porque al código máquina casi siempre se le aplica una optimización. Por eso lo que hay suelen ser desensambladores, ya que existe una bisección entre cada instrucción máquina y cada instrucción ensamblador. * Se utilizan especialmente cuando el código máquina ha sido generado con opciones de depuración, y contiene información adicional de ayuda a la depuración de errores ( puntos de ruptura, opciones de visualización de variables, etc) También se emplea cuando el compilador original no generó código máquina puro, sino pseudocódigo (para ejecutarlo a través de un pseudointérprete)

Preparado por Prof. Julio Suárez

4

Apuntes de Compiladores I

Estructura de un Compilador Un compilador se divide en dos fases : Una parte que analiza la entrada y genera estructuras intermedias y otra parte que sintetiza la salida. En base a tales estructuras intermedias

El esquema de traductor es ahora

Fuente

ANÁLISIS

SÍNTESIS

Destino

Mensajes de Error

Básicamente los objetivos de la fase de Análisis son: * Controlar la corrección del programa fuente * Generar estructuras necesarias para comenzar la síntesis. Para llevar esto a cabo el Análisis consta de las siguientes tareas: * Análisis Lexicográfico : Divide el programa fuente en los componentes básicos: números, identificadores de usuario (variables, constantes, tipos, nombres de procedimientos,...), palabras reservadas, signos de puntuación. A cada componente le asocia la categoría a la que pertenece. * Análisis Sintáctico : Comprueba que la estructura de los componentes básicos sea correcta según ciertas reglas gramaticales. * Análisis semántico : Comprueba todo lo demás posible, es decir ,todo lo relacionado con el significado, chequeo de tipos, rangos de valores, existencia de variables, etc. * En cualquiera de los tres análisis puede haber errores.

El objetivo de la fase de síntesis consiste en: * Construir el programa objeto deseado a partir de las estructuras generadas por la fase de análisis. Para ello realiza tres tareas fundamentales. * Generación de código intermedio : Genera un código independiente de la máquina. Ventajas, es fácil hacer seudo compiladores y además facilita la optimización de código. * Generación del código máquina : Crea un fichero ‘.exe’ directamente o un fichero ‘.obj’. Aquí también se puede hacer optimización propia del microprocesador.

Preparado por Prof. Julio Suárez

5

Apuntes de Compiladores I

* Fase de optimización: La optimización puede realizarse durante las fases de generación de código intermedio y/o generación de código máquina y puede ser una fase aislada de éstas, o estar integrada con ellas. La optimización del código intermedio debe ser independiente de la máquina. El siguiente cuadro muestra un ejemplo de compilación de una sentencia de asignación, que incluye una expresión aritmética:

TRADUCCION DE UNA PROPOSICION posicion = inicial + velocidad * 60

Analizador sintáctico

id1

= * id3

temp1 = id3 * 60.0 id1 = id2 + temp1

Analizador Semántico

+ id2

Generador de Código intermedio

id1=id2 + id3 * num

Analizador léxico

60

temp1= entareal (60) temp2 = id3 * temp1 temp3 = id2 + temp2 id1 = temp3

Generador de Código

Optimizador de Código MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1

En este esquema, se supone que el compilador realiza todas las tareas listadas: La entrada fuente es la sentencia posicion = inicial + velocidad * 60 El análisis léxico separa la sentencia en sus componentes léxicos: id: es un terminal, en una gramática libre de contexto, que representa a cualquier nombre o identificador de variable de memoria, presente en el programa fuente. num: es un terminal, de la misma gramática, que representa a un número entero. La salida del análisis léxico será la entrada para el análisis sintáctico.

Con frecuencia, las fases se agrupan en una etapa inicial (Front-End) y una etapa final (Back- End). La etapa inicial comprende aquellas fases, o partes de fases que dependen principalmente del lenguaje fuente y que son en gran parte independientes de la máquina objeto. Ahí normalmente se introducen los análisis léxicos y sintácticos, la creación de la tabla de símbolos, el análisis semántico y la generación de código intermedio. La etapa inicial también puede hacer cierta optimización de código e incluye además, el manejo de errores correspondiente a cada una de esas fases. La etapa final incluye aquellas partes del compilador que dependen de la máquina objeto y, en general, esas partes no dependen del lenguaje fuente, sino sólo del lenguaje intermedio. En la etapa final, se encuentran aspectos de la fase de optimización de código además de la generación de código, junto con el manejo de errores necesario y las operaciones con la tabla de símbolos. Se ha convertido en rutina el toma r la etapa inicial de un compilador y rehacer su etapa final asociada para producir un compilador para el mismo lenguaje fuente en una máquina distinta. También resulta tentador compilar varios lenguajes distintos en el mismo lenguaje intermedio y usar una etapa final Preparado por Prof. Julio Suárez

6

Apuntes de Compiladores I

común para las distintas etapas iniciales, obteniéndose así varios compiladores para una máquina. Veamos ejemplos:

Una función esencial de un compilador es registrar los identificadores utilizados en el programa fuente y reunir información sobre los distintos atributos de cada identificador. Preparado por Prof. Julio Suárez

7

Apuntes de Compiladores I

Estos atributos pueden proporcionar información sobre la memoria asignada a un identificador, su tipo, su ámbito (la parte del programa donde tiene validez),... Tabla de símbolos : Posee información sobre los identificadores definidos por el usuario, ya sean constantes, variables o tipos. Dado que puede contener información de diversa índole, debe hacerse de forma que no sea uniforme. Hace funciones de diccionario de datos y su estructura puede ser una tabla hash, un árbol binario de búsqueda, etc.

Esquema definitivo de un traductor

Fuente

ANÁLISIS

SÍNTESIS

Mensajes de Error

Tabla de Símbolos

Destino

Ejercicios Capítulo de Introducción

Trabaja individualmente, y luego en forma grupal para completar el siguiente ejercitario. 1) Completa las definiciones de los siguientes términos Traductores:

Compiladores:

Interpretes:

2) Menciona otros tipos de traductores y haz una breve explicación de cada uno.

3) Escribe ejemplos conocidos de los traductores mencionados en el item 2 Preparado por Prof. Julio Suárez

8

Apuntes de Compiladores I

4) Explica el concepto de compilación incremental, con un programa fuente escrito en un hipotético lenguaje Alfa.

5) Grafica estructuralmente las fases de un proceso de compilación, incluyendo una breve explicación al costado de cada fase.

6) Las fases de un compilador pueden agruparse en dos etapas de construcción: a)……………………………………. y b)…………………………………… La diferencia entre ambas etapas se refiere a que la etapa de …………………….., tiene en cuenta los aspectos ………………………………………………………………………………….. …………………………....…………………………………………………………y la etapa …………………………...., se basa en los aspectos,………………………. …………………………………………………………………………………………………………………….. ……………………………………………………………………………………………………………………..

7) Si el siguiente gráfico se refiere a las etapas constructivas del compilador de un lenguaje de programación, explica su significado. Front-End 1

Front-End 2

Front-End 3

Preparado por Prof. Julio Suárez

Back-End 1

Back-End 2

9

Back-End 3

Apuntes de Compiladores I

Interpretación del gráfico:

8) Diferencia entre código fuente y código objeto.

9) En todos los casos los códigos objetos se encuentran en lenguaje de máquina. Justifica.

10) Qué utilidad ofrece la utilización de la tabla de símbolos en un proceso de compilación?

2. Análisis Léxico Este capítulo estudia la primera fase de un compilador, es decir su análisis lexicográfico, o más concisamente análisis léxico. Las técnicas utilizadas para construir analizadores léxicos también se pueden aplicar a otras áreas, como, por ejemplo, a lenguajes de consulta y sistemas de recuperación de información. En cada aplicación, el problema de fondo es la especificación y diseño de programas que ejecuten las acciones activadas por palabras que siguen ciertos patrones dentro de las cadenas a reconocer. Como la programación dirigida por patrones es de mucha utilidad, se introduce un lenguaje de patrón-acción, llamado LEX, para especificar los analizadores léxicos. En este lenguaje, los patrones se especifican por medio de expresiones regulares, y un compilador de LEX puede generar un reconocedor de las expresiones regulares mediante un autómata finito eficiente.

¿Que es un analizador léxico? Se encarga de buscar los componentes léxicos o palabras que componen el programa fuente, según unas reglas o patrones. La entrada del analizador léxico podemos definirla como una secuencia de caracteres.

Preparado por Prof. Julio Suárez

10

Apuntes de Compiladores I

El analizador léxico tiene que dividir la secuencia de caracteres en palabras con significado propio y después convertirlo a una secuencia de terminales desde el punto de vista del analizador sintáctico, que es la entrada del analizador sintáctico. El analizador léxico reconoce las palabras en función de una gramática regular de manera que sus SENTENCIAS se convierten en los elementos de entrada de fases posteriores.

2.1 Funciones del analizador léxico El analizador léxico es la primera fase de un compilador. Su principal función consiste en leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que utiliza el analizador sintáctico para hacer el análisis. Esta interacción, suele aplicarse convirtiendo al analizador léxico en una subrutina o co-rutina del analizador sintáctico. Recibida la orden “Dame el siguiente componente léxico” del analizador sintáctico, el analizador léxico lee los caracteres de entrada hasta que pueda identificar el siguiente componente léxico.

Fig. Interacción de la fase de Análisis Léxico con el Analizador Sintáctico Otras funciones: Como parte de la función de explorar el programa fuente, carácter por carácter, en esta fase también es posible: • Eliminar los comentarios del programa. • Eliminar espacios en blanco, tabuladores, retorno de carro, etc, y en general, todo aquello que carezca de significado según la sintaxis del lenguaje. • Reconocer los identificadores de usuario, números, palabras reservadas del lenguaje, ..., y tratarlos correctamente con respecto a la tabla de símbolos (solo en los casos que debe de tratar con la tabla de símbolos). • Llevar la cuenta del número de línea por la que va leyendo, por si se produce algún error, dar información sobre donde se ha producido. Preparado por Prof. Julio Suárez

11

Apuntes de Compiladores I

• Avisar de errores léxicos. Por ejemplo, si @ no pertenece al lenguaje, avisar de un error. • Puede hacer funciones de pre-procesador. 2.2 Necesidad del Analizador Léxico Un tema importante es el porqué se separan los dos análisis lexicográfico y sintáctico, en vez de realizar sólo el análisis sintáctico, del programa fuente, cosa perfectamente posible aunque no plausible. Algunas razones de esta separación son:

• Un diseño sencillo es quizás la consideración más importante. Separar el análisis léxico del análisis sintáctico a menudo permite simplificar una u otra de dichas fases. El analizador léxico nos permite simplificar el analizador sintáctico. • Se mejora la eficiencia del compilador. Un analizador léxico independiente permite construir un procesador especializado y potencialmente más eficiente para esa función. Gran parte del tiempo se consume en leer el programa fuente y dividirlo en componentes léxicos. Con técnicas especializadas de manejo de buffers para la lectura de caracteres de entrada y procesamiento de componentes léxicos se puede mejorar significativamente el rendimiento de un compilador. • Se mejora la portabilidad del compilador. Las peculiaridades del alfabeto de entrada y otras anomalías propias de los dispositivos pueden limitarse al analizador léxico. La representación de símbolos especiales o no estándares, como _ en Pascal, pueden ser aisladas en el analizador léxico. • Otra razón por la que se separan los dos análisis es para que el analizador léxico se centre en el reconocimiento de componentes básicos complejos. Por ejemplo en FORTRAN, existen el siguiente par de proposiciones: DO 5 I = 2.5 (Asignación de 2.5 a la variable DO5I) DO 5 I = 2,5 (Bucle que se repite para I = 2, 3, 4, 5) En éste lenguaje los espacios en blancos no son significativos fuera de los comentarios y de un cierto tipo de cadenas, de modo que supóngase que todos los espacios en blanco eliminables se suprimen antes de comenzar el análisis léxico. En tal caso, las proposiciones anteriores aparecerían al analizador léxico como DO5I = 2.5 DO5I = 2,5 El analizador léxico no sabe si DO es una palabra reservada o es el prefijo de una variable hasta que llegue a la coma. El analizador ha tenido que mirar más allá de la propia palabra a reconocer haciendo lo que se denomina lookahead (o prebúsqueda).

Componentes léxicos, patrones y lexemas Cuando se menciona el análisis sintáctico, los términos “componente léxico”(token), “patrón” y “lexema” se emplean con significados específicos. En el cuadro de abajo, aparecen ejemplos de dichos usos. En general, hay un conjunto de cadenas en la entrada para el cual se produce como salida el mismo componente léxico. Este conjunto de cadenas se describe mediante una regla llamada patrón asociado al componente léxico. Se dice que el patrón concuerda con cada cadena del conjunto. Un lexema es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un componente léxico. Por ejemplo, en la proposición de Pascal const pi = 3.1416; La subcadena pi es un lexema para el componente léxico “identificador”.

Componente Léxico

Lexemas de ejemplo

Descripción Informal del patrón

const

const

const palabra reservada

Preparado por Prof. Julio Suárez

12

Apuntes de Compiladores I

if

if

if palabra reservada

relación

=

< o o >=

id

pi, cuenta, D2

Letra seguida de letras y digitos

num

3.1416, 0 , 6.02E23

Cualquier constante numérica

literal

“vaciado de pila”

Cualquier carácter entre “ y “, excepto

Los componentes léxicos se tratan como símbolos terminales de la gramática del lenguaje fuente. Los lexemas para el componente léxico que concuerdan con el patrón representan cadenas de caracteres en el programa fuente que se pueden tratar juntos como una unidad léxica. En la mayoría de los lenguajes de programación, se consideran componentes léxicos las siguientes construcciones: palabras clave, operadores, identificadores, constantes, cadenas literales y signos de puntuación, como paréntesis, coma y punto y coma. Un patrón es una regla que describe el conjunto de lexemas que pueden representar a un determinado componente léxico en los programas fuente. El patrón para el componente léxico const, de la tabla anterior, es simplemente la cadena sencilla const. El patrón para el componente léxico relación es el conjunto de los seis operadores relacionales de Pascal. Para describir con precisión los patrones para componentes léxicos más complejos, como id (para identificador) y num(para número), se utilizará la notación de expresiones regulares.

2.3 Atributos de los componentes léxicos Cuando concuerda con un lexema más de un patrón, el analizador léxico debe proporcionar información adicional sobre el lexema concreto que concordó con las siguientes fases del compilador. Por ejemplo, el patrón núm concuerda con las cadenas 0 y 1, pero es indispensable que el generador de código conozca qué cadena fue realmente la que se emparejó. El analizador léxico recoge información sobre los componentes léxicos en sus atributos asociados. Los componentes léxicos influyen en las decisiones del análisis sintáctico, y los atributos, en la traducción de los componentes léxicos. Ejemplo. Los componentes léxicos y los valores de atributos asociados para la proposición de FORTRAN. E = M * C ** 2 Se escriben a continuación como una secuencia de parejas:



< id, apuntador a la entrada de la tabla de símbolos para C>

2.4 Errores léxicos

Preparado por Prof. Julio Suárez

13

Apuntes de Compiladores I

Son pocos los errores que se pueden detectar simplemente en el nivel léxico porque un analizador léxico tiene una visión muy restringida de un programa fuente. Si aparece la cadena fi por primera vez en un programa C en el contexto fi ( a == f(x))… un analizador léxico no puede distinguir si fi es un error de escritura de la palabra clave if o si es un identificador de función no declarado. Como fi es un identificador válido, el analizador léxico debe devolver el componente léxico de un identificador y dejar que alguna otra fase del compilador se ocupe de los errores. Pero, supóngase que surge una situación en la que el analizador léxico no puede continuar porque ninguno de los patrones concuerda con un prefijo de la entrada restante.

2.5 Un lenguaje para la especificación de Analizadores Lexicos Se han desarrollado algunas herramientas para construir analizadores léxicos a partir de notaciones de propósito especial basadas en expresiones regulares. Ya se ha estudiado el uso de expresiones regulares en la especificación de patrones de componentes léxicos. Antes de considerar los algoritmos para compilar expresiones regulares en programas de concordancia de patrones, se da un ejemplo de una herramienta que pueda ser utilizada por dicho algoritmo. En esta sección se describe una herramienta concreta, llamada LEX, muy utilizada en la especificación de analizadores léxicos para varios lenguajes. Esa herramienta se denomina compilador LEX, y la especificación de su entrada, lenguaje LEX.

Esquema para creación de un analizador léxico con LEX Programa fuente en LEX Prog1.l

Compilador

prog1. c

de LEX

prog1.c

Archivo de entrada

Compilador de C

prog1.exe

prog1.exe

Secuencia de componentes léxicos

Especificaciones en LEX

Un programa en LEX consta de tres partes: declaraciones %% reglas de traducción %% procedimientos auxiliares

Preparado por Prof. Julio Suárez

14

Apuntes de Compiladores I

La sección de declaraciones incluye declaraciones de variables, constantes manifiestas y definiciones regulares ( Una constante manifiesta es un identificador que se declara para representar una constante). Las reglas de traducción de un programa en LEX son proposiciones de la forma p1

{acción 1}

p2

{acción 2}

…

…

pn

{acción n}

donde pi es una expresión regular y cada acción es un fragmento de programa que describe cuál ha de ser la acción del analizador léxico cuando el patrón pi concuerda con un lexema. En LEX, las acciones se esriben en C, en general, sin embargo, pueden estar en cualquier lenguaje de implantación. La tercera sección contiene todos los procedimientos auxiliares que puedan necesitar las acciones. A veces, estos procedimientos se pueden compilar por separado y cargar con el analizador léxico. Un analizador léxico creado por LEX se comporta en sincronía con un analizador sintáctico como sigue. Cuando es activado por el analizador sintáctico, el analizador léxico comienza a leer su entrada restante, un carácter a la vez, hasta que encuentre el mayor prefijo de la entrada que concuerde con una de las expresiones regulares pi. Entonces, ejecuta acción i. Generalmente, acción i devolverá el control al analizador sintáctico. Sin embargo, si no lo hace, el analizador léxico se dispone a encontrar más lexemas, hasta que una acción hace que el control regrese al analizador sintáctico. La búsqueda repetida de lexemas hasta encontrar una instrucción return explícita permite al analizador léxico procesar espacios en blanco y comentarios de manera apropiada. El analizador léxico devuelve una única cantidad, el componente léxico, al analizador sintáctico. Para pasar un valor de atributo con la información del lexema, se puede asignar una variable global llamada yylval.

Expresiones del lex Una expresión especifica un conjunto de literales que se van a comparar. Esta contiene caracteres de texto (que coinciden con los caracteres correspondientes del literal que se está comparando) y caracteres operador (estos especifican repeticiones, selecciones, y otras características). Las letras del alfabeto y los dígitos son siempre caracteres de texto. Por lo tanto, la expresión integer coincide con el literal “integer” siempre que éste aparezca y la expresión a57d busca el literal a57d. Los caracteres operadores son: “\[]^-?.*+|()$/{}% Si cualquiera de estos caracteres se va a usar literalmente, es necesario incluirlos individualmente entre caracteres barra invertida ( \ ) o como un grupo dentro de comillas ( “ ). El operador comillas ( “ ) indica que siempre que esté incluido dentro de un par de comillas se va a tomar como un carácter de texto. Por lo tanto xyz“++” coincide con el literal xyz++ cuando aparezca. Nótese que una parte del literal puede estar entre comillas. No produce ningún efecto y es innecesario poner entre comillas caracteres de texto normal; la expresión “xyz++” es la misma que la anterior. Por lo tanto poniendo entre comillas cada carácter no alfanumérico que se está usando como carácter de texto, no es necesario memorizar la lista anterior de caracteres operador. Un carácter operador también se puede convertir en un carácter de texto poniéndole delante una barra invertida ( \ ) como en xyz\+\+ el cual, aunque menos legible, es otro equivalente de las expresiones anteriores. Preparado por Prof. Julio Suárez

15

Apuntes de Compiladores I

Este mecanismo también se puede usar para incluir un espacio en blanco dentro de una expresión; normalmente, según se explicaba anteriormente, los espacios en blanco y los tabuladores terminan una orden. Cualquier carácter en blanco que no esté contenido entre corchete tiene que ponerse entre comillas. Se reconocen varios escapes C normales con la barra invertida ( \ ): \ n newline \ t tabulador \ b backspace \ \ barra invertida Puesto que el carácter newline es ilegal en una expresión, es necesario usar n; no se requiere dar escape al carácter tabulador y el backspace. Cada carácter excepto el espacio en blanco, el tabulador y el newline y la lista anterior es siempre un carácter de texto.

Especificación de clases de caracteres. Las clases de caracteres se pueden especificar usando corchetes: [y]. La construcción [ abc ] coincide con cualquier carácter, que pueda ser una a, b, o c. Dentro de los corchetes, la mayoría de los significados de los operadores se ignoran. Sólo tres caracteres son especiales: éstos son la barra invertida ( \ ), el guión ( - ), y el signo de intercalación ( ^ ). El carácter guión indica rangos, por ejemplo [ a-z0-9_ ] indica la clase de carácter que contiene todos los caracteres en minúsculas, los dígitos, los ángulos y el subrayado. Los rangos se pueden especificar en cualquier orden. Usando el guión entre cualquier par de caracteres que ambos no sean letras mayúsculas, letras minúsculas, o dígitos, depende de la implementación y produce un mensaje de aviso. Si se desea incluir el guión en una clase de caracteres, éste deberá ser el primero o el último; por lo tanto [ -+0-9 ] coincide con todos los dígitos y los signos más y menos. En las clases de caracteres, el operador ( ^ ) debe aparecer como el primer carácter después del corchete izquierdo; esto indica que el literal resultante va a ser complementado con respecto al conjunto de caracteres del ordenador. Por lo tanto [ ^abc ] coincide con todos los caracteres excepto a, b, o c, incluyendo todos los caracteres especiales o de control; o [ ^a-zA-Z ] es cualquier carácter que no sea una letra. El carácter barra invertida ( \ ) proporciona un mecanismo de escape dentro de los corchete de clases de caracteres, de forma que éstos se pueden introducir literalmente precediéndolos con este carácter. Especificar expresiones opcionales. El operador signo de interrogación ( ? ) indica un elemento opcional de una expresión. Por lo tanto ab?c coincide o con ac o con abc. Nótese que aquí el significado del signo de interrogación difiere de su significado en la shell. Especificación de expresiones repetidas. Las repeticiones de clases se indican con los operadores asterisco ( * ) y el signo más ( + ). Por ejemplo a* coincide con cualquier número de caracteres consecutivos, incluyendo cero; mientras que a+ coincide con una o más apariciones de a. Por ejemplo, [ a-z ]+ coincide con todos los literales de letras minúsculas, y [ A-Za-z ] [A-Za-z0-9 ]* coincide con todos los literales alfanuméricos con un carácter alfabético al principio; ésta es una expresión típica para reconocer identificadores en lenguajes informáticos. Especificación de alternación y de agrupamiento. El operador barra vertical ( | ) indica alternación. Por ejemplo ( ab|cd )

Preparado por Prof. Julio Suárez

16

Apuntes de Compiladores I

coincide con ab o con cd. Nótese que los paréntesis se usan para agrupar, aunque éstos no son necesarios en el nivel exterior. Por ejemplo ab | cd hubiese sido suficiente en el ejemplo anterior. Los paréntesis se deberán usar para expresiones más complejas, tales como ( ab | cd+ )?( ef )* la cual coincide con tales literales como abefef, efefef, cdef, cddd, pero no abc, abcd, o abcdef. Especificación de sensitividad de contexto El lex reconoce una pequeña cantidad del contexto que le rodea. Los dos operadores más simples para éstos son el signo de intercalación ( ^ ) y el signo de dólar ( $ ). Si el primer carácter de una expresión es un signo ^, entonces la expresión sólo coincide al principio de la línea (después de un carácter newline, o al principio del input). Esto nunca se puede confundir con el otro significado del signo ^, complementación de las clases de caracteres, puesto que la complementación sólo se aplica dentro de corchetes. Si el último carácter es el signo de dólar, la expresión sólo coincide al final de una línea (cuando va seguido inmediatamente de un carácter newline). Este último operador es un caso especial del operador barra ( / ) , el cual indica contexto al final. La expresión ab/cd coincide con el literal ab, pero sólo si va seguido de cd. Por lo tanto ab$ es lo mismo que ab/\n Especificación de repetición de expresiones. Las llaves ( { y } ) especifican o bien repeticiones ( si éstas incluyen números) o definición de expansión (si incluyen un nombre). Por ejemplo {dígito} busca un literal predefinido llamado dígito y lo inserta en la expresión, en ese punto. Especificar definiciones. Las definiciones se dan en la primera parte del input del lex, antes de las órdenes. En contraste, a{1,5} busca de una a cinco apariciones del carácter “a”. Finalmente, un signo de tanto por ciento inicial ( % ) es especial puesto que es el separador para los segmentos fuente del lex. Especificación de acciones. Cuando una expresión coincide con un modelo de texto en el input el lex ejecuta la acción correspondiente. Esta sección describe algunas características del lex, las cuales ayudan a escribir acciones. Nótese que hay una acción por defecto, la cual consiste en copiar el input en el output. Esto se lleva a cabo en todos los literales que de otro modo no coincidirían. Por lo tanto el usuario del lex que desee absorber el input completo, sin producir ningún output, debe proporcionar órdenes para hacer que coincida todo. Cuando se está usando el lex con el yacc, ésta es la situación normal. Se puede tener en cuenta qué acciones son las que se hacen en vez de copiar el input en el output; por lo tanto, en general, una orden que simplemente copia se puede omitir. Una de las cosas más simples que se pueden hacer es ignorar el input. Especificar una sentencia nula de C; como una acción produce este resultado. La orden frecuente es [ \ t \ n] ; la cual hace que se ignoren tres caracteres de espaciado (espacio en blanco, tabulador, y newline). Otra forma fácil de evitar el escribir acciones es usar el carácter de repetición de acción, | , el cual indica que la acción de esta orden es la acción para la orden siguiente. El ejemplo previo también se podía haber escrito: “”| “\ t” | Preparado por Prof. Julio Suárez

17

Apuntes de Compiladores I

“\ n” ; con el mismo resultado, aunque en un estilo diferente. Las comillas alrededor de \ny\t no son necesarias. En acciones más complejas, a menudo se quiere conocer el texto actual que coincida con algunas expresiones como: [ a-z ] + El lex deja este texto en una matriz de caracteres externos llamada yytext. Por lo tanto, para imprimir el nombre localizado, una orden como [ a-z ] + printf (“%s” , yytext); imprime el literal de yytext. La función C printf acepta un argumento de formato y datos para imprimir; en este caso , el formato es print literal donde el signo de tanto por ciento ( % ) indica conversión de datos, y la s indica el tipo de literal, y los datos son los caracteres de yytext. Por lo tanto esto simplemente coloca el literal que ha coincidido en el output. Esta acción es tan común que se puede escribir como ECHO. Por ejemplo [ a-z ]+ ECHO; es lo mismo que el ejemplo anterior. Puesto que la acción por defecto es simplemente imprimir los caracteres que se han encontrado, uno se puede preguntar ¿Porqué especificar una orden, como ésta, la cual simplemente especifica la acción por defecto? Tales órdenes se requieren a menudo para evitar la coincidencia con algunas otras órdenes que no se desean. Por ejemplo, si hay una orden que coincide con “read”, ésta normalmente coincidirá con las apariciones de “read” contenidas en “bread” o en “readjust”; para evitar esto, una orden de la forma [ a-z ] + es necesaria. Esto se explica más ampliamente a continuación. A veces es más conveniente conocer el final de lo que se ha encontrado; aquí el lex también proporciona un total del número de caracteres que coinciden en la variable yyleng. Para contar el número de palabras y el número de caracteres en las palabras del input, será necesario escribir [ a-zA-Z ] + {words++ ; chars += yyleng;} lo cual acumula en las variables chars el número de caracteres que hay en las palabras reconocidas. Al último carácter del literal que ha coincidido se puede acceder por medio de yytext[ yyleng - 1] La acción REJECT quiere decir, “ ve y ejecuta la siguiente alternativa”. Esto hace que se ejecute cualquiera que fuese la segunda orden después de la orden en curso. La posición del puntero de input se ajusta adecuadamente. Suponga que el usuario quiere realmente contar las apariciones incluidas en “she”: she { s++; REJECT;} he { h++; REJECT;} \n| .; Estas órdenes son una forma de cambiar el ejemplo anterior para hacer justamente eso. Después de contar cada expresión, ésta se desecha; siempre que sea apropiado, la otra expresión se contará. En este ejemplo, naturalmente, el usuario podría tener en cuenta que she incluye a he, pero no viceversa, y omitir la acción REJECT en he; en otros casos, no sería posible decir qué caracteres de input estaban en ambas clases. Considere las dos órdenes

Preparado por Prof. Julio Suárez

18

Apuntes de Compiladores I

a [ bc ] + { ... ; REJECT;} a [ cd ] + { ... ; REJECT;} Si el input es ab, sólo coincide la primera orden, y en ad sólo coincide la segunda. La cadena de caracteres del input accb, cuatro caracteres coinciden con la primera orden, y después la segunda orden con tres caracteres. En contrate con esto, el input accd coincide con la segunda orden en cuatro caracteres y después la primera orden con tres. En general, REJECT es muy útil cuando el propósito de lex no es dividir el input, sino detectar todos los ejemplares de algunos items del input, y las apariciones de estos items pueden solaparse o incluirse uno dentro de otro. Suponga que se desea una tabla diagrama del input; normalmente los diagramas se solapan, es decir, la palabra “the” se considera que contiene a th y a he. Asumiendo una matriz bidimensional llamada digram que se va a incrementar, el fuente apropiado es %% [ a-z ] [ a-z ] {digram[yytext[0]] [yytext[1]] ++; REJECT; } .; \n; donde el REJECT es necesario para tomar un par de letras que comienzan en cada carácter, en vez de en un carácter si y otro no. Recuerde que REJECT no vuelve a explorar el input. En vez de esto recuerda los resultados de la exploración anterior. Esto quiere decir que si se encuentra una orden con un contexto, y se ejecuta REJECT, no debería haber usado unput para cambiar los caracteres que vienen del input. Esta es la única restricción de la habilidad de manipular el input que aún no ha sido manipulado.

Ejemplos Sencillos de Programas Lex

%{ /*PROG1.L: Cuenta cantidad de letras y números encontrados*/ #include int contal,contad; %} %% [a-zA-Z] {contal++;} [0-9] {contad++;} . ; %% main() { yylex(); printf ("Cantidad de letras :%d", contal); printf ("Cantidad de digitos :%d", contad); } %{ /*Prog2.l: imprime OK cada vez que encuentre la palabra automata*/ #include int conta; %} %% "automata " {printf ("OK\n"); conta++;} . ; %% Preparado por Prof. Julio Suárez

19

Apuntes de Compiladores I

main() { yylex(); printf ("\nCantidad de apariciones de la palaba automata :%d", conta); }

%{ /* PROG 3.l*/ /*imprime Cantidad de lineas que terminan con a o con o*/ #include int conta; %} %% (a|o)$ {conta++;} . ; %% main() { yylex(); printf ("\nCantidad de lineas que terminan con a or o :%d", conta); }

%{ /* PROG 4.l */ /*imprime Cantidad de cadenas que tienen de 2 a 3 "a" */ /* seguidas,como máximo*/ #include int conta=0; %} %% ^(a{2,3})" "|" "(a{2,3})" " {printf("Encontrado \n");conta++;} . ; %% main() { yylex(); printf ("\nCantidad de subcadenas con 2 o 3 a :%d", conta); }

%{ /* PROG5.L: imprime Cantidad de palabras con letras minúsculas y números enteros*/ #include int conta, contan; %} %% [a-z]+ {conta++;} [0-9]+ {contan++;} . ; %% main() Preparado por Prof. Julio Suárez

20

Apuntes de Compiladores I

{ yylex(); printf ("\nCantidad de cadenas :%d", conta); printf ("\nCantidad de números :%d", contan); } %{ /* PROG6.L: Reconoce tres palabras reservadas, identificadores y numeros enteros y reales*/ /* En cada caso imprime la cadena encontrada*/ /* Indentificadores : empieza con a, continua con _ y luego cualquier letra y/o digito*/ /* pudiendo esta última sección, ser vacia*/ #include %} %% if" " {printf("Reservada: %s\n", yytext);} else" " {printf("Reservada: %s\n", yytext);} endif" " {printf("Reservada: %s\n", yytext);} (w|W)(h|H)(i|I)(l|L)(e|E) {printf("Reservada: %s\n", yytext);} (e|E)(n|N)(d|D)(w|W)(h|H)(i|I)(l|L)(e|E) {printf("Reservada: %s\n", yytext);} ([0-9]+) {printf("Entero : %s\n", yytext);} ([0-9]+\.[0-9]+) {printf("Real : %s\n",yytext);} a_[a-zA-Z0-9]* {printf("Identificador:%s\n", yytext);} \n | . {;} %% main() { yylex(); } %{ /* PROG7.L*/ /* Preparado por : Prof. Julio Suárez año 2003 */ /* Reconoce tres palabras reservadas, identificadores y numeros enteros y reales*/ /* En cada caso imprime la cadena encontrada*/ /* A más de la cadena, imprimir la línea en la que se encuentra*/ /*Caracteristicas Similares al PROG6*/ #include int conta=1; %} %% if" " {printf("Reservada: %s en linea %d\n", yytext,conta);} else" " {printf("Reservada: %s en linea %d\n", yytext,conta);} endif" " {printf("Reservada: %s en linea %d\n", yytext,conta);} ([0-9]+) {printf("Entero : %s en linea %d\n", yytext,conta);} ([0-9]+\.[0-9]+) {printf("Real : %s en linea %d\n",yytext,conta);} a_[a-zA-Z0-9]* {printf("Identificador:%s en linea %d\n",yytext,conta);} \n {conta++;} . {;} %% main() { yylex(); }

Ejercitario Trabaja individualmente y luego en grupo, para completar lo siguiente : Preparado por Prof. Julio Suárez

21

Apuntes de Compiladores I

1) Describe la principal función de la fase de Análisis Léxico

2) Explica las demás funciones de del analizador Léxico

3) Por qué se afirma que el analizador léxico, es una subrutina del analizador sintáctico?

4) Con respecto al item anterior, grafica un esquema que represente este trabajo coordinado entre las dos fases mencionadas.

5) Explica tres razones por los cuales es conveniente construir un analizador léxico, para el compilador.

6) Explica que diferencia existe entre los conceptos de lexemas y componentes léxicos o tokens

Preparado por Prof. Julio Suárez

22

Apuntes de Compiladores I

7) Cómo se relacionan los componentes léxicos y los patrones?

8) Escribe un ejemplo de lexemas, patrones y componentes léxicos, para los siguientes casos: identificadores, números enteros, una palabra reservada, un operador matemático.

9) Escribe y explica dos ejemplos de errores léxicos que puede tener un programa fuente.

Los siguientes ejercicios son para desarrollarlos en máquina 10) Modifica el programa prog1.l, del material, de tal manera que informe la cantidad de símbolos encontrados, en el programa de entrada, correspondientes a cada uno de los digitos numéricos. Es decir cantidad de 0, cantidad de 1, cantidad de 2, etc.

11) Escribe programas lex para : a. Un Procesador de texto que corrija uso de mayúsculas después de un punto, cuente cantidad de líneas del texto, separe con una línea en blanco dos párrafos, y otras 3 funciones más a agregar. b. Un scanner que lea archivos de textos con números romanos y los convierta al sistema numérico decimal, ignorando los valores incorrectos. Los números romanos deben estar separados por un espacio delante y detrás, con excepción de los inician una línea o los que terminan la línea.

c.

Un scanner que lea archivos de textos con numeros binarios de longitud 8. y convierta, al sistema numérico decimal y hexadecimal. Los números binarios deben estar separados por un espacio delante y detrás, con excepción de los inician una línea o los que terminan la línea.

d. Un scanner que lea archivos de textos y corrija errores ortograficos como : n antes de b, v despues de m, uso de h intermedia en 5 palabras, 5 palabras que empiecen con h y que en

Preparado por Prof. Julio Suárez

23

Apuntes de Compiladores I

el texto no se haya escrito correctamente, puntuación de coma o punto y coma que debe escribirse a continuación de la letra de la palabra anterior, sin espacio intermedio.

12) Escribe un programa lex que busque las palabras reservadas mientras, para, y numeros reales que pueden no tener ningún digito como parte entero, pero si al menos un cero en la parte decimal, utilizando la coma como separador entre ambos. Si se detecta una cadena que no corresponda a ninguno de estos tokens, imprimir un mensaje de error, y continuar el análisis. 13) Con el uso de LEX escribe programas que generen los autómatas finitos para las siguientes expresiones regulares : 13.1 13.2

( a+ ( b* | 2) + | b) (a|b) (5* 4+ | abc) (d |e )

14) Con el uso de LEX escribe programas que generen los autómatas finitos para los lenguajes de las siguientes gramáticas regulares : G( Z ) ZàZ0 | Z1| P0 PàP0| T1| 0 Tà Z1|P1| T1| 0 | 1 VT= { 0, 1} G( P ) Pàb | a | Pa| Fb FàFb | Eb | Ea | b EàEb | a | Fa| Fb VT={a, b} 3. Análisis

sintáctico

3.1 Introducción El análisis sintáctico (parser en inglés) recibe la cadena de tokens, que le envía el analizador léxico y comprueba si con ellos se puede formar alguna sentencia válida generada por la gramática del lenguaje fuente. La sintaxis de los lenguajes de programación habitualmente se describe mediante gramáticas libres de contexto. 3.2 Funciones del analizador sintáctico • Comprobar si la cadena de tokens proporcionada por el analizador léxico puede se generada por la gramática que define el lenguaje fuente ( GLC) •

Construir el árbol de análisis sintáctico que define la estructura jerárquica de un programa y obtener la serie de derivaciones para generar la cadena de tokens. El árbol sintáctico, puede ser utilizado como representación intermedia en la generación de código.

•

Informar de los errores sintácticos de forma precisa y significativa. Deberá contener un mecanismo de recuperación de errores para continuar con el análisis.

Preparado por Prof. Julio Suárez

24

Apuntes de Compiladores I

token programa fuente

Analizador Léxico

Obtener siguiente componente léxico

Analizador Sintáctico

Árbol de análisis sintáctico

Resto del Front-End

Representación intermedia

Gestor de errores Tabla de Símbolos

Fig. Posición del analizador sintáctico en el modelo del Compilador El análisis sintáctico se puede considerar como una función que toma como entrada la secuencia de componentes léxicos (tokens) producida por el análisis léxico y produce como salida el árbol sintáctico. En realidad, el análisis sintáctico hace una petición al análisis léxico del token siguiente en la entrada (terminales) conforme lo va necesitando en el proceso de análisis. En la práctica, el analizador sintáctico también hace: • Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico). • Chequeo de tipos ( del analizador semántico). • Generar código intermedio. • Generar errores cuando se producen. En definitiva, realiza casi todas las operaciones de la compilación. Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis. 3.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. •

El manejador de errores en un analizador sintáctico tiene objetivos fáciles de establecer:

•

Debe informar de la presencia de errores con claridad y exactitud

•

Se debe recuperar de cada error con la suficiente rapidez como para detectar errores posteriores.

•

No debe retrasar de manera significativa el procesamiento de programas correctos.

3.4 Estrategias de recuperación de errores Recuperación en modo de pánico: Es el método más sencillo de implantar. 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. Preparado por Prof. Julio Suárez

25

Apuntes de Compiladores I

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. Reglas de producción adicionales para el control de errores: La gramática se puede aumentar con las reglas que reconocen los errores más comunes. En el caso anterior, se podría haber puesto algo como:

Lo cual nos da mayor control en ciertas circunstancias Corrección Global : Dada una secuencia completa de tokens a ser reconocida, si hay algún error por el que no se puede reconocer, consiste en encontrar la secuencia completa más parecida que sí se pueda reconocer. Es decir, el analizador sintáctico le pide toda la secuencia de tokens al léxico, y lo que hace es devolver lo más parecido a la cadena de entrada pero sin errores, así como el árbol que lo reconoce.

3.4 Tipo de gramática que acepta un analizador sintáctico Nosotros nos centraremos en el análisis sintáctico para lenguajes basados en gramáticas formales, ya que de otra forma se hace muy difícil la comprensión del compilador, y se pueden corregir, quizás más fácilmente, errores de muy difícil localización, como es la ambigüedad en el reconocimiento de ciertas sentencias. La gramática que acepta el analizador sintáctico es una gramática de contexto libre: Gramática : G (N, T, P, S) N = No terminales. T = Terminales. P = Reglas de Producción. S = Axioma Inicial.

Preparado por Prof. Julio Suárez

26

Apuntes de Compiladores I

3.6 Tipos de Análisis De la forma de construir el árbol sintáctico se desprenden dos tipos o clases de analizadores sintácticos. Pueden ser descendentes o ascendentes. Descendentes: Parten del axioma inicial, y van efectuando derivaciones a izquierda hasta obtener la secuencia de derivaciones que reconoce a la sentencia. Pueden ser: _ Con retroceso. _ Con recursión. _ LL(1)

Ascendentes: Parten de la sentencia de entrada, y van aplicando reglas de producción hacia atrás (desde el consecuente hasta el antecedente), hasta llegar al axioma inicial. Pueden ser: _ Con retroceso. _ LR(1)

4 Análisis Descendente Predictivo No-Recursivo 4.1 Consideraciones Previas Como se mencionó anteriormente, el método de construcción de una analizador sintáctico descendente, implica considerar que éste verificará la cadena de tokens, construyendo el árbol sintáctico en forma descendente. Por los conocimientos de la teoría de Lenguajes y Autómatas, sabemos que esto implica una secuencia de operaciones de derivaciones desde el Axioma de la gramática, raíz del árbol, hasta las hojas del mismo (sentencia). En este proceso de construcción del árbol, pueden surgir los siguientes inconvenientes: 4.2 El problema del retroceso

Preparado por Prof. Julio Suárez

27

Apuntes de Compiladores I

El primer problema que se presenta con el análisis sintáctico descendente, es que a partir del nodo raíz el analizador sintáctico no elija las producciones adecuadas para alcanzar la sentencia a reconocer. Cuando el analizador se da cuenta de que se ha equivocado de producción, se tienen que deshacer las producciones aplicadas hasta encontrar otras producciones alternativas, volviendo a tener que reconstruir parte del árbol sintáctico. A este fenómeno se le denomina retroceso, vuelta a atrás o en inglés backtracking. El proceso de retroceso puede afectar a otros módulos del compilador tales como la tabla de símbolos , código generado, interpretación, etc. teniendo que deshacerse también los procesos desarrollados en estos módulos. Ejemplo de retroceso : Sea la gramática G()

Se desea analizar la sentencia module d ; d ; p ; p end A continuación se construye el árbol sintáctico de forma descendente: 1. Se parte del símbolo inicial 2. Aplicando la primera regla de producción de la gramática se obtiene:

3. Aplicando las derivaciones más a la izquierda, se tiene que : 3.1 module es un terminal, que coincide con el primero de la cadena a reconocer 3.2 se deriva con la primera alternativa (consecuente).

Preparado por Prof. Julio Suárez

28

Apuntes de Compiladores I

Se observa que el siguiente terminal generado, tampoco coincide con el token de la cadena de entrada. Entonces el analizador sintáctico debe volver atrás, hasta encontrar la última derivación de un no terminal, y comprobar si tiene alguna alternativa más. En caso afirmativo se debe de elegir la siguiente y probar. En caso negativo, volver más atrás para probar con el no terminal anterior. Este fenómeno de vuelta atrás es el que se ha definido anteriormente como retroceso.

Llegamos a este punto, también se debe de retroceder en la cadena de entrada hasta la primera d, ya que en el proceso de vuelta atrás lo único valido que nos ha quedado del árbol ha sido el primer token module. Si se deriva nuevamente con la primera alternativa, se tiene

Preparado por Prof. Julio Suárez

29

Apuntes de Compiladores I

En este momento se tienen reconocidos los primeros 5 tokens de la cadena. Se deriva el no terminal , con la primera alternativa, y el árbol resultante se muestra a continuación. Se ha reconocido el sexto token de la cadena.

El siguiente token de la cadena es ; mientras que en el árbol se tiene end, por lo tanto habrá de volver atrás hasta el anterior no terminal, y mirar si tiene alguna otra alternativa. El último no terminal derivado es , si se deriva con su otra alternativa se tiene el árbol mostrado a continuación. Con esta derivación se ha reconocido la parte de la cadena de entrada module d ; d; p;

Se deriva con la primera alternativa y se obtiene el siguiente árbol sintáctico, reconociéndose module d; d; p; p …

El árbol sintáctico ya acepta el siguiente token de la cadena (‘end’) y por tanto la cadena completa. Puede concluirse, que los tiempos de reconocimiento de sentencias de un lenguaje pueden dispararse a causa del retroceso, por lo tanto los analizadores sintácticos deben eliminar las causa que producen el retroceso.

Preparado por Prof. Julio Suárez

30

Apuntes de Compiladores I

4.3 Análisis Descendente sin retroceso Para eliminar el retroceso en el análisis descendente, se ha de elegir correctamente la regla correspondiente a cada no terminal que se deriva. Es decir que el análisis descendente debe ser determinista, y solo se debe tomar una opción en la derivación de cada no terminal. A este tipo de análisis se le denomina LL(K). La primera L representa la forma de exploración de la sentencia : de Izquierda a Derecha ( L : left to right). La segunda L por la forma de construcción del árbol (descendente), utilizando la derivación del no terminal más a la izquierda, en cada paso (L : left most). El símbolo K representa la cantidad de tokens de la sentencia, que se tendrán en cuenta, para que el analizador sepa, predictivamente, que regla aplicar. Generalmente K = 1.

4.3.1

Gramáticas LL(1)

Las gramáticas LL(1) son un subconjunto de las gramáticas libres de contexto. Permiten un análisis descendente determinista ( sin retroceso ). Las gramáticas LL(1), como ya se mencionó, permiten construir un analizador determinista descendente con tan solo examinar en cada momento el símbolo actual de la cadena de entrada ( símbolo de preanálisis) para saber que producción aplicar. Una gramática LL(1) debe cumplir con las siguientes condiciones : Debe ser una gramática limpia ( como toda gramática formal ) No debe ser ambigua No debe tener recursividades por izquierda, en sus reglas Por lo tanto, previo a la construcción de un analizador sintáctico LL(1), deberá tratarse la gramática libre de contexto de manera que cumpla con las condiciones señaladas. 4.3.2

Gramáticas limpias

Las gramáticas de los lenguajes de programación están formadas por un conjunto de reglas, cuyo número suele ser bastante amplio, lo cual incide en la ocultación de distintos problemas que pueden producirse, tales como tener reglas que produzcan símbolos que se usen después, o que nunca se llegue a cadenas de terminales. Todo esto se puede solucionar transformando la gramática inicial “sucia” a una gramática “limpia”.

Definiciones • Símbolo muerto : es un Símbolo no terminal que no genera sentencia. •

Símbolo inaccesible: es un símbolo no terminal al que no se puede llegar por medio de producciones desde el símbolo inicial de la gramática.

•

Gramática sucia: es toda gramática que contiene símbolos muertos y/o inaccesibles.

•

Gramática limpia: es toda gramática que no contiene símbolos muertos y/o inaccesibles.

•

Símbolo vivo: es un símbolo no terminal del cual se puede derivar una sentencia. Todos los terminales son símbolos vivos. Es decir son símbolos vivos los que no son muertos

•

Símbolo accesible: es un símbolo que aparece en una cadena derivada el símbolo inicial. Es decir, aquel símbolo que no es inaccesible.

Preparado por Prof. Julio Suárez

31

Apuntes de Compiladores I

Limpieza de Gramáticas Como práctica constante, deberá procederse a la “limpieza” de las gramáticas, luego que las mismas hayan sido diseñadas. Para el efecto, existen algoritmos para la depuración. El método consiste en detectar y eliminar, en primer lugar, a los símbolos muertos de la gramática. Posteriormente, se procederá a detectar y eliminar los símbolos inaccesibles. Es importe respetar el orden en que se citaron los tipos de símbolos a eliminar, debido a que la eliminación de símbolos muertos, puede generar símbolos inaccesibles en la gramática.

4.3.2.1 Teorema de los símbolos vivos Si todos los símbolos de la parte derecha de una producción son vivos, entonces el símbolo de la parte izquierda también lo es. El procedimiento consiste en iniciar una lista de no terminales que sepamos que son símbolos vivos, y aplicando el teorema anterior para detectar otros símbolos no terminales vivos para añadirlos a la lista. Dicho de otra forma, los pasos del algoritmo son: 1. Hacer una lista de no terminales que tengan al menos una producción sin símbolos no terminales en su consecuente. 2. Dada una producción, si todos los no-terminales de la parte derecha pertenecen a la lista, entonces podemos incluir al no terminal del antecedente. 3. Cuando no se puedan incluir mas símbolos mediante la aplicación del paso 2, la lista contendrá todos los símbolos vivos, el resto serán muertos. Ejemplo Sea la gramática escrito en la BNF G()

Determinamos los símbolos muertos : Paso 1: la lista empieza con los símbolos: y Paso 2: En la lista se agregan los símbolos: y Paso 3: Como ya no se pueden añadir nuevos símbolos a la lista, ésta contiene a los símbolos vivos, y lo que no están incluidas en ella, son símbolos muertos: y

Entonces se procede a eliminar de la gramática los símbolos muertos y , y las reglas que contienen a estos símbolos, quedando el conjunto de producciones como sigue :

Preparado por Prof. Julio Suárez

32

Apuntes de Compiladores I

: := a : := b : := e | d e : := g | h

4.3. 2.2 Teorema de símbolos accesibles Si el símbolo no terminal de la parte izquierda de una producción es accesible, entonces todos los símbolos de la parte derecha también lo son. Se hace una lista de símbolos accesibles, y aplicando el teorema para detectar nuevos símbolos accesibles para añadir a la lista, hasta que no se pueden encontrar más. Los pasos a seguir son: 1. Se comienza la lista con un único no terminal, el símbolo inicial de la gramática 2. Si la parte izquierda de la producción está en la lista, entonces se incluyen en la misma a todos los no terminales que aparezcan en la parte derecha. 3. Cuando ya no se puedan incluir más símbolos mediante la aplicación del paso 2, la lista contendrá todos los símbolos accesibles, y el resto será inaccesible.

Ejemplo Sea la gramática en la BNF , G()

Determinamos los símbolos inaccesibles : Paso 1: la lista empieza con los símbolos: Paso 2: En la lista se agregan los símbolos: y Paso 3: Como ya no se pueden añadir nuevos símbolos a la lista, ésta contiene a los símbolos accesibles, y lo que no están incluidas en ella, son símbolos inaccesibles: y

Entonces se procede a eliminar de la gramática los símbolos inaccesibles y , y las reglas que contienen a estos símbolos, quedando el conjunto de producciones como sigue :

Preparado por Prof. Julio Suárez

33

Apuntes de Compiladores I

: := a | : := c d : := e | f : := g | h

4.3.3

Recursividad

Las reglas de producción de una gramática están definidas de forma que al realizar derivaciones dan lugar a recursividades. Entonces se dice que una regla de derivación es recursiva si es de la forma: Aà A a

donde A pertenece a VN y a pertenece a (VT U VN )*

Los analizadores LL(1), deben evitar las gramáticas con recursividad por izquierda, debido a que estás pueden producir ciclos infinitos en las derivaciones por izquierda. Cabe aquí repasar el algoritmo para eliminar dichas recursividades. Algoritmos para eliminación de recursividades: A lo largo del curso de Lenguajes y autómatas, hemos aprendido dos métodos distintos con idénticos efectos. En el primero que repasaremos, se presenta la generación de cadenas vacías como consecuentes de no terminales de la gramática. En el segundo método, los consecuentes equivalentes generan nuevos casos de factores comunes, que deberán ser nuevamente factorizados (sobre la factorización veremos más adelante). Método 1: Por cada caso de recursividad de la forma : Aà A a1 | A a2 | ….| Aan | ß1 | ß2 | …| ßm Donde A pertenece a VN, ai y ßj pertenecen a (VT U VN)* con la aclaración que ßj no empieza con A. Se reemplazan estas reglas por las siguientes, con C es un nuevo no terminal en la gramática : A à ß1 C | ß2 C | …| ßm C Cà a1 C | a2 C | ….| an C | e

Preparado por Prof. Julio Suárez

34

Apuntes de Compiladores I

Método 2 : Por cada caso de recursividad de la forma : Aà A a1 | A a2 | ….| Aan | ß1 | ß2 | …| ßm Donde A pertenece a VN, ai y ßj pertenecen a (VT U VN)* con la aclaración que ßj no empieza con A. Se reemplazan estas reglas por las siguientes, con C es un nuevo no terminal en la gramática : A à ß1 | ß2 | …| ßm | ß1 C | ß2 C | …| ßm C Cà a1 | a2 | ….| an | a1 C | a2 C | ….| an C Ejemplo Dada la gramática G( S ) donde VT = {(,), a, “,”} y P:{ Sà ( L ) | a Là L , S | S } La recursividad se presenta en L, entonces habrá que eliminarlo, antes de construir el analizador LL(1) Por el método 1: Là L , S | S

se convierte en su equivalente, introduciendo el no terminal A :

LàSA Aà,SA| e Entonces las reglas de la gramática equivalente, sin recursividad por izquierda quedán: Sà ( L ) | a LàSA Aà,SA| e

Por el método 2: Là L , S | S

se convierte en su equivalente, introduciendo el no terminal B :

Là S | S B Bà , S | , S B Entonces las reglas de la gramática equivalente, sin recursividad por izquierda quedán: Sà ( L ) | a Là S | S B Bà , S | , S B

Preparado por Prof. Julio Suárez

35

Apuntes de Compiladores I

4.3.4

Gramáticas Ambiguas

Una sentencia generada por una gramática es ambigua si existe más de un árbol sintáctico para ella. Una gramática es ambigua si genera al menos una sentencia ambigua, en caso contrario es no ambigua. Hay muchas gramáticas equivalentes que pueden generar el mismo lenguaje, algunas son ambiguas y otras no. Sin embargo existen ciertos lenguajes para los cuales no pueden encontrarse gramáticas no ambiguas. A tales lenguajes se les denomina ambiguos intrínsecos. La ambigüedad de una gramática es una propiedad indecidible, lo que significa que no existe ningún algoritmo que acepte una gramática y determine con certeza y en un tiempo finito si la gramática es ambigua o no. Ejemplo de gramática ambigua : G ()

Las siguientes son derivaciones posibles de la cadena 5 – c * 6

Definición de precedencia y asociatividad Una las principales formas de evitar la ambigüedad es definiendo la precedencia y asociatividad de los operadores. Lógicamente para las gramáticas con expresiones de cualquier tipo. Se define el orden de precedencia de evaluación de las expresiones y los operadores. A continuación se presenta este orden de precedencia de mayor a menor 1) ( ) , identificadores, constantes 2) - operador unario de negación 3) ^ operador de potenciación 4) * / 5) + -

Preparado por Prof. Julio Suárez

36

Apuntes de Compiladores I

La asociatividad se define de forma diferente para el operador de potenciación que para el resto de los operadores. El operador ^ es asociativo de derecha a izquierda

Mientras que el resto de los operadores binarios, son asociativos de izquierda a derecha, si hay casos de igual precedencia.

Estas dos propiedades, precedencia y asociatividad, son suficientes para convertir la gramática ambigua basada en operadores en no ambigua, es decir, que cada sentencia tenga sólo un árbol sintáctico. Para introducir las propiedades anteriores de las operaciones en la gramática se tiene que escribir otra gramática equivalente en la cual se introduce un símbolo no terminal por cada nivel de precedencia. Ejemplo Sea la gramática G( Con las reglas :

Nivel 1 de precedencia: Introducimos el no terminal , para describir una expresión indivisible, con la máxima precedencia, entonces las reglas quedan: ::= ( ) | identificador | constante Nivel 2 de precedencia: Se introduce un nuevo no terminal, , que describe el operador unario de negación y el no terminal del nivel anterior : : = - |

Nivel 3 de precedencia: Agregamos el no terminal , para representar al operador de potenciación, considerando su asociatividad; y el no terminal del nivel anterior. : : = ^ | Preparado por Prof. Julio Suárez

37

Apuntes de Compiladores I

Como el operador ^ es binario, la regla de potenciación debe incluir dos operadores. Esta consideración se tendrá igualmente con los operadores binarios siguientes. Nivel 4 de precedencia: Para este nivel, introducimos el no terminal , y representamos las operaciones de producto y división; y como en los casos anteriores, el no terminal del nivel inmediato superior. : : = * | / | Como puede verse, el nuevo no terminal aparece a la izquierda de los operadores, por la asociatividad de izquierda a derecha de los mismos.

Nivel 5 de precedencia: Para el último nivel de precedencia, se procede a utilizar el mismo no terminal de la gramática original, utilizada para representar las operaciones de este nivel. ::= + | - |

La gramática queda entonces: G() S = VT= {+, -, *, /, ^, (, ), identificador, constante} VN= {, , , , } P:{ ::= + | - | : : = * | / | : : = ^ | : : = - | ::= ( ) | identificador | constante } Siendo ésta una gramática equivalente de la anterior, pero no ambigua

4.3.5 Factorización Hay veces en las que una gramática no es recursiva por izquierda y sin embargo no es LL(1) Veamos un caso: ::= if then else | if then

Según estas producciones de , no podemos optar por una alternativa con sólo el primer token leído if. Esta situación se puede resolver usando la segunda técnica de transformación de gramáticas: la factorización. En una forma general, las reglas con factor común tienen la forma:

::= a ß | a d

donde a ,ß , d ? ( VT U VN )+

La transformación de las reglas, implicará la inserción en la gramática, de un nuevo no terminal por cada caso de factor común existente en la misma: ::= a ::= ß | d

Preparado por Prof. Julio Suárez

38

Apuntes de Compiladores I

Ejemplo del if ::= if then else | if then

Transformado a: ::= if then ::= else | e

4.4 Esquema del Analizador Descendente Predictivo no Recursivo

Entrada

X Y Pila

a

+

b

$

Programa para análisis sintáctico predictivo

SALIDA

Z $ Tabla de análisis sintáctico

El analizador descendente LL(1) utiliza una pila auxiliar para almacenar los símbolos de la gramática libre de contexto, en base al cual se construyó el analizador sintáctico. La tabla de análisis sintáctico, contiene las configuraciones de las reglas que predictivamente deberán ser utilizadas en cada paso de derivación por izquierda. La salida del análisis sintáctico, es la secuencia de reglas utilizadas en la derivación descendente ( o por izquierda).

Preparado por Prof. Julio Suárez

39

Apuntes de Compiladores I

4.4.1 Algoritmo para el análisis LL(1) La pila se carga, inicialmente con los símbolos $ y Z, donde $ indica el final de cadena de una sentencia, y Z corresponde al símbolo inicial de la gramática. El método consiste en seguir el algoritmo partiendo: •

La cadena a reconocer

•

Una pila de símbolos ( terminales y no terminales)

•

Una tabla ( M ) asociada de forma unívoca a la gramática

La cadena de entrada acabará en el símbolo $ ( como ya se explicó )

Sea X el elemento en la cima de la pila y a el terminal apuntado en la entrada. El algoritmo consiste en:

1- Si X = a = $ entonces aceptar la sentencia de entrada 2- Si X = a $ entonces Se quita X de la pila y se avanza el apuntador de entrada 3- Si X es un terminal y X a entonces rechazar la sentencia de entrada 4- Si X es un no terminal entonces consultamos la tabla de acuerdo a la siguiente indexación: M(X,a) Si M(X,a) es vacía entonces rechazar la sentencia de entrada Si M(X,a) no es vacía entonces: se quita X de la pila y se inserta el consecuente de la regla cargada en dicha posición, en orden inverso. 5- Repetir desde el paso 1

Preparado por Prof. Julio Suárez

40

Apuntes de Compiladores I

4.4.2 Construcción de la Tabla de Análisis LL(1) La tabla de análisis sintáctico LL(1), es un elemento fundamental, en el proceso de análisis descendente predictivo. Esta contiene las reglas gramaticales que serán utilizadas en cada paso de un reconocimiento sintáctico, por este método. La tabla es una matriz, donde una de sus dimensiones se indexa de acuerdo a cada no terminal de la gramática, y la otra de acuerdo a cada terminal a más del símbolo de fin de cadena ($). Para la construcción de la tabla es necesario el cálculo de los conjuntos llamados de cabecera o primero, y siguiente. Posterior a estos cálculos, se desarrolla el algoritmo de construcción de la tabla.

4.4.2.1 Función Primero o Cabecera Si a es un cadena de símbolos gramaticales, se considera PRIMERO(a) como el conjunto de terminales que inician las cadenas derivadas de a. Si a =>*e, entonces e también está en PRIMERO(a). Para calcular PRIMERO(X), para todos los símbolos gramaticales X, aplíquense las siguientes reglas, hasta que no se puedan añadir más terminales o e a ningún conjunto PRIMERO. 1. Si X es terminal, entonces PRIMERO(X) es {X}. Un solo elemento en el conjunto PRIMERO. 2. Si Xà e es una producción, entonces añádase e a PRIMERO(X). 3. Si X es un no-terminal y XàY1Y2...Yk , es una producción : ( cada Yi es un símbolo del consecuente) 3.1 Agregar a a PRIMERO(X), si a está en algún Yi y e está en todos los PRIMERO(Y1)...,PRIMERO(Yi-1), es decir en los elementos que están antes de Yi, en la parte derecha de la regla. 3.2 Si e está en PRIMERO( Yj) para j=1,2,...k, agregar e a PRIMERO(X). Si Y1 no deriva a un e, no se añade más que todo lo que esté en PRIMERO(Y1) a PRIMERO(X).

Ejemplo:

PRIMERO(A) = {d, a, c} PRIMERO(S)=PRIMERO(A) = {d, a, c} PRIMERO(B)=PRIMERO(A) U {b} = {d, a, c, b}

Preparado por Prof. Julio Suárez

41

Apuntes de Compiladores I

4.4.2.2 Función Siguiente Se define Siguiente (A), para el no Terminal A, como el conjunto de terminales a que pueden aparecer inmediatamente a la derecha de A, en alguna forma de frase. Para calcular SIGUIENTE(A), para todos los no-terminales A, aplíquense las siguientes reglas, hasta que no se puedan añadir nada más a ningún conjunto SIGUIENTE 1. Póngase $ en SIGUIENTE(S), donde S es el símbolo inicial de la gramática, y $ el indicador de fin de cadena (FDC). 2. Si hay un producción A--> aBß, entonces todo lo que esté en PRIMERO(ß), excepto e, se pone en SIGUIENTE(B) . 3. Si hay una producción A-->aB o una producción A--> aBß, donde PRIMERO(ß) contenga e, entonces todo lo que esté en SIGUIENTE(A) se pone en SIGUIENTE(B).

Ejemplo: G( S )

SIGUIENTE (S) = {$, d, a, c, b } SIGUIENTE (A)= PRIMERO(B) U PRIMERO(S)= { d, a, c, b } SIGUIENTE (B)= e U SIGUIENTE(A)= { d, a, c, b, e}

4.2.2.3 Algoritmo para construcción de tabla LL(1)

Método: Suponemos que la tabla se identifica con M 1. Para cada producción A-->a de la gramática, aplicar los pasos 2 y 3. 2. Para cada terminal a en PRIMERO(a), cargar A-->a, en la posición M[A,a] 3. Si e está en PRIMERO(a), cargar A-->a a M[A,b] para cada terminal b que pertenezca a SIGUIENTE(A). Si e está en PRIMERO(a) y $ está en SIGUIENTE(A), cargar A-->a a M[A,$] . 4. Todas las posiciones de M, que no contengan una producción, serán consideradas como entradas de ERROR.

Preparado por Prof. Julio Suárez

42

Apuntes de Compiladores I

Ejercicios 1) Dada la gramática G(S) Sà ( L ) | a Là L , S | S Gráfica árboles sintácticos, ascendentes y descendentes, para las siguientes sentencias : i) (a,a) ii) (a,(a,a)) iii) (a,((a,a),(a,a))) 2) Eliminar recursividad por izquierda de la gramática G(S) del ejercicio anterior

3) Dada las gramáticas a) G ( S ) VT = {(,),;,x,a}, Verifica si son gramáticas limpias Sà ( A ) Aà C B Bà;A|e Cà x | S | C a | F a x DàxDa| Exa Fà F xa| EFax Eà(E)| ax b) G ( K) VT = {a,e,c,m,n, d, j} KàaZb| eMP ZàcA|D|mm A à M a | Bn Fàn R à cd R PàT|jBP M à nd 4) Considera la gramática G( Y ) Yà Y ‘|’ Y donde ‘|’ es un Terminal de la gramática que indica separador de alternativa Yà Y Y implica concatenación de dos Y Yà Y * | Y+ * es operador de cierre absoluto de una Y, + operador de cierre positivo Yà ( Y ) Yà a Yà b * y + : tienen la mayor precedencia y son asociativos por la izquierda Concatenación: tiene la segunda mayor precedencia y es asociativa por izquierda | : tiene la menor precedencia y es asociativa por la izquierda Construye una gramática no ambigua equivalente de acuerdo a las precedencias y las asociatividades. 5) Dada la siguiente gramática, modifica y adecua sus producciones, de manera que sea factible para un análisis LL(1) : G(F) VT={ >,= F | F E + E | E*E | ( E ) | id Análisis para la sentencia id + id * id

PILA $

ENTRADA id + id * id $

ACCION Desplazar

$id

+ id * id $

Reducir E-->id

$E

+ id * id $

Desplazar

id * id $

Desplazar

$E+ $E+id

* id $

Reducir E-->id

$E+E

* id $

Desplazar

id $

Desplazar

$E+E* $E+E*id

$

Reducir E-->id

$E+E*E

$

Reducir E-->E * E

$E+E

$

Reducir E-->E + E

$E

$

Aceptar

Preparado por Prof. Julio Suárez

46

Si se reduce aquí, la traducción que podría acompañar al análisis, daría resultado erróneo

Apuntes de Compiladores I

5.2 Conflictos durante el análisis sintáctico por desplazamiento – reducción Existen gramáticas independientes del contexto para los cuales no se puede utilizar el analizador sintáctico por desplazamiento-reducción. El analizador puede alcanzar una configuración en la que el mismo, conociendo el contenido total de la pila y el siguiente símbolo de la entrada, no puede decidir si Desplazar o Reducir ( conflicto Desplazar / Reducir ), o no puede decidir qué tipo de reducción efectuar ( conflicto Reducir / Reducir ). En general ninguna gramática ambigua, como la del ejemplo aplicarse a este método.

5.3 Analizadores Sintácticos LR Es una técnica eficiente de análisis sintáctico ascendente que se puede utilizar para analizar una clase más amplia de gramáticas independientes del contexto. Los analizadores LR reconocen lenguajes realizando las dos operaciones vistas, desplazar y reducir ( shift/reduce en inglés). Lo que hacen es leer los tokens de la entrada e ir cargándolos en una pila, de forma que se puedan explorar los n tokens superiores que contiene ésta y ver si se corresponden con la parte derecha de alguna de las reglas de la gramática. Si es así se realiza una reducción, consistente en sacar de la pila esos n tokens y en su lugar colocar el símbolo que aparezca en la parte izquierda de esa regla. En caso contrario, se carga en la pila el siguiente token y una vez hecho esto se vuelve a intentar una reducción. La técnica se denomina LR(K); la “L” es por la lectura de la sentencia de izquierda a derecha, la “R” por construir una derivación por la derecha en orden inverso, y la “K” por el número de símbolos de entrada de examen por anticipado utilizados para tomar decisiones en el análisis sintáctico. Cuando se omite K = 1. Una gramática que puede ser analizada por un analizador LR mirando hasta k símbolos de entrada por delante (lookaheads), en cada movimiento, se dice que es una gramática LR (k). 5.4 Ventajas •

Se pueden construir analizadores LR para reconocer prácticamente todas las construcciones de los lenguajes de programación para los que se pueden escribir GLC.

•

El método de análisis sintáctico LR es el método de análisis por desplazamiento y reducción sin retroceso más general y eficiente.

•

Los analizadores que utilizan la técnica LR pueden analizar un número mayor de gramáticas que los analizadores descendentes.

•

Un analizador sintáctico LR puede detectar un error sintáctico tan pronto como sea posible hacerlo en un examen de izquierda a derecha de la entrada

5.5 Desventajas •

La principal desventaja del método es el volumen de trabajo que supone construir un analizador sintáctico LR, “a mano”.

•

Se necesita de una herramienta especializada ( un generador de análisis LR ), por ejemplo el YACC.

Preparado por Prof. Julio Suárez

47

Apuntes de Compiladores I

5.6 Estructura y funcionamiento de un Analizador LR Un analizador LR consta de un programa analizador LR, una tabla de análisis, y una pila en la que se van cargando los estados por los que pasa el analizador y los símbolos de la gramática que se van leyendo. Se le da una entrada para que la analice y produce a partir de ella una salida Lo único que cambia de un analizador a otro, es la tabla de análisis, que consta de dos partes: una función de acción que se ocupa de las acciones a realizar y una función goto (Transición), que se ocupa de decidir a qué estado se pasa a continuación.

5.6.1 Modelo del Analizador LR

Entrada

a1

...

ai

...

an

$

Programa para análisis sintáctico LR

Sm

SALIDA

Xm Pila

Sm-1 Xm-1 ... S0

Acción

Ir_a (Transición)

Tabla de Análisis LR

El programa lee caracteres de un buffer de entrada de uno en uno. Utiliza una pila para almacenar una cadena de la forma S0X1S1X2S2...XmSm, donde Sm está en la cima. Cada Xi es un símbolo gramatical y cada Si es un estado del autómata.

5.6.2 Acciones en el Análisis LR El programa que maneja el analizador LR, se comporta como sigue : Determina Sm, el estado de la cima de la pila y ai, el símbolo en curso de la entrada. Se consulta la entrada Acción[Sm,ai] de la tabla de acciones, que puede tener uno de estos cuatro valores : 1. Desplazar S, donde S es un estado 2. Reducir por una producción gramatical A--> ß 3. Aceptar 4. Error Preparado por Prof. Julio Suárez

48

Apuntes de Compiladores I

5.6.3 Función Ir-A en Análisis LR La función Ir-A toma un estado y un símbolo gramatical como argumentos y produce un estado. Se verá que la función IR-A de una tabla de análisis sintáctico construida a partir de la gramática G, utilizando cualquiera de los métodos, que se verán, es la función de transiciones de un autómata finito determinista que reconoce los prefijos viables de G. 5.6.4 Algoritmo de Análisis Sintáctico LR Entrada : una cadena w y una tabla de análisis sintáctico LR con las funciones ACCION e IR-A para la Gramática G. Salida : si w ∈ L(G), un análisis ascendente de w, sino se indica error. Método : Inicialmente, S0 está en la pila, donde S0 es el estado inicial, y w$ está en el buffer de entrada. El analizador ejecuta entonces el siguiente algoritmo: Apuntar al primer símbolo de w$ Repetir Sea S el estado en la cima de la pila y a el símbolo apuntado SI ACCION[S,a] = desplazar S’ apilar a y luego S’ en la cima de la pila. Avanzar al siguiente símbolo de w$ SINO SI ACCION [S,a] = reducir A-->ß Desapilar 2*| ß| . Donde ß, representa a la cadena de estados y símbolos pertenecientes al pivote, desde la cima de la pila. Sea S’ el estado que ahora está en la cima de la pila; apilar A y después IR-A[S’,A] en la cima de la pila. Salida de la producción A--> ß SINO SI ACCION[S,a] = Aceptar Retornar SINO error( ) FINSI FINSI FINSI Fin Repetir

Preparado por Prof. Julio Suárez

49

Apuntes de Compiladores I

Ejemplo: Sea la gramática G(E), donde P : (1) E-->E+T (2) E--> T (3) T-->T*F (4) T--> F (5) F-->(E) (6) F--> id

Su tabla de Análisis sintáctico LR, la sgt. :

Análisis de la sentencia id * id + id $ PILA 0

ENTRADA id * id + id $

ACCION Desplazar

0id5

* id + id $

reducir por F-->id

0F3

* id + id $

reducir por T-->F

0T2

* id + id $

Desplazar

id + id $

Desplazar

0T2*7 0T2*7id5

+ id $

reducir F-->id

0T2*7F10

+ id $

reducir T-->T*F

0T2

+ id $

reducir E-->T

0E1

+ id $

Desplazar

id $

Desplazar

0E+6 0E+6id5

$

reducir F-->id

Preparado por Prof. Julio Suárez

50

Apuntes de Compiladores I

0E+6F3 0E+6T9

$ $

reducir T-->F reducir E-->E+T

0E1

$

Aceptar

5.7 Cálculos previos para la construcción de las tablas de Análisis LR ITEM LR(0) o simplemente item de una Gramática CUALQUIER PRODUCCION CON UN PUNTO EN LA PARTE DERECHA DE LA REGLA EJEMPLO : SEA LA REGLA

S à aA

à

ITEM : S à a . A

COLECCIÓN DE ITEMS o Colección LR(0) Conjunto de items. Cada conjunto de esta colección representa un estado AFD. Este autómata servirá para construir la tabla de análisis SLR Para construir la Colección LR(0) necesitamos definir lo que se conoce como gramática aumentada, y las operaciones de CLAUSURA y GOTO

GRAMATICA AUMENTADA Si G es una GLC con axioma S , la gramática aumentada G’ para G, se construye añadiendo S’ -> S , siendo el nuevo axioma S’ Sea la gramática G(S): S->E$ E-> E+T | E – T | T T-> (E ) | a Función CLAUSURA o CIERRE Sobre un conjunto I de items, se define la función cierre(I) como el conjunto de items resultante de aplicar las siguientes reglas : Regla 1: todos los items pertenecientes a I pertenecen a cierre (I) Regla 2: Si [A-> α . Bß] es un item que pertenece a cierre(I) y existe una regla de la forma B->µ, entonces el item [B->.µ] pertenece a cierre(I) Regla 3: Repetir la regla anterior hasta que no se añada ningún nuevo item al conjunto cierre(I) Ejemplo si I={ S->.E$} Cierre( I )={ S->.E$, E->.E+T, E->.E-T, E->.T , T-> .( E ), T-> .a} Función GOTO o de Transición Se define la función de transición δ , que se aplica a un conjunto de ítems y a un símbolo (terminal o no terminal) de la gramática, y da como resultado un nuevo conjunto de ítems. α, ß pertenece(VN U VT)* δ (I,X) es igual al cierre del conjunto de todos los items de la forma [A-> α X.ß], tales que Preparado por Prof. Julio Suárez

51

Apuntes de Compiladores I [A-> α .Xß] ∈ a I

Ejemplo: Sea I={ S->.E$, E->.E+T, E->.E-T, E->.T , T-> .( E ), T-> .a} Si X = E δ (I,E) = cierre(S->E.$, E->E.+T, E->E.-T)={ S->E.$, E->E.+T, E->E.-T } Si X= a δ (I,a)= cierre(T->a.)={T->a.}

COLECCIÓN DE CONJUNTOS DE ITEMS LR(0) Sea C un conjunto de items LR(0) compuesto por los conjuntos de items C={I0 , I1 , I2 , ......} Paso 1: I0 = cierre( item asociado al axioma de la gramática) Paso 2: Para cada I perteneciente a C y para cada símbolo X ∈ ( N U T), se halla GOTO(I,X). Si este conjunto no es vacio y no pertenece ya a la colección C, se añade a la misma. Ejemplo de la gramática anterior: I0 = cierre(S->.E$) = { S->.E$, E->.E+T, E->.E-T, E->.T , T-> .( E ), T-> .a} Ahora para I0 ( único elemento de C) y para cada X (terminal o no terminal ) de la gramática se halla el conjunto δ (I,X). Si este no es vacío y no pertenece a C, se añade a C ∈δβα

I1=δ(I0,E)= cierre (S->E.$, E->E.+T, E->E.-T} = { S->E.$, E->E.+T, E->E.-T } I2=δ(I0,T)=cierre(E->T.)={E->T.} I3=δ(I0, a ) = cierre(T->a.) ={T->a.} De la misma forma se obtienen los demas conjuntos de items I, y la colección completa será:

I0 = {[S -> ·E$],[E -> ·E+T],[E -> ·E-T],[E -> ·T], [T -> ·(E)],[T -> ·a]} I1 = {[S -> E·$],[E -> E·+T],[E -> E·-T]} I2 = {[E -> T·]} I3 = {[T -> a·]} I4 = {[T -> (·E)],[E -> ·E+T],[E -> ·E-T],[E -> ·T],[T -> ·(E)],[T -> ·a]} I5 = {[S -> E$·]} I6 = {[E -> E+·T],[T -> ·(E)],[T -> ·a]}

Preparado por Prof. Julio Suárez

52

Apuntes de Compiladores I

I7 = {[E -> E-·T],[T -> ·(E)],[T -> ·a]} I8 = {[E -> E+T·]} I9 = {[E -> E-T·]} I10 = {[T -> (E·)],[E -> E·+T],[E -> E·-T]} I11 = {[T -> (E)·]}

5.8 Algoritmo para la Construcción de la tabla de Análisis SLR

Preparado por Prof. Julio Suárez

53

Apuntes de Compiladores I

Como práctica construimos en clase, la tabla de análisis SLR, según la colección anterior

5.9 Tabla de Análisis LR-Canónica El método LR-canónico es más general que el SLR, ya que en algunos casos resuelve algún conflicto que puede darse al intentar construir una tabla de análisis SLR. La razón es que maneja una información más precisa que ayuda decidir cuándo se deben aplicar reducciones Llamamos item LR(1) de una gramática aumentada G’, a un elemento [Aà a.ß,a] donde Aàaß ? P y a ? Vt U {$}. Decimos que un item LR(1) [Aà ß1 . ß2,a ] es válido para el prefijo viable aß1, si:

S’ =>* r.m. a A x => r.m. aß1ß2 x, x ? Vt* Y ( a es el primer símbolo de x) o (x es ? y a= $). Ahora, igual que se hizo antes, hay que construir una colección de ítems LR(1) válidos para cada prefijo viable de la gramática. Para ello se modifican ligeramente las definiciones de clausura y goto

Preparado por Prof. Julio Suárez

54

Apuntes de Compiladores I

Preparado por Prof. Julio Suárez

55

Apuntes de Compiladores I

Preparado por Prof. Julio Suárez

56

Apuntes de Compiladores I

Preparado por Prof. Julio Suárez

57

Apuntes de Compiladores I

5.10 Tabla de Análisis LALR El método LALR es menos potente que LR-Canónico (hay gramáticas que son LR-Canónicas pero no LALR) y más potente que el SLR. Además el tamaño de la tabla de análisis LALR es igual que el de una SLR. Esto hace que sea un método muy utilizado en la práctica. Para construir una tabla de análisis LALR partimos de la colección de conjuntos de ítems LR(1) y del AFD, como en el caso del método LR-Canónico. Después nos fijamos en los estados que tienen las mismas producciones punteadas en los ítems y sólo se diferencian en los símbolos de anticipación del item. Una vez agrupados los estados de esta forma y modificando las transiciones de forma conveniente, se llegaría a otro AFD simplificado, a partir del cual se construye la tabla LALR, exactamente igual que la tabla LR-Canónica. Los nuevos estados del AFD constituyen lo que se llama colección LALR. Si la tabla resultante no tiene conflictos, entonces la gramática es LALR

Preparado por Prof. Julio Suárez

58

Apuntes de Compiladores I

TABLA ANALISIS LALR ESTADO 0 1 2 36 47 5 89

c D36 D36 D36 R3 R2

ACCION d $ D47 aceptar D47 D47 R3 R3 R1 R2 R2

S 1

IR-A C 2 5 89

Preparado por Prof. Julio Suárez

59

Apuntes de Compiladores I

Ejercicios 1) CONTESTA EL SIGUIENTE CUESTIONARIO a) Qué representa un item LR(1), en la construcción de tablas para el análisis SLR? Escribe un ejemplo.

b) Qué significan los términos Desplazar y Reducir en un análisis sintáctico ascendente?

c) Qué tipos de acciones se verifican en un análisis LR?

d) Por los métodos estudiados, cuántos estados finales puede tener una analizador sintáctico LR?

e) Cómo se determina el estado final para el autómata del analizador sintáctico LR?

f)

Qué ventaja encuentra al diseñar un analizador ascendente, en sustitución de un analizador descendente?

g) Explica el significado del item [ P à id + . P]

2) Dada la siguiente gramática G (S) Preparado por Prof. Julio Suárez

60

Apuntes de Compiladores I SàA AàB%A|BC Bà D|D*B Dàx|(C) C à +x | -x VT= { %, *, x, (, ), +, - } Obtener la tabla de análisis LALR

3) Construye la Colección de conjuntos de items LR(1) y la tabla de análisis LR-Canónica, para la siguiente gramática: (1) Z → RdT VN= {Z, R TB} (2) R→ dRd VT= {d,H,b} (3) R→ h (4) T→ b

4) Escribe programas en Yacc/Lex para reconocer conjuntos de sentencias del lenguaje, separadas por un retorno de carro. Correspondiente a la gramática del item anterior. Imprimir al final del reconocimiento de un texto con sentencias, la cantidad de sentencias válidas analizadas. Incluir el programa en LEX, que genere el analizador léxico correspondiente.

5) Considere la gramática :

i) ii) iii)

Sà (L) |a Là L,S | S

Construya una derivación de más a la derecha para (a,(a,a)) y muestre el handle de cada forma sentencial derecha. Muestre los pasos de un parser shift-reduce correspondiente a una derivación de más a la derecha de (a). Muestre los pasos en la construcción bottom-up de un árbol de parser, durante el parser shift-reduce de ii).

6) Considere la siguiente gramática escrita en formato estilo YACC (ignore las acciones por el momento): decl : lista_id ':' tipo_id { printf("DECL\n"); } tipo_id : ID { printf("TIPO: %s\n", yytext); } lista_id : id { printf("UNO\n"); } | id ' , ' lista_id { printf { ("LISTA\n"; } id : ID { printf("VAR: %s\n", yytext); } i) ii)

Muestre una derivación de más a la derecha para la tira de entrada : a, b, c: int Considere ahora las acciones, y de la salida que un parser bottom-up imprimiría para la misma tira de entrada.

7) Considere la siguiente gramática que genera el lenguaje de las expresiones aritméticas: EàEBE | (E) E à id | num Bà+|*| /|i)

Usando YACC escriba la gramática para reconocer el lenguaje.

ii)

Agréguele el manejo de errores.

Preparado por Prof. Julio Suárez

61