Lex Y Yacc

Reseña
¿ 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 sustokens 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 ejemploanterior 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 :

=======================================
%%

. 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 estuvierondisponibles 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, podemosdefinir 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 aun 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...