PDF de programación - Introduccin a Flex y Bison

Introducción a Flex y Bison
Prácticas de Lenguajes, Gramáticas y Autómatas,
cuarto cuatrimestre (primavera) de Ingeniería en



Informática

http://webdiis.unizar.es/asignaturas/LGA



Profesor Responsable: Rubén Béjar Hernández

Dpto. Informática e Ingeniería de Sistemas

Universidad de Zaragoza



Introducción a Flex y Bison


Introducción a Flex __________________________________________________________________3
Patrones _________________________________________________________________________4
Emparejamiento de la entrada_______________________________________________________5
Acciones _________________________________________________________________________6
El analizador generado _____________________________________________________________7
Condiciones de arranque (sensibilidad al contexto) ______________________________________7
Algunas variables disponibles para el usuario __________________________________________8
Compilación y ejecución de un programa Flex__________________________________________8
Notas finales______________________________________________________________________9
Introducción a Bison ________________________________________________________________10
Símbolos, terminales y no terminales_________________________________________________10
Sintaxis de las reglas gramaticales (producciones)______________________________________11
Semántica del lenguaje ____________________________________________________________12
Acciones ______________________________________________________________________13
Tipos de Datos de Valores en Acciones ______________________________________________13
Acciones a Media Regla __________________________________________________________14
Declaraciones en Bison ____________________________________________________________14
Nombres de Token ______________________________________________________________15
Precedencia de Operadores ________________________________________________________15
La Colección de Tipos de Valores___________________________________________________16
Símbolos No Terminales __________________________________________________________16
El Símbolo Inicial _______________________________________________________________16
Precedencia de operadores _________________________________________________________16
Especificando Precedencia de Operadores ____________________________________________17
Precedencia Dependiente del Contexto _______________________________________________17
Funcionamiento del analizador _____________________________________________________18
La Función del Analizador yyparse________________________________________________18
La Funcion del Analizador Léxico yylex ____________________________________________18
Un ejemplo sencillo _______________________________________________________________18
Compilación y ejecución de un programa Bison________________________________________20
Notas finales_____________________________________________________________________21
Bibliografía________________________________________________________________________21


2

Introducción a Flex y Bison

Introducción a Flex
Flex es un una herramienta que permite generar analizadores léxicos. A partir de un
conjunto de expresiones regulares, Flex busca concordancias en un fichero de entrada y
ejecuta acciones asociadas a estas expresiones. Es compatible casi al 100% con Lex,
una herramienta clásica de Unix para la generación de analizadores léxicos, pero es un
desarrollo diferente realizado por GNU bajo licencia GPL.

Los ficheros de entrada de Flex (normalmente con la extensión .l) siguen el siguiente
esquema:
%%
patrón1 {acción1}
patrón2 {acción2}
...
donde:
patrón: expresión regular
acción: código C con las acciones a ejecutar cuando se encuentre concordancia del
patrón con el texto de entrada

{printf(“X”);};
;

Flex recorre la entrada hasta que encuentra una concordancia y ejecuta el código
asociado. El texto que no concuerda con ningún patrón lo copia tal cual a la salida. Por
ejemplo:
%%
a*b
re
El ejecutable correspondiente transforma el texto:
abre la puertaab
en
X la puertX
pues ha escrito X cada vez que ha encontrado ab o aab y nada cuando ha encontrado re.
Flex lee los ficheros de entrada dados, o la entrada estándar si no se le ha indicado
ningún nombre de fichero, con la descripción de un escáner a generar. La descripción se
encuentra en forma de parejas de expresiones regulares y código C, denominadas
reglas. Flex genera como salida un fichero fuente en C, ‘lex.yy.c’, que define una
función ‘yylex()’. Este fichero se compila y se enlaza con la librería de Flex para
producir un ejecutable. Cuando se arranca el fichero ejecutable, este analiza su entrada
en busca de casos de las expresiones regulares. Siempre que encuentra uno, ejecuta el
código C correspondiente.
El fichero de entrada de Flex está compuesto de tres secciones, separadas por una línea
donde aparece únicamente un ‘%%’ en esta:
definiciones
%%
reglas
%%
código de usuario

3

Introducción a Flex y Bison

La sección de definiciones contiene declaraciones de definiciones de nombres sencillas
para simplificar la especificación del escáner, y declaraciones de condiciones de
arranque, que se explicarán en una sección posterior. Las definiciones de nombre tienen
la forma:
nombre definición
El "nombre" es una palabra que comienza con una letra o un subrayado (‘_’) seguido
por cero o más letras, dígitos, ‘_’, o ‘-’ (guión). La definición se considera que
comienza en el primer carácter que no sea un espacio en blanco siguiendo al nombre y
continuando hasta el final de la línea. Posteriormente se puede hacer referencia a la
definición utilizando "{nombre}", que se expandirá a "(definición)". Por ejemplo,
DIGITO [0-9]
ID [a-z][a-z0-9]*
define "DIGITO" como una expresión regular que empareja un dígito sencillo, e "ID"
como una expresión regular que empareja una letra seguida por cero o más letras o
dígitos. Una referencia posterior a
{DIGITO}+"."{DIGITO}*
es idéntica a
([0-9])+"."([0-9])*
y empareja uno o más dígitos seguido por un ‘.’ seguido por cero o más dígitos.
La sección de reglas en la entrada de Flex contiene una serie de reglas de la forma:
patrón acción
donde el patrón debe estar sin sangrar y la acción debe comenzar en la misma línea.
Finalmente, la sección de código de usuario simplemente se copia a ‘lex.yy.c’
literalmente. Esta sección se utiliza para rutinas de complemento que llaman al escáner
o son llamadas por este. La presencia de esta sección es opcional; Si se omite, el
segundo ‘%%’ en el fichero de entrada se podría omitir también.

Patrones
Los patrones en la entrada se escriben utilizando un conjunto extendido de expresiones
regulares y usando como alfabeto cualquier carácter ASCII. Cualquier símbolo excepto
el espacio en blanco, tabulador, cambio de línea y los caracteres especiales se escriben
tal cual en las expresiones regulares (patrones) de Flex. Los caracteres especiales son:

“ \ [ ^ - ? . * + | ( ) $ / { } % < >

empareja el carácter ‘x’

Algunos de los patrones de Flex son:
x
.
[xyz]
[abj-oZ]

cualquier carácter excepto una línea nueva
un conjunto de caracteres; en este caso, el patrón empareja una ‘x’, una ‘y’, o una ‘z’
un conjunto de caracteres con un rango; empareja una ‘a’, una ‘b’, cualquier letra desde la
‘j’ hasta la ‘o’, o una ‘Z’

[^A-Z]

4

cualquier carácter menos los que aparecen en el conjunto. En este caso, cualquier carácter
EXCEPTO una letra mayúscula.

cualquier carácter EXCEPTO una letra mayúscula o una línea nueva

cero o más r’s, donde r es cualquier expresión regular

Introducción a Flex y Bison

una o más r’s

[^A-Z\n]
r*
r+
r?
r{2,5}
r{4}
{nombre}
"[xyz]\"foo"
\x

cero o una r (es decir, "una r opcional")

entre dos y cinco concatenaciones de r

exactamente 4 r’s

la expansión de la definición de "nombre" (ver más abajo)

la cadena literal: [xyz]"foo
si x es una ‘a’, ‘b’, ‘f’, ‘n’, ‘r’, ‘t’, o ‘v’, entonces la interpretación ANSI-C de \x
(por ejemplo \t sería un tabulador). En otro caso, un literal ‘x’ (usado para la concordancia
exacta de caracteres especiales (\\ \. \?)

empareja una R; los paréntesis se utilizan para anular la precedencia (ver más abajo)

la expresión regular r seguida por la expresión regular s; se denomina "concatenación"

bien una r o una s

una r pero sólo si va seguida por una s.

una r, pero sólo al comienzo de una línea


(r)

rs
r|s
r/s
^r
r$

una r, pero sólo al final de una línea (es decir, justo antes de una línea nueva). Equivalente a
"r/\n".

<s>r
<s1,s2,s3>r

una r, pero sólo en la condición de arranque s (ver más adelante).

lo mismo, pero en cualquiera de las condiciones de arranque s1, s2, o s3

Emparejamiento de la entrada
Cuando el escáner generado está funcionando, este analiza su entrada buscando cadenas
que concuerden con cualquiera de sus patrones. Si encuentra más de un
emparejamiento, toma el que empareje el texto más largo. Si encuentra dos o más
emparejamientos de la misma longitud, se escoge la regla listada en primer lugar en el
fichero de entrada de Flex.
Una vez que se determina el emparejamiento, el texto correspondiente al
emparejamiento (denominado el token) está disponible en el puntero de carácter global
yytext, y su longitud en la variable global entera yyleng. Entonces la acción
correspondiente al patrón emparejado se ejecuta y luego la entrada restante se analiza
para otro emparejamiento.
Si no se encuentra un emparejamiento, entonces se ejecuta la regla por defecto: el
siguiente carácter en la entrada se considera reconocido y se copia a la salida estándar.

5

Introducción a Flex y Bison

{printf(“1”);}
{printf(“2”);}
{printf(“3”);}
{printf(“4”);}

Un