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 :


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


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