PDF de programación - Análisis Léxico / Expresiones Regulares

ANÁLISIS LÉXICO

EXPRESIONES REGULARES





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

© Todos los derechos de propiedad intelectual de esta obra pertenecen en exclusiva a la Universidad
Europea de Madrid, S.L.U. Queda terminantemente prohibida la reproducción, puesta a disposición del
público y en general cualquier otra forma de explotación de toda o parte de la misma.

La utilización no autorizada de esta obra, así como los perjuicios ocasionados en los derechos de
propiedad intelectual e industrial de la Universidad Europea de Madrid, S.L.U., darán lugar al ejercicio
de las acciones que legalmente le correspondan y, en su caso, a las responsabilidades que de dicho
ejercicio se deriven.

2





Índice

Presentación

Expresiones regulares

Operaciones con expresiones regulares

Definiciones regulares, precedencia y asociatividad

Implementación de un analizador léxico con Flex

Secciones de un programa Flex I

Secciones de un programa Flex II

Sección de Reglas

Secciones de un programa Flex III

Ejemplo de analizador léxico

Resumen

ANÁLISIS LÉXICO

EXPRESIONES REGULARES

4

5

6

8

9

10

12

12

14

15

16

3
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





Presentación

ANÁLISIS LÉXICO

EXPRESIONES REGULARES

El objetivo de este tema es aprender qué son las expresiones regulares, así como a operar con

ellas. También aprenderemos a implementar un analizador léxico utilizando una herramienta
generadora de analizadores léxicos, denominada Flex, de acceso libre.

Para ello seguiremos el siguiente índice:

Expresiones regulares.

Operaciones con expresiones regulares.

Definiciones regulares, precedencia y asociatividad.

Implementación de un analizador léxico con Flex.

Secciones de un programa Flex.

Ejemplo de analizador léxico.

Errores más comunes con Flex.

Se probará a generar un analizador léxico básico con Flex, con la idea de ir ampliándolo de

acuerdo con la gramática que se decida para el compilador.

4
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





Expresiones regulares

ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Se corresponden con las gramáticas de tipo 3 de la jerarquía de Chomsky. Las expresiones
regulares son una forma de especificar patrones, entendiendo por patrón la forma de describir
cadenas de caracteres. Es la forma de definir los tokens o componentes léxicos y, como
veremos, cada patrón concuerda con una serie de cadenas.

De esta forma, utilizamos las expresiones regulares para darle nombre a estos patrones.

El lenguaje que se reconoce mediante estas expresiones regulares (r), se
denomina lenguaje generado por la expresión regular L(r) (Louden, 2004).

Recordando la siguiente tabla:

Token (Componente léxico)

Lexema

Patrón

Identificador
Número

a, valor, b
5, 3,25, 56

[a-zA-Z]+
[0-9]+(\.[0-9]+)?

Vemos que para describir un identificador que se define solo por letras utilizando el patrón [a-zA-

Z]+, que reconoce cualquier letra mayúscula o minúscula seguido del símbolo +, estamos

indicando que al menos tiene que haber una letra para describir un identificador, pero no hay

límite para el número de caracteres que puede tener ese token (identificador).

Una expresión regular se puede construir a partir de otras expresiones regulares más simples.

Cuando definamos los símbolos mediante los que se especifican las expresiones regulares

veremos ejemplos de estos, definiendo letras y dígitos y como un identificador es una

combinación de ambos.

Para definir las expresiones regulares usamos metacaracteres o metasímbolos que especifican
las acciones que se pueden reconocer sobre un determinado carácter o símbolo. Algunos de
estos metacaracteres son: *, +, ?, |.

Cuando queremos utilizar estos símbolos, como por ejemplo * con su significado normal, para la

operación de multiplicar se utiliza un carácter de escape que anula el significado especial del

metacarácter. En este ejemplo la forma correcta sería \*, y así tenemos el símbolo de multiplicar

en un patrón.

5
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





Operaciones con expresiones regulares

Hay tres operaciones básicas con expresiones regulares:

ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Selección entre
alternativas

Concatenación

Repetición

Se denota por el metacarácter |. Ejemplo: a|b, significa que
puede ser a ó b. Esta operación equivale a la unión, puesto
que tanto a como b valdrían como lexemas para este
patrón (obsérvese que utilizamos patrón y expresión
regular de forma indistinta).

Se construye poniendo un símbolo al lado del otro y no
utiliza ningún metacarácter. Ejemplo: ab, significa que el
lexema equivalente tiene que ser "ab", sin alternativa
posible.

También se la denomina cerradura de Kleene y se denota
por el matacarácter *. Identifica una concatenación de
símbolos incluyendo la cadena vacía, es decir "0 o mas
instancias" del símbolo afectado. Ejemplo: a*, significa que
los lexemas para este patrón podrían ser:
, a, aa, aaa,
aaaa,...

Además de estas operaciones básicas, aparecieron posteriormente extensiones a las mismas

para cubrir algunas lagunas a la hora de especificar patrones:

6
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

7
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Definiciones regulares, precedencia y asociatividad

Con el objeto de simplificar la notación, se pueden poner nombres a las expresiones regulares,
con el objeto de no tener que volver a escribir la expresión cada vez que tenemos que utilizarla.

Por tanto, una definición regular es, a modo de ejemplo:

Pudiendo reutilizarlas para definir otro concepto, como por ejemplo:

Identificador = letra (letra|digito)*, donde queremos decir que un identificador una cadena

que comienza por una letra a la que le pueden seguir 0 ó mas letras (minúsculas o

mayúsculas) o dígitos. Ejemplo de lexemas serían: a, a3, a3b123. Los paréntesis sirven

para indicar que todo lo que está incluido entre ellos se verá afectado por el metacarácter,

en este caso el *, que implica 0 o mas repeticiones.

Otro aspecto importante de las expresiones regulares es la precedencia y la
asociatividad. Está basada en la convención de que el orden de precedencia de
mayor a menor es: repetición (*, +, ?), concatenación y alternativa y todas son
asociativas por la izquierda.

También es importante tener en cuenta los paréntesis, si queremos tener una precedencia

diferente para determinados símbolos afectados por ellos. Como nos indica Louden (2004) en su

ejemplo, (a|b) c, la operación alternativa tiene mayor precedencia que la concatenación al estar

afectada por los paréntesis.

La norma es igual que en matemáticas, donde (5 - 2) * 4 = 3*4 = 12, la operación afectada por

los paréntesis se realiza antes (tiene mayor precedencia) que la multiplicación, aunque sea una

resta.

8
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Implementación de un analizador léxico con Flex

Se han desarrollado herramientas para construir analizadores léxicos a partir de
expresiones regulares. Un ejemplo de este tipo es LEX escrito por Mike Lex y Eric
Schmidt, que en su versión libre se denominó Flex (Fast Lex).

Aprenderemos a utilizar las expresiones regulares, combinándolas con acciones para reconocer

los símbolos de un lenguaje.

Posteriormente lo combinaremos con el analizador sintáctico para generar el embrión de un

compilador.

El proceso es el siguiente:

Primero

Segundo

Se escribe con un editor de texto (por ejemplo, Notepad)
una especificación del analizador léxico mediante un
programa denominado ejemplo.l, en lenguaje flex.

Después ejemplo.l, se ejecuta con el flex para producir el

programa en C, ejemplo.yy.c (flex ejemplo.l).

Este programa construye una representación en forma de

tabla de diagrama de transiciones que se construye a

partir de las expresiones regulares definidas en ejemplo.l.

Las acciones asociadas a las expresiones regulares de

ejemplo.l se convierten en código escrito en C y se

transfieren a ejemplo.yy.c.

Tercero

Compilamos ejemplo.yy.c con el compilador de C y
obtenemos el programa ejecutable ejemplo.exe.

9
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Secciones de un programa Flex I

Un programa en Flex tiene tres partes o secciones, separadas por una línea con %%.

La sección de declaraciones: son los #include, #define, declaración de variables
(que serán globales), etc. que se copian tal cual en la cabecera del fichero

"nombre_lex.lex.c". Son previas al uso del reconocimiento de símbolos.

Tiene cuatro partes:

10
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Partes del programa en Flex

Declaraciones

%%

Reglas

%%

Código de usuario

11
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS LÉXICO

EXPRESIONES REGULARES

Secciones de un programa Flex II
Sección de Reglas
Esta sección contiene reglas con el formato PATRÓN ACCIÓN, donde cada acción es un
fragmento de programa que describe cual ha de ser la acción que realizará el analizador léxico

cuando el patrón concuerde con un lexema del fichero que contiene el código fuente.

En

los patrones se pueden utilizar expresiones regulares, definiciones regulares y
condiciones de arranque. En el ejemplo que realizaremos en este tema el analizador léxico

trabajará solo, pero normalmen