LEX Y YACC

¿ Que son y para que sirven ?

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 programació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 ejem0.l

=======================================

. 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

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

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.

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 ejem1.1.y
Download ejem1.1.l

%{

#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

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 :
Download ejem2.l y ejem2.y
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.
Este lexer esta probado usando flex si estas usando Solaris o SunOS algun sistema similar, puedes bajar la version 2.5.4 compilada y lista para usarse haciendo click aca.
Download ejem2.l y ejem2.y
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

bye

Cerrando calculadora...

Comentarios sobre este Parser

Se usa la variable CharFlag para indicar que valor se usara cuando se tienen cadenas, ya sea su valor numerico (su longitud) o como cadena.

Comunicación entre YACC y LEX

Los programas que son generados por yacc y lex están diseñados para funcionar juntos. Así, lex debe devolver los números de token que asigna yacc¹², y yacc llama a una función yylex que debe retornar en cada caso exactamente lo mismo que retorna la que genera lex.

Además de devolver un entero indicando qué token se ha reconocido, el analizador léxico debe devolver el valor léxico de ese token. El lexema que el analizador generado por lex ha reconocido se copia en la cadena de caracteres yytext (y no yytexto como pone en la traducción a castellano del libro de Aho, Sethi y Ullman, en la página 113). 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 yylval¹³ que debe rellenar el analizador léxico ¹⁴ y que yacc copia en la pila semántica cuando desplaza el símbolo a la pila sintáctica.

Notas al pie

...yacc¹²

Es posible (con la opción -d) hacer que yacc genere un fichero y.tab.h que contenga sólo los defines, para ser utilizado con lex.

... yylval ¹³

Dependiendo de la versión de yacc y lex está declarada en el código que genera yacc o en el código que genera lex.

... l\'exico ¹⁴

Las acciones que se ejecutan cuando se reconoce un componente léxico deben asignar un valor adecuado a esa variable antes de devolver con return el número correspondiente a ese componente léxico.

LEX

Estructura de un programa en LEX

{ definiciones }

{ reglas }

{ subrutinas del usuario }

Las definiciones y subrutinas son opcionales. El segundo %% es opcional pero el primer %% indica el

comienzo de las reglas.

Expresiones Regulares

Las expresiones regulares en LEX son formadas en base a las siguientes reglas:

· Si se desea una expresión regular cuyo lenguaje que denota sea a entonces la expresión

regular es a.

· Las operaciones básicas de una expresión regular (selección, concatenación, cerradura de

Kleen y cerradura positiva, son representadas como :

n a | b es la expresión regular que denota la selección entre a y b.

n ab es la expresión regular que denota la concatenación de a y b.

n a* es la expresión regular para indicar la cerradura de Kleen.

n a+ es la expresión regular para indicar la cerradura positiva.

n Agrupamiento. El agrupamiento es realizado con el uso de los operandos ( y ).

LEX incluye otros operadores para darle mayor poder a las expresiones regulares y estos son:

· Clases de Caracteres. Son especificadas utilizando el operador [ ], por ejemplo [abc], lo

cual indica que se puede seleccionar entre el carácter a, b o c. Dentro de los corchetes, la

mayoría de los operandos son ignorados, excepto:

· \. Secuencia de Escape. Permite indicar números en octal, los cuales son considerados

como caracteres, así como la indicación de considerar operadores como caracteres.

· ^. Complemento del conjunto dentro de los corchetes, debe colocarse inmediatamente

después del corchete izquierdo.

· -. Operador de rango, indica un rango de elementos dentro del conjunto, dicho rango se

especifica en orden ascendente y su comportamiento está establecido por el código ASCII

o EBCDIC.

[a-z] [^a-z] [\0\n] [\0-\134]

· Expresiones Opcionales. El operador ? indica que un elemento es opcional en una

expresión.

ab?c

· Sensitivo al Contexto. Son operadores para condicionar la aceptación de una cadena

que cumpla con un cierto patrón.

n ^. Si el primer carácter de una expresión es ^, entonces una cadena que cumpla

con dicha expresión solo será aceptada si comienza al principio de una línea

(después de una nueva línea y al comienzo de la entrada).

^abc

n /. Condiciona la aceptación de una cadena siempre y cuando termine con un cierto

patrón.

ab/cd

n $. Condiciona la aceptación de una cadena si esta termina con un carácter de

nueva línea.

ab$ = ab/\n

n <>. Indican que la aceptación solo re sealiza si se cumple con la condición que se

encuentre dentro de los símbolos de mayor y menor que.

<x> = ^x si la condición es que comience desde el principio de la línea

· Repeticiones y Definiciones. Los operadores { y }, sirven vara indicar repeticiones o para

hacer uso de una constante previamente definida.

{digito} Usa el valor de digito y sustituye el nombre por su valor en la expresión.

a{1,5} Espera desde una a cinco ocurrencias de a.

· Operadores para indicar operadores como caracteres. Permiten tratar a los operadores

como caracteres dentro de una expresión, dichos operadores son:

n \. Secuencia de Escape. Permite indicar números en octal, los cuales son

considerados como caracteres, así como la indicación de considerar operadores

como caracteres.

\n \{ \%

n "". Comillas dobles. Se coloca el carácter entre comillas y es tratado como tal y no

como un operador, en caso de serlo.

"\t" "[" "a"

· Operador .. Este operador sirve para aceptar cualquier otra cosa que no haya sido

especificada en patrones previos. Si el punto es colocado como parte de una expresión

permite indicar que se aceptan todos los caracteres excepto el fin de linea.

Acciones

Cuando una cadena que se está analizando cumple con una expresión, se ejecuta la acción asociada a dicha

expresión. La acción que se asocia a la expresión se escribe en lenguaje C, pero LEX no realiza ninguna

verificación sobre dicha acción, para LEX esta acción es como si fuera un comentario.

[ \t\n] ;

En esta regla, la acción es nula, por lo tanto, lo que se hace es que los caracteres dentro de los corchetes sean

ignorados.

[a-z]+ printf( "%s", yytext );

En esta regla, la acción a realizar es la impresión del valor de yytext.

Si se requiere que una acción esté formada por más de una instrucción, entonces se usan los operadores { y },

donde las instrucciones son especificadas dentro de las llaves.

\"[^"]* { if (yytext[yyleng-1] == ‘\\')

yymore();

else

….

}

Existen en LEX ciertas variables y funciones predefinidas, las cuales son utilizadas normalmente en la parte

correspondiente a las acciones.

Cuando se requiere que dos o más reglas realicen la misma acción, se puede utilizar el operador | al final de cada

expresión:

{d}{s}{e}{n} |

{d}{c}{o}{s} |

…

{d}{r}{e}{a}{l} printf( "%s"m yytext+1 );

Variables

· yylex. Variable de tipo char * que contiene la cadena que cumplió un patrón (lexema).

· yyleng. Variable de tipo int que contiene la longitud del valor contenido en yytext.

Funciones

· yymore(). Permite indicarle a LEX que la siguiente cadena que sea reconocida va al final

de la cadena que se acaba de reconocer.

· yyless( n ). Permite indicarle a LEX que los n últimos caracteres en yytext son requeridos

en este momento y deben ser reprocesados. Por ejemplo, si en C queremos resolver el

problema de ambigüedad generado por "=-a" y suponiendo que se desea tratar como "=a"

entonces:

=-[a-zA-Z] {

printf( "Op ( =-) ambigüo\n");

yyless( yyleng-1);

…..

}

Si se reguiere que sea tratado como "=-a", entonces tenemos

=-[a-zA-Z] {

printf( "Op ( =-) ambiguo \n");

yyless( yyleng-2);

…..

}

Una forma para escribir lo anterior sería:

=-/[A-Za-z] en el primer caso

=/-[A-Za-z] para el segundo

· input(). Regresa el siguiente carácter a ser leido.

· output( c ). Escribe el carácter c en el lugar indicado como salida.

· unput( c ). Coloca el carácter c en la entrada, para que posteriormente pueda ser leído.

· yywrap(). Es una función que regresa una valor de 1 para indicar que LEX termina el

proceso de análisis al encontrar el fin de archivo, pero si regresa 0 al encontrarse el fin de

archivo, esto le indica a LEX que el análisis debe continuar pero en un archivo diferente.

· yylex(). Función para inicial el análisis

LEX maneja especificaciones ambiguas, lo cual se presenta cuando una cadena de entrada cumple con más de un

patrón, por lo que LEX realiza las siguientes acciones:

· Selecciona la regla en la que el empatamiento sea más largo.

· Para las reglas en donde el empatamiento es el mismo número de caracteres, se da

preferencia a la primera regla en orden de aparición.

Definiciones

· Cualquier texto en un programa para LEX, que no es tratado, es copiado enteramente al programa

generado.

· Cualquier línea que no sea parte de una regla en LEX o una acción que comience con un espacio

en blanco o tabulador, son copiados al programa a ser generado.

· Cualquier cosa que haya sido incluida entre %{ y %}. Los delimitadores son descartados.

Normalmente son utilizados para indicar acciones de preprocesamiento (include, define, etc. ).

· Cualquier cosa que aparezca después del segundo %%.

Las definiciones en LEX son especificadas antes del primer %%, donde cualquier línea en esta sección que no

esté dentro de %{ y %} y que comience en la columna uno, se asume que es una definición de sustitución de

cadenas.

D [0-9]

E [DEde][-+]?{D}+

{D}+ printf( "Entero" );

{D}+ "."{D}*({E})?|{D}*"."{D}+({E})?|{D}+{E}

Uso

· Compilar el programa escrito para LEX

lex programa

· Compilar el programa generado por LEX con un compilador de C.

· Ejecutar el programa objeto resultante de la siguiente manera.

programa >entrada <salida

LEX y YACC

LEX escribe una función llamada yylex(), la cual es requerida por YACC, para que pueda hacer su análisis.

Normalmente, la acción que se realiza cuando se cumple un patrón es regresar a YACC un token asociado con el

patrón que se cumple.

return (token);

Donde los tokens son definidos en un archivo de encabezado y posteriormente es incluido

Ejemplo

/* Archivo de Encabezado */

#define identificador 0

#define numero 1

#define suma 2

#define error 3

/* Archivo de LEX */

#include "encabeza.h"

D [0-9]

L [A-Za-z]

(_|{L})({L}|{D}|_)* return identificador;

{D}+ return numero;

+|\- return suma;

. return error;

main()

{

yylex();

}

Sumario

El esquema general de un archivo fuente de LEX es

{definiciones}

{reglas}

{subrutinas}

La sección de definiciones esta formada por una combinación de

· Definiciones, en la forma nombre espacio traslación.

· Código, en la forma espacio código.

· Código, en la forma %{ código %}.

· Condiciones de inicio, en la forma %S nombre1 nombre2 …

· Tablas de conjuntos de caracteres, en la forma

numero espacio cadena-de-caracteres

· Cambios de tamaños a arreglos internos

%x nnn

donde nnn es un número entero representando el tamaño de un arreglo y x puede ser cualquiera

de los siguientes valores

o p posiciones

o n estados

o e nodos del árbol

o a transiciones

o k clases empacadas de caracteres

o o arreglo de salida.

Las líneas en la sección de reglas son de la forma expresión acción, donde la acción puede contener más de una

línea usando las llaves como delimitadores.

Las expresiones regulares en LEX usan los siguientes operadores:

x el carácter "x".

"x" el carácter "x", aún si x es un operador.

\x el carácter "x", aún si x es un operador.

[xy] el carácter x o y.

[x-z] los caracteres x, y o z.

[^x] cualquier carácter excepto x.

. cualquier carácter excepto nueva línea.

^x una x al comienzo de una línea.

<y>x una x si se cumplió la condición y.

x$ una x al final de la línea.

x? Una x opcional.

x* 0, 1, 2, … ocurrencias de x.

x+ 1, 2, 3, … ocurrencias de x.

x|y una x o una y.

(x) una x.

x/y una x pero solo si es seguida por una y.

{xx} la sustitución de xx por su valor especificado en la sección de definiciones.

x{m,n} de m hasta n ocurrencias de x.