PDF de programación - Lex como localizador de expresiones regulares con acciones asociadas - Modelos de Computación 1

Modelos de computación 1.
Prácticas



Pag. 1

Modelos de Computación I

Ingeniería Informática



Lex como localizador de expresiones regulares

con acciones asociadas



Práctica 1

Curso 2008-2009



Profesores:

Carlos J. Mantas Ruiz
Aida Jiménez Moscoso del Prado


Modelos de computación 1.
Prácticas



Pag. 2

Práctica 1



1.- Introducción


Normalmente, Lex se usa en la primera etapa necesaria a la hora de elaborar un
compilador, un intérprete, un emulador o cualquier otro tipo de herramienta que necesite
procesar un fichero de entrada para poder cumplir su misión.

Otra utilidad de Lex consiste en ser una herramienta que nos permite ejecutar acciones
tras la localización de cadenas de entrada que emparejan con expresiones regulares.

En esta prácticas nos centraremos en esta segunda utilidad de Lex. Se le pedirá al
estudiante la realización de un trabajo práctico de procesamiento de un fichero que
involucre el uso de Lex para localizar ciertas cadenas en el fichero y ejecutar una acción
correspondiente con cada una de ellas. Por ejemplo, localizar y borrar direcciones de
correo electrónico en una página web; cambiar de color los comentarios de un fichero con
código fuente en C++; etc.

El alumno deberá plantear su propio trabajo práctico de procesamiento de ficheros usando
Lex. A continuación se describirá una breve introducción sobre Lex y sus conceptos
asociados que podrá servir de ayuda al estudiante para la realización de su práctica.


2.- Introducción a Lex

Lex es una herramienta de los sistemas UNIX/Linux que nos va a permitir generar código
C que luego podremos compilar y enlazar con nuestro programa. La principal
característica de Lex es que nos va a permitir asociar acciones descritas en C, a la
localización de las Expresiones Regulares que le hayamos definido.

Lex se apoya en una plantilla que recibe como parámetro y que deberemos diseñar con
cuidado. En esta plantilla le indicaremos las expresiones regulares que debe localizar y las
acciones asociadas a cada una de ellas.

A partir de esta plantilla, Lex genera código fuente en C. Este código contiene una
función llamada yylex(), que localiza cadenas en la entrada que se ajustan a las
expresiones regulares definidas, realizando entonces las acciones asociadas a dicho
patrón.



3.- Expresiones regulares en Unix

Una expresión regular es un patrón que describe un conjunto de cadenas de caracteres.
Por ejemplo, en MS-Dos el patrón aba*.txt describe el conjunto de cadenas de caracteres
que comienzan con aba, contienen cualquier otro grupo de caracteres, luego un punto, y
finalmente la cadena txt.

Modelos de computación 1.
Prácticas



Pag. 3

Una Expresión Regular en Unix nos sirve para definir lenguajes, imponiendo
restricciones sobre las secuencias de caracteres que se permiten en este lenguaje. Por
tanto una Expresión Regular estará formada por el conjunto de caracteres del alfabeto
original, más un pequeño conjunto de caracteres extra (meta-caracteres) que nos
permitirán definir estas restricciones.

El conjunto de metacaracteres para expresiones regulares es el siguiente:

\ ^ $ . [ ] { } | ( ) * + ?


Estos caracteres, en una expresión regular, son interpretados de una manera especial y no
como los caracteres que normalmente representan. Una búsqueda que implique alguno de
estos caracteres obligará a usar el carácter \ . Por ejemplo, en una expresión regular, el
caracter ‘.’ representa "un caracter cualquiera"; si escribimos \. , estamos representando el
caracter ‘.’ tal cual, sin significado adicional.


Expresión Regular
Caracteres normales

.
r*
r+
r?
r | r
1
^
$

-

2

[...]

[^...]

(...)
\n
\t
r r1 2
r{n}
r{n,}
r{,m}
r{n,m}
{nombre}

“...”
\b

\metacarácter

Significado

Ellos mismos
Un carácter cualquiera excepto el carácter fin de línea
r debe aparecer cero o más veces
r debe aparecer una o más veces
r debe aparecer cero o una vez
La expresión regular r1 o la r2
Comienzo de línea
Fin de línea
Dentro de un conjunto de caracteres escrito entre corchetes,
podemos especificar un rango (ej. [a-zA-Z0-9].
Un carácter cualquiera de los incluidos entre corchetes; acepta
intervalos del tipo a-z, 0-9 A-Z, etc.
Cualquier carácter menos el indicado o indicados entre
corchetes; acepta intervalos del tipo a-z, 0-9 A-Z, etc.
Agrupación de los elementos dentro del paréntesis
Carácter de salto de línea, fin de línea
Carácter de tabulación
La expresión regular r1 seguida de la expresión regular r2
n ocurrencias de la expresión regular r
n o más ocurrencias de la expresión regular r
Cero o a los sumo m ocurrencias de la expresión regular r
n o más ocurrencias de la expresión regular r, pero a lo sumo m
Se sustituye la expresión regular llamada nombre
Los caracteres entre comillas literalmente
Indica un espacio en blanco
Literalmente el metacarácter

Modelos de computación 1.
Prácticas



Pag. 4

Ejemplos de expresiones regulares

Expresión Regular

Significado

a.b
a..b
[abc]
[aA]

[aA][bB]

[0123456789]

[0-9]

[A-Za-z]

[0-9][0-9][0-9]

[0-9]*

[0-9][0-9]*

^1
^[12]
^[^12]

(123|124)$

[0-9]+
[0-9]?
(ab)*
^[0-9]?b
([0-9]+ab)*
(ab|cd+)?(ef)*

[xy]
[^abc]
“$”

axb aab abb aSb a#b ...
axxb aaab abbb a4$b ...
a b c (cadenas de un carácter)
a A (cadenas de un carácter)
ab Ab aB AB (cadenas de dos caracteres)
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
A B C ... Z a b c ... z
000 001 .. 009 010 .. 019 100 .. 999
Cadena vacía 0 1 9 00 99 123 456 999 9999 ...
0 1 9 00 99 123 456 999 9999 99999 99999999 ...
Símbolo ‘1’ al comienzo de una línea
Símbolo ‘1’ o ‘2’ al comienzo de una línea
Cualquier símbolo al comienzo de una línea menos ‘1’ o ‘2’
Cadenas “123” o “124” al final de una línea
0 1 9 00 99 123 456 999 9999 99999 99999999 ..
Cadena vacía 0 1 2 .. 9
Cadena vacía ab abab ababab ...
Cadenas b 0b 1b 2b ... 9b al comienzo de una línea
Cadena vacía 1234ab 9ab9ab9ab 9876543210ab 99ab99ab ...
Cadena vacía abef cdef cdddd efefef
Representa el carácter ‘x’ o el carácter ‘y’
Representa cualquier carácter excepto ‘a’, ‘b’ o ‘c’
Carácter ‘$’, no indica fin de línea



Declaraciones

%%

Reglas

%%

Procedimientos de Usuario

%%

Modelos de computación 1.
Prácticas



Pag. 5



4.- Estructura de un fichero Lex

La plantilla en la que Lex se va a apoyar para generar el código C, y donde nosotros
deberemos describir toda la funcionalidad requerida, va a ser un fichero de texto plano
con una estructura bien definida, donde iremos describiendo las expresiones regulares y
las acciones asociadas a ella.

La estructura de la plantilla es la siguiente:



Se compone de tres secciones con estructuras distintas y claramente delimitadas por una
línea en la que lo único que aparece es la cadena “%%”.

Las secciones de ‘Declaraciones’ y la de ‘Procedimientos de Usuario’ son opcionales,
mientras que la de ‘Reglas’ es obligatoria (aunque se encuentre vacía), con lo que
tenemos que la plantilla más pequeña que podemos definir es:



Esta plantilla, introducida en Lex, generaría un programa C donde el contenido de la
entrada estándar sería copiado en la salida estándar por la aplicación de las reglas y
acciones por defecto.

Lex va a actuar como un pre-procesador que va a trasformar las definiciones de esta
plantilla en un fichero de código C.



Modelos de computación 1.
Prácticas



Pag. 6

La sección de Declaraciones


En la sección de Declaraciones podemos encontrar dos tipos de declaraciones bien
diferenciados:

• Un bloque donde le indicaremos al pre-procesador que lo que estamos definiendo
queremos que aparezca ‘tal cual’ en el fichero C generado. Es un bloque de copia
delimitado por las secuencias ‘%{‘ y ‘%}’ donde podemos indicar la inclusión de los
ficheros de cabecera necesarios, o la declaración de variables globales o constantes, o
declarar la cabecera de procedimientos descritos en la sección “Procedimientos de
Usuario”. Por ejemplo:

%{
/* Este bloque aparecerá tal cual en el fichero lex.yy.c */

#include <stdio.h>
#include <stdlib.h>
#define VALUE 3

int nl, np, nw;
void escribir_datos (int dato1, int dato2, int dato3);

%}



• Un bloque de definición de ‘alias’, donde ‘pondremos nombre’ a algunas de las
expresiones regulares utilizadas. En este bloque, aparecerá AL COMIENZO DE LA
LÍNEA el nombre con el que bautizaremos a esa expresión regular y SEPARADO
POR UN TABULADOR (al menos), indicaremos la definición de la expresión
regular. Por ejemplo:



letra

digito

entero
real


real2
numero



[a-zA-Z]
[0-9]
{digito}+
{entero}.{entero}
{real}[eE][\+\-]?{entero}
{entero}|{real}|{real2}



Estos bloques pueden aparecer en cualquier orden, y pueden aparecer varios de ellos a lo
largo de la sección de declaraciones. Recordemos que esta sección puede aparecer vacía.

Estos ‘alias’ deben de ir entre llaves para su posterior uso. Por ejemplo, {numero}



Modelos de computación 1.
Prácticas



Pag. 7



La sección de Reglas


En la sección de Reglas sólo permitiremos un único tipo de escritura. Las reglas se
definen como sigue:


Expresión_Regular Tabulador {acciones escritas en C}



AL COMIENZO DE LA LÍNEA se indica la expresión regular, seguida inm