PDF de programación - 8- LEX-Expresiones regulares

8- LEX-Expresiones regulares


Objetivos:


 Utilizar la herramienta KEX para trabajar con expresiones regulares


Recursos:


 Maquina virtual Linux distribución Bodhi
 LXterminal y FLEX



Introducción

Flex le permite implementar un analizador léxico escribiendo reglas que coinciden en
expresiones regulares definidas por el usuario y la realización de una acción específica para
cada patrón emparejado. Flex compila su archivo de reglas (por ejemplo, "lexer.l") a C (o, si
está usando JLex, Java) Código fuente de la implementación de un autómata finito que
reconoce
las expresiones regulares que especifique en su archivo de reglas.
Afortunadamente, no es necesario entender o incluso mirar el archivo generado
automáticamente (y a menudo muy desordenado) la implementación de sus normas.

Lenguajes regulares
Los lenguajes regulares sobre un alfabeto dado ∑ son todos los lenguajes que se pueden
formar a partir de los lenguajes básicos Ø, { λ }, {a}, a ∈ ∑, por medio de las operaciones de
unión, concatenaci+on y estrella de Kleene.
Podemos dar una definición recursiva de los lenguajes regulares. Sea ∑ un alfabeto.

1. Ø, { λ } y {a}, para cada a ∈ ∑, son lenguajes regulares sobre ∑. Estos son los

denominados lenguajes regulares básicos.

2. Si A y B son lenguajes regulares sobre ∑, también lo son:

A ∪ B (unión
A . B (concatenación)
A*

Observese que ∑ y ∑* son lenguajes regulares sobre ∑


Ejemplo Sea Σ = {a, b}. Los siguientes son lenguajes regulares sobre Σ.
1. El lenguaje A de todas las palabras que tienen exactamente una a:
A = {b}* · {a} · {b}*
2. El lenguaje B de todas las palabras que comienzan con b:

B = {b} · {a, b}*

3. El lenguaje C de todas las palabras que contienen la cadena ba:


C = {a, b}*· {ba} · {a, b}*



Expresiones regulares

Las expresiones regulares representan lenguajes regulares y su propósito es
simplificar la escritura de los lenguajes regulares.
La siguiente es la definición recursiva de las expresiones regulares sobre un alfabeto
Σ dado.

1. Expresiones regulares básicas:

Øes una expresión regular que representa al lenguaje Ø
λ es una expresión regular que representa al lenguaje {λ}.
a es una expresión regular que representa al lenguaje {a}, a ∈ Σ

2. Si R y S son expresiones regulares sobre Σ, también lo son:

RS
R ∪ S
R*

RS representa la concatenación de los lenguajes representados por R y S; RUS representa
su unión, y R* representa la clausura de Kleene del lenguaje representado por R.

Patrones



Procedimento
Crear el programa en LEX pascal.l
/* analizador básico un lenguaje similar a Pascal */

%{
/* se necesita math.h para la llamada a atof()*/
#include <math.h>
%}

DIGITO [0-9]
ID [a-z][a-z0-9]*

%%

{DIGITO}+ {
printf( "Un entero: %s (%d)\n", yytext,
atoi( yytext ) );
}

{DIGITO}+"."{DIGITO}* {
printf( "Un real: %s (%g)\n", yytext,
atof( yytext ) );
}

if|then|begin|end|procedure|function {
printf( "Una palabra clave: %s\n", yytext );
}

{ID} printf( "Un identificador: %s\n", yytext );

"+"|"-"|"*"|"/" printf( "Un operador: %s\n", yytext );

"{"[^}\n]*"}" /* elimina una linea de comentarios */

[ \t\n]+ /* elimina los espacios en blanco */

. printf( "Caracter no reconocido: %s\n", yytext );

%%

main()
{
yylex();
}


Luego de compilar el programa pruébelo con el siguiente archivo fuente.txt
{programa que calcula el factorial }
Fuction f1
begin
if(n>1) then

F1 :=n*(f1(n-1))
Else
F1:=n
end;

Ejercicios:

Construir un analizador léxico usando FLEX que identifique los token de un fichero fuente
C.

El analizador recibirá como parámetro de línea de comandos el nombre de un archivo
fuente en C. Para cada token que identifique imprimirá por pantalla su tipo, el valor
asociado (si lo tiene) y la línea en la que se encuentra. Por ejemplo :


int prueba(void)
{
return 12;
}

Tendrá como salida :


TK_TIPO_INT linea=1
TK_IDENTIFICADOR linea=1
TK_PARENT_ABIERTO linea=1
TK_TIPO_VOID linea=1
TK_PARENT_CERRADO linea=1
TK_INICIO_BLOQUE linea=2
TK_RETURN linea=3
TK_CONST_ENTERA Valor=12 linea=3
TK_FIN_SENTENCIA linea=3
TK_FIN_BLOQUE linea=4


Consideraciones

El nombre asignado a cada tipo de token es libre

Se cubrirá sólo un subconjunto de las palabras reservadas de C. Habrá un token asociado a
cada una de esas palabras reservadas.

Lista de palabras reservadas en C a reconocer.

break case char continue default
do double else enum float
for goto if int return
struct switch typedef union void
while



Las palabras reservadas no listadas, se indicarán con un token de error.

Habrá un token para cada uno de los siguientes símbolos:


"(" ")" "{" "}" ";" y ","


Para simplificar, se considerará un único token que englobará a todos los posibles
operadores. Sólo será necesario soportar los operadores de la siguiente lista.


"+" "-" "*" "/" "=" "++" "--"
"<" ">" "==" "!=" "&&" "||"
"&" "|" "~"

Probar con un programa escrito en C, las librerías se pueden ignorar