Transcript
BENEMÉRITA UNIVERSIDAD AUTONÓMA DE PUEBLA
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN
NOTAS DE
COMPILADORES
ANÁLISIS LÉXICO Y SINTÁCTICO
Otoño 2013
Capítulo I 1
Visión Histórica del Desarrollo de los Compiladores En 1946, se desarrolla el primer ordenador digital ejecutaban instrucciones en códigos numéricos (lenguaje de máquina) interpretado por un secuenciador cableado. Posteriormente, surgen los ensambladores (claves más fáciles de recordar) en donde la propia máquina realizaba el proceso mecánico de traducción. A pesar de todo el lenguaje ensamblador seguía siendo de una máquina. Las líneas de investigación para crear leguajes más fáciles e independientes de la máquina desde 1950 con John Backus hasta 1957 el FORTRAN (Formule Translator) primer lenguaje de alto nivel. Por primera vez surge el concepto traductor. Traductor. Programa que traduce de un lenguaje a otro. Compilador. Traduce un lenguaje de alto nivel a uno de bajo nivel. El primer compilador de FORTRAN tardó 18 años en realizarse y era muy sencillo. El FORTRAN aún estaba muy influenciado por la máquina en la que iba ser implementado. Las líneas de investigación continúan hasta 1958 un grupo de investigadores junto con J. Backus crean ALGOL 58 (Algorithmic Language). Después ALGOL 60, LAGOL 68 lenguaje modular estructurado en bloques. En ALGOL aparecen por primera vez conceptos de los nuevos lenguajes algorítmicos. a) Definición de la sintaxis en notación BNF (Backus Naur Form): Gramática independiente del contexto. Ejemplo: prop if(expr) prop else prop b) c) d) e) f) g)
Formato libre: Declaración explícita de tipo para todos los identificadores Estructuras iterativas Recursividad Paso de parámetros por valor y por referencia Estructura de bloques
Paralelamente, se avanzaba en la técnica de compilación. En 1958 Strong y otros proponen una solución al problema de que un compilador fuera utilizable por varia máquinas objeto. Para ello dividen el compilador en dos fases: 1) front end 2) back end front end: se encarga de analizar el programa fuente. back end: se encarga de generar el código para la máquina objeto
2
El puente de unión entre las 2 fases era un lenguaje intermedio que se designó como UNCOL (Universal Computer Oriented Language). Para que el compilador fuera utilizable por varia máquinas bastaba modificar su back_end. Aunque no tuvo éxito la definición de UNCOL la división del compilador fue un adelanto importante. En eso años se van proponiendo las bases par la división de tarea en un compilador. Así en 1959 Rabin y Scott proponen el empleo de autómatas deterministas y no deterministas para el reconocimiento lexicográfico de los lenguajes. En 1975, con la aparición de LEX, surge el concepto de analizadores léxicos a partir de expresiones regulares. Avance Sintáctico A partir de los trabajos de Chomsky se produce una sistematización de la sintaxis de los lenguajes de programación, y con ello un desarrollo de diversos métodos de análisis sintáctico. Con la notación BNF desarrollada en 1960 por Backus, modificada en 1963 por Naur y formalizada por Knuth en 1964 se tiene una guía para el desarrollo del análisis sintáctico. Los diversos métodos sintácticos ascendentes y descendentes se desarrollaron durante los 60’s. En 1959, Sheridan describe un método de parsing de FORTRAN que introducía paréntesis adicionales alrededor de los operandos para ser capaz de analizar las expresiones. Más adelante, Floyd introduce la técnica de precedencia de operador. A mitad de los 60’s, Knuth define las gramáticas LR (ascendente). En 1968, se estudia y definen las gramáticas LL (ascendentes). Debido a la sencillez y capacidad de análisis para una gran variedad de lenguajes, la técnica de parsing LR es la elegida par los generadores automáticos de parsers. A mediados de los 70’s Johnson crea el generador de analizadores sintácticos YACC. Avance Semántico Junto al análisis sintáctico, también se fue desarrollando el análisis semántico. En los primeros lenguajes (FORTRAN y ALGOL 60) los tipos posibles de datos eran muy simples y la comprobación de tipos era muy sencilla. Avance de Optimización La inclusión en ALGOL de procedimientos recursivos potenció el uso de la pila como una forma de manejo de memoria. Así mismo, se estudió el paso de parámetros por valor y referencia, con la aparición de lenguajes que permiten la localización dinámica de datos, se desarrolla otra forma de manejo de memoria. La técnica de optimización apareció desde el desarrollo del primer compilador FORTRAN. Backus comenta que se tenía el temor de optimizaciones dependientes de la máquina e independientes de ésta. Entre las dependientes se pueden encontrar:
3
Localización de registros Uso de instrucciones propias de la máquina Reordenamiento de código Entre las independientes se pueden encontrar: Propagación de valores Arreglo de expresiones Eliminación de redundancia En la actualidad un compilador es una herramienta bien conocida, dividida en diversas fases. Algunas se pueden generar automáticamente (analizador léxico y sintáctico) y otras requieren mayor atención (traducción y generación de código) De todas formas, todavía se llevan a cabo varias vías de investigación. El hecho de que surjan nuevos lenguajes, como los de 5ª generación implica la revisión de cada fase del compilador. ¿Qué es un Compilador? Tipos de Traductores Traductor. Cualquier programa que toma como entrada un texto escrito en un lenguaje llamado fuente y da como salida un programa equivalente en otro lenguaje, denominado objeto.
Lenguaje fuente
Traductor
Lenguaje Objeto
Compilador: Lenguaje de alto nivel (fuente) y lo traduce en lenguaje de bajo nivel (objeto). Ensamblador. Traduce del lenguaje ensamblador (fuente) a lenguaje de bajo nivel (objeto). Intérprete. Toma una sentencia del programa fuente de un lenguaje de alto nivel y la traduce al código equivalente y al mismo tiempo lo ejecuta. Históricamente con a la escasez de memoria en los primeros ordenadores, se puso de moda el uso de intérpretes pero, la mejor información sobre los errores por parte del compilador así como una mayor velocidad de ejecución del código resultante hizo que los compiladores se impusieran. Hoy en día, con el problema de la memoria prácticamente resuelto se tiene un predominio de los compiladores. Ventajas de compilar frente a interpretar a) Se compila una vez, se ejecuta n veces b) En bucles, la compilación genera código equivalente al bucle, interpretándolo se traduce tantas veces una línea como veces se repite el bucle 4
c) El compilador tiene un visión global del programa, por lo que la información de mensajes de error es más detallada. Ventajas del intérprete vs el compilador a) Un intérprete necesita menos memoria que un compilador b) Permiten una mayor interactividad con el código en tiempo de desarrollo Un compilador no es un programa que funcione de forma asilada, sino que necesita de otros programas para conseguir su objetivo, algunos de esos programas son: El preprocesador: incluye ficheros, expandir macros, eliminar comentarios, etc. El linker: construir el fichero ejecutable añadiendo las cabeceras necesarias y las funciones de librería utilizadas por el programa fuente. El depurador: si se generó el programa objeto, permite seguir paso a paso la ejecución de un programa. El ensamblador: convierte del lenguaje a un ejecutable. Tipos de Compiladores a) Ensamblador: Tiene una estructura sencilla. b) Compilador cruzado: Genera código en lenguaje objeto para una máquina diferente de la que se esta utilizando para compilar. c) Compiladores con montador: Compila distintos módulos de forma independiente y después los enlaza. d) Autocompilador: Compilador de compiladores, aunque tiene la dificultad de unir la generación de código con la parte de análisis. Lo que sí se han desarrollado son: LEX generador de analizadores léxicos YACC generador de analizadores sintácticos Aunque los analizadores que generan no son muy eficientes. e) Descompilador: Traduce código máquina a un lenguaje de alto nivel. Si hay optimización es posible descompilar. Estructura de un Compilador Para la realización del proceso de traducción es necesario dividir el compilador en varias fases.
5
Programa fuente Análisis léxico Análisis sintáctico Manejo de la Tabla de símbolos
Análisis semántico
Manejo de errores
Generación de código intermedio Optimización de código Generación de código Programa objeto Etapas que constituyen el Proceso de Compilación Al principio el tamaño del archivo ejecutable y la memoria utilizada por el compilador era un recurso crítico, por lo que cada fase leía un fichero escrito por la fase anterior y producía un nuevo fichero con el resultado de las transformaciones realizadas en dicha fase lo que provocaba que el compilador realizará muchas pasadas sobre el programa fuente. En los últimos años ya no se tienen ambos problemas, el segundo fue resuelto gracias a la memoria virtual, así que leer y escribir un fichero en cada fase es una pérdida considerable de tiempo (incluso en los sistemas modernos). Las fases se agrupan en 2 partes: 1) front_end: fases de análisis 2) back_end: fases de generación y optimización de código Estas dos se comunican mediante una representación intermedia generada por el front_end que puede ser: una representación de la sintaxis del programa (un árbol sintáctico abstracto) un programa en lenguaje intermedio
6
El front end depende del lenguaje fuente y casi siempre es independiente de la máquina objeto. El back end depende del lenguaje objeto y debe ser independiente del lenguaje fuente (excepto quizá para algún tipo de optimización). Análisis Léxico También conocido como scanner, lee los caracteres uno a uno y va formando grupos de caracteres con alguna relación entre sí (tokens), que serán la entrada para la siguiente etapa. Tipos de tokens: • Tiras específicas: palabras reservadas, ; , , =, +, -, and, etc. • Tiras no específicas: identificadores, constantes o etiquetas. Un token tiene dos partes: • •
Tipo de token Valor
Las tiras específicas solo tienen tipo (lo que representan). Las tiras no específicas tienen tipo y valor. Ejemplo: si “contador” es un identificador El tipo es identificador Su valor es la cadena “contador” El analizador léxico permite saber si es un lenguaje de formato libre o no. Frecuentemente va unido al analizador sintáctico en la misma pasada, funcionando como una subrutina de este. El analizador léxico ignora elementos innecesarios para la siguiente fase, como tabuladores, comentarios, espacios en blanco, etc. Ejemplo: entrada CONT * Análisis léxico id por
+ mas
CONT id Análisis sintáctico
También llamado Parser comprueba si los tokens van llegando en el orden correcto (orden permitido). Su salida sería un árbol sintáctico. Sus funciones son: • Aceptar lo que es válido sintácticamente y rechazar lo que no lo es • Hacer explícito el orden jerárquico que tienen los operadores en el lenguaje de que se trate, por ejemplo A/B * C es interpretado como (A/B) * C en FORTRAN • Guiar el proceso de traducción (traducción dirigida por sintaxis)
7
Análisis semántico Es más difícil de formalizar que el sintáctico. Se encarga de comprobar que lo que va leyendo es válido. Sus funciones son: a) determinar el tipo de los resultados intermedios b) comprobar que los argumentos que tiene un operador pertenecen al conjunto de operadores posibles c) compatibilidad entre operandos La salida es un árbol semántico. Esto es un árbol sintáctico en donde cada rama ha adquirido el significado que debe tener. Para el caso de lo operadores polimorficos (un símbolo con varios significados), el análisis semántico determina cuál es el aplicable. Por ejemplo: A:= B + C En Pascal “+” sirve para sumar enteros, reales, concatenar cadenas de caracteres y unir conjuntos. Por ejemplo: :=
posición
+
inicial velocidad
* entero real 60
8
Generación de Código Intermedio Cuando una empresa desarrolla un compilador para un lenguaje fuente y un lenguaje objeto determinados, normalmente no es el único compilador que la empresa piensa desarrollar. El uso de un lenguaje intermedio permite construir en mucho menos tiempo un compilador. Por ejemplo, si un compilador de C, uno de FORTRAN y uno de PASCAL usan el mismo lenguaje intermedio pueden ser portados a todos los sistemas y máquinas en las que ya exista un compilador de C relativamente poco esfuerzo. La generación de código intermedio transforma un árbol de análisis sintáctico (semántico) en una representación en lenguaje intermedio. Una forma es usando el código de tres direcciones. Ejemplo: temp1:= enteroreal (60) temp2:= id3 * temp1 temp3:= id2 + temp2 id:= temp3
:=
id 1
+
id2
* id3
enteroreal 60
Optimización de Código Esta fase se añade para conseguir que el programa objeto sea más rápido en la ejecución y que necesite menos memoria ala hora de ejecutarse. Ejemplo de optimizaciones locales: eliminar algunos saltos eliminar expresiones comunes optimizaciones de bucles Ejemplo: 1) temp1:= enteroreal (60) temp2:= id3 * temp1
≈ temp1:= id3 * 60.0 optimización de código 9
≈ B:= 1 repeat A:= A – B until A:= 0
2) repeat B:= 1 A:= A – B until A:= 0 Generación de Código
Consiste en generar código objeto que consiste en código máquina o ensamblador. Ejemplo: MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 Tabla de Símbolos Utilizada para que el compilador guarde y use la información de los objetos que encuentra en el texto fuente, como variables, etiquetas, declaraciones de tipos, etc. El compilador usa la estructura de datos para insertar, consultar, borrar, etc. Los accesos deben ser rápidos para que el compilador sea eficiente. Ejemplo: 1 Posición 2 Inicial 3 Velocidad 4
……… ……… ……… ………
Manejo de Errores Es una de las funciones más importantes de un compilador, aunque es lo que más dificulta su realización. Se utiliza más en el análisis sintáctico y semántico. Es una tarea difícil por dos razones: A veces unos errores ocultan otros A veces un error provoca una avalancha de muchos errores que se solucionan con el primero Es conveniente que el compilador detecte todos los errores que tiene el programa y no se pare con el primero que encuentre. Hay dos criterios para manejar los errores:
10
1) Pararse al detectar el primer error 2) Detectar todos los errores de una pasada ¿Cómo se específica un Compilador? Cuando se va a diseñar un compilador, es necesario especificar: a) b) c) d)
el lenguaje fuente el lenguaje objeto el sistema operativo sobre el que funcionará el lenguaje usado para construirlo La especificación del lenguaje fuente se divide en tres partes:
1) Especificación léxica: se especifican los componentes léxicos (tokens) o palabras del lenguaje, para ello se usan expresiones regulares. 2) Especificación sintáctica: se detalla la forma o estructura (la sintaxis) que tendrán los programas en este lenguaje fuente. Para lo cual se utiliza una gramática independiente del contexto en notación BNF. 3) Especificación semántica: se describe el significado de cada construcción sintáctica y las reglas semánticas que deben cumplirse. Tarea 1: Aplicaciones de las Técnicas Aprendidas en Compiladores a) Desarrolla de interfaces textuales: cualquier programa cuya interacción con el usuario sea algo más que pulsar teclas. b) Tratamiento de ficheros de texto con información estructurada: lenguajes como PERL y TCL. c) Procesadores de texto: procesadores como VI o EMACS usan expresiones regulares. d) Diseño e interpretación de lenguajes para el formateo de texto y descripción de gráficos: HTML, PostScript. e) Gestión de base de datos: exploración y proceso de ficheros. f) Procesamiento de lenguaje natural. g) Traducción de formatos de fichero: estructura de datos de ficheros con registros de programas obsoletos se pueden actualizar a formatos actualizados. h) Reconocimiento de formas: detección de patrones en texto, reconocimiento automático del habla o la visión por computador. El Papel del Analizador Léxico El analizador léxico es el único que gestiona con el fichero de entrada para construir elementos léxicos llamados “tokens”. El analizador léxico ignora tabuladores, espacios en blanco, cambios de línea, comentarios, etc. ¿Por qué separar el análisis léxico y sintáctico? 11
1) El diseño de las partes posteriores al análisis queda simplificado. 2) Con fases separadas se pueden aplicar técnicas específicas para cada fase, que son más eficientes en sus respectivos dominios. 3) Se facilita la portabilidad. Si se quiere cambiar alguna característica del alfabeto del lenguaje, sólo tiene que cambiar el analizador léxico. Ejemplo: si tomamos las expresiones 6 – 2 * 30 / 7 6 - 2* 30/7 8-2*3/5
Tienen la misma estructura (analizador sintáctico) pero los caracteres no son pero los caracteres no son los mismos
Es por eso que el procesamiento de caracteres se deja en manos del analizador léxico. Ejemplo: las tres expresiones anteriores son representadas por el analizador léxico de la misma manera.
Cada par está representado por el tipo de token (lexema). Gran parte del tiempo se consume en leer el archivo fuente El analizador léxico debe rechazar cualquier texto en el que aparezcan caracteres ilegales (no recogidos en el alfabeto) o combinaciones ilegales (no permitidas por las especificaciones léxicas). Errores Léxicos Pocos son lo errores de esta etapa, pues el compilador tiene todavía una visión muy local del programa. Por ejemplo: Si encuentra y aísla la cadena while creerá que es un identificador, cuando posiblemente se trata de un while mal escrito y no es el quien informa de esto sino etapas sucesivas del análisis. Los errores que típicamente detecta el analizador léxico son: a) Utilizar caracteres que no pertenecen al alfabeto del lenguaje, por ejemplo: “ñ” o “±” b) Se encuentra una cadena que no coincide con ninguno de los patrones de los tokens posibles, por ejemplo: En un lenguaje ‘:=’ puede ser la asignación pero que no permita ‘:’ solo. Cuando el analizador léxico encuentra un error, lo habitual es parar su ejecución e informa, pero hay una serie de posibles acciones para anotar los errores, recuperarse de ellos y seguir trabajando.
12
Tarea 2: Investigar acerca del manejo de buffers de entrada pareja de buffers y centinelas. Ignorar los caracteres no válidos hasta formar un token según los patrones dados. Borrar los caracteres extraños. Insertar un caracter que pudiera faltar. Reemplazar un caracter presuntamente incorrecto por uno correcto. Conmutar las posiciones de dos caracteres adyacentes. Todas son complicadas de llevar a cabo y peligrosas por las equivocadas que pueden resultar para el resto del análisis. Funcionamiento de Analizador Léxico 1) La primera función del analizador léxico es procesar la cadena de caracteres y devolver pares (token, lexema). Debe ser una subrutina del analizador sintáctico.
Programa fuente
Analizador léxico
Componente léxico Obtén el siguiente componente léxico
Analizador sintáctico
Tabla de símbolos 2) Maneja el fichero del programa fuente; es decir: abrirlo, leer sus caracteres y cerrarlo. También deberá ser capaz de gestionar posibles errores de lectura. 3) Ignora comentarios, tabuladores, espacios en blanco, retornos de carro, etc. 4) Cuando se produce una situación de error este es el que sitúe el error en el programa fuente (tal línea, tal posición). Lleva la cuenta de las líneas procesadas. 5) Preproceso de macros, definiciones, constantes y órdenes de inclusión de otros ficheros. Cada vez que se llame al analizador este debe continuar en el caracter donde se quedó hasta completar un token y en ese momento debe devolver el par (token, lexema). Cuando se reconocen algunos tipos de tokens como los identificadores o los números el analizador léxico debe leer caracteres hasta que lea uno que no pertenece a la categoría del token que se está leyendo: este último caracter debe devolverse al buffer de entrada para ser leído en primer lugar en la próxima llamada. Ejemplo: En la cadena Grande / 307>= ↑↑ ↑↑ El nombre del identificador Grande ha concluido basta colocarse en él y ver si no es prefijo de ningún otro 13
El analizador léxico debe intentar siempre leer el token más largo posible, pero si no es correcto debe devolver el token correcto y debe retroceder en el buffer hasta el final de ese token correcto. “!>” no es válido pero “!”es válido
Ejemplo:
Para especificar correctamente el funcionamiento de un analizador léxico se debe utilizar una máquina de estados, llamada Diagrama de Transiciones (DT), muy parecido a un autómata finito determinista con las siguientes diferencias: Un ADF sólo dice si la cadena de caracteres pertenece al lenguaje o no; un DT debe leer caracteres hasta completar un token, y entonces retornar (en los estados de aceptación) el token leído y dejar el buffer de entrada preparado para la siguiente llamada. Un DT no puede tener estados de absorción (cadenas incorrectas en AFDs) En un DT se considerará que las entradas para las que no hay transición desde cada estado son error. De los estados de aceptación de un DT no deben salir transiciones. En el caso de tiras no especificas, se necesita otro estado al que ir cuando se lea un caracter que no pueda formar parte del patrón. En este último estado (al que se llega con la transición especial a otro) se debe devolver al buffer de entrada el caracter leído que puede ser parte del siguiente token, lo cual se indica marcando el estado con un *, y se debe retornar el token correspondiente a ese estado de aceptación. Ejemplo: Reconocedor de números enteros sin signo mediante la expresión regular [0-9]+ = digito+ DT [0-9] [0-9] 1
2
*Entero
otro
[0-9] 0
1
3
Otro: significa cualquier otro caracter del alfabeto del lenguaje que no esté en el rango [0-9] x
x
Transición
No obligatorio (repetición) Estados
* Retroceso de un estado
Transición
Si durante el recorrido del autómata se produce una transición no autorizada o la tira de entrada finaliza en un estado de no aceptación, el analizador informaría del error.
14
El analizador suele tener unos subprogramas auxiliares encargados de gestionar el buffer (técnicas de doble buffer, doble salto de línea, , etc.) y de ir volviendo caracteres al buffer de entrada cada vez que el procedimiento de reconocimiento y aislamiento lo requiera. Identificación de Palabras Reservadas El problema es como reconocer palabras reservadas si responden al mismo patrón que los identificadores, pero son tokens diferentes al token “identificador”. Existen dos enfoques para resolver este problema: 1) Resolución Implícita: Considerar que todos son identificadores y buscarlos en una tabla. 2) Resolución Explícita: Se indican todas las expresiones regulares de todas las palabras reservadas y se integran los DT resultantes de sus especificaciones léxicas en la máquina reconocedora. Para 1) en definitiva, las palabras reservadas se toman como lexemas particulares del patrón del identificador. Para esto en el AL. Primero inicializará la tabla de símbolos con todas las palabras reservadas (por orden alfabético). Cuando encuentre identificador se revisará la tabla de símbolos. o Si lo encuentra en la zona reservada para ellos entonces es una palabra reservada. o Si no, será un identificador, que como tal, será añadido a la tabla de símbolos. Ejemplo: “cont” Tabla de símbolos do end for while … cont …
Pal. reservada Pal. reservada Pal. reservada Pal. reservada … Identificador …
Zona de Palabras Reservadas
Zona de identificadores
Cuando la detección es explicita. Las especificaciones léxicas de las palabras reservadas, (tiras específicas) constan de concatenaciones de caracteres y pueden ser siempre prefijos de identificadores (por ejemplo “do” y “dos” (identificador). Cuando un elemento léxico es prefijo de otro y ambos son tiras especificas, aparecen estados de aceptación que partirán de estados intermedios.
15
Ejemplo 1: Construir un diagrama de transiciones para el reconocimiento de identificadores, números enteros sin signo y palabras reservadas “do” y “done”. Notación d = dígito, l = letra, t = otro, f = otro alfanumérico (dígito o letra), an = ir al estado n
Ejemplo 2: Construir un diagrama de transiciones para el reconocimiento de números enteros con signo negativo o si n signo. (ER: (- | E) · d+ y los operadores suma (“+”) e incremento (“++”) Notación d = dígito, t = otro
Ejercicio 1: Construir un diagrama de transiciones para el reconocimiento de operadores relacionales: <, <=, < >, =, >=, >
Ejercicio 2: Construir un diagrama de transiciones para el reconocer números en notación científica ejemplo ± 3 ε ± 5 científico → signo d+ E signo d+ Ejercicio 3: Construir un diagrama de transiciones para el reconocer números reales dígitos+ (.dígitos+)
Ejercicio 4: Construir un diagrama de transiciones para el reconocer los siguientes componentes léxicos while, when, ident, opersum (+), opermul (*), operinc (++)
Ejercicio 5: Construir un diagrama de transiciones para el reconocer opersum (+), opermul (*), operdiv (/), operrest (-), parizq ( ( ), parder( ) ), entero, real, ident.
Ejercicio 6: Construir un diagrama de transiciones para el reconocer los siguientes componentes léxicos read, print, palabras reservadas pradir, redir, ident, raya (_), punto ( . ) Ejercicio 7: Construir un diagrama de transiciones para el reconocer los siguientes operadores lógicos and, or, not.
16
Implementación del Analizador Léxico La forma de implementar el Diagrama de Transiciones es mediante la construcción de su tabla de transiciones. Para ello se etiquetan las filas como los estados del DT y las columnas como las distintas posibles entradas a las que hay que añadir el token que se reconoce. Ejemplo: [0-9] [0-9] 1
*Entero
otro
2
3
# de retroceso
Entradas Estado 1 2 3
[0-9] 2 2 0
_
token retroceso 0 0 Entero 1
otro
0
Tabla de Transiciones del ejemplo 1 Entradas Estado l ‘d’ ‘d’ ‘o’ ‘n’ 1 2 4 6 2 2 2 2 2 2 2 2 3 0 0 0 0 0 4 $ 4 $ $ $ 5 0 0 0 0 0 6 2 2 2 7 2 7 2 2 2 2 9 8 0 0 0 0 0 9 2 2 2 2 2 10 2 2 2 2 2 11 0 0 0 0 0
‘e’ 2 2 0 $ 0 2 2 0 10 2 0
t 0 2 0 $ 0 3 8 0 3 11 0
Una vez que se tiene esta, el analizador léxico la recorrerá cada vez mediante un bucle con la sentencia. Estado:= Tabla de Transiciones [Estado, Entrada]. 17
El Analizador intentará llegar a un estado de aceptación, en el que restaura la entrada según el “retroceso”. Prioridad de tokens Dar prioridad al token para el que encontramos el lexema más largo. Ejemplo “Do” / “DOT” se toma (“DOT”) Si el lexema es el mismo que se puede asociar a dos tokens, estos estarán definidos en un orden (el primero).
Ejemplo: while → Palabra reservada l (l | d) → identificador Así que el Analizador Léxico devuelve el token palabra reservada. TT Ejemplo 2
Entradas Estado + ‘d’ ‘_’ t 1 2 5 7 0 2 4 3 0 3 3 0 0 0 0 4 0 0 0 0 5 0 5 0 6 6 0 0 0 0 7 0 5 0 0
* Suma incremento * Entero
PROYECTO 1: Hacer un Analizador Léxico para: ALGOL ADA MODULA II Que por lo menos contenga: Tipos de datos Constantes Variables (Identificadores)
18
Operadores Sentencias de control (Decisión y Repetición) Funciones Paso de parámetros Ejercicio 7: Hacer el DT, TT para reconocer números decimales, octales y binarios d = 0 | 1 |…| 9 oct = 2 | 3 |…| 7 dd = 8 | 9 bin = 0 | 1
Tabla de Símbolos El Analizador Léxico guarda una entrada de la tabla de símbolos el lexema correspondiente a los identificadores (las variables). Las fases posteriores del compilador pueden añadir a esta entrada información, como el tipo de identificador, su uso (por ejemplo, procedimiento, variable o etiqueta) y su posición en la memoria. Gran parte de la detección y recuperación de errores en un compilador se centra en la fase de análisis sintáctico. El analizador sintáctico debe hacer lo siguiente: Informar de los errores con claridad y exactitud Recuperarse de cada error rápido para detectar los errores posteriores No retrasar de manera significativa el proceso de programas correctos Existen varia técnicas para que el Analizador Sintáctico se recupere de fallos, pero: Una recuperación inadecuada puede introducir una avalancha de errores introducidos por los cambios hechos al estado del analizador sintáctico La recuperación del error sintáctico puede introducir errores semánticos Tarea 1: Estrategias de recuperación de Errores.
19
Capítulo II Análisis Sintáctico (PARSER) Su función principal es construir una representación interna del programa. Agrupa los lexemas suministrados por el A.L. con el fin de reconocer frases. Determina si el programa es sintácticamente correcto. Esto es si la sucesión de símbolos que representan los tokens es generada por la gramática correspondiente al lenguaje. Los tokens los agrupa de acuerdo a producciones especificadas por la GLC. La sintaxis se especifica con GLC. La forma más habitual de representar la sintaxis de un programa es el árbol de análisis sintáctico y el A.S. construye una derivación por la izquierda o por la derecha del programa fuente.
El A. S. constituye el esqueleto principal del compilador Hay dos opciones para implementar un parser 1. “A mano” usando técnicas (eficiente y complejo) 2. Utilizando un generador de A.S., por ejemplo YACC (ineficiente y fácil) 2.1 Notación EBNF (Extended Backus-Naur Form).
Esta se usa con el objetivo de reducir el número de producciones en las gramáticas. 1.- Alternativas de una regla: ‘|’ para separar las distintas posibilidades que definen al no terminal de la izquierda. Ejemplo: a) si A → a A→b A→ c =A →a | b | c b) entero → digito | entero dígito 2.- { }, lo que aparece entre llaves se repite de cero a n veces.
20
Ejemplos: a) Lista_parámetros → parámetro {, parámetro> b) tren → locomotora {vagón } 3.- Llaves con repetición especificada: { }yx: lo que aparece entre llaves se repite de x a y veces. Ejemplo: tren con 3, 4 ó 5 vagones: tren → locomotora { vagón }53 4.- [ ]: lo que está entre los corchetes puede o no aparecer. Es un caso particular de3.-, pues es equivalente a { }10 Ejemplo: Sentencia IF de Pascal: IF expresión THEN sentencia [ ELSE sentencia ] 2.2 Gramática GLC o BNF Sea G = (N, T, S, P) es una 4- tupla donde: N = conjunto de no terminales: Genera más de un única cadena T = conjunto de terminales: Genera una única cadena P = conjunto de producciones: Regla que establece una transformación S = Símbolo inicial o axioma: Genera todas las cadenas del lenguaje Sea G = (N, T, S, P), donde N = {frase, sujeto, predicado, articulo, nombre, verbo, adverbio} T = {el, la, está, lejos, cerca, perro, gato} S = {frase} P = {P1, P2, P3, P4, … , P10} P1 = frase → sujeto predicado P2 = sujeto → articulo nombre P3 = predicado → verbo adverbio P4 = articulo → el P5 = articulo → la P6 = nombre → perro P7 = nombre → gata P8 = verbo → está P9 = adverbio → cerca P10 = adverbio → lejos Forma de frase: Cualquier string que se pueda derivar del símbolo inicial (string de símbolos gramaticales). Frase: Cualquier forma de frase con solo elementos terminales
21
Lenguaje: Definido por una G (conjunto de todas las frases de la G). Para el ejemplo anterior, los siguientes elementos pertenecen al lenguaje generado por la G: El perro está cerca La perro está lejos El gata está cerca
Cadena – Frase Cadena - Frase Cadena – Frase
Los siguientes elementos no pertenecen al lenguaje generado por la G: El perro La lejos perro está Convenios para la GLC Terminales: o Primeras minúsculas del abecedario o Símbolos de operación y puntuación o Dígitos o Palabras en negrita: perro, begin Son no Terminales: o Primeras mayúsculas del abecedario o Palabras en cursiva: sujeto, expresión La S, suele representar el símbolo inicial Letras griegas minúsculas representan formas de frase o Así en un GLC una producción de escribe A→B Parte izq. Parte der. Varias producciones con igual parte izquierdo se agrupan en una producción con alternativas. Diseño de Gramáticas para Lenguajes de Programación Como se plasma en el aspecto de las reglas sintácticas algunas propiedades de los operadores y operandos en los lenguajes de programación. RECURSIVIDAD Una dificultad a la hora de diseñar un compilador es que debe procesar correctamente un número infinito de programas distintos. Por otro lado, la especificación sintáctica de un lenguaje debe ser finita. El concepto que hace compatible ambas afirmaciones Recursividad. Permite definir sentencias complicadas con un número pequeño de sencillas reglas de producción. 22
EJEMPLO: Formar un tren con locomotora y un número cualquiera de vagones detrás. tren → locomotora tren → locomotora vagón tren → locomotora vagón vagón ...
Infinitas reglas de producción
Usando recursividad manera: 1) Regla base (no recursiva) tren → locomotora 2) Una o más reglas recursivas tren → tren vagón Con esto no necesitamos infinitas reglas de producción. Estructura de la recursividad 1. Regla no recursiva que se define como caso base. 2. Una o más reglas recursivas que permiten el crecimiento a partir del caso base. EJEMPLO 1: La gramática para describir un identificador escrita como GLC, podría ser: N = { Letra, Dígito, Identificador} T = { a, b, c,..., z, 0, 1,..., 9 } S = Identificador P = { Letra → a ... Letra → z Dígito → 0 ... Dígito → 9 Identificador → Letra Identificador → Identificador Letra Identificador → Identificador Dígito } Así, el árbol sintáctico de “id02a” sería:
23
Definición: Una gramática se dice que es recursiva, si podemos hacer una derivación (sucesión de una o más producciones) de un símbolo no terminal tras la cual se vuelve a tener dicho símbolo entre los símbolos de la parte derecha de la derivación. A → α Aβ Si se tiene: A → A β se denomina recursividad izquierda A → α A se denomina recursividad derecha Un no terminal recursivo: si a partir de A se puede derivar una forma sentencial en que aparece él mismo en la parte derecha. AMBIGÜEDAD Una gramática es ambigua si el lenguaje que define contiene alguna sentencia que tenga más de un único árbol de análisis sintáctico. No es posible construir analizadores sintácticos eficientes para gramáticas ambiguas. Se debe evitar diseñar gramáticas ambiguas características, es sencillo encontrar una cadena con dos o más árboles. o Gramáticas con ciclos simples o menos simples: S→A S→a A→S o Alguna regla con una forma
24
E E … E
Con cualquier cadena de terminales y no terminales entre las dos E. Es posible que con algún terminal antes de la primera E o algún terminal después de la última E pueda producirse ambigüedad; por ejemplo, el if-then-else de Pascal. o SA SB AB o Producciones recursivas en las que las variables no recursivas de la producción puedan derivar a la cadena vacía: SHRS Ss Hh|e Rr|e o Variables que puedan derivar a la cadena vacía y a la misma cadena de terminales, y que aparezcan juntas en la parte derecha de una regla o en alguna forma esencial. SHR Hh|e Rr|h|e EJEMPLO: Sea una gramática cuyas reglas de producción son: E E + E | E * E | (ε) | número Se puede generar la tira 2+3*5 que tiene dos posibles árboles sintácticos.
Para solucionar esta ambigüedad se deben modificar las reglas de producción de la gramática. Se debe lo que es un factor y lo que es un término (producto de dos factores - monomio). Así se establece la jerarquía de precedencias de los operadores: + | * | ( ) | número
25
Una gramática es ambigua si se produce más de una derivación por la izquierda o por la derecha de la misma frase. De esta forma sólo hay un árbol sintáctico para 2+3*5:
n2
n3
ASOCIATIVIDAD Y PRECEDENCIA DE LOS OPERADORES Asociatividad: La forma de reflejar la asociatividad de un operador en la G es de la forma siguiente: cuando la asociatividad del operador es por la izquierda, la regla sintáctica en la que interviene dicho operador debe ser recursiva por la izquierda, y cuando es por la derecha debe tener recursión por la derecha. Ejemplo: 9 – 5 – 2 y a = b = c
Precedencia: Orden de cada operador con respecto a los demás operadores. La forma de reflejar la precedencia de los operadores aritméticos es bastante sencilla. Es necesario utilizar una variable en la gramática por cada operador de distinta precedencia. Cuanto más cerca esté la producción de la del símbolo inicial, menor será la precedencia del operador involucrado. Cercanía tiene que ver con el número de producciones que hay que llevar a cabo para llegar hasta esa regla desde el símbolo inicial. Parentización: Los paréntesis siempre tienen la máxima precedencia. Se usan para agrupar los operadores según la conveniencia del programador. Para incluirlos en la gramática, se añade una variable que produzca expresiones entre paréntesis y los operandos (números, variables, etc.) a la mayor distancia posible del símbolo inicial. En esta producción se pondrían los operadores unarios a no ser que tengan una precedencia menor. EJEMPLO: Supónganse los operadores +, -, con asociatividad por la izquierda (en 6-3-3), y * y / por la derecha, * / precedencia 1 y los paréntesis tienen la suma y la resta precedencia 2 máxima precedencia. La gramática que genera las expresiones con estos operadores y además recoge la asociatividad y la precedencia es la siguiente: 12-4-6/2/2
26
E E + T E E T E T T F T T F / T T F F ( E ) F número
TIPOS DE ANÁLISIS SINTÁCTICO Los algoritmos de análisis sintáctico general para gramáticas independientes del contexto tienen un coste temporal del orden de O(n3); lo que es demasiado elevado para un compilador, por lo que es necesario buscar subclases de gramáticas que permitan un análisis sintáctico en tiempo lineal. Desde el punto de vista de la teoría de Análisis Sintáctico, hay dos estrategias para construir el árbol sintáctico: o Análisis descendente: partimos de la raíz del árbol (axioma o símbolo inicial) y se van aplicando reglas por la izquierda de forma que se obtiene una derivación por la izquierda de la cadena de entrada. Para decidir qué regla aplicar, se lee un token de la entrada. Recorriendo el árbol de análisis sintáctico resultante, en profundidad de izquierda a derecha, encontraremos en las hojas del árbol los tokens que nos devuelve el A.L. en ese mismo orden. o Análisis ascendente: partiendo de la cadena de entrada, se construye el árbol de análisis sintáctico empezando por las hojas (donde están los tokens) y se van creando nodos intermedios hasta llegar a la raíz (hasta el axioma), construyendo así el árbol de abajo a arriba. El recorrido del árbol se hará desde las hojas hasta la raíz. El orden en el que se van encontrando las producciones corresponde a la inversa de una derivación por la derecha. Análisis Sintáctico Descendente Este intenta encontrar entre las producciones de la gramática una derivación por la izquierda del símbolo inicial para una cadena de entrada. Backtracking: Cuando el análisis sintáctico descendente (ASD) puede incluir retrocesos en el análisis. Análizadores Sintácticos Predictivos (ASP) Para que el algoritmo tenga una complejidad lineal, el analizador debe realizar una predicción de la regla a aplicar. Para ello, se debe conocer, dado el token de la entrada, a, que esté siendo analizado, y el no terminal a expandir A, cuál de las alternativas de producción A → α1 | α 2 |…| α n es la única posible que da lugar a que el resto de la cadena que se está analizando empiece por a. Dicho de otra forma, la
27
alternativa apropiada debe poderse predecir sólo con ver el primer símbolo que produce. Que forma deben tener las gramáticas a las que se puede aplicar. EJEMPLO: Sent if Expres then Sent while Expres do Sent begin Sent end En esta gramática sólo existe siempre una posibilidad de derivación, según sea el valor del token. Derivaciones Ejemplo 1) de gramáticas Define expresiones aritméticas expr expr op exp. expr expr) expr expr exp id op + op op * op / op ↑
Los símbolos terminales son: id +, -, *, /, ( ), ↑ Los símbolos no terminales son: exp y op Símbolo inicial expr
Derivaciones La visión derivativa de una descripción precisa de la construcción descendente de un árbol de análisis sintáctico. La idea central es que se considera una producción como una regla de reescritura, donde el no Terminal de la izquierda es sustituido por la cadena del lado derecho de la producción. Ejemplo: Gramática para expresiones aritméticas E → E + E | E * E | (E) | - E | id E → ε significa que una expresión precedida por un signo menos es también una expresión. Ejemplo: E → - E → -(E) → -(id) A esta secuencia de sustituciones se le llama derivación de –(id) a partir de E. Las cadenas de L (G) pueden contener sólo símbolos terminales de G.
28
Se dice que una cadena de terminales W está en L (G) si, y sólo si, S → W. A la cadena W sed le llama frase de G. Si el lenguaje puede ser generado por una gramática se dice que es lenguaje independiente del contexto. Ejemplo: La cadena –(id + id) es una frase de la G (1), por que existe la derivación: E → -E → -(E) → -(E + E) → -(id + E) → -(id + id) Derivación por la derecha: Donde el no Terminal más a la derecha se sustituye en cada paso. Ejemplo: E → -E → -(E) → -(E + E) → -(E + id) → -(id + id) Este tipo de gramáticas que son susceptibles de ser analizados sintácticamente de forma descendente y mediante un análisis predictivo, pertenecen al conjunto de gramáticas denominado LL (1). A partir de este tipo de G se puede construir automáticamente ASDP (Análisis Sintáctico Descendente Predictivos), que no son otra cosa que ASD sin retroceso. LL (1) donde: L = Análisis de izquierda a derecha de la cadena de entrada, L = Derivación por la izquierda y 1 = Basta con solo ver un token. Conjuntos de predicción Son conjuntos de tokens que ayudan a predecir qué regla se debe aplicar para la variable que hay que derivar. Se construyen, como veremos a continuación, a partir de los símbolos de las partes derechas de las producciones de la gramática. El analizador consulta el siguiente token en la entrada y si pertenece al conjunto de predicción de una regla (de la variable que hay que derivar), aplica esa regla. Si no puede aplicar ninguna regla, se produce un de error. CÁLCULO DE LOS CONJUNTOS DE PREDICCIÓN Los conjuntos de predicción de una regla se calculan en función de los primeros símbolos que puede generar la parte derecha de esa regla, y a veces (cuando esa parte genera la cadena vacía) en función de los símbolos que pueden aparecer a continuación de la parte izquierda de la regla en una forma sentencial. Cálculo del conjunto de PRIMEROS
29
La función PRIMEROS se aplica a cadenas de símbolos de la gramática (α ε (T υ N)* y devuelve un conjunto que puede contener cualesquiera terminales de la gramática y puede contener a la cadena vacía, ε. Definición: Si α es una forma sentencial compuesta por una concatenación de símbolos, PRIMEROS (α) es el conjunto de terminales ó ε que pueden aparecer iniciando las cadenas que pueden derivar (en cero o más pasos) de α. Definición formal: a PRIMEROS() si a ( T {} ) / * apara alguna tira Algoritmo 1. Si T, PRIMEROS () = {} 2. Si N: Inicialmente, PRIMEROS () = Si aparece la producción , PRIMEROS () = PRIMEROS () {} Si a1 a2 ... an entonces PRIMEROS() = PRIMEROS() PRIMEROS(a1 a2 ...an) y para el cálculo de PRIMEROS(a1 a2 ... an) pueden darse dos casos: 1. Si PRIMEROS(a1) entonces PRIMEROS() = PRIMEROS() PRIMEROS(a1) 2. Si PRIMEROS(a1) entonces PRIMEROS() = PRIMEROS() ( PRIMEROS(a1){}) PRIMEROS(a2...an) y de nuevo pueden darse estos dos casos para PRIMEROS(a2 ... an) y siguientes, hasta an. Si i, PRIMEROS(ai) entonces PRIMEROS() = PRIMEROS() {} 3. Para recoger todos los casos posibles habría que considerar que Si 1 | 2 | ... | n entonces PRIMEROS () = PRIMEROS(i) n
i 1
EJEMPLO 1: Sea la siguiente gramática para expresiones aritméticas con sumas y multiplicaciones: E T E’ E’ + T E’ T F T’ T’ F T’ F ( E ) ident
Cálculo de los PRIMEROS de todos los no terminales de esta gramática: PRIMEROS(E’) = { + , } PRIMEROS(T’) = { , } PRIMEROS(F) = { ( , ident } PRIMEROS(E) =(ETE’, TN) PRIMEROS(T) =(TFT’, FN) PRIMEROS(F) = { ( , ident }
30
EJEMPLO 2: Sea la gramática siguiente: A A a A B C D B b B C c C D d D C e
Calculamos los conjuntos de PRIMEROS de todas las variables de esta gramática: PRIMEROS(C) = { c , } PRIMEROS(B) = { b , } PRIMEROS(D) = PRIMEROS(d) PRIMEROS(Ce) = = { d } ( ( PRIMEROS(C) {} ) PRIMEROS(e) ) = { d , c , e } PRIMEROS(A) = PRIMEROS(Aa) PRIMEROS(BCD) =(*) PRIMEROS(BCD) (*) Puesto que el miembro se calcula como PRIMEROS(A) que aún es . = { b } PRIMEROS(CD) = { b , c } PRIMEROS(D) = { b , c , d , e }
Cálculo del conjunto de SIGUIENTES La función SIGUIENTES se aplica a variables de la gramática (A N) y devuelve un conjunto que puede contener cualesquiera terminales de la gramática y además puede contener un símbolo especial, “$”, que representa el final de la cadena de entrada. Esto es equivalente a añadir una producción adicional a la gramática en la que el axioma, S, es definido como X S$. Definición: Si A es un símbolo no terminal de la gramática, SIGUIENTES(A) es el conjunto de terminales que pueden aparecer a continuación de A en alguna forma sentencial derivada del símbolo inicial. Definición formal: a SIGUIENTES(A) si a ( T {$} ) / S * Aapara algún par de tiras ,.
Reglas para el cálculo del conjunto de los SIGUIENTES 1. Inicialmente, SIGUIENTES(A)= 2. Si A es el símbolo inicial, entonces SIGUIENTES(A)=SIGUIENTES(A) {$} 3. (s1) Para cada regla de la forma: B A entonces SIGUIENTES(A)=SIGUIENTES(A) PRIMEROS()-{} 4. (s2) Para cada regla de la forma: B A o bien B A en la que PRIMEROS() entonces 31
SIGUIENTES(A)=SIGUIENTES(A) SIGUIENTES(B) 5. Repetir los pasos 3 y 4 hasta que no se puedan añadir más símbolos a SIGUIENTES(A) NOTA: Las reglas (S1) y (S2) no son excluyentes. Primero habrá que intentar aplicar (S1) y luego (S2) Sólo en el caso de producciones del tipo B A, no tendrá sentido intentar aplicar (S1). X E$ SIGUIENTES(E) = F(E) y XE$ { ) , $ } S1
SIGUIENTES(E’) = E’+TE’ y ETE’ SIGUIENTES(E) SIGUIENTES(E’)== { ) , $ } S2
SIGUIENTES(T) = E’+TE’ PRIMEROS(E’){}SIGUIENTES(E)SIGUIENTES(E’) = S1
= {+} SIGUIENTES(E) SIGUIENTES(E’) = { + , ) , $ } SIGUIENTES(T’) = TFT’ y TFT’ SIGUIENTES(T) SIGUIENTES(T’) == { + , ) , $ } S2
SIGUIENTES(F)= TFT’yTFT’PRIMEROS(T’){}SIGUIENTES(T)SIGUIENTES(T’)= S1
= { } { + , ) , $ } = { , + , ) , $ }
Cálculo del conjunto PREDICT: La función PREDICT se aplica a producciones de la gramática (A a) y devuelve un conjunto, llamado conjunto de predicción, que puede contener cualesquiera terminales de la gramática y el símbolo “$”, pero nunca puede contener . Reglas para el cálculo del conjunto PREDICT PREDICT(A ) = Si PRIMEROS() entonces = (PRIMEROS()-{}) {SIGUIENTES(A)} sino = PRIMEROS() EJEMPLO: Supóngase la siguiente gramática: S AB s A aSc eBf B bAd
Calculamos los conjuntos de predicción utilizando la regla adecuada en cada caso: PREDICT(S AB) = (PRIMEROS(AB){}) SIGUIENTES(S) = { a , e , b , c , $ } PREDICT(S s) = PRIMEROS(s) = { s } PREDICT(A aSc) = PRIMEROS(aSc) = { a } PREDICT(A eBf) = PRIMEROS(eEf) = { e } PREDICT(A ) = (PRIMEROS(){}) SIGUIENTES(A) = { b , d , c , $ } PREDICT(B bAd) = PRIMEROS(bAd) = { b } PREDICT(B ) = (PRIMEROS(){}) SIGUIENTES(B) = { f , c , $ }
LA CONDICIÓN LL(1)
32
Para que una gramática pertenezca al conjunto de gramáticas LL(1) ha de cumplir la condición LL(1). Para que la regla a aplicar sea siempre única, se debe exigir que los conjuntos de predicción de las reglas de cada no terminal sean disjuntos entres sí. Si la gramática es LL(1) y se puede realizar su análisis sintáctico en tiempo lineal. La condición LL(1) es necesaria y suficiente para poder construir un ASDP para una gramática. Condición LL(1): Dadas todas las producciones de la gramática para un mismo terminal: A 1 | 2 | ... | n A N
se debe cumplir la siguiente condición: i, j ( i j ) PREDICT(Ai) PREDICT(Aj) =
Ejemplo 1: A a b B A B b B b B c
{a} {b,c} {b} {c}
EJEMPLO 2: Sea la siguiente gramática: E E + T T T T F F F num ( E )
PREDICT(E E+T) = PRIMEROS(E+T) = PRIMEROS(E) = { num , ( } PREDICT(E T) = PRIMEROS(T) = PRIMEROS(F) = { num , ( } PREDICT(T TF) = PRIMEROS(TF) = PRIMEROS(T) = { num , ( } PREDICT(T F) = PRIMEROS(F) = { num , ( } PREDICT(F num) = PRIMEROS(num) = { num } PREDICT(F (E) ) = PRIMEROS( (E) ) = { ( }
MODIFICACIÓN DE GRAMÁTICAS NO LL(1) Existen características que, en el caso de ser observadas en una gramática, garantizan que no es LL(1) (sin calcular los conjuntos de predicción). Si la gramática no es LL(1) no necesariamente debe tener alguna de estas características.
33
Existen métodos para modificar gramáticas que no son LL(1) y convertirlas en LL(1). ELIMINACIÓN DE LA AMBIGÜEDAD Cualquier gramática ambigua no cumple LL(1). Si la gramática no es ambigua no necesariamente es LL(1), pues puede presentar otros problemas. El problema de la ambigüedad es el más difícil de resolver pues no existe una metodología para eliminarla y tampoco hay otra fórmula para saber que una gramática es ambigua (sólo queda encontrar alguna sentencia que tenga dos árboles de análisis sintáctico distintos). La mejor opción cuando se presenta una gramática ambigua es replantear la gramática por una equivalente (que genere el mismo lenguaje). FACTORIZACIÓN IZQUIERDA Si dos producciones alternativas de un símbolo A empiezan igual, no se sabrá por cuál de ellas seguir, se trata de reescribir las producciones de A para retrasar la decisión hasta haber visto lo suficiente de la entrada, se soluciona uno de los problemas que tenia la gramática para no cumplir la condición LL (1) como para elegir la opción correcta. EJEMPLO: Sean las producciones: 1) Sent if Expr then Sent else Sent 2) Sent if Expr then Sent 3) Sent Otras Para expandir Sent no se sabe si 1) o 2) con sólo ver “if”. De hecho, un analizador sintáctico descendente no sabría hasta ver el cuarto símbolo de esta producción, si entonces llega else ya sabe que se trataba de la primera y si entra cualquier otro pero es tarde para el ASDP. Regla general para factorizar por la izquierda una gramática Para todos los no terminales, A, de la gramática, encontrar el prefijo más largo común a dos o más alternativas suyas. Si entonces sustituir todas las producciones. A 1 | 2 | … | n | i donde i representa a todas las alternativas que no empiezan por , por: A A’ | i A’ 1 | 2 | … | n
34
Repetir el paso anterior hasta que no haya 2 alternativas de un no terminal con un prefijo común. EJEMPLO: Sent if Expr then Sent else Sent Sent if Expr then Sent Sent Otras if Expr then Sent i Otras Con la gramática factorizada queda: Sent if Expr then Sent Sent’ Sent Otras Sent’ else Sent Sent’ ELIMINACIÓN DE LA RECURSIVIDAD IZQUIERDA Los analizadores sintácticos descendentes no pueden manejar gramáticas recursivas por la izquierda pues estarían en ciclos de recursividad infinita al ejecutarse. Cualquier gramática recursiva por la izquierda no cumple la condición LL (1). A A| A| … | Am| | | … | n
Sustituir por: A 1A’| 2A’|…| nA’ A’ α1A’|α2A’|…| αmA’ EJEMPLO: Eliminar la recursividad izquierda de la gramática de las expresiones aritméticas. 1º E E + T E T T 2º T T F | T / F | F F ( E ) | núm 1º E E + T | T A A | 2º T T F A A |
E T E’ E’+ T E’ | T F T’ T’F T’ |
Por tanto nos queda la siguiente gramática: E T E’ E’ + T E’ T E’ T F T’
35
T’ F T’ / F T’ F ( E ) | num IMPLEMENTACIÓN DE UN ANALIZADOR SINTÁCTICO DESCENDENTE RECURSIVO Es un método de análisis sintáctico descendente que sólo se puede aplicar en gramáticas LL (1) y por tanto es un analizador sintáctico descendente predictivo (ASDP). Consiste en un conjunto de funciones recursivas (una por cada variable de la gramática) que son diseñadas a partir de los elementos que definen cada una de las producciones de la gramática. La secuencia de llamadas al procesar la cadena de entrada define implícitamente su árbol de análisis sintáctico. Símbolo de preanálisis Si esta metodología es aplicable a las gramáticas LL (1) es porque basta ver un único token para saber qué hacer. Ese token se llama símbolo de preanálisis o LookAhead y será pedido al analizador léxico cada vez que se necesite. Este token el que se busque en los conjuntos de predicción. Función de emparejamiento (Match) Comprueba si el símbolo de preanálisis coincide con el terminal de la gramática que, de acuerdo con los elementos de la producción escogida debería aparecer en esa posición. También se encarga de la petición del siguiente token al analizador léxico si se da la coincidencia o invoca a la función de error en caso contrario. Estructura FUNCIÓN Emparejar ( Parámetro de entrada: token; Usa variable global preanálisis ) SI preanálisis coincide con token ENTONCES Pedir el siguiente preanálisis al analizador léxico SINO Error Sintáctico(Encontrado preanálisis, esperaba token) Si t es el token que el ASDR espera encontrar en la entrada y, la función Emparejar en “C” queda: void Emparejar ( int t ) { if ( t == preanalisis ) preanalisis = analex(); /* analex es el nombre que hemos dado al Analizador Léxico */ else ErrorSintáctico(preanalisis,t); } 36
Algoritmo para construir un ASDR 1) Escribir una función por cada símbolo no terminal de la gramática. Cada una llevará a cabo el análisis de las producciones de dicho no terminal. 2) Cuando este no terminal tenga distintas alternativas, para decidir durante su ejecución cuál de las producciones utilizar, se optará por aquella alternativa a cuyo conjunto de predicción pertenezca el token de preanálisis. EN CASO DE QUE Preanálisis PERTENEZCA A PREDICT(a1): ... proceder según alternativa a1 ... PREDICT(a2): ... proceder según alternativa a2 ... ... FIN Si el token de preanálisis no pertenece a ninguno de los PREDICT, entonces se considerará error sintáctico. 3) Si una de las alternativas para el no terminal que se está analizando es la cadena vacía (A → ε), en ese caso no se hará nada. 4) Para analizar cada alternativa, se aplican distintas metodologías a los símbolos de la parte derecha de la producción, en el mismo orden en el que aparecen, según si son terminales o no: - Para cada A Є N hacemos una llamada a su función correspondiente. - Para cada a Є T hacemos una llamada a la función Emparejar con a como parámetro. 5) La invocación o puesta en marcha del ASDR se realiza mediante una llamada al símbolo inicial de la gramática. Para hacer esa llamada se supone que el token de preanálisis habrá sido inicializado por una llamada previa al analizador léxico. EJEMPLO: Sea la siguiente gramática LL(1) con sus conjuntos de predicción: S A { a , $ } S s { s } A a S c { a } A { c , $ } Supondremos que: -
Están definidos los tokens a, c y s Se tiene definida una variable lexema como un array de caracteres Ya se tiene implementada la función emparejar
void S(void) { if ( preanalisis == a || preanalisis = FINFICHERO ) 37
A(); else if ( preanalisis == s ) emparejar(s); else ErrorSintactico(lexema,a,s,FINFICHERO); /* encontrado 'lexema', esperaba 'a', 's' o fin de fichero */ } void A(void) { if ( preanalisis == a ) { emparejar(a); S(); emparejar(c); } else if ( preanalisis == c || preanalisis = FINFICHERO ) ; /* producción epsilon */ else ErrorSintactico(lexema,a,c,FINFICHERO); } NOTA: A la función de error sintáctico se le suele pasar como argumentos el lexema que ha producido el error (el del token de preanálisis) y los que esperaba en su lugar (los terminales que aparezcan en la unión de todos los conjuntos de predicción de las reglas del no terminal al que pertenece la función). EJEMPLO 2: Sea G E T E’ E’ + T E’ T E’ T F T’ T’ F T’ / F T’ F ( E ) | num void E() { T(); E2(); } void E2() { switch ( preanalisis ) { case MAS : Emparejar(MAS); T(); E2(); break; case MENOS : Emparejar(MENOS); T(); E2(); berak; case RPAR : case FDF : /* E’ ® e */ break; default : ErrorSintactico(lexema,MAS,MENOS,RPAR,FDF); } } void T() {
38
F(); T2(); } void T2() { switch ( preanalisis ) { case POR : Emparejar(POR); F(); T2(); break; case DIV : Emparejar(DIV); F(); T2(); break; case MAS : case MENOS : case RPAR : case FDF : /* T’ ® e */ break; default : ErrorSintactico(lexema,POR,DIV,MAS,MENOS,RPAR,FDF); } } void F() { switch ( preanalisis ) { case NUM : Emparejar(NUM); break; case LPAR : Emparejar(LPAR); E(); Emparejar(RPAR); break; default : ErrorSintactico(lexema,NUM,LPAR); } } NOTA: Al final se debe comprobar que la cadena de entrada se ha analizado en su totalidad para dar como exitoso el análisis. Como se indica: token = analex(); S(); if (token != FINFICHERO) error(token,lexema,{FINFICHERO}); /* encontrado 'lexema', esperaba fin de fichero */ ANALIZADORES SINTÁCTICOS DESCENDENTES DIRIGIDOS POR TABLA Se puede construir un analizador sintáctico descendente predictivo utilizando una pila de símbolos (terminales y no terminales) en vez de haciendo llamadas recursivas. Para determinar qué producción debe aplicarse a la vista de un terminal (token de preanálisis), se buscará en una tabla llamada tabla de análisis.
39
Se debe construir la tabla (depende de la gramática) y posteriormente aplicar el algoritmo. Procedimiento para construir tablas de análisis LL (1) 1. Las filas de la tabla se etiquetan con las variables de la gramática. 2. Las columnas se etiquetan con los terminales y el símbolo de fin de entrada, $. a. [En cada celda de la tabla se va a colocar la regla que se debe aplicar para analizar la variable de esa fila cuando el terminal de esa columna (o $) aparezca en la entrada (ese terminal o $ debe pertenecer al conjunto de predicción de esa regla) ]. 3. Se calculan los conjuntos de predicción para cada regla. 4. Para cada regla A → α de la gramática, hacer:
Para cada terminal a PREDICT(A ), añádase A a Tabla[A,a.
5. Cada entrada no definida de Tabla será error sintáctico. NOTA: Al implementar el algoritmo no es necesario almacenar la regla completa en la tabla sino sólo los símbolos de su parte derecha (que es conveniente guardar al revés) o incluso es más eficiente almacenar un número de regla que haga referencia a otra tabla con los símbolos de las partes derechas de las reglas. EJEMPLO: Sea G X E $ E T E’ E’ + T E’ | T E’ | T F T’ T’ F T’ | / F T’ | F ( E ) | id
1: PREDICT(E T E’) = { ( , id } en las celdas [E,(] y [E,id] añadir ETE’ 2: PREDICT(E’+ T E’) = {+} en la celda [E’,+] añadir E’+TE’ 3: PREDICT(E’T E’) = {} en la celda [E’,] añadir E’TE’ 4: PREDICT(E’) = { ) , $ } en la celda [E’,$] añadir E’ 5: PREDICT(T F T’) = { ( , id } en las celdas [F,(] y [F,id] añadir TFT’ 6: PREDICT(T’ F T’) = {} en la celda [T’,] añadir F’FT’ 7: PREDICT(T’ / F T’) = {/} en la celda [T’,/] añadir F’/FT’ 8: PREDICT(T’) = {+,,),$} en las celdas [T’,+] [T’, ] [T’,)] [T’,$] añadir T’ 9: PREDICT(F( E ) ) = { ( } en la celda [F,)] añadir F (E) 10: PREDICT(Fid) = {id} en la celda [F,id] añadir F id Todas las celdas vacías se marcan como error sintáctico.
40
Tener en cuenta es que este tipo de analizador es predictivo, esto es que sólo puede construir si la gramática a analizar es LL (1). Esto en la tabla se refleja en el hecho de que no aparezcan dos producciones en la misma casilla. EJEMPLO: Sea una gramática para las sentencias IF en Pascal: Sent if Expr then Sent Sent’ otras Sent’ else Sent Expr lógico Su tabla es:
Podemos observar que la gramática es ambigua pues existen dos producciones en la casilla señalada. Una vez que se tiene la tabla de análisis ya se puede construir el ASDP. Algoritmo de ejecución del Analizador Descendente Dirigido por Tabla: Entrada: cadena de elementos léxicos devueltos por el A.L. Salida: producciones que construyen su árbol de análisis sintáctico Pasos: push($) push(S) REPETIR A := Pila[tope] /* el símbolo que haya en el tope de la pila */ a := analex( ) /* a es el símbolo de preanálisis */ SI A es un terminal o $ ENTONCES SI A = a ENTONCES pop A a := analex( ) SINO Error Sintáctico ( encontrado lexema de a, esperaba A )
41
FINSI SINO /* A es un no terminal */ SI Tabla[A,a= A c1 c2 ... ck ENTONCES pop(A) DESDE i := k HASTA 1 HACER push(ci) FINDESDE /* A efectos de traza se puede indicar que se usa A c1 c2 ... ck */ SINO n Error Sintáctico(encontrado lexema de a, esperaba PREDICT( A i 1 i ) ) FINSI FINSI HASTA A = $ /* La pila está vacía */ EJEMPLO: La traza se realizará sobre la gramática LL(1) de las expresiones aritméticas, tomando la tabla descrita antes. La entrada para la traza es: “id + id id $”.
42
La columna de PILA muestra el contenido de la pila en cada momento, quedando el fondo a su izquierda y la cima a su derecha, donde se van colocando los símbolos de las partes derechas de las producciones en orden inverso a como aparecen en dichas producciones. La columna ENTRADA representa lo que en cada paso resta por analizar de la cadena de entrada. El primer símbolo de la izquierda representa el símbolo de preanálisis. Cuando este símbolo coincide el terminal de la pila se eliminan ambos (el tope y el preanálisis) avanzando el análisis al siguiente símbolo de la entrada. La columna SALIDA muestran los emparejamientos de tokens que se realizan y las producciones que se van aplicando de la tabla de análisis para ir actualizando el contenido de la pila y construyendo el árbol de análisis sintáctico que se muestra a la derecha de la tabla. EJEMPLO: Sea G: S C A B S a C b A a S d A B b B C c
{c} {a} {a} {b,d,$} {b} {d,$} {c}
La tabla de análisis:
43
La traza del análisis para la cadena “cacdb” sería:
44