1

BENEMRITA UNIVERSIDAD AUTONMA DE PUEBLA

FACULTAD DE CIENCIAS DE LA COMPUTACIN

NOTAS DE

COMPILADORES

ANLISIS LXICO Y SINTCTICO

Otoo 2013

Captulo I

2

Visin Histrica del Desarrollo de los Compiladores

En 1946, se desarrolla el primer ordenador digital ejecutaban instrucciones en cdigos

numricos (lenguaje de mquina) interpretado por un secuenciador cableado.

Posteriormente, surgen los ensambladores (claves ms fciles de recordar) en donde la propia

mquina realizaba el proceso mecnico de traduccin.

A pesar de todo el lenguaje ensamblador segua siendo de una mquina.

Las lneas de investigacin para crear leguajes ms fciles e independientes de la mquina

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 aos en realizarse y era muy sencillo.

El FORTRAN an estaba muy influenciado por la mquina en la que iba ser implementado.

Las lneas de investigacin continan hasta 1958 un grupo de investigadores junto con J. Backus

crean ALGOL 58 (Algorithmic Language). Despus ALGOL 60, LAGOL 68 lenguaje modular

estructurado en bloques.

En ALGOL aparecen por primera vez conceptos de los nuevos lenguajes algortmicos.

a) Definicin de la sintaxis en notacin BNF (Backus Naur Form): Gramtica independiente del contexto. Ejemplo:

prop if(expr) prop else prop

b) Formato libre: c) Declaracin explcita de tipo para todos los identificadores d) Estructuras iterativas e) Recursividad f) Paso de parmetros por valor y por referencia g) Estructura de bloques

Paralelamente, se avanzaba en la tcnica de compilacin. En 1958 Strong y otros proponen

una solucin al problema de que un compilador fuera utilizable por varia mquinas 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 cdigo para la mquina objeto

3

El puente de unin 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 mquinas bastaba modificar su back_end.

Aunque no tuvo xito la definicin de UNCOL la divisin del compilador fue un adelanto

importante. En eso aos se van proponiendo las bases par la divisin de tarea en un compilador. As

en 1959 Rabin y Scott proponen el empleo de autmatas deterministas y no deterministas para el

reconocimiento lexicogrfico de los lenguajes.

En 1975, con la aparicin de LEX, surge el concepto de analizadores lxicos a partir de expresiones

regulares.

Avance Sintctico

A partir de los trabajos de Chomsky se produce una sistematizacin de la sintaxis de los

lenguajes de programacin, y con ello un desarrollo de diversos mtodos de anlisis sintctico.

Con la notacin BNF desarrollada en 1960 por Backus, modificada en 1963 por Naur y formalizada

por Knuth en 1964 se tiene una gua para el desarrollo del anlisis sintctico. Los diversos mtodos

sintcticos ascendentes y descendentes se desarrollaron durante los 60s.

En 1959, Sheridan describe un mtodo de parsing de FORTRAN que introduca parntesis

adicionales alrededor de los operandos para ser capaz de analizar las expresiones. Ms adelante,

Floyd introduce la tcnica de precedencia de operador. A mitad de los 60s, Knuth define las

gramticas LR (ascendente).

En 1968, se estudia y definen las gramticas LL (ascendentes).

Debido a la sencillez y capacidad de anlisis para una gran variedad de lenguajes, la tcnica

de parsing LR es la elegida par los generadores automticos de parsers. A mediados de los 70s

Johnson crea el generador de analizadores sintcticos YACC.

Avance Semntico

Junto al anlisis sintctico, tambin se fue desarrollando el anlisis semntico. En los

primeros lenguajes (FORTRAN y ALGOL 60) los tipos posibles de datos eran muy simples y la

comprobacin de tipos era muy sencilla.

Avance de Optimizacin

La inclusin 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 parmetros por valor y referencia,

con la aparicin de lenguajes que permiten la localizacin dinmica de datos, se desarrolla otra

forma de manejo de memoria.

La tcnica de optimizacin apareci desde el desarrollo del primer compilador FORTRAN.

Backus comenta que se tena el temor de optimizaciones dependientes de la mquina e

independientes de sta. Entre las dependientes se pueden encontrar:

4

Localizacin de registros Uso de instrucciones propias de la mquina Reordenamiento de cdigo

Entre las independientes se pueden encontrar:

Propagacin de valores Arreglo de expresiones Eliminacin de redundancia

En la actualidad un compilador es una herramienta bien conocida, dividida en diversas fases.

Algunas se pueden generar automticamente (analizador lxico y sintctico) y otras requieren mayor

atencin (traduccin y generacin de cdigo)

De todas formas, todava se llevan a cabo varias vas de investigacin. El hecho de que surjan

nuevos lenguajes, como los de 5 generacin implica la revisin 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.

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

Intrprete. Toma una sentencia del programa fuente de un lenguaje de alto nivel y la traduce al

cdigo equivalente y al mismo tiempo lo ejecuta.

Histricamente con a la escasez de memoria en los primeros ordenadores, se puso de moda el

uso de intrpretes pero, la mejor informacin sobre los errores por parte del compilador as como una

mayor velocidad de ejecucin del cdigo resultante hizo que los compiladores se impusieran.

Hoy en da, con el problema de la memoria prcticamente 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 compilacin genera cdigo equivalente al bucle, interpretndolo se

traduce tantas veces una lnea como veces se repite el bucle

Traductor Lenguaje

Objeto

Lenguaje

fuente

5

c) El compilador tiene un visin global del programa, por lo que la informacin de mensajes de error es ms detallada.

Ventajas del intrprete vs el compilador

a) Un intrprete necesita menos memoria que un compilador b) Permiten una mayor interactividad con el cdigo 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 aadiendo las cabeceras necesarias y las

funciones de librera utilizadas por el programa fuente.

El depurador: si se gener el programa objeto, permite seguir paso a paso la ejecucin de un programa.

El ensamblador: convierte del lenguaje a un ejecutable.

Tipos de Compiladores

a) Ensamblador: Tiene una estructura sencilla. b) Compilador cruzado: Genera cdigo en lenguaje objeto para una mquina diferente de la

que se esta utilizando para compilar.

c) Compiladores con montador: Compila distintos mdulos de forma independiente y despus los enlaza.

d) Autocompilador: Compilador de compiladores, aunque tiene la dificultad de unir la generacin de cdigo con la parte de anlisis. Lo que s se han desarrollado son:

LEX generador de analizadores lxicos YACC generador de analizadores sintcticos

Aunque los analizadores que generan no son muy eficientes.

e) Descompilador: Traduce cdigo mquina a un lenguaje de alto nivel. Si hay optimizacin es posible descompilar.

Estructura de un Compilador

Para la realizacin del proceso de traduccin es necesario dividir el compilador en varias

fases.

6

Etapas que constituyen el Proceso de Compilacin

Al principio el tamao del archivo ejecutable y la memoria utilizada por el compilador era un

recurso crtico, por lo que cada fase lea un fichero escrito por la fase anterior y produca 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 aos 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 prdida considerable de tiempo

(incluso en los sistemas modernos).

Las fases se agrupan en 2 partes:

1) front_end: fases de anlisis 2) back_end: fases de generacin y optimizacin de cdigo

Estas dos se comunican mediante una representacin intermedia generada por el front_end

que puede ser:

una representacin de la sintaxis del programa (un rbol sintctico abstracto) un programa en lenguaje intermedio

Anlisis sintctico

Anlisis lxico

Anlisis semntico

Generacin de

cdigo intermedio

Optimizacin de cdigo

Generacin de cdigo

Programa objeto

Manejo

de errores

Manejo de la

Tabla de

smbolos

Programa fuente

7

El front end depende del lenguaje fuente y casi siempre es independiente de la mquina

objeto. El back end depende del lenguaje objeto y debe ser independiente del lenguaje fuente

(excepto quiz para algn tipo de optimizacin).

Anlisis Lxico

Tambin conocido como scanner, lee los caracteres uno a uno y va formando grupos de

caracteres con alguna relacin entre s (tokens), que sern la entrada para la siguiente etapa.

Tipos de tokens:

Tiras especficas: palabras reservadas, ; , , =, +, -, and, etc. Tiras no especficas: identificadores, constantes o etiquetas.

Un token tiene dos partes:

Tipo de token Valor

Las tiras especficas solo tienen tipo (lo que representan).

Las tiras no especficas tienen tipo y valor.

Ejemplo: si contador es un identificador

El tipo es identificador

Su valor es la cadena contador

El analizador lxico permite saber si es un lenguaje de formato libre o no. Frecuentemente va

unido al analizador sintctico en la misma pasada, funcionando como una subrutina de este.

El analizador lxico ignora elementos innecesarios para la siguiente fase, como tabuladores,

comentarios, espacios en blanco, etc.

Ejemplo: entrada CONT * + CONT

Anlisis lxico id por mas id

Anlisis sintctico

Tambin llamado Parser comprueba si los tokens van llegando en el orden correcto (orden

permitido). Su salida sera un rbol sintctico.

Sus funciones son:

Aceptar lo que es vlido sintcticamente y rechazar lo que no lo es Hacer explcito el orden jerrquico 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 traduccin (traduccin dirigida por sintaxis)

8

Anlisis semntico

Es ms difcil de formalizar que el sintctico. Se encarga de comprobar que lo que va leyendo

es vlido.

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 semntico. Esto es un rbol sintctico en donde cada rama ha adquirido

el significado que debe tener.

Para el caso de lo operadores polimorficos (un smbolo con varios significados), el anlisis

semntico determina cul es el aplicable.

Por ejemplo:

A:= B + C

En Pascal + sirve para sumar enteros, reales, concatenar cadenas de caracteres y unir

conjuntos.

Por ejemplo:

:=

posicin +

inicial *

velocidad entero real

60

9

Generacin de Cdigo 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 mquinas en las que ya exista un

compilador de C relativamente poco esfuerzo.

La generacin de cdigo intermedio transforma un rbol de anlisis sintctico (semntico) en

una representacin en lenguaje intermedio.

Una forma es usando el cdigo de tres direcciones.

Ejemplo:

temp1:= enteroreal (60)

temp2:= id3 * temp1

temp3:= id2 + temp2

id:= temp3 :=

id 1 +

id2 *

id3 enteroreal

60

Optimizacin de Cdigo

Esta fase se aade para conseguir que el programa objeto sea ms rpido en la ejecucin 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) temp1:= id3 * 60.0 temp2:= id3 * temp1 optimizacin de cdigo

10

2) repeat B:= 1 B:= 1 repeat

A:= A B A:= A B

until A:= 0 until A:= 0

Generacin de Cdigo

Consiste en generar cdigo objeto que consiste en cdigo mquina o ensamblador.

Ejemplo:

MOVF id3, R2

MULF #60.0, R2

MOVF id2, R1

ADDF R2, R1

MOVF R1, id1

Tabla de Smbolos

Utilizada para que el compilador guarde y use la informacin 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 rpidos para que el compilador sea eficiente.

Ejemplo:

1 Posicin

2 Inicial

3 Velocidad

4

Manejo de Errores

Es una de las funciones ms importantes de un compilador, aunque es lo que ms dificulta su

realizacin.

Se utiliza ms en el anlisis sintctico y semntico. Es una tarea difcil 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:

11

1) Pararse al detectar el primer error 2) Detectar todos los errores de una pasada

Cmo se especfica un Compilador?

Cuando se va a disear un compilador, es necesario especificar:

a) el lenguaje fuente b) el lenguaje objeto c) el sistema operativo sobre el que funcionar d) el lenguaje usado para construirlo

La especificacin del lenguaje fuente se divide en tres partes:

1) Especificacin lxica: se especifican los componentes lxicos (tokens) o palabras del lenguaje, para ello se usan expresiones regulares.

2) Especificacin sintctica: se detalla la forma o estructura (la sintaxis) que tendrn los programas en este lenguaje fuente. Para lo cual se utiliza una gramtica independiente del

contexto en notacin BNF.

3) Especificacin semntica: se describe el significado de cada construccin sintctica y las reglas semnticas que deben cumplirse.

Tarea 1: Aplicaciones de las Tcnicas Aprendidas en Compiladores

a) Desarrolla de interfaces textuales: cualquier programa cuya interaccin con el usuario sea algo ms que pulsar teclas.

b) Tratamiento de ficheros de texto con informacin estructurada: lenguajes como PERL y TCL.

c) Procesadores de texto: procesadores como VI o EMACS usan expresiones regulares. d) Diseo e interpretacin de lenguajes para el formateo de texto y descripcin de grficos:

HTML, PostScript.

e) Gestin de base de datos: exploracin y proceso de ficheros. f) Procesamiento de lenguaje natural. g) Traduccin de formatos de fichero: estructura de datos de ficheros con registros de

programas obsoletos se pueden actualizar a formatos actualizados.

h) Reconocimiento de formas: deteccin de patrones en texto, reconocimiento automtico del habla o la visin por computador.

El Papel del Analizador Lxico

El analizador lxico es el nico que gestiona con el fichero de entrada para construir

elementos lxicos llamados tokens.

El analizador lxico ignora tabuladores, espacios en blanco, cambios de lnea, comentarios,

etc.

Por qu separar el anlisis lxico y sintctico?

12

1) El diseo de las partes posteriores al anlisis queda simplificado. 2) Con fases separadas se pueden aplicar tcnicas especficas para cada fase, que son ms

eficientes en sus respectivos dominios.

3) Se facilita la portabilidad. Si se quiere cambiar alguna caracterstica del alfabeto del lenguaje, slo tiene que cambiar el analizador lxico.

Ejemplo: si tomamos las expresiones

6 2 * 30 / 7 Tienen la misma estructura (analizador sintctico) pero los caracteres no son

6 - 2* 30/7 pero los caracteres no son los mismos

8-2*3/5

Es por eso que el procesamiento de caracteres se deja en manos del analizador lxico.

Ejemplo: las tres expresiones anteriores son representadas por el analizador lxico 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 lxico debe rechazar cualquier texto en el que aparezcan caracteres ilegales (no

recogidos en el alfabeto) o combinaciones ilegales (no permitidas por las especificaciones lxicas).

Errores Lxicos

Pocos son lo errores de esta etapa, pues el compilador tiene todava una visin muy local del

programa.

Por ejemplo:

Si encuentra y asla 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 anlisis.

Los errores que tpicamente detecta el analizador lxico 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 asignacin pero que no permita : solo.

Cuando el analizador lxico encuentra un error, lo habitual es parar su ejecucin e informa,

pero hay una serie de posibles acciones para anotar los errores, recuperarse de ellos y seguir

trabajando.

13

Tarea 2: Investigar acerca del manejo de buffers de entrada pareja de buffers y centinelas.

Ignorar los caracteres no vlidos hasta formar un token segn los patrones dados. Borrar los caracteres extraos. 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 anlisis.

Funcionamiento de Analizador Lxico

1) La primera funcin del analizador lxico es procesar la cadena de caracteres y devolver pares (token, lexema). Debe ser una subrutina del analizador sintctico.

2) Maneja el fichero del programa fuente; es decir: abrirlo, leer sus caracteres y cerrarlo. Tambin 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 situacin de error este es el que site el error en el programa fuente

(tal lnea, tal posicin). Lleva la cuenta de las lneas procesadas.

5) Preproceso de macros, definiciones, constantes y rdenes de inclusin 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 nmeros el

analizador lxico debe leer caracteres hasta que lea uno que no pertenece a la categora del token que

se est leyendo: este ltimo caracter debe devolverse al buffer de entrada para ser ledo en primer

lugar en la prxima 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 ningn otro

Analizador

lxico

Analizador

sintctico

Tabla de smbolos

Componente lxico

Obtn el siguiente

componente lxico

Programa

fuente

14

1 2 3

0 1

[0-9]

*Entero otro

x

*

Transicin

Estados

Transicin

No obligatorio (repeticin)

Retroceso de un estado

El analizador lxico debe intentar siempre leer el token ms 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.

Ejemplo: !> no es vlido pero

!es vlido

Para especificar correctamente el funcionamiento de un analizador lxico se debe utilizar una

mquina de estados, llamada Diagrama de Transiciones (DT), muy parecido a un autmata finito

determinista con las siguientes diferencias:

Un ADF slo 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 aceptacin) el

token ledo y dejar el buffer de entrada preparado para la siguiente llamada. Un DT no puede

tener estados de absorcin (cadenas incorrectas en AFDs)

En un DT se considerar que las entradas para las que no hay transicin desde cada estado son error.

De los estados de aceptacin 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 patrn. En este ltimo estado (al que se llega con la transicin

especial a otro) se debe devolver al buffer de entrada el caracter ledo 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 aceptacin.

Ejemplo: Reconocedor de nmeros enteros sin signo mediante la expresin regular [0-9]+ = digito+

DT

Otro: significa cualquier otro caracter del alfabeto del lenguaje que no est en el rango [0-9]

Si durante el recorrido del autmata se produce una transicin no autorizada o la tira de

entrada finaliza en un estado de no aceptacin, el analizador informara del error.

[0-9] [0-9]

x

15

El analizador suele tener unos subprogramas auxiliares encargados de gestionar el buffer

(tcnicas de doble buffer, doble salto de lnea, , etc.) y de ir volviendo caracteres al buffer de

entrada cada vez que el procedimiento de reconocimiento y aislamiento lo requiera.

Identificacin de Palabras Reservadas

El problema es como reconocer palabras reservadas si responden al mismo patrn que los

identificadores, pero son tokens diferentes al token identificador.

Existen dos enfoques para resolver este problema:

1) Resolucin Implcita: Considerar que todos son identificadores y buscarlos en una tabla.

2) Resolucin Explcita: Se indican todas las expresiones regulares de todas las palabras reservadas y se integran los DT resultantes de sus especificaciones lxicas en

la mquina reconocedora.

Para 1) en definitiva, las palabras reservadas se toman como lexemas particulares del patrn

del identificador. Para esto en el AL.

Primero inicializar la tabla de smbolos con todas las palabras reservadas (por orden alfabtico).

Cuando encuentre identificador se revisar la tabla de smbolos. 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 aadido a la tabla de smbolos.

Ejemplo: cont

Tabla de smbolos

do Pal. reservada

end Pal. reservada

for Pal. reservada

while Pal. reservada

cont Identificador

Cuando la deteccin es explicita. Las especificaciones lxicas de las palabras reservadas,

(tiras especficas) constan de concatenaciones de caracteres y pueden ser siempre prefijos de

identificadores (por ejemplo do y dos (identificador).

Cuando un elemento lxico es prefijo de otro y ambos son tiras especificas, aparecen estados

de aceptacin que partirn de estados intermedios.

Zona

de

Palabras Reservadas

Zona de identificadores

16

Ejemplo 1: Construir un diagrama de transiciones para el reconocimiento de identificadores,

nmeros enteros sin signo y palabras reservadas do y done.

Notacin

d = dgito, l = letra, t = otro, f = otro alfanumrico (dgito o letra), an = ir al estado n

Ejemplo 2: Construir un diagrama de transiciones para el reconocimiento de nmeros enteros con

signo negativo o si n signo.

(ER: (- | E) d+ y los operadores suma (+) e incremento (++)

Notacin

d = dgito, 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 nmeros en notacin cientfica

ejemplo 3 5 cientfico signo d+ E signo d+

Ejercicio 3: Construir un diagrama de transiciones para el reconocer nmeros reales dgitos+

(.dgitos+)

Ejercicio 4: Construir un diagrama de transiciones para el reconocer los siguientes componentes

lxicos 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

lxicos read, print, palabras reservadas pradir, redir, ident, raya (_), punto ( . )

Ejercicio 7: Construir un diagrama de transiciones para el reconocer los siguientes operadores

lgicos and, or, not.

17

1 2 3

[0-9]

*Entero otro

Implementacin del Analizador Lxico

La forma de implementar el Diagrama de Transiciones es mediante la construccin 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 aadir el token que se reconoce.

Ejemplo:

Estado

Entradas

[0-9] _ otro

# de retroceso

token retroceso

1 2 0 0

2 2 0 - -

3 0 Entero 1

Tabla de Transiciones del ejemplo 1

Entradas

Estado l d d o n e t 1 2 4 6 2 2 2 0

2 2 2 2 2 2 2 2

3 0 0 0 0 0 0 0

4 $ 4 $ $ $ $ $

5 0 0 0 0 0 0 0

6 2 2 2 7 2 2 3

7 2 2 2 2 9 2 8

8 0 0 0 0 0 0 0

9 2 2 2 2 2 10 3

10 2 2 2 2 2 2 11

11 0 0 0 0 0 0 0

Una vez que se tiene esta, el analizador lxico la recorrer cada vez mediante un bucle con la

sentencia.

Estado:= Tabla de Transiciones [Estado, Entrada].

[0-9]

18

El Analizador intentar llegar a un estado de aceptacin, en el que restaura la entrada segn el

retroceso.

Prioridad de tokens

Dar prioridad al token para el que encontramos el lexema ms largo. Ejemplo Do / DOT se toma (DOT)

Si el lexema es el mismo que se puede asociar a dos tokens, estos estarn definidos en un orden (el primero).

Ejemplo:

while Palabra reservada l (l | d) identificador

As que el Analizador Lxico 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

PROYECTO 1: Hacer un Analizador Lxico para:

ALGOL ADA MODULA II

Que por lo menos contenga:

Tipos de datos Constantes Variables (Identificadores)

* Suma

incremento

* Entero

19

Operadores Sentencias de control (Decisin y Repeticin) Funciones Paso de parmetros

Ejercicio 7: Hacer el DT, TT para reconocer nmeros decimales, octales y binarios

d = 0 | 1 || 9

oct = 2 | 3 || 7

dd = 8 | 9

bin = 0 | 1

Tabla de Smbolos

El Analizador Lxico guarda una entrada de la tabla de smbolos el lexema correspondiente a

los identificadores (las variables).

Las fases posteriores del compilador pueden aadir a esta entrada informacin, como el tipo

de identificador, su uso (por ejemplo, procedimiento, variable o etiqueta) y su posicin en la

memoria.

Gran parte de la deteccin y recuperacin de errores en un compilador se centra en la fase de

anlisis sintctico.

El analizador sintctico debe hacer lo siguiente:

Informar de los errores con claridad y exactitud Recuperarse de cada error rpido para detectar los errores posteriores No retrasar de manera significativa el proceso de programas correctos

Existen varia tcnicas para que el Analizador Sintctico se recupere de fallos, pero:

Una recuperacin inadecuada puede introducir una avalancha de errores introducidos por los cambios hechos al estado del analizador sintctico

La recuperacin del error sintctico puede introducir errores semnticos

Tarea 1: Estrategias de recuperacin de Errores.

20

Captulo II

Anlisis Sintctico (PARSER)

Su funcin principal es construir una representacin interna del programa.

Agrupa los lexemas suministrados por el A.L. con el fin de reconocer frases.

Determina si el programa es sintcticamente correcto. Esto es si la sucesin de smbolos que representan los tokens es generada por la gramtica correspondiente al lenguaje.

Los tokens los agrupa de acuerdo a producciones especificadas por la GLC.

La sintaxis se especifica con GLC.

La forma ms habitual de representar la sintaxis de un programa es el rbol de anlisis sintctico y el A.S.

construye una derivacin 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 tcnicas (eficiente y complejo) 2. Utilizando un generador de A.S., por ejemplo YACC (ineficiente y fcil)

2.1 Notacin EBNF (Extended Backus-Naur Form).

Esta se usa con el objetivo de reducir el nmero de producciones en las gramticas.

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 dgito

2.- { }, lo que aparece entre llaves se repite de cero a n veces.

21

Ejemplos: a) Lista_parmetros parmetro {, parmetro>

b) tren locomotora {vagn }

3.- Llaves con repeticin especificada: { }yx: lo que aparece entre llaves se repite de x a y veces.

Ejemplo: tren con 3, 4 5 vagones: tren locomotora { vagn }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 expresin THEN sentencia

[ ELSE sentencia ]

2.2 Gramtica GLC o BNF

Sea G = (N, T, S, P) es una 4- tupla donde:

N = conjunto de no terminales: Genera ms de un nica cadena

T = conjunto de terminales: Genera una nica cadena

P = conjunto de producciones: Regla que establece una transformacin

S = Smbolo 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 smbolo inicial (string de smbolos

gramaticales).

Frase: Cualquier forma de frase con solo elementos terminales

22

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 Cadena Frase La perro est lejos Cadena - Frase El gata est cerca 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 minsculas del abecedario o Smbolos de operacin y puntuacin o Dgitos o Palabras en negrita: perro, begin

Son no Terminales: o Primeras maysculas del abecedario o Palabras en cursiva: sujeto, expresin

La S, suele representar el smbolo inicial Letras griegas minsculas representan formas de frase

o As en un GLC una produccin de escribe A B Parte izq. Parte der.

Varias producciones con igual parte izquierdo se agrupan en una produccin con alternativas.

Diseo de Gramticas para Lenguajes de Programacin

Como se plasma en el aspecto de las reglas sintcticas algunas propiedades de los operadores

y operandos en los lenguajes de programacin.

RECURSIVIDAD

Una dificultad a la hora de disear un compilador es que debe procesar correctamente un

nmero infinito de programas distintos.

Por otro lado, la especificacin sintctica de un lenguaje debe ser finita. El concepto que hace

compatible ambas afirmaciones

Recursividad. Permite definir sentencias complicadas con un nmero pequeo de sencillas reglas de

produccin.

23

EJEMPLO:

Formar un tren con locomotora y un nmero cualquiera de vagones detrs.

tren locomotora tren locomotora vagn tren locomotora vagn vagn . . .

Usando recursividad manera:

1) Regla base (no recursiva) tren locomotora

2) Una o ms reglas recursivas tren tren vagn

Con esto no necesitamos infinitas reglas de produccin.

Estructura de la recursividad

1. Regla no recursiva que se define como caso base. 2. Una o ms reglas recursivas que permiten el crecimiento a partir del caso base.

EJEMPLO 1:

La gramtica para describir un identificador escrita como GLC, podra ser:

N = { Letra, Dgito, Identificador}

T = { a, b, c,..., z, 0, 1,..., 9 }

S = Identificador

P = { Letra a ...

Letra z Dgito 0 ...

Dgito 9 Identificador Letra Identificador Identificador Letra Identificador Identificador Dgito }

As, el rbol sintctico de id02a sera:

Infinitas reglas

de produccin

24

Definicin: Una gramtica se dice que es recursiva, si podemos hacer una derivacin (sucesin de

una o ms producciones) de un smbolo no terminal tras la cual se vuelve a tener dicho smbolo entre

los smbolos de la parte derecha de la derivacin.

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.

AMBIGEDAD

Una gramtica es ambigua si el lenguaje que define contiene alguna sentencia que tenga ms

de un nico rbol de anlisis sintctico.

Se debe evitar disear gramticas ambiguas caractersticas, es sencillo encontrar una cadena con dos

o ms rboles.

o Gramticas con ciclos simples o menos simples: S A S a A S

o Alguna regla con una forma

No es posible construir analizadores sintcticos eficientes para gramticas ambiguas.

25

E E E

Con cualquier cadena de terminales y no terminales entre las dos E. Es posible que con algn

terminal antes de la primera E o algn terminal despus de la ltima E pueda producirse

ambigedad; por ejemplo, el if-then-else de Pascal.

o S A S B

A B

o Producciones recursivas en las que las variables no recursivas de la produccin puedan derivar a la cadena vaca:

S H R S

S s

H h | e

R r | e

o Variables que puedan derivar a la cadena vaca y a la misma cadena de terminales, y que aparezcan juntas en la parte derecha de una regla o en alguna forma esencial.

S H R

H h | e

R r | h | e

EJEMPLO:

Sea una gramtica cuyas reglas de produccin son:

E E + E | E * E | () | nmero

Se puede generar la tira 2+3*5 que tiene dos posibles rboles sintcticos.

Para solucionar esta ambigedad se deben modificar las reglas de produccin de la gramtica.

Se debe lo que es un factor y lo que es un trmino (producto de dos factores - monomio). As se

establece la jerarqua de precedencias de los operadores:

+ |

* |

( ) | nmero

26

Una gramtica es ambigua si se produce ms de una derivacin por la izquierda o por la

derecha de la misma frase.

De esta forma slo hay un rbol sintctico para 2+3*5:

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 sintctica en la que interviene

dicho operador debe ser recursiva por la izquierda, y cuando es por la derecha debe tener recursin

por la derecha. Ejemplo: 9 5 2 y a = b = c

Precedencia: Orden de cada operador con respecto a los dems operadores.

La forma de reflejar la precedencia de los operadores aritmticos es bastante sencilla. Es necesario

utilizar una variable en la gramtica por cada operador de distinta precedencia. Cuanto ms cerca

est la produccin de la del smbolo inicial, menor ser la precedencia del operador involucrado.

Cercana tiene que ver con el nmero de producciones que hay que llevar a cabo para llegar hasta esa

regla desde el smbolo inicial.

Parentizacin: Los parntesis siempre tienen la mxima precedencia. Se usan para agrupar los operadores segn la conveniencia del programador.

Para incluirlos en la gramtica, se aade una variable que produzca expresiones entre parntesis y los

operandos (nmeros, variables, etc.) a la mayor distancia posible del smbolo inicial. En esta

produccin se pondran los operadores unarios a no ser que tengan una precedencia menor.

EJEMPLO:

Supnganse los operadores +, -, con asociatividad por la izquierda (en 6-3-3), y * y / por la derecha,

* / precedencia 1 y los parntesis tienen la suma y la resta precedencia 2 mxima precedencia.

La gramtica que genera las expresiones con estos operadores y adems recoge la asociatividad y la

precedencia es la siguiente:

12-4-6/2/2

n2 n3

27

E E + T

E E T

E T

T F T

T F / T

T F

F ( E )

F nmero

TIPOS DE ANLISIS SINTCTICO

Los algoritmos de anlisis sintctico general para gramticas 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 gramticas que permitan un anlisis sintctico en tiempo lineal.

Desde el punto de vista de la teora de Anlisis Sintctico, hay dos estrategias para construir el rbol

sintctico:

o Anlisis descendente: partimos de la raz del rbol (axioma o smbolo inicial) y se van aplicando reglas por la izquierda de forma que se obtiene una derivacin por la izquierda

de la cadena de entrada. Para decidir qu regla aplicar, se lee un token de la entrada.

Recorriendo el rbol de anlisis sintctico 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 Anlisis ascendente: partiendo de la cadena de entrada, se construye el rbol de anlisis sintctico empezando por las hojas (donde estn los tokens) y se van creando nodos

intermedios hasta llegar a la raz (hasta el axioma), construyendo as el rbol de abajo a

arriba. El recorrido del rbol se har desde las hojas hasta la raz. El orden en el que se

van encontrando las producciones corresponde a la inversa de una derivacin por la

derecha.

Anlisis Sintctico Descendente

Este intenta encontrar entre las producciones de la gramtica una derivacin por la izquierda del

smbolo inicial para una cadena de entrada.

Backtracking: Cuando el anlisis sintctico descendente (ASD) puede incluir retrocesos en el

anlisis.

Anlizadores Sintcticos Predictivos (ASP)

Para que el algoritmo tenga una complejidad lineal, el analizador debe realizar una prediccin

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, cul de las alternativas de produccin 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

28

alternativa apropiada debe poderse predecir slo con ver el primer smbolo que produce. Que forma

deben tener las gramticas a las que se puede aplicar.

EJEMPLO:

Sent if Expres then Sent while Expres do Sent begin Sent end

En esta gramtica slo existe siempre una posibilidad de derivacin, segn sea el valor del

token.

Derivaciones

Ejemplo 1) de gramticas

Define expresiones aritmticas

expr expr op exp.

expr expr)

expr expr

exp id

op +

op -

op *

op /

op

Derivaciones

La visin derivativa de una descripcin precisa de la construccin descendente de un rbol de

anlisis sintctico.

La idea central es que se considera una produccin como una regla de reescritura, donde el no

Terminal de la izquierda es sustituido por la cadena del lado derecho de la produccin.

Ejemplo: Gramtica para expresiones aritmticas

E E + E | E * E | (E) | - E | id E significa que una expresin precedida por un signo menos es tambin una expresin.

Ejemplo:

E - E -(E) -(id)

A esta secuencia de sustituciones se le llama derivacin de (id) a partir de E.

Las cadenas de L (G) pueden contener slo smbolos terminales de G.

Los smbolos terminales son: id +, -, *, /,

( ),

Los smbolos no terminales son: exp y op

Smbolo inicial expr

29

Se dice que una cadena de terminales W est en L (G) si, y slo si, S W. A la cadena W sed le llama frase de G.

Si el lenguaje puede ser generado por una gramtica se dice que es lenguaje independiente del

contexto.

Ejemplo: La cadena (id + id) es una frase de la G (1), por que existe la derivacin:

E -E -(E) -(E + E) -(id + E) -(id + id)

Derivacin por la derecha: Donde el no Terminal ms a la derecha se sustituye en cada paso.

Ejemplo:

E -E -(E) -(E + E) -(E + id) -(id + id)

Este tipo de gramticas que son susceptibles de ser analizados sintcticamente de forma

descendente y mediante un anlisis predictivo, pertenecen al conjunto de gramticas denominado LL

(1).

A partir de este tipo de G se puede construir automticamente ASDP (Anlisis Sintctico

Descendente Predictivos), que no son otra cosa que ASD sin retroceso.

LL (1) donde: L = Anlisis de izquierda a derecha de la cadena de entrada, L = Derivacin por la

izquierda y 1 = Basta con solo ver un token.

Conjuntos de prediccin

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 continuacin, a partir de los smbolos de las partes

derechas de las producciones de la gramtica.

El analizador consulta el siguiente token en la entrada y si pertenece al conjunto de prediccin de una

regla (de la variable que hay que derivar), aplica esa regla. Si no puede aplicar ninguna regla, se

produce un de error.

CLCULO DE LOS CONJUNTOS DE PREDICCIN

Los conjuntos de prediccin de una regla se calculan en funcin de los primeros smbolos que puede

generar la parte derecha de esa regla, y a veces (cuando esa parte genera la cadena vaca) en funcin

de los smbolos que pueden aparecer a continuacin de la parte izquierda de la regla en una forma

sentencial.

Clculo del conjunto de PRIMEROS

30

La funcin PRIMEROS se aplica a cadenas de smbolos de la gramtica ( (T N)* y devuelve un conjunto que puede contener cualesquiera terminales de la gramtica y puede contener a la cadena

vaca, .

Definicin:

Si es una forma sentencial compuesta por una concatenacin de smbolos, PRIMEROS () es el conjunto de terminales que pueden aparecer iniciando las cadenas que pueden derivar (en cero o ms pasos) de . Definicin formal:

a PRIMEROS() si a ( T {} ) / * apara alguna tira

Algoritmo

1. Si T, PRIMEROS () = {}

2. Si N:

Inicialmente, PRIMEROS () =

Si aparece la produccin , PRIMEROS () = PRIMEROS () {}

Si a1 a2 ... an entonces PRIMEROS() = PRIMEROS() PRIMEROS(a1 a2 ...an) y para el clculo 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 habra que considerar que

Si 1 | 2 | ... | n entonces

PRIMEROS () = PRIMEROS(i)

EJEMPLO 1:

Sea la siguiente gramtica para expresiones aritmticas con sumas y multiplicaciones:

E T E

E + T E

T F T

T F T

F ( E ) ident

Clculo de los PRIMEROS de todos los no terminales de esta gramtica:

PRIMEROS(E) = { + , }

PRIMEROS(T) = { , }

PRIMEROS(F) = { ( , ident }

PRIMEROS(E) =(ETE, TN) PRIMEROS(T) =(TFT, FN) PRIMEROS(F) = { ( , ident }

n

i 1

31

EJEMPLO 2:

Sea la gramtica 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 gramtica:

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 an es .

= { b } PRIMEROS(CD) = { b , c } PRIMEROS(D) = { b , c , d , e }

Clculo del conjunto de SIGUIENTES

La funcin SIGUIENTES se aplica a variables de la gramtica (A N) y devuelve un conjunto

que puede contener cualesquiera terminales de la gramtica y adems puede contener un smbolo

especial, $, que representa el final de la cadena de entrada. Esto es equivalente a aadir una

produccin adicional a la gramtica en la que el axioma, S, es definido como X S$.

Definicin:

Si A es un smbolo no terminal de la gramtica, SIGUIENTES(A) es el conjunto de

terminales que pueden aparecer a continuacin de A en alguna forma sentencial derivada del smbolo

inicial.

Definicin formal:

a SIGUIENTES(A) si a ( T {$} ) / S * Aapara algn par de tiras ,.

Reglas para el clculo del conjunto de los SIGUIENTES

1. Inicialmente, SIGUIENTES(A)=

2. Si A es el smbolo 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

32

SIGUIENTES(A)=SIGUIENTES(A) SIGUIENTES(B)

5. Repetir los pasos 3 y 4 hasta que no se puedan aadir ms smbolos a SIGUIENTES(A)

NOTA:

Las reglas (S1) y (S2) no son excluyentes. Primero habr que intentar aplicar (S1) y luego (S2)

Slo 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)= TFTyTFTPRIMEROS(T){}SIGUIENTES(T)SIGUIENTES(T)= S1 = { } { + , ) , $ } = { , + , ) , $ }

Clculo del conjunto PREDICT:

La funcin PREDICT se aplica a producciones de la gramtica (A a) y devuelve un

conjunto, llamado conjunto de prediccin, que puede contener cualesquiera terminales de la

gramtica y el smbolo $, pero nunca puede contener .

Reglas para el clculo del conjunto PREDICT

PREDICT(A ) =

Si PRIMEROS() entonces = (PRIMEROS()-{}) {SIGUIENTES(A)}

sino = PRIMEROS()

EJEMPLO:

Supngase la siguiente gramtica:

S AB s

A aSc eBf

B bAd

Calculamos los conjuntos de prediccin 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 CONDICIN LL(1)

33

Para que una gramtica pertenezca al conjunto de gramticas LL(1) ha de cumplir la

condicin LL(1).

Para que la regla a aplicar sea siempre nica, se debe exigir que los conjuntos de prediccin

de las reglas de cada no terminal sean disjuntos entres s.

Si la gramtica es LL(1) y se puede realizar su anlisis sintctico en tiempo lineal.

La condicin LL(1) es necesaria y suficiente para poder construir un ASDP para una gramtica.

Condicin LL(1):

Dadas todas las producciones de la gramtica para un mismo terminal:

A 1 | 2 | ... | n A N

se debe cumplir la siguiente condicin:

i, j ( i j ) PREDICT(Ai) PREDICT(Aj) =

Ejemplo 1:

A a b B { a }

A B b { b , c }

B b { b }

B c { c }

EJEMPLO 2:

Sea la siguiente gramtica:

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) ) = { ( }

MODIFICACIN DE GRAMTICAS NO LL(1)

Existen caractersticas que, en el caso de ser observadas en una gramtica, garantizan que no

es LL(1) (sin calcular los conjuntos de prediccin).

Si la gramtica no es LL(1) no necesariamente debe tener alguna de estas caractersticas.

34

Existen mtodos para modificar gramticas que no son LL(1) y convertirlas en LL(1).

ELIMINACIN DE LA AMBIGEDAD

Cualquier gramtica ambigua no cumple LL(1).

Si la gramtica no es ambigua no necesariamente es LL(1), pues puede presentar otros problemas.

El problema de la ambigedad es el ms difcil de resolver pues no existe una metodologa para

eliminarla y tampoco hay otra frmula para saber que una gramtica es ambigua (slo queda

encontrar alguna sentencia que tenga dos rboles de anlisis sintctico distintos).

La mejor opcin cuando se presenta una gramtica ambigua es replantear la gramtica por una

equivalente (que genere el mismo lenguaje).

FACTORIZACIN IZQUIERDA

Si dos producciones alternativas de un smbolo A empiezan igual, no se sabr por cul de

ellas seguir, se trata de reescribir las producciones de A para retrasar la decisin hasta haber visto lo

suficiente de la entrada, se soluciona uno de los problemas que tenia la gramtica para no cumplir la

condicin LL (1) como para elegir la opcin 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 slo ver if.

De hecho, un analizador sintctico descendente no sabra hasta ver el cuarto smbolo de esta

produccin, 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 gramtica

Para todos los no terminales, A, de la gramtica, encontrar el prefijo ms largo comn a dos o ms

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

35

Repetir el paso anterior hasta que no haya 2 alternativas de un no terminal con un prefijo comn.

EJEMPLO:

Sent if Expr then Sent else Sent

Sent if Expr then Sent

Sent Otras

if Expr then Sent

i Otras

Con la gramtica factorizada queda:

Sent if Expr then Sent Sent

Sent Otras

Sent else Sent

Sent

ELIMINACIN DE LA RECURSIVIDAD IZQUIERDA

Los analizadores sintcticos descendentes no pueden manejar gramticas recursivas por la izquierda

pues estaran en ciclos de recursividad infinita al ejecutarse.

Cualquier gramtica recursiva por la izquierda no cumple la condicin LL (1).

A A| A| | Am| | | | n

Sustituir por: A 1A| 2A|| nA

A 1A|2A|| mA

EJEMPLO:

Eliminar la recursividad izquierda de la gramtica de las expresiones aritmticas.

1 E E + T E T T

2 T T F | T / F | F

F ( E ) | nm

1 E E + T | T

A A |

2 T T F

A A |

Por tanto nos queda la siguiente gramtica:

E T E

E + T E T E

T F T

E T E

E+ T E |

T F T

TF T |

36

T F T / F T

F ( E ) | num

IMPLEMENTACIN DE UN ANALIZADOR SINTCTICO DESCENDENTE

RECURSIVO

Es un mtodo de anlisis sintctico descendente que slo se puede aplicar en gramticas LL

(1) y por tanto es un analizador sintctico descendente predictivo (ASDP).

Consiste en un conjunto de funciones recursivas (una por cada variable de la gramtica) que

son diseadas a partir de los elementos que definen cada una de las producciones de la gramtica.

La secuencia de llamadas al procesar la cadena de entrada define implcitamente su rbol de

anlisis sintctico.

Smbolo de preanlisis

Si esta metodologa es aplicable a las gramticas LL (1) es porque basta ver un nico token

para saber qu hacer. Ese token se llama smbolo de preanlisis o LookAhead y ser pedido al

analizador lxico cada vez que se necesite. Este token el que se busque en los conjuntos de

prediccin.

Funcin de emparejamiento (Match)

Comprueba si el smbolo de preanlisis coincide con el terminal de la gramtica que, de

acuerdo con los elementos de la produccin escogida debera aparecer en esa posicin.

Tambin se encarga de la peticin del siguiente token al analizador lxico si se da la

coincidencia o invoca a la funcin de error en caso contrario.

Estructura

FUNCIN Emparejar ( Parmetro de entrada: token; Usa variable global preanlisis ) SI preanlisis coincide con token ENTONCES

Pedir el siguiente preanlisis al analizador lxico SINO

Error Sintctico(Encontrado preanlisis, esperaba token)

Si t es el token que el ASDR espera encontrar en la entrada y, la funcin Emparejar en C queda:

void Emparejar ( int t )

{

if ( t == preanalisis )

preanalisis = analex(); /* analex es el nombre que hemos dado al Analizador Lxico */

else

ErrorSintctico(preanalisis,t);

}

37

Algoritmo para construir un ASDR

1) Escribir una funcin por cada smbolo no terminal de la gramtica. Cada una llevar a cabo el anlisis de las producciones de dicho no terminal.

2) Cuando este no terminal tenga distintas alternativas, para decidir durante su ejecucin cul de las producciones utilizar, se optar por aquella alternativa a cuyo conjunto de prediccin

pertenezca el token de preanlisis.

EN CASO DE QUE Preanlisis PERTENEZCA A

PREDICT(a1): ... proceder segn alternativa a1 ...

PREDICT(a2): ... proceder segn alternativa a2 ...

...

FIN

Si el token de preanlisis no pertenece a ninguno de los PREDICT, entonces se considerar error

sintctico.

3) Si una de las alternativas para el no terminal que se est analizando es la cadena vaca (A ), en ese caso no se har nada.

4) Para analizar cada alternativa, se aplican distintas metodologas a los smbolos de la parte derecha de la produccin, en el mismo orden en el que aparecen, segn si son terminales o

no:

- Para cada A N hacemos una llamada a su funcin correspondiente. - Para cada a T hacemos una llamada a la funcin Emparejar con a como parmetro.

5) La invocacin o puesta en marcha del ASDR se realiza mediante una llamada al smbolo inicial de la gramtica. Para hacer esa llamada se supone que el token de preanlisis habr

sido inicializado por una llamada previa al analizador lxico.

EJEMPLO: Sea la siguiente gramtica LL(1) con sus conjuntos de prediccin:

S A { a , $ }

S s { s }

A a S c { a }

A { c , $ }

Supondremos que:

- Estn definidos los tokens a, c y s - Se tiene definida una variable lexema como un array de caracteres - Ya se tiene implementada la funcin emparejar

void S(void)

{

if ( preanalisis == a || preanalisis = FINFICHERO )

38

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 )

; /* produccin epsilon */

else ErrorSintactico(lexema,a,c,FINFICHERO);

}

NOTA: A la funcin de error sintctico se le suele pasar como argumentos el lexema que ha

producido el error (el del token de preanlisis) y los que esperaba en su lugar (los terminales que

aparezcan en la unin de todos los conjuntos de prediccin de las reglas del no terminal al que

pertenece la funcin).

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

{

39

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 anlisis. Como se indica:

token = analex();

S();

if (token != FINFICHERO) error(token,lexema,{FINFICHERO});

/* encontrado 'lexema', esperaba fin de fichero */

ANALIZADORES SINTCTICOS DESCENDENTES DIRIGIDOS POR TABLA

Se puede construir un analizador sintctico descendente predictivo utilizando una pila de

smbolos (terminales y no terminales) en vez de haciendo llamadas recursivas.

Para determinar qu produccin debe aplicarse a la vista de un terminal (token de preanlisis), se

buscar en una tabla llamada tabla de anlisis.

40

Se debe construir la tabla (depende de la gramtica) y posteriormente aplicar el algoritmo.

Procedimiento para construir tablas de anlisis LL (1)

1. Las filas de la tabla se etiquetan con las variables de la gramtica.

2. Las columnas se etiquetan con los terminales y el smbolo 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 prediccin de esa regla) ].

3. Se calculan los conjuntos de prediccin para cada regla. 4. Para cada regla A de la gramtica, hacer:

Para cada terminal a PREDICT(A ), adase A a Tabla[A,a.

5. Cada entrada no definida de Tabla ser error sintctico.

NOTA: Al implementar el algoritmo no es necesario almacenar la regla completa en la tabla sino

slo los smbolos de su parte derecha (que es conveniente guardar al revs) o incluso es ms eficiente

almacenar un nmero de regla que haga referencia a otra tabla con los smbolos 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] aadir ETE

2: PREDICT(E+ T E) = {+} en la celda [E,+] aadir E+TE

3: PREDICT(ET E) = {} en la celda [E,] aadir ETE

4: PREDICT(E) = { ) , $ } en la celda [E,$] aadir E

5: PREDICT(T F T) = { ( , id } en las celdas [F,(] y [F,id] aadir TFT

6: PREDICT(T F T) = {} en la celda [T,] aadir FFT

7: PREDICT(T / F T) = {/} en la celda [T,/] aadir F/FT

8: PREDICT(T) = {+,,),$} en las celdas [T,+] [T, ] [T,)] [T,$] aadir T

9: PREDICT(F( E ) ) = { ( } en la celda [F,)] aadir F (E)

10: PREDICT(Fid) = {id} en la celda [F,id] aadir F id

Todas las celdas vacas se marcan como error sintctico.

41

Tener en cuenta es que este tipo de analizador es predictivo, esto es que slo puede construir

si la gramtica 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 gramtica para las sentencias IF en Pascal:

Sent if Expr then Sent Sent otras

Sent else Sent

Expr lgico

Su tabla es:

Podemos observar que la gramtica es ambigua pues existen dos producciones en la casilla sealada.

Una vez que se tiene la tabla de anlisis ya se puede construir el ASDP.

Algoritmo de ejecucin del Analizador Descendente Dirigido por Tabla:

Entrada: cadena de elementos lxicos devueltos por el A.L.

Salida: producciones que construyen su rbol de anlisis sintctico

Pasos:

push($)

push(S)

REPETIR

A := Pila[tope] /* el smbolo que haya en el tope de la pila */

a := analex( ) /* a es el smbolo de preanlisis */

SI A es un terminal o $ ENTONCES

SI A = a ENTONCES

pop A

a := analex( )

SINO

Error Sintctico ( encontrado lexema de a, esperaba A )

42

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

Error Sintctico(encontrado lexema de a, esperaba PREDICT( A

i ) )

FINSI

FINSI

HASTA A = $ /* La pila est vaca */

EJEMPLO:

La traza se realizar sobre la gramtica LL(1) de las expresiones aritmticas, tomando la tabla

descrita antes. La entrada para la traza es: id + id id $.

n

i 1

43

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 smbolos 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 smbolo de la izquierda representa el smbolo de preanlisis. Cuando este smbolo

coincide el terminal de la pila se eliminan ambos (el tope y el preanlisis) avanzando el anlisis al

siguiente smbolo 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 anlisis para ir actualizando el contenido de la pila

y construyendo el rbol de anlisis sintctico que se muestra a la derecha de la tabla.

EJEMPLO:

Sea G:

S C A B { c }

S a C b { a }

A a S d { a }

A { b , d , $ }

B b { b }

B { d , $ }

C c { c } La tabla de anlisis:

44

La traza del anlisis para la cadena cacdb sera: