Tutorial de Lex & Yacc
Genreración de Parsers de Gramaticas Libres de Contexto.

Regístrate y participa en el foro: http://flex.chocoforum.com
www.medina-web.com

Índice :

Usando Lex

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 ejem1.l 
%{
#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.

Copyright © 2002 Oscar Medina Duarte
Cualquier persona es libre de imprimir y reproducir este documento siempre y cuando esta nota permanezca en el documento.