INTRODUCCIÓN

 

 

Los programas yacc y lex son herramientas de gran utilidad para un

 

diseñador de compiladores. Muchos compiladores se han construido

 

utilizando stas herramientas (p.ej., el compilador de C de GNU, gcc)

 

o versiones masavanzadas. Los programas bison y flex son las

 

versiones mas modernas (nocomerciales) de yacc y lex, y se

 

distribuyen bajo licencia GPL con cualquier istribucion de Linux (y

 

tambien estan disponibles para muchos otros UNIX).

 

 

 

 

 

 

 

 

 

 

 

 

LENGUAJE LEX

 

 

El programa lex genera analizadores lexicos a partir de una especificación de los componentes lexicos en terminos de expresiones regulares (al estilo de UNIX); lex toma como entrada un fichero (con la extension .l) y produce un

fichero en C (llamado “lex.yy.c”) que contiene el analizador lexico. El fichero de entrada tiene tres partes (ver los ejemplos al final de este documento):

 

1. Al principio del fichero puede aparecer una parte de definiciones auxiliares.

a) Una definicion ocupa una linea y esta formada por un identificador,

uno o mas espacios en blanco o tabuladores y una expresion regular.

b) En la parte de definiciones auxiliares pueden aparecer fragmentos de codigo (que debe ser C o C++; lex no lo comprueba).

 

2.En algunas versiones de lex solamente se puede hacer referencia a definiciones regulares

en la segunda parte del fichero, pero como parte de otra definicion. Afortunadamente, lex si permite utilizar las definiciones para construir otras definiciones regulares.

Despues de la parte de definiciones auxiliares (que puede no tener nada)debe aparecer el simbolo “%%” y una secuencia de cero o mas pares expresion regular – accion. Estas expresiones regulares deben representar los componentes lexicos del lenguaje que se quiere reconocer.

Cada accion es un fragmento en C que debe estar encerrado entre llaves.

Nota: lex elimina las llaves y construye una funcion con un switch que ejecuta cada accion. Si es necesario declarar variables locales a esa funcion se puede hacer poniendo un fragmento de codigo encerrado entre “%{” y “%}” despues del simbolo “%%”, antes de cualquier par expresion regular accion.Normalmente, las acciones consistiran en incrementar los contadores delíneas y columnas, y hacer un return del token correspondiente. Si no sehace return, el analizador léxico sigue buscando otro componente léxico.

 

3. Después de todas las expresiones y sus acciones puede aparecer más códigoen C. En este caso debe aparecer el símbolo “%%” antes del código (que no debe estar encerrado entre “%{” y “%}”).

 

Notas sobre el comportamiento de lex:

En el caso de que una cadena de texto pueda ser reconocida por dos o más expresiones regulares (como p.ej. las palabras reservadas, que normalmentetambién son reconocidas por la expresión regular que reconoce identificadores), lex tomará la que aparezca antes en el fichero.

El analizador léxico que genera lex reconoce siempre la cadena más larga que coincida con una de las expresiones regulares, aunque un prefijo de esa cadena sea reconocido por otras expresiones regulares.

Si un carácter no puede ser reconocido por ninguna expresión regular, lex lo imprime por la salida estándar. Esta función está pensada para que lex pueda actuar como filtro con ficheros de texto4, pero para implementar un compilador esta función debe ser controlada, y para eso la última expresión suele ser un punto (que reconoce cualquier carácter excepto \n) y la acción correspondiente suele producir un mensaje de error.

Las expresiones regulares deben aparecer al principio de la línea para ser reconocidas por lex; si aparecen más a la derecha lex pensará que son parte de las acciones.

En general, lex no comprueba que el código sea C, C++ o cualquier otro lenguaje; simplemente lo inserta en el lugar que le corresponde en el analizador léxico que va a generar. Este analizador léxico se construye a partir de un esqueleto que suele estar escrito en C.

 

4.Por ejemplo, se puede utilizar para convertir todas las palabras en mayúsculas a palabras en minúsculas, ignorando lo que no sean palabras.

El fichero en C que genera lex contiene una función y lex que realiza la función del analizador léxico, y devuelve un int que debe ser el número que representa

cada token del lenguaje; cuando llega al final de la entrada devuelve cero.

El fichero lex.yy.c se puede compilar (si se a˜naden los #define correspondientes a los tokens que devuelve), pero el linker dara error porque necesita dos funciones: main y yywrap. Para solucionar este problema se puede indicar allinker que utilice la libreria del lex (con la opción -ll al final) o bien se pueden definir las funciones en la parte de código al final de la especificación de expresiones regulares; si se elige esta opción, se debe tener en cuenta que la función yywrap no tiene argumentos y debe devolver un entero, que normalmente debe ser un 15.

Por defecto, el analizador léxico generado por lex lee caracteres de la entrada estandar stdin. Si se desea cambiar este comportamiento basta con hacer que la variable in (que es de tipo FILE *) apunte a otro fichero (previamente

abierto para lectura con fopen) antes de llamar a Lex y Yacc

A partir de un fichero de especificación (bastante parecido a un ETDS),yacc genera un fichero en C (llamado “y.tab.c”), que contiene un analizador sintáctico ascendente por desplazamiento yreducción, y una función que ejecutalas acciones semánticas que aparecen en el fichero de especificación. Este fichero (que normalmente llevará la extensión .y) tiene tres partes, separadasigual que en el fichero para lex con el símbolo “%%”:

 

1. La primera parte es una secuencia de definición de tokens. Cada definición ocupa una línea, y empieza con la cadena “%token” y una secuencia deuno o más identificadores (los nombres de los tokens o terminales de la gramática). Por cada token definido yacc generara una línea parecida a “#define NINT 260”, numerando los tokens a partir del 256.

 

Existen otras formas de definir tokens en las que además se puede especificar su asociatividad y precedencia (para resolver conflictos provocados porla utilización de gramáticas ambiguas), pero no se deben utilizar en las prácticas de la asignatura.

En esta primera parte es posible incluir fragmentos de código encerrados entre “%{” y “%}”, como en los ficheros de especificación para lex. Todo

este código es global a todo el fichero.

 

2. La segunda parte del fichero debe contener las reglas de la gramática y las acciones semánticas, en una notación muy similar a los ETDS. Los no terminales se representan con identificadores, los terminales se ponen

 

3.La función yywrap es llamada por el analizador léxico cuando alcanza el final del fichero;si devuelve 1, termina el análisis y si devuelve 0 continua. Esta función se puede utilizar para procesar varios ficheros en una pasada (includes). En la documentación del lex se explica mejor el funcionamiento de yywrap.

 

Igual que lex, yacc elimina las llaves y pone todo el código de las acciones en una única función dentro de un switch. A diferencia de lex, no es posible declarar variables locales a esa función (al menos no es posible con bison).

Cada regla de la gramática debe empezar por un no terminal al principio de la línea, seguido del símbolo ‘:’ (dos puntos) y la parte derecha de la regla con terminales, no terminales y acciones separados por espacios en blanco, tabuladores o \n. Si se desea definir mas reglas de la misma variable sepuede poner el símbolo “|” (barra vertical) y otra parte derecha. Después de la última parte derecha debe aparecer el símbolo “;” (punto y coma).

Las partes derechas de las reglas pueden partirse en varias líneas si es necesario, y normalmente no continúan en la primera columna.

 

3. La tercera parte contiene código en C o C++ (que no debe estar encerrado entre “%{” y “%}”). En este código deben definirse dos funciones al menos: main y error. El argumento de error es una cadena de caracteres (char *); cuando el analizador generado por yacc encuentra un error sintáctico llama a la función y error con la cadena “parse error”7.

El fichero generado por yacc contiene una función y parse que llama a  lex (si no se utiliza lex se debe definir una función con ese nombre que devuelva un int, que realice las funciones del analizador léxico) cada vez que necesita un token, analiza sintacticamente el fichero fuente y ejecuta las acciones en el momento adecuado. Es necesario tener en cuenta que yacc genera sus propios marcadores para las acciones que aparezcan antes del final de la parte derecha de la regla8, por lo que no es necesario introducir explícitamente esos marcadores en el ETDS antes de proporcionárselo al yacc; además, se puede aprovechar el espacio ocupado por dichos marcadores en la pila de atributos para almacenar atributos heredados o valores locales a una regla9.

Los valores que debe devolver el analizador léxico son los que genera el yacc a partir de la primera parte de definición de tokens.

Atributos con yacc

La función gestiona una pila paralela a la del análisis sintáctico. Esa pila contiene elementos del tipo YYSTYPE, que por defecto está definido a int.

Para acceder a esta pila en las acciones se debe utilizar una notación especial (que yacc traduce a código en C):

 

7.El programa bison puede generar una cadena que proporciona mas información sobre la causa del error, pero para realizar las prácticas se debe ignorar esa cadena y elaborar el mensaje de error como se especifica en los enunciados de las prácticas.

 

8.Puesto que yacc sustituye cada acción por un no terminal marcador

 

9.Si en una acción intermedia se le asigna un valor a $$, realmente se está utilizando los atributos del marcador, no los de la parte izquierda de la regla (aunque en una acción al final se utilice $$ para hacer referencia a la parte izquierda)

Los símbolos de la parte derecha se numeran del uno en adelante (las acciones en medio de las partes derechas ocupan el espacio de un símbolo y es necesario tenerlo en cuenta).

Para hacer referencia a la posición en la pila de un símbolo se pone (dentro del código en C) $n, donde n es el número de ese símbolo en la parte derecha.

Para hacer referencia a la parte izquierda se pone $$ (sólo en acciones al final de la parte derecha, justo antes de que el analizador reduzca por la regla10).

Es muy aconsejable situar las acciones semánticas al final de las reglas.

Cuando no sea posible, es recomendable situarlas siempre entre terminales o variables que no generen ²; si se colocan después de una variable que puede derivar a ² es probable que el yacc no pueda decidir cuando realizar la acción y produzca conflictos reducción-reducción.

Para hacer que YYSTYPE sea un tipo distinto de int es suficiente con poner en un fragmento de código en la primera parte del fichero (junto con las definiciones de los tokens) la siguiente línea:

 

#define YYSTYPE MITIPO11

Atributos heredados

Al utilizar un analizador sintáctico ascendente no es posible implementar directamente un ETDS con atributos heredados en yacc; es necesario conseguir

que cada atributo heredado se corresponda con un atributo sintetizado de otra variable que este mas abajo en la pila

Para acceder a atributos que se encuentren debajo del primer

símbolo de la parte derecha habría que utilizar los índices $0, $-1, etc., siempre teniendo en cuenta que las acciones ocupan un hueco en la pila.

Variables locales a una regla

Cuando se desea utilizar variables locales a una regla, es decir, variables locales al proceso de análisis de una regla, no es posible utilizar variables locales de C, ya que son globales a todas las reglas (y a todos los procesos de análisis de

cada regla), ya que es una única función de C la que ejecuta todas las acciones.

En su lugar se deben utilizar atributos de algún símbolo de la parte derecha de la regla (que ya se haya analizado, por supuesto); los terminales son los

10Si se utiliza $$ en alguna acción antes del final de la regla, en realidad se estará utilizando

el espacio ocupado por la acción (seria lo mismo que utilizar $n, siendo n la posición de la acción en la regla), lo cual puede (a veces) ser conveniente.

 

 

 

11.Es imprescindible definir el tipo con type def : : : MITIPO, y después poner el #define

YYSTYPE MITIPO, ya que si se pone type def : : : YYSTYPE es posible que no funcione bien (depende del compilador de C). candidatos mas adecuados para esa tarea, aunque también se pueden utilizar marcadores o los marcadores de las propias acciones. Si se utiliza esta técnica se debe documentar con comentarios en el código.

Comunicación entre YACC y LEX

Los programas que son generados por yacc y lex están diseñados para funcionar juntos. Asi lex debe devolver los numeros de token que asigna yacc12, y yacc llama a una funcion y lex que debe retornar en cada caso exactamente lo mismo que retorna la que genera lex.

Ademas de devolver un entero indicando que token se ha reconocido, el analizador lexico debe devolver el valor lexico de ese token. El lexema que el analizador generado por lex ha reconocido se copia en la cadena de caracteres

El analizador léxico debe procesar esa cadena de caracteres (convertirla a número, etc.) y devolver al analizador sintáctico el valor léxico del token (que no tiene por qué coincidir con el lexema). Para hacer esto con yacc y lex existe una variable YYSTYPE yylval13 que debe rellenar el analizador lexico14 y que yacc copia en la pila semantica cuando desplaza el simbolo a la pila sintactica.

Recomendacion: Por varios motivos (defines de los tokens, variables declaradas en un fichero y no en el otro, redireccion de la entrada, etc) es aconsejable que el fichero que genera lex, lex.yy.c se incluya (con una sentencia #include,

por supuesto) en la parte de definiciones de tokens del fichero .y, en un fragmento de codigo despues de todas las definiciones de los tokens. En ese fragmento

(y antes del #include) se podria tambien redefinir YYSTYPE. De esta forma, al compilar el fichero generado por yacc se compilara tambien el fichero generado por lex y se obtendria un unico fichero objeto.

 

Ejemplo de implementacion con YACC y LEX

El siguiente ejemplo es una implementacion de un sencillo ETDS utilizando yacc y lex. Para generar el ejecutable hay que teclear:

flex ej.l

bison -y ej.y

cc -o ej y.tab.c

 

El codigo para lex es:

 

12.Es posible (con la opcion -d) hacer que yacc genere un fichero y.tabb.h que contenga solo los defines, para ser utilizado con lex.

 

13.Dependiendo de la version de yacc y lex esta declarada en el codigo que genera yacc o en el codigo que genera lex.

 

14.Las acciones que se ejecutan cuando se reconoce un componente lexico deben asignar un valor adecuado a esa variable antes de devolver con return el numero correspondiente a ese componente lexico.

/* ej.l */

%{

#include <string.h>

void linecode (void);

char *dupcad(char *s);

extern YYSTYPE yylval;

%}

delim [ \t]

eb {delim}+

letra [a-zA-Z]

digito [0-9]

id {letra}({letra}|{digito})*

%%

{eb} {numcolumna+=strlen(yytext);}

"\n" {numlinea++; numcolumna=1;}

"," {linecode(); return (COMA);}

":" {linecode(); return (DOSP);}

class {linecode(); return (CLASS);}

private {linecode(); return (PRIVATE);}

public {linecode(); return (PUBLIC);}

int {linecode(); return (INT);}

float {linecode(); return (FLOAT);}

{id} {linecode(); return (ID);}

"(" {linecode(); return (PARI);}

")" {linecode(); return (PARD);}

"{" {linecode(); return (LLAVEI);}

"}" {linecode(); return (LLAVED);}

. {fprintf(stderr,"Error 1 (%d,%d): caracter '%c' incorrecto\n",

numlinea,numcolumna,yytext[0]);

exit(-1);}

%%

int yywrap (void) {return 1;}

void linecode (void) {yylval.lexema=dupcad(yytext); numcolumna+=strlen(yytext);}

Por otro lado, el c´odigo para yacc es:

/* ej.y */

%token COMA DOSP INT FLOAT PUBLIC PRIVATE CLASS

%token ID PARI PARD LLAVEI LLAVED

%start s

%{

typedef struct {

char *lexema;

char *s;

} atrib;

#define YYSTYPE atrib

int streq(char *a,char *b);

char *concat(char *s1, char *s2, ...);

int numlinea, numcolumna;

#include "lex.yy.c"

#define cEOA "!$%&"

%}

%%

s : c

{

printf("%s\n",$1.s);

}

;

c : CLASS ID LLAVEI b v LLAVED

{

$$.s= concat("clase ",$2.lexema," {",$4.s,$5.s,"} ",cEOA);

}

;

b : PUBLIC DOSP p

{

$$.s= concat("publico: ",$3.s,cEOA);

}

;

b :

{

$$.s= dupcad("");

}

;

v : PRIVATE DOSP p

{

$$.s= concat("privado: ",$3.s,cEOA);

}

;

v :

{

$$.s= dupcad("");

}

;

p : p d

{

$$.s= concat($1.s,$2.s,cEOA);

}

;

p :

{

$$.s= dupcad("");

}

;

d : t ID PARI t ID l PARD

{

$$.s= concat($2.lexema,"(",$4.s,$6.s," -> ",$1.s,") ",cEOA);

}

;

d : c

{

$$.s= $1.s;

}

;

l : l COMA t ID

{

$$.s= concat($1.s," x ",$3.s,cEOA);

}

;

l :

{

$$.s= dupcad("");

}

;

t : INT

{

$$.s= dupcad("entero");

}

;

t : FLOAT

{

$$.s= dupcad("real");

}

;

%%

int main (int argc, char **argv) {

int c;

numlinea= numcolumna= 1;

if (argc != 2) {

fprintf(stderr,"uso: ej fichero\n");

exit (-1);

}

if ((yyin=fopen(argv[1],"rt")) == NULL) {

fprintf(stderr,"Error: no se puede abrir el fichero\n");

exit (-1);

}

return yyparse();

fclose(yyin);

}

int yyerror (char *s) {

if (!strlen(yytext)) {

fprintf(stderr,"Error 3: final de fichero inesperado\n");

}

else {

fprintf(stderr,"Error 2 (%d,%d): no se esperaba '%s'\n",

numlinea,numcolumna-strlen(yytext),yytext);

}

}

char *dupcad (char *s) {

char *t;

t=strdup(s);

if (t==NULL) {

puts("Fatal: no hay suficiente memoria en dupcad");

exit(20);

}

return t;

}

char *concat(char *s1, char *s2, ...) {

...

}

Generalidades


Un generador de analizadores es un programa que acepta como entrada la especificación de las ca­racterísticas de un lenguaje L y produce como salida un analizador para L. La especificación de en­trada puede referirse a la lexicografía, la sintaxis o la semántica; el analizador resultante servirá para analizar las características especificadas.

      E   Especificación de las características del lenguaje L

      A   Analizador para L

Los generadores Lex y Yacc sirven, respectivamente, para generar analizadores lexicográficos y analizadores sintácticos para su aprovechamiento como partes de los compiladores de los lenguajes de programación; estos usos de Lex y Yacc no son los únicos, aunque sí son los que aquí se consi­deran principalmente.

Para entender cabalmente el funcionamiento de los generadores de analizadores, hay que co­nocer la teoría de compiladores relacionada con las tareas de análisis de lenguajes.

        Cuando se emplea el término Lex, se mencionan dos posibles significados:

a) una notación para especificar las características lexicográficas de un lenguaje de programación,

b) un traductor de especificaciones lexicográficas.

Esta misma dualidad también es de aplicación al término Yacc.

Esquema de uso

El esquema de la página siguiente ilustra la manera de usar los generadores Lex y Yacc para obte­ner un analizador léxico-sintáctico de un lenguaje de programación L, y de ejecutar el analizador ob­tenido. Los nombres que aparecen en el esquema significan:

eLexic.l
es la especificación de las características lexicográficas del lenguaje L, escrita en Lex

eSint.y
es la especificación de las características sintácticas del lenguaje L, escrita en Yacc

lex.yy.c
es el analizador lexicográfico de L generado por Lex; está constituido, en su parte principal, por una función escrita en C que realiza las tareas de análisis lexicográfico basándose en autómatas re­gulares reconocedores de la forma de las piezas sintácticas de L

libl
es una librería asociada a Lex que contiene estructuras de datos y funciones a las que se puede hacer referencia desde el código generado

liby
es una librería asociada a Yacc con la misma utilidad que la anterior

y.tab.c
es el analizador sintáctico generado por Yacc; está constituido, en su parte principal, por una función escrita en C que realiza las tareas de análisis sintáctico según el método ascendente LALR(1), basado en tablas

anLeSi
es el analizador generado; analiza las características lexicográficas y sintácticas especificadas del lenguaje L; acepta como entrada un programa escrito en L y comprueba si está codificado según las especificaciones dadas



programa escrito en el lenguaje L

No es preciso que los nombres de los ficheros de entrada para Lex y Yacc  tengan una extensión de­terminada; los nombres de los ficheros generados por Lex y Yacc son siempre los indicados, con independencia de cuál sea el nombre de los ficheros de entrada.

 

 

Obtención y ejecución del analizador

El analizador léxico-sintáctico se obtiene tras la realización de los siguientes pasos:

     1)   vi eLexic.l
              edición del fichero con las características lexicográficas

     2)   vi eSint.y
              edición del fichero con las características sintácticas

     3)   lex eLexic.l
              traducción de las características lexicográficas

     4)   yacc eSint.y
              traducción de las características sintácticas

     5)   cc lex.yy.c  y.tab.c  –ll  –ly  –o  anLeSi
              compilación del código de los analizadores generados

(El orden de pasos citado es una posibilidad, no una necesidad; se ha supuesto el uso del editor vi).

Los ficheros sobre los que actúa el analizador léxico-sintáctico generado son (salvo que de manera explícita se indique otra cosa) los pre-definidos de entrada y de salida; así pues, la ejecución del ana­lizador obtenido puede hacerse de una las siguientes formas:

                        anLeSi

                        anLeSi <Entrada

                        anLeSi <Entrada >Salida

según que se haga o no re-direccionamiento de los ficheros de entrada y de salida pre-definidos.

En el fichero de entrada se proporciona un programa escrito en L. La salida, que debe de informar sobre el resultado del análisis, puede ser más o menos elaborada; por ahora se considera la posibili­dad más sencilla. Si el programa analizado es correcto en lo que respecta al léxico y a la sintaxis, no se emite indicación alguna; si el programa no es correcto porque tiene algún error lexicográfico o sintáctico, se emite el mensaje syntax error (más adelante se justificará la razón por la que se emite este mensaje, tanto si se trata de un error lexicográfico como si es uno sintáctico).

Ejemplo 1

Con este ejemplo inicial se muestra, antes de empezar el estudio detallado, una aplicación de los ge­neradores Lex y Yacc para obtener un analizador léxico-sintáctico de un lenguaje simple. Se pro­porciona la solución sin explicación alguna; lo único que se pretende ahora es obtener automática­mente un analizador, y probar su funcionamiento.

        Se trata de una clase sencilla de expresiones aritméticas en las que pueden encontrarse:

- variables (nombres escritos en minúsculas, de cualquier longitud),

- constantes (números con cifras decimales de cualquier longitud),

- operadores ( +, *),

- paréntesis.

La sintaxis de las expresiones se define mediante la siguiente gramática (escrita en notación BNF-Ampliada):

                  <Expresion> ::= <Termino> { +  <Termino> }

                  <Termino>   ::= <Factor> { *  <Factor> }

                  <Factor>    ::= ( <Expresion> )

                               |  id

                               |  cte

La entrada a Lex (la especificación lexicográfica), si se emplean los nombres pId, pCte, pSum, pMul, pAbr y pCer para representar las distintas piezas sintácticas del lenguaje, es:

  │%{

  │#define pId  1

  │#define pCte 2

  │#define pSum 3

  │#define pMul 4

  │#define pAbr 5

  │#define pCer 6

  │#define Error  999

  │%}

  │%%

  │[a-z]+     { return pId;   }

  │[0-9]+     { return pCte;  }

  │"+"        { return pSum;  }

  │"*"        { return pMul;  }

  │"("        { return pAbr;  }

  │")"        { return pCer;  }

  │[\ \t\n]   { ;             }

  │.          { return Error; }

La entrada a Yacc (la especificación sintáctica) es, considerada a partir de una gramática equivalente a la dada, pero escrita en notación BNF-No ampliada, es:

  │%token pId  1

  │%token pCte 2

  │%token pSum 3

  │%token pMul 4

  │%token pAbr 5

  │%token pCer 6

  │%start Expresion

  │%%

  │Expresion : Termino RestoExpr ;

  │RestoExpr : pSum Termino RestoExpr ;

  │          |  ;

  │Termino : Factor RestoTerm ;

  │RestoTerm : pMul Factor RestoTerm ;

  │          |  ;

  │Factor : pId ;

  │       | pCte ;

  │       | pAbr Expresion pCer ;

  │%%

  │main () {

  │  yyparse ();

  │}

La raya vertical puesta a la izquierda de las dos especificaciones representa la posición de la primera columna de las líneas de los ficheros de tipo texto.

Si el analizador obtenido se aplica a la entrada (x + y) * cota, que es una expresión correcta, no se obtiene mensaje alguno como resultado del análisis; si se aplica a la entrada x+y*+z, que es una expresión incorrecta, se obtiene como salida la indicación syntax error; si se aplica a la en­trada x + y? – z, que contiene un carácter que no pertenece al alfabeto (error lexicográfico), tam­bién se obtiene el resultado syntax error.

 

 

 

Conflictos

Como se ha visto, el análisis ascendente por desplazamiento reducción se basa en la localización del pivote de cada forma sentencial derecha, que se traduce en la decisión entre desplazar o reducir, y en el último caso, la regla por la que reducir.

Yacc determina, para cada situación de la pila y cada símbolo de entrada, la acción correspondiente, realizando determinado algoritmo1 a partir de las reglas de la gramática. Si ésta permite determinar de forma única la acción en cada caso, se dice que es LALR(1). Si no, es decir, cuando

haya más de una posibilidad en algún caso, en alguna casilla aparecerá más de una acción, y Yacc lo indicará como “conflicto”. Hay dos tipos de conflicto:

desplazamiento-reducción cuando se obtenga en la casilla una acción de desplazamiento y una (o más) de reducción

reducción-reducción cuando no se obtenga en la casilla acción de desplazamiento, pero sí más de una acción de reducción

1.1. Ejemplo de conflicto desplazamiento-reducción

Consideremos la gramática:

S ! cAba j cbbb j bA

A ! b

El lenguaje generado es fcbba; cbbb; bbg mediante las derivaciones más a la derecha (únicas):

S ) cAba ) cbba

S ) cbbb

S ) bA ) bb

Yacc detecta un conflicto desplazamiento-reducción, en la casilla [4; b], que aparece en y.output

de la siguiente manera:

4: shift/reduce conflict (shift 8, reduce 4) on 'b'

state 4

S : 'c' 'b' . 'b' 'b' (2)

A : 'b' . (4)

El problema surge cuando se realiza el análisis de las sentencias cbba y cbbb:

1Sección 4.7 de “Compiladores. Principio, Técnicas y Herramientas”, Aho, Sethi y Ullman

1

 

 

Pila E ntrada Acción Pila Entrada Acción

$ c bba$ desplazar $ c bbb$ desplazar

$c b ba$ desplazar $c b bb$ desplazar

$cb b a$ reducir 4 (A ! b) $cb b b$ desplazar

$cA b a$ desplazar $cbb b $ desplazar

$cAb a $ desplazar $cbbb $ reducir 2(S ! cbbb)

$cAba $ reducir 1(S ! cAba) $S $ aceptar

$S $ aceptar

Los análisis empiezan a diferenciarse en la tercera línea, en la que Yacc debería tomar la decisión decuada teniendo a la vista solamente un símbolo de la entrada (en este caso, b). Como la decisión depnde realmente de un símbolo posterior (en este caso, el siguiente, a ó b), Yacc no puede decidir

entre desplazamiento y reducción. La situación exacta de aparición del conflicto es cb:b : : :

Un problema similar se encuentra en la siguiente gramática:

S ! cAba j cBbb j bB

A ! b

B ! _

Ahora el conflicto es

1: shift/reduce conflict (shift 4, reduce 5) on 'b'

state 1

S : 'c' . A 'b' 'a' (1)

S : 'c' . B 'b' 'b' (2)

B : . (5)

y aparece en la situación c:b : : : entre desplazar (para buscar el pivote b para cbba), o reducir (por la egla B ! _, porque ya se ha encontrado el consecuente del pivote _ para cba = c_ba)

1.2. Ejemplo de conflicto reducción-reducción

La gramática

S ! cAba j cBbb j bB

A ! b j a

B ! b

produce un conflicto reducción-reducción:

4: reduce/reduce conflict (reduce 4, reduce 6) on 'b'

state 4

A : 'b' . (4)

B : 'b' . (6)

que se produce, en la situación cb:b : : : como se ve en las siguientes simulaciones:

Pila Entrada Acción Pila Entrada Acción

$ c bba$ desplazar $ c bbb$ desplazar

$c b ba$ desplazar $c b bb$ desplazar

$cb b a$ reducir 4 (A ! b) $cb b b$ reducir 6 (B ! b)

$cA b a$ desplazar $cB b b$ desplazar

$cAb a $ desplazar $cBb b $ desplazar

$cAba $ reducir 1 $cBbb $ reducir 2

Nuevamente la decisión depende de un símbolo que aparecerá más tarde.

2

Gramáticas ambiguas

En los ejemplos anteriores, cada forma sentencial derecha tenía un único pivote, y el problema urgía al intentar localizarlo, viendo sólo una parte de los datos.

Si la gramática es ambigua, para alguna forma sentencial existirá más de un árbol de derivación,luego más de una derivación más a la derecha, y ello se traducirá en que tal forma sentencial tendrá masde un pivote. Por lo tanto se detectará, por fuerza, algún conflicto.

Recordemos que un pivote consta de dos partes: una subcadena (con su posición) y una regla

cuyo consecuente es dicha subcadena: < (_; p); A ! _ >. El análisis por desplazamiento-reduccióndebe desplazar símbolos de entrada hasta colocar el pivote en la cima de la pila, momento en el que dberá realizar una reducción.

Por ejemplo, la gramática para expresiones

G5 n E ! E _ E j núm

presenta un conflicto desplazamiento-reducción por su ambigüedad. Para la cadena núm - núm -

núm, hay dos derivaciones más a la derecha:

E ) E _ E ) E _ núm ) E _ E _ núm ) E _ núm _ núm ) núm _ núm _ núm

E ) E _ E ) E _ E _ E ) E _ E _ núm ) E _ núm _ núm ) núm _ núm _ núm

La forma sentencial E_E_núm tiene dos pivotes, para las subcadenas E_E y núm, correspondientes

a las intepretaciones de cálculo (núm-núm)-núm y núm-(núm-núm) respectivamente. Cuandoel análisis llegue a la situación

Pila Entrada Acción

$ núm - núm - núm $ desplazar

$ núm -núm-núm$ reducir

$ E - núm-núm$ desplazar

$ E - núm-núm$ desplazar

$ E-núm - núm$ reducir

$E-E - núm ?

la elección entre reducir o desplazar determinará la elección entre la la primera y segunda de las interpretaciones respectivamente s decir la asociación por la izquierda o derecha del operador

-. Tal elección no podría ser resuelta leyendo más símbolos de la entrada.

Las siguientes gramáticas, ambiguas, producen conflictos por ello de tipo desplazamiento-reducción

( S ! Bb j bB

B ! bb ( S ! cAb j cA

A ! bb j b

y en las siguientes, la ambigüedad produce conflitcos reducción-reducción:

8><>:

S ! cAbb j cBbb

A ! b

B ! b ( S ! cA j cbb

A ! bb 8><>:

S ! abBc j Ac

A ! ab

B ! _

1.4. Resolución de conflictos

CuandoYacc detecta un conflicto (bien por ambigüedad de la gramática o por otros motivos), aún

genera un analizador sintáctico resolviéndolos sistemáticamente en favor de los desplazamientos, o

eligiendo la primera regla que aparezca en la gramática para conflictos reducción-reducción. En.output pueden comprobarse estas decisiones.

Como consecuencia, es posible que haya cadenas del lenguaje que el analizador no reconozca

como correctas.

Algunas veces, es fácil darse cuenta de esta reducción del lenguaje, porque puede ocurrir queuna de las reglas nunca llegue a usarse, y Yacc lo indica mediante el mensaje “1 rule neverreduced”.

En general, lo más recomendable es modificar la gramática para que no aparezcan conflictos.

Nuevamente para los ejemplos de los apartados 1.1 y 1.2, se podrían utilizar las gramáticas equivalentes

LALR(1) siguientes:

S ! cABA j cABb j bA

A ! a

B ! b

8><>:

S ! cbbA j bB

A ! a j _

B ! b

8><>:

S ! cAa j cBb j B

A ! bb j ab

B ! bb

Para gramáticas ambiguas, muy frecuentemente la técnica de resuloción de conflictos de Yacc spone sencillamente la elección de una de las posibles derivaciones más a la derecha para la cadena

de entrada, con lo que el lenguaje reconocido sigue siendo el mismo, aunque se elige una de las

interpretaciones o estructuras, entre varias posibles.

Este es el caso de la gramática de expresiones aritméticas de 1.3: la elección del desplazamiento

en lugar de la reducción supone la elección del segundo de los árboles que siguen para núm - núm -

núm (con lo que 7_ 5 _ 2 tomaría el valor 4), pero no reduciría el conjunto de cadenas reconocidas.

E

_

_

_

_

_

_

E - E

_

_

_

_

_

_

E - E

núm núm

núm

E

_

_

_

_

_

_

E - E

núm

_

_

_

_

_

_

E - E

núm núm

La elección de resolución de conflictos en favor de los desplazamientos favorece que los árbolestengán más desarrollo en su parte derecha, y que lo operadores sean asociativos a la derecha, comoen este ejemplo. Como muchos operadores son asociativos por la izquierda, la política de resoluciónde conflictos en Yacc no será suficiente. Por lo tanto, o se formula una gramática no ambigua que

contemple las asociatividades deseadas, o se indica a Yacc especificamente de qué forma se desea laresolución de conflictos.

Además de un problema de asociatividad de operadores puede aparecer también un problemade precedencias. Si contemplamos en las expresiones aritméticas el operador producto, la meraespecificación

E ! E + E j E _ E j E _ E j númhará también ambigua la expresión núm+ núm* núm y Yacc interpretaría (núm+ núm)* núm encontra de lo que normalmente significa. Se desea el operador * también asociativo por la izquierda,

pero con precedencia sobre el + .

La gramática

E ! E + T j E _ T j T

T ! T _ F j T=F j F

F ! núm j (E)

es inambigua y mantiene las precedencias y asociatividades deseadas. Además, es también LALR(1),

con lo que Yacc podrá generara un analizador sin problemas. En general, las reglas recursivas por

la izquierda (A ! A_) hacen asociativos a la izquierda a los operadores, mientras que las recursivas

por la derecha (A ! _A) los hacen asociativos a la derecha. El orden de precedencia se resuelvemediante el uso de distintos niveles de sustitución: la “expresión” (E) aparece como suma o resta de“términos” (T), y éstos como producto o cociente de “factores” (F), que son finalmente expresioneselementales (núm) o bien expresiones entre paréntesis.

Otras posibilidad es especificar en Yacc el modo en que se quiere resolver los conflictos, proporcionandoinformación sobre asociatividad y precedencia. En la sección de declaraciones se puedenasociar precedencias y asociatividades a los componentes léxicos con líneas de la forma %left, %right  %nonassoc. Todos los componentes léxicos de una misma línea tendrán la misma precedencia, y

las líneas deben escribirse en orden creciente de precedencia. Por ejemplo:

%left '+' '-'

%left '*' '/'

%nonassoc se usa para especificar operadores no asociativos (por ejemplo, los relacionales <, <=

. . . ) Las reglas también llevarán asociadas una precedencia y asociatividad, que será la que tenga el

último componente léxico del consecuente. Los componentes léxicos pueden o no estar declarados

también en una línea %token.A veces se necesita que operadores unarios de alta precedencia utilicen la misma representaciónsimbólica que otros binarios de precedencia menor, como el “-” de cambio de signo respecto al binario

de resta. La palabra clave %prec cambia el nivel deprecedencia asociado en una regla particular,cuando aparece inmediatamente a continuación del cuerpo de la regla, antes de la acción o el “;” decierre. Provoca que la regla tenga la precedencia que se especifica en %prec.

Por ejemplo, las expresiones aritméticas podrían describirse en Yacc:

%token NUM

%left '+' '-'

%left '*' '/'

%%

expr : expr '+' expr

| expr '-' expr

| expr '*' expr

| expr '/' expr

| '-' expr %prec '*'

| NUM

;

que está estableciendo 2 niveles de precedencia (para operadores aditivos y multiplicativos, respectivamente),

ambos con asociatividad izquierda, y además el operador unario “-” que tendrá la mismaprecedencia que los multiplicativos.

Yacc ahora resolverá los conflictos con el siguiente algoritmo:

1. se asignará a cada componente léxico las asociatividades y precedencias que se hayan especificado (algunos pueden no tenerlas)

2. cada regla tendrá asociada la asociatividad y precedencia del último componente léxico delconsecuente (si lo tiene y éste tiene asignadas asociatividad y precedencia), salvo que se especifiqueotra cosa mediante %prec

3. ante un conflicto reducción-reducción, o un conflicto desplazamiento-reducción cuando las

posibles reglas a usar en reducciones o el símbolo de entrada no tienen asignadas precedenciay asociatividad, se actuará como se expuso al principio de esta sección

4. ante un conflicto desplazamiento-reducción, en el que tanto el símbolo de entrada como la egla a emplear en la reducción tienen asignadas asociatividad y precedencia, el conflicto se

resolverá en favor de la acción de desplazamiento si el símbolo de entrada tiene más precedenciaque la regla, y en favor de la reducción si ésta lo tiene mayor. A igualdad de precedencia,

5Seoptará por la reducción si la asociatividad es izquierda, desplazamiento si es derecha o semarcará un error si está especificada no asociatividad.

Los conflictos resueltos por precedencia no se tomarán en cuenta en el resumen de número deconflictos encontrados (lo que aún podría disfrazar errores).

 

 

Lex y Yacc son un par de especificaciones que sirven para generar tokenizers y parsers en C que reconozcan gramáticas libres de contexto, como lenguajes de pogramación o calculadoras entre otros.
Lex es el encargado de leer de la entrada, típicamente stdin y extraer de la misma los tokens reconocidos por el basado en un lenguaje de expresiones regulares.
Ejemplos: 

          "=="              Reconocería el token "=="
          [a-z]             Reconocería una letra de la a "a" la "z"
          [0-9]             Reconocería un numero del 0 al 9
          [0-9]+           Reconocería un numero entero a partir del mayor que 0
          -?[0-9]+        Reconocería cualquier numero entero

Mas adelante estudiaremos las expresiones regulares de lex con mayor detalle.
Yacc sirve para generar parsers, usa a lex para leer y reconocer sus tokens y basado en reglas sencillas en formato similar al BNF, es capaz de ir reduciendo una expresión con bastante eficiencia.
Ejemplos: 

          Expresion: Numero   {/* Esta linea reduce un numero a una expresion */}
                    | Expresion '+' Numero {/* Tambien una expresion mas un numero es una expresión */}
                    | Expresion '-' Numero {/* una expresion menos un numero es una expresion */}
                    ;

En el ejemplo anterior no estamos haciendo nada mas que definir una expresión de manera recursiva que puede sumar o restar. Mas adelante examinaremos mejor este concepto.

El ejemplo más sencillo

El ejemplo posible más sencillo en lex es un tokenizer que reconozca cualquier caracter de stdin y lo imprima en stdout.
Ejemplo :
Download 

 
. printf("%c",yytext[0]);
 
%%
 

Para correr este ejemplo en un sitema UNIX o similar : 

$ lex ejem0.l
$ cc -o ejem0 lex.yy.c -ll
$ ejem0
Ejemplo de Lex
Ejemplo de Lex
^C$


El primer comando "lex ejem0.l" genera un archivo en C (lex.yy.c) que contiene el tokenizer en C de las reglas introducidas en ejem0.l por lo que después hay que compilarlo (cc -o ejem0 lex.yy.c -ll) y ligarlo usando "-ll" para usar las librerías de lex, y finalmente lo ejecutamos (ejem0), ahora, cada vez que tecleemos algo, y reciba un retorno de carro, el programa va a imprimir lo mismo que leyó en stdout. Para terminar su ejecución, solo basta con presionar ^C (CONTROL-C).

 

Principales implementaciones

Ambos, Lex y Yacc, fueron desarrollados en los 70's en los laboratorios Bell de AT&T, y estuvieron disponibles desde la 7a Edición de UNIX, versiones antiguas derivadas de BSD seguían usando Lex y Yacc de AT&T, hasta la aparición de flex y bison (Análogos a lex y yacc respectivamente) que cuentan con algunas caracteristicas extra ademas de las tradicionales, así como un mejor soporte para reducciones o expresiones muy largas o complejas.

 

Conceptos Basicos

Formalmente, podemos definir a lex como una herramienta para construir analizadores léxicos o "lexers". Un lexer lee de un flujo de entrada cualquiera, y la divide en unidades léxicas (la tokeniza), para ser procesada por otro programa o como producto final.
Para escribir una especificación léxica en lex, es necesario crear un conjunto de patrones (Expresiones Regulares), mismos, que cuando el programa este completo, van a ser reconocidos como tokens o unidades léxicas.
Lex no produce un programa compilado, lo que hace, es traducir esa especificación a C, incluyendo una rutina llamada yylex(), que es la usada para iniciar en análisis de la entrada.
La entrada es tomada de yyin, que por defecto su valor es stdin, es decir, la pantalla o terminal, pero este valor puede ser modificado por cualquier apuntador a un archivo.
También es posible leer la entrada desde un arreglo de caracteres u otros medios, para cual es necesario implementar algunas funciones de lex mismas que definiremos en la ultima parte de esta sección (Agregar Funcionalidad).

 

 

Ejemplo 1

A continuación se presenta un ejemplo que ilustra de manera general el uso de lex para reconocer patrones de expresiones regulares basicas, que reconoce cualquier numero entero y cualquier palabra formada por letras mayusculas de la "a" a la "z", sin importar si son mayusculas o minusculas.
Download 

%{
#include 
int palabra=0, numero=0;
%}
 
Numero         -?[0-9]+
Palabra          [a-zA-Z]+
 
%%
"bye"             {bye();return 0;}
"quit"            {bye();return 0;}
"resume"       {bye();return 0;}
{Palabra}       {printf("Se leyo la palabra : %s", yytext);palabra++;}
{Numero}       {printf("Se leyo el numero : %d", atoi(yytext));numero++;}
. printf("%s",yytext[0]);
 
 
%%
main(){
          printf("ejem1.l\nEste ejemplo, distingue entre un numero entero y palabras.\nIntroduzca bye, quit o resume para terminar.\n");
          yylex();
}
 
bye(){
          printf("Se leyeron %d entradas, de las cuales se reconocieron\n%d\tEnteros\ny\n%d\tPalabras.\n", (palabra+numero), numero, palabra);
}
 

 

Definiciones

En este ejemplo, una de las primeras cosas a notar, son las dos lineas "%%" que sirven como separadores para las tres secciones de una especificacion lex, la primera, la de definiciones, sirve para definir cosas que se van a usar en el programa resultante o en la misma especificacion, si vemos al ejemplo : 

%{
#include 
int palabra=0, numero=0;
%}
 
Numero         -?[0-9]+
Palabra          [a-zA-Z]+
 

Podemos ver dos tipos de declaraciones, declaraciones de C y declaraciones de lex, las de C son aquellas encerradas entre dos lineas %{ y %} respectivamente que le indican a lex, cuando se incluye codigo que será copiado sin modificar al archivo generado en C (tipicamente lex.yy.c).
Las declaraciones de lex estan formadas por un nombre o identificador y su respectiva expresion regular, su funcionamiento es analogo a aquel del "#define" del preprocesador de C, cada vez que aparecen es como si en ese lugar estubiera escrita la expresion regular equivalente, tambien se pueden usar estas para formar nuevas expresiones regulares, incluso dentro de la misma seccion de declaraciones como veremos más adelante.

Reglas

Esta sección tambien puede incluir codigo de C encerrado por %{ y %}, que será copiado dentro de la función yylex(), su alcance es local dentro de la misma función.
Las reglas de lex, tienen el siguiente formato :

<Expresion regular><Al menos un espacio>{Codigo en C}

En el ejemplo podemos ver que : 

"bye"             {bye();return 0;}
"quit"            {bye();return 0;}
"resume"       {bye();return 0;}
{Palabra}       {printf("Se leyo la palabra : %s", yytext);palabra++;}
{Numero}       {printf("Se leyo el numero : %d", atoi(yytext));numero++;}
. printf("%s",yytext[0]);

son reglas tipicas de lex, donde la primera columna es la lista de expresiones regulares, "bye", "quit" y "resume" por ejemplo, se encargan de terminar con el programa, terminando la funcion yylex() llamando a la funcion bye() y depues return, especificados en la segunda columna.
Como ya vimos en la segunda columna se escriben acciones en C a realizar cada que se acepta una cadena con ese patron, misma que es almacenada en un array apuntado por yytext, podemos ver que las acciones estan encerradas entre "{" y "}" lo que indica que se incluye más de un statement de C por regla, el contra ejemplo es la ultima regla, que reconoce cualquier caracter y lo imprime a la pantalla mediante el uso de printf().
Entonces,podemos decir que una regla de lex esta formada por una expresion regular y la accion correspondiente, tipicamente encerrada entre "{" y "}".

Subrutinas

La tercera y última sección es usada para escribir codigo C, generalmente se usa para incluir funciones o subrutinas que se va a ocupar en el programa resultante, ya sea que se llamen desde una regla como es el caso de bye() en nuestro ejemplo, o que se llamen desde otro lugar como main(), es posible tambien modificar las funciones internas que usa lex, redefiniendolas en esta sección como veremos más adelante.

Expresiones regulares

Para poder crear expresiones regulares y patrones para las reglas, es necesario saber que la concatenacion de expresiones se logra simplemente juntando dos expresiones, sin dejar espacio entre ellas y que es bueno declarar una expresion muy compleja por partes como definiciones, y asi evitar tener errore dificiles de encontrar y corregir.

A continuación una lista de las expresiones regulares mas usadas en lex.

Ops

Ejemplo

Explicación

[]

[a-z]

Una clase de Caracteres, coincide con un caracter perteneciente a la clase, pueden usarse rangos, como en el ejemplo, cualquier caracter, excepto aquellos especiales o de control son tomados literalmente, en el caso de los que no, pueden usarse secuencias de escape como las de C, \t, \n etcétera.
Si su primer caracter es un "^", entonces coincidira con cualquier caracter fuera de la clase.

*

[ \n\t]*

Todas las cadenas que se puedan formar, se puede decir que este operador indica que se va a coincidir con cadenas formadas por ninguna o varias apariciones del patron que lo antecede.
El ejemplo coincide con cualquier convinacion de simbolos usados para separ, el espacio, retorno y tabulador.

+

[0-9]+

Todas las cadenas que se puedan formar, excepto cadenas vacias. En el ejemplo se aceptan a todos los numeros naturales y al cero.

.

.+

Este es una expresión regular que coincide con cualquier entrada excepto el retorno de carro ("\n"). El ejemplo acepta cualquier cadena no vacia.

{}

a{3,6}

Indica un rango de repeticion cuando contiene dos numeros separados por comas, como en el ejemplo, la cadena aceptada sera aquella con longitud 3, 4, 5 o 6 formada por el cadacter 'a'.
Indica una repeticion fija cuando contiene un solo numero, por ejemplo, a{5}, aceptaria cualquier cadena formada por 5 a's sucesivas.
En caso de contener un nombre, indica una sustitucion por una declaracion en la seccion de declaraciones (Revisar el ejemplo1).

?

-?[0-9]+

Indica que el patron que lo antecede es opcional, es decir, puede existir o no. En el ejemplo, el patron coincide con todos los numeros enteros, positivos o negativos por igual, ya que el signo es opcional.

|

(-|+|~)?[0-9]+

Este hace coincidir, al patron que lo precede o lo antecede y puede usarse consecutivamente. En el ejemplo tenemos un patron que coincidira con un entero positivo, negativo o con signo de complemento.

""

"bye"

Las cadenas encerradas entre " y " son aceptadas literalmente, es decir tal como aparecen dentro de las comillas, para incluir carecteres de control o no imprimibles, pueden usarse dentro de ellas secuencias de escape de C. En el ejemplo la unica cadena que coincide es 'bye'.

\

\.

Indica a lex que el caracter a continuacion sera tomado literalmente, como una secuencia de escape, este funciona para todos los caracteres reservados para lex y para C por igual. En el ejemplo, el patron coincide solo con el caracter "." (punto), en lugar de coincidir con cualquier caracter, como seria el casi sin el uso de "\".

<<EOF>>

[a-z]

Solo en flex, este patron coincide con el fin de archivo.

Agregar Funcionalidad

Es posible hacer que el lexer se comporte un tanto diferente de los defaults en cuanto a la implementacion se refiere, redefiniendo las funciones que el lexer usa, algunas de las cosas que se pueden hacer es cambiar la entrada, modificar el manejo de final de archivo, etcetera.
Pero antes de poder hacer esto, es necesario repasar algunas variables y funciones, que se usan dentro de un programa generado por lex.

 

Prototipo

 

Descripcion

char *yytext;

Contiene el token que acaba de ser reconocido, su uso es principalmente dentro de las reglas, donde es comun hacer modificaciones al token que acaba de ser leido o usarlo con algun otro fin. En el ejemplo 1 este token es usado para dar echo en la pantalla.

int yyleng;

Contiene la longitud del token leido, su valor es equivalente a yyleng = strlen(yytext);.

FILE *yyin;

Es un apuntador del que se leen los datos, si este no se modifica, su valor por defecto es stdin.

FILE *yyout;

Es un apuntador a la salida por default del programa, su valor predefinido es stdout.

int input(void);

Esta es en realidad una macro, cuya funcion es alimentar al tokenizer cada vez que se le llama, esta regresa el siguiente caracter de la entrada.

void unput(int);

Esta macro hace lo contrario a input(), esta pone el caracter especificado como argumento de regreso a la entrada del flujo.

void output(int);

Esta macro, escribe su argumento en yyout.

int yyinput(void);

Es una interfaz para la macro input().

void yyunput(int);

Es una interfaz para la macro unput().

void yyoutput(int);

Es una interfaz para la macro output().

int yywrap(void);

Esta funcion sirve para manejar las condiciones de fin de archivo, cada vez que el lexer llega a un fin de archivo, llama a esta funcion para saber que hacer, si regresa 0, entonces sigue leyendo de la entrada, si es 1 el lexer regresa un token nulo para indicar que se llego al fin de archivo.

int yylex(void);

Esta es la funcion principal de un lexer, para anadir codigo a esta funcion, es necesario, incluirlo en la seccion de reglas encerrado entre %{ y %}.

Reimplementaciones y usos más comunes

 
FILE *yyin

Este es un apuntador declarado globalmente que aupunta al lugar de donde se van a leer los datos, por ser un file pointer, este solo puede leer de flujos como archivos, para leer de una cadena es necesario reimplementar el macro input() como se vera mas adelante.

FILE *yyout

Este es el lugar al que se escriben por default todos los mensajes, al igual que yyin esta declarado globalmente y es un apuntador.

int input(void)

El objetivo de esta Macro es alimentar a yylex() caracter por caracter, devuelve el siguiente caracter de la entrada, la intencion más comun para modificar esta funcion, es cambiar el origen de la entrada de manera mas flexible que con yyin, ya que no solo es posible leer de otro archivo, sino que tambien es posible leer el flujo para parsear una cadena cualquiera, o un grupo de cadenas como una linea de comandos.
Para reimplementar esta macro, es necesario primero eliminarla del archivo por lo que es necesario incluir un comando del preprocesador de C el seccion de declaraciones : 

%{
#undef input
%}

y en la parte de subrutinas, implementar nuestro nuevo input() con el prototipo mostrado anteriormente.

 
 
void unput(int)

El objetivo de esta macro, es regresar un caracter a la entrada de datos, es util para yylex() tener una de estas, ya que para identificar un patron puede ser necesario saber que caracter es el que sigue. La intencion de reimplementar esta es complementar el uso de la reimplementacion de input(), ya que input() y unput() deben ser congruentes entre si.
Antes de reimplementar esta, también es necesario eliminarla antes usando una instruccion del preprocesador de C: 

%{
#undef unput
%}
int yywrap(void)

Esta funcion, es auxiliar en el manejo de condiciones de final de archivo, su mision es proporcionarle al programador la posibilidad de hacer algo con estas condiciones, como continuar leyendo pero desde otro archivo etcetera.

int yylex(void)

Esta funcion, es casi totalmente implementada por el usuario en la seccion de reglas, dondcomo ya vimos, puede agregarse codigo encerrado entre %{ y %} asi como en las reglas mismas.

 

 

USANDO YACC

 

Conceptos Basicos

En la seccion anterior de este documento, ya repasamos como generar un analizador lexico, un lexer o tokenizer, que puede reconocer patrones de expresiones regulares y en un momento dado determinar que es lo que se esta leyendo, pero para aplicaciones un poco más complejas, tambien puede ser necesario, analizar gramaticalmente la composicion de la entrada para en un momento dado, determinar si la entrada coincide o no con una gramatica definida y resolverla, o darle algun significado un tanto mas complejo.
Es correcto decir que yacc es una herramienta que sirve para generar un programa, capaz de analizar gramaticalmente una entrada dada por lex, a partir de una especificacion. Esta especificacion, debe contener los tokens reconocidos y los tipos de datos de los mismos si es que se ocupan para realizar operaciones sobre ellos, y una especificacion de gramatica en un formato similar a BNF (Backus Naus Form), que va desde el simbolo no terminal más general a cada una de las opciones terminales.
Ejemplo : 

<Expresion>
Numero + <Expresion>
Numero - <Expresion>
Numero
 

En el ejemplo podemos ver que <Expresion> es un simbolo no terminal que esta compuesto por un "Numero" terminal seguido de un simbolo '+' o '-' terminales seguido por un <Expresion> no terminal, que a su vez puede ser otro numero u otra expresion mas compleja.

 

Es importante notar que esta especificacion es recursiva sobre

<Expresion> pero no es ambigua, es decir, siempre se llegara a un terminal.
Una especificación yacc se divide en tres secciones diferentes de manera similar a lex, la de definiciones, la de reglas, y la de subrutinas, que van igualmente separadas por un '%%', mismas que pueden incluir codigo de C encerrado entre un %{ y un %}.

Ejemplo 1.1 (Mini calculadora)

A continuacion, vamos a analizar un ejemplo sencillo de una verdadera especificacion de yacc, que es la gramatica para una calculadora sencilla que permite hacer operaciones como suma, resta, multiplicacion, divición y exponente.
Download
Download 

%{
#include <math.h>
%}
 
%union{
        double dval;
}
 
%token  <dval> NUMBER 
%token  PLUS    MINUS   TIMES   DIVIDE  POWER
%token  LEFT_PARENTHESIS        RIGHT_PARENTHESIS
%token  END
 
 
%left   PLUS    MINUS
%left   TIMES   DIVIDE
%left   NEG
%right  POWER
 
%type <dval> Expression
%start Input
 
%%
 
Input: Line
          | Input Line
        ;
 
Line:    END
        | Expression END                { printf("Result: %f\n",$1); }
        ;
 
Expression:    NUMBER                        { $$=$1; }
 
        | Expression PLUS Expression    { $$=$1+$3; }
        | Expression MINUS Expression   { $$=$1-$3; }
        | Expression TIMES Expression   { $$=$1*$3; }
        | Expression DIVIDE Expression  { $$=$1/$3; }
        | MINUS Expression %prec NEG    { $$=-$2; }
        | Expression POWER Expression   { $$=pow($1,$3); }
        | LEFT_PARENTHESIS Expression RIGHT_PARENTHESIS { $$=$2; }
        ;
 
%%
int yyerror(char *s) {
  printf("%s\n",s);
}
 
int main(void) {
  yyparse();
}

Definiciones

En esta primera seccion, al igual que en lex, incluimos las librerias que usaremos en el programa, definiciones de los tokens, tipos de datos y precedencia de la gramatica.

%union

Esta definicion, se traduce a una union de C que a su vez dara el tipo de dato a una variable global de nombre yylval que sera de donde yacc tomara los datos a procesar, en la union se definen miembros cuyos correspondientes tipos de datos serán usados para dar el tipo de dato a los tokens como se explicara en la siguiente seccion. %union se traduce de la siguiente forma : 

En yacc :
 
%union{
        double dval;
}
 
En C :
 
typedef union
{
        double dval;
} YYSTYPE;
 

Con esta definicion, yacc declara algunas uniones de este tipo, de las cuales la mas importante es : 

YYSTYPE yylval;

que sera usada en la especificacion de lex, del mismo programa para asignarle valor a los tokens que yacc usara para realizar operaciones. Esta estructura puede llegar a ser muy compleja, y para saber de que tipo es cada token devuelto por yylex(), se usan las definiciones %token y %type.

%token y %type

%token sirve para definir los tokens que hay, y si es necesario, el tipo de dato que usan, todos los tokens son tomados como simbolos terminales, lo cual veremos mejor reflejado en la seccion de reglas, estos tambien tienen el objetivo de servir como etiquetas que yylex() regresa a yacc para identificar el token que se ha leido recientemente.
Su uso es como sigue :
%token [<miembro_de_union>] ETIQUETA1 [ETIQUETA2 ... ETIQUETAn]
Donde todo lo que esta entre [ y ] es opcional.
<miembro_de_union> : Indica el miembro al que seran mapeados los tokens en la union yylval dentro de lex.
ETIQUETAS : Estos son los nombres con los que se identificaran los tokens mismos, que serán traducidos en C como numberos en instrucciones #define del preprocesador de C.

%type es analogo a %token, solo que este define el tipo de dato para simbolos no terminales de nuestra gramatica, la unica diferencia es que el tipo de dato a usar es obligatorio.
En nuestro ejemplo : 

%token  <dval> NUMBER 
%token  PLUS    MINUS   TIMES   DIVIDE  POWER
%token  LEFT_PARENTHESIS        RIGHT_PARENTHESIS
%token  END
 
.
.
.
 
%type <dval> Expression

La primera linea indica que el token NUMERO sera del tipo de miembro de dval, es decir, un double.
Las siguientes tres lineas, son para definir algunos tokens mas que seran usados en la gramatica, pero no necesitan un tipo de dato ni un miembro en yylval asociado.
En la ultima linea definimos el tipo de dato que usara nuestro no terminal Expression.

%left y %right

El siguiente paso, es definir el tipo de precedencia de nuestros tokens operadores, en este punto tenemos dos factores, la precedencia por si misma, y la agrupación de los operadores.

Precedencia

La precedencia es asignada en orden inverso al que aparecen, es decir, el ultimo operador declarado, tiene mayor precedencia que el anterior y asi sucesivamente.

Asociatividad

%left y %right indican si el operador se agrupa a la derecha o a la izquierda, por ejemplo, en el caso de POWER (Exponente) debe asociarse a la derecha, por que buscamos que se resuelva de ese modo, de derecha a izquierda, por ejemplo :

Buscamos que
          4^3^5^2^9
sea evaluado asi :
          4^(3^(5^(2^9)))

Por lo contrario, las sumas y restas queremos resolverlas de izquierda a derecha:

Buscamos que
          4-3+5+2-9
sea evaluado asi :
          (((4-3)+5)+2)-9

Usar este tipo de declaraciones es importante para dismiuir la posibilidad de ambiguedades en el lenguaje generado.

%start

En algunos casos es conveniente indicarle a yacc cual es el simbolo (no terminal) inicial a la hora de hacer el parseo, es decir, el simbolo que se trata de reducir, si esta opcion no es especificada, yacc toma al primer simbolo de la seccion de reglas como simbolo inicial.
En nuestro ejemplo, se presentan ambos casos, nuestro simbolo inicial "Input" se encuentra al inicio del archivo y tambien esta declarado como simbolo inicial. 

%start Input

Reglas

En esta parte finalmente llegamos a la definición de la gramatica, aca podemos observar que cada simbolo se define con su nombre, seguido de dos puntos ":" seguidos de varios simbolos que conformaran su composicion gramatical que en caso de tener varias opciones, son separados por "|" (or) indicando que se tienen varias opciones para reducir ese simbolo y para terminar cada regla, un ";".
Ejemplo :
Si tomamos la gramatica que definimos al principio de esta seccion : 

<Expresion>
Numero + <Expresion>
Numero - <Expresion>
Numero
 

Y la transformamos a una regla de yacc, se veria como esto: 

 
Expresion: NUMERO '+' Expresion           {$$ = $1 + $3;}
          | NUMERO '-' Expresion               {$$ = $1 - $3;}
          | NUMERO                        {$$ = $1;}
          ;
 

en el ejemplo ya transformado a una regla gramatical de yacc, podemos ver que ya se especifica que hacer con los simbolos de la gramatica una vez que son resueltos en la parte de codigo de C. En este ejemplo, Expresion es el simbolo no terminal que se esta definiendo de manera recursiva, el valor que tomara una vez resuelto es el valor asignado a la variable $$, que traducida a C es una variable mapeada al simbolo no terminal, $1, $2 y $3 son variables que son mapeadas al valor de los simbolos de cada linea de cada regla, estas son numeradas de izquierda a derecha.
Ejemplo :

En este segmento de regla :
 
Expresion: NUMERO '+' Expresion
 
Expresion equivale a $$
NUMERO equivale a $1
'+' equivale a $2
y
Expresion (la parte recursiva) equivale a $3
 
todo esto claro, en la parte de acciones en C para cada linea de la regla en yacc.

En el ejemplo tambien podemos encontrar el uso de %prec que sirve para cambiar la precedencia de un operador dependiendo del contexto en el ejemplo, le estamos dando una más alta precedencia a la operacion "menos" cuando esta en un contexto unario, que a la mayoria de los operadores excepto el POWER (exponente) : 

.
.
.
| MINUS Expression %prec NEG    { $$=-$2; }
.
.
.
Reducción

Yacc reduce sus reglas generando un parse tree (no literalmente), y va resolviendo cada regla completa tan pronto como puede, lo cual nos trae un detalle de diseño de gramaticas en yacc, y es la diferencia entre especificar la recursividad por la derecha o por la izquierda, para expresiones muy sencillas que generen un parse tree pequeno no hay ningun problema pero para casos donde la reduccion es compleja, puede desbordar la pila ya que cuando la recursion es derecha, para resolverla, tiene que guardar los datos de la izquierda, y si estos son demaciados, no puede manejarlos.
Por lo contrario, cuando la recursion es izquierda, no tiene que guardar datos que no va a utilizar por que recorre el arbol de izquierda a derecha y resuelve las reglas tan pronto como puede.
En el ejemplo anterior tenemos la recursion por la derecha, un analogo recurrente por la izquierda seri como este : 

 
Expresion: Expresion '+' NUMERO                     {$$ = $1 + $3;}
          | Expresion '-' NUMERO               {$$ = $1 - $3;}
          | NUMERO                        {$$ = $1;}
          ;
 
Especificacion de Lex para el ejemplo1.1

Para que el Ejemplo1.1 pueda funcionar, al igual que cualquier otro programa en yacc, necesita un tokenizer, y a continuacion tenemos su tokenizer correspondiente escrito en lex. 

 
%{
#include "y.tab.h"
#include <stdlib.h>
#include <stdio.h>
%}
 
white           [ \t]+
digit           [0-9]
integer         {digit}+
 
%%
 
{white}         { /* Ignoramos espacios en blanco */ }
"exit"|"quit"|"bye"    {printf("Terminando programa\n");exit(0);}
{integer}        {
                  yylval.dval=atof(yytext);
                  return(NUMBER);
                }
 
"+"           return(PLUS);
"-"           return(MINUS);
"*"           return(TIMES);
"/"           return(DIVIDE);
"^"           return(POWER);
"("           return(LEFT_PARENTHESIS);
")"           return(RIGHT_PARENTHESIS);
"\n"  return(END);
 
%%

Acerca de la seccion de definiciones de este lexer, lo unico relevante que podemos mencionar es la linea de C que dice : 

#include "y.tab.h"

esta linea incluye al archivo y.tab.h que contiene algunas de las definiciones de yacc que lex necesita para poder interactuar con el, entre las mas importantes se encuentran definidas todas las etiquetas de los tokens, como PLUS, MINUS, NUMBER, etcetera. Estas constantes son los valores que yylex() regresara a yyparse() (la funcion del parser de yacc) para identificar el tipo de token que recien se ha leido.
En la seccion de reglas, en la parte del codigo, podemos ver como al final de cada regla, se hace un return especificando la etiqueta que fue declarada como %token o como %left/%rigth en la especificacion yacc.
Para compilar y correr este ejemplo en sistemas UNIX o similares : 

$ lex ejem1.1.l
$ yacc -d ejem1.1.y
$ cc -o ejem1.1 lex.yy.c y.tab.c -ly -ll -lm
$ ejem1.1
25*5-5
Result: 120.000000
5^2*2
Result: 50.000000
5^(2*2)
Result: 625.000000
bye
Terminando programa
$

Subrutinas

En esta ultima seccion, es posible reimplementar, siguiendo la misma idea de lex, algunas funciones que pueden ser utiles en algun momento dado o declarar nuevas funciones para usar dentro de nuestro codigo o nuestras reglas, no hay mucho que reimplementat a este nivel (yacc) a menos que sea con propositos realmente especificos. Las funciones mas comunmente implementadas son main() e yyerror(), la primera se usa para presonalizar el programa con mensajes antes o despues del parser, o para llamarlo varias veces en el codigo y la segunda la ocupa yyparse() cada vez ue encuentra un error de sintaxis, en este ejemplo, se incluyen ambas con su contenido minimo.

 

Juntos Lex & Yacc

A continuacion se presenta un ejemplo mas complejo con explicación y algunas corridas del mismo.

Ejemplo 2

Descripción

El ejemplo 2 es una calculadora booleana/aritmetica que puede relover expresiones entre numeros y cadenas por igual, aplicando algunos estandares para ello, el resultado de esta calculadora sera verdadero o falso dependiendo si su resultado es mayor que o menor o igual que cero (recordando los parametros booleanos en C) la lista de operadores, en orden de precedencia, de mayor a menor son:

Ops

Descripción

^ , | , &

XOR , OR y AND bit por bit. (funcionan igual que en C)

+ , -

Suma y Resta.

* , / , %

Multiplicacion, Divición y Módulo.

eq , ne , gt , lt , ge , le

Comparadores entre cadenas, 'igual que', 'diferente de', 'mayor que', 'menor que', 'mayor o igual que' y 'menor o igual que' respectivamente entre cadenas, estos operadores son analogos a las funciones de comparacion entre cadenas de la libreria "string.h" de C.

|| , && , > , < , == , != , >= , <=

Comparadores y operadores logicos, OR , AND, 'mayor que', 'menor que', 'igual que', 'diferente de', 'mayor o igual que' y 'menor o igual que' respectivamente.

!

Descripción

-

Descripción

~

Descripción

Cuando se usan operadores numericos entre cadenas o mixtos, el valor tomado para las cadenas es la longitud de la misma, si se usan numeros con operadores de cadenas se genera un error de sintaxis.

A continuacion el codigo de ejemplo :

Lexer : 

%{
#define HELLO "Parser booleano/aritmetico\nPor: Oscar Medina Duarte\nBajo licencia BSD"
#include "y.tab.h"
#include <math.h>
#include <string.h>
#include <stdlib.h>
 
%}
 
Natural ([0-9]+)
Cadena \"[^"\n]*["]
Return "\n"
 
%%
%{
int i;
%}
 
{Return} {return NL;}
"bye"|"quit"|"exit"|"resume"          {return BYE;}
 
{Natural} {
                    yylval.entero =atoi(yytext);
                    return ENTERO;
                    }
{Cadena} {
                    for(i=1;i<strlen(yytext)-1;i++)
                               yytext[i-1] = yytext[i];
                               
                    yytext[i-1] = '\0';
                    yylval.cadena = malloc(strlen(yytext)+1);
                    strcpy(yylval.cadena,yytext);
                    return CADENA;
                    }
 
"=="              {return EQ;}
"!="               {return NE;}
"||"               {return OR;}
"&&"              {return AND;}
">="               {return GEQ;}
"=>"               {return GEQ;}
"<="               {return LEQ;}
"=<"               {return LEQ;}
 
"eq"              {return SEQ;}
"ne"              {return SNE;}
"gt"               {return SG;}
"lt"                {return SL;}
"ge"              {return SGE;}
"le"               {return SLE;}
 
[ \t];
. return yytext[0];
 
 
%%
 

Comentarios sobre este lexer

Cuando se reconoce una cadena, esta se encuentra encerrada entre "`s y es necesario eliminar las comillas de yytext, antes de asignarlo a yylval.cadena que es de donde el parser tomara el valor.


Parser : 

%{
int CharFlag=0;
%}
%union{
          char *cadena;
          int entero;
}
 
%token NL BYE
%token <cadena> CADENA;
%token <entero> ENTERO;
 
%left '^' '|' '&'
%left '-' '+' 
%left '*' '/' '%'
%left SEQ SNE SG SL SGE SLE
%left OR AND '>' '<' EQ NE GEQ LEQ
 
%nonassoc SNOT
%nonassoc SMENOS
%nonassoc SNNOT
 
%type <entero> expression
 
%%
 
entrada: statement
          | entrada statement
        ;
 
 
statement: NL 
          | expression NL                  {printf("== %d \n",$1);}
          | BYE NL       {printf("Cerrando calculadora...\n");exit(0);}
          ;
 
expression: expression '+' expression       {$$ = $1 + $3;}
          | expression '-' expression  {$$ = $1 - $3;}
          | expression '*' expression  {$$ = $1 * $3;}
          | expression '/' expression  
                    {
                               if($3 == 0.0)
                                         yyerror("Division por cero\n");
                               else
                                         $$ = $1 / $3;
                    }
          | expression '%' expression 
                    {
                               if($3 == 0.0)
                                         yyerror("Division por cero\n");
                               else
                                         $$ = $1 % $3;}
          
          | expression '^' expression  {$$ = $1 ^ $3;}
          | expression '|' expression  {$$ = $1 | $3;}
          | expression OR expression {$$ = $1 || $3;}
          | expression '&' expression {$$ = $1 & $3;}
          | expression AND expression         {$$ = $1 && $3;}
          | expression '>' expression  {$$ = $1 > $3;}
          | expression '<' expression  {$$ = $1 < $3;}
          | expression EQ expression {$$ = $1 == $3;}
          | expression NE expression {$$ = $1 != $3;}
          | expression GEQ expression         {$$ = $1 >= $3;}
          | expression LEQ expression         {$$ = $1 <= $3;}
          
          | CADENA SEQ CADENA
                    {
                               CharFlag=1;
                               if(strcmp($1,$3)==0)
                                         $$ = 1;
                               else $$ = 0;
                    }
          | CADENA SNE CADENA
                    {
                               CharFlag=1;
                               if(strcmp($1,$3)==0)
                                         $$ = 0;
                               else $$ = 1;
                    }
          | CADENA SG CADENA
                    {
                               CharFlag=1;
                               if(strcmp($1,$3)>0)
                                         $$ = 0;
                               else $$ = 1;
                    }
          | CADENA SL CADENA
                    {
                               CharFlag=1;
                               if(strcmp($1,$3)<0)
                                         $$ = 0;
                               else $$ = 1;
                    }
          | CADENA SGE CADENA
                    {
                               CharFlag=1;
                               if(strcmp($1,$3)>=0)
                                         $$ = 0;
                               else $$ = 1;
                    }
          | CADENA SLE CADENA
                    {
                               CharFlag=1;
                               if(strcmp($1,$3)<=0)
                                         $$ = 0;
                               else $$ = 1;
                    }
          
          | '!' expression %prec SNOT         {$$ = !$2;}
          | '-' expression %prec SMENOS   {$$ = -$2;}
          | '~' expression %prec SNNOT     {$$ = ~$2;}
          | '('expression')'      {$$ = $2;}
          | ENTERO
          | CADENA
                    {
                               if (CharFlag==0)
                                         $$ = strlen($1);
                               else{
                                         $$ = $1;
                                         CharFlag=0;
                               }
                               
                    }
          ;
 
%%
 
main (){
          printf("Parser de Expresiones variadas\n");
          yyparse();
 
}

Para correr este parser :

$ flex ejem2.l
$ yacc -d ejem2.y
$ cc -o ejem2 lex.yy.c y.tab.c -ly -ll -lm
$ ejem2
Parser de Expresiones variadas
25+"hola"
== 29 
"hola"eq"helo"
== 0 
"hola"=="helo"
== 1 
"s"=="s"
== 1 
"hola"=="hole"
== 1 
12+23
== 35

 

 

 

 

CONCLUSION

 

 

Un generador de analizadores es un programa que acepta como entrada la especificación de las ca­racterísticas de un lenguaje  y produce como salida un analizador paraelLa especificación de en­trada puede referirse a la lexicografía, la sintaxis o la semántica; el analizador resultante servirá para analizar las características especificadas.

 

 

Los generadores Lex y Yacc sirven, respectivamente, para generar analizadores lexicográficos y analizadores sintácticos para su aprovechamiento como partes de los compiladores de los lenguajes de programación; estos usos de Lex y Yacc no son los únicos, aunque sí son los que aquí se consi­deran principalmente.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Bibliografía y Referencias

ACG+94 ABD-ALLAH, Ahmed, CLARK, Bradford, GACEK, Cristina y BOEHM, Barry. Knowledge

Summary. USC Center for Software Engineering - Focused Workshop on Software

Architectures, USC (Los Angeles, CA) - 6 al 9 de Junio de 1994.

AG96 ATKINSON, Darren C. y GRISWOLD, William G. The Design of Whole-Program

Analysis Tool. En Proceedings of the 18th International Conference on Software

Engineering (ICSE-18), Berlin, Alemania, Marzo 1996.

Agr91 AGRAWAL, Hiralal. Towards Automatic Debugging of Computer Programs. Phd.

Thesis, Purdue University, Agosto 1991.

ASU86 AHO, Alfred V., SETHI, Ravi y ULLMAN, D. Jeffrey. Compilers: Principles, techniques

and tools. Addison Wesley,1986.

BE94 BALL, Thomas y EICK, Stephen G. Visualizing Program Slices. Proceedings of the

1994 IEEE Symposium on Visual Languages. pp. 288-295. Octubre 1994.

BE96 BALL, Thomas y EICK, Stephen G. Software Visualization in the Large. IEEE

Computer, pp. 33-43. Abril 1996.

BM92 BALLANCE, Robert A. y MACCABE, Arthur B. Program dependence graph for the rest

of us. Tehnical Report 92-10, University of New Mexico, Agosto 1992.

Ern94 ERNST, Michael D. Practical fine-grained static slicing of optimised code. Microsoft

Research Technical Report MSR-TR-94-14, Redmond, Julio 1994.