LENGUAJE LEX

 

El lex es un generador de programas diseñado para el proceso léxico de

cadenas de caracteres de input. El programa acepta una especificación, orientada

a resolver un problema de alto nivel para comparar literales de caracteres, y

produce un programa C que reconoce expresiones regulares. Estas expresiones

las especifica el usuario en las especificaciones fuente que se le dan al lex. El

código lex reconoce estas expresiones en una cadena de input y divide este input

en cadenas de caracteres que coinciden con las expresiones. En los bordes entre

los literales, se ejecutan las secciones de programas proporcionados por el

usuario. El fichero fuente lex asocia las expresiones regulares y los fragmentos

de programas. Puesto que cada expresión aparece en el input del programa

escrito por el lex, se ejecuta el fragmento correspondiente.

El usuario proporciona el código adicional necesario para completar estas

funciones, incluyendo código escrito por otros generadores. El programa que

reconoce las expresiones se genera en forma de fragmentos de programa C del

usuario. El lex no es un lenguaje completo sino un generador que representa una

cualidad de un nuevo lenguaje que se añade al leguaje de programación C.

El lex convierte las expresiones y acciones del usuario (llamadas fuente) en un programa C llamado yylex. El programa yylex reconoce

expresiones en un flujo (llamado input) y lleva a cabo las

acciones especificadas para cada expresión a medida que se va detectando.

Considere un programa para borrar del input todos los espacios en blanco

y todos los tabuladores de los extremos de las líneas. Las líneas siguientes:

%%

[b\ t]+ $ ;

es todo lo que se requiere. El programa contiene un delimitado %% para marcar

el principio de las órdenes, y una orden. Esta orden contiene una expresión que

coincide con una o más apariciones de los caracteres espacio en blanco o

tabulador (escrito \ t para que se vea con mayor claridad, de acuerdo con la

convención del lenguaje C) justo antes del final de una línea. Los corchetes

indican la clase del carácter compuesto de espacios en blanco y tabuladores; el +

indica uno o más del item anterior; y el signo de dólar ($) indica el final de la

línea. No se especifica ninguna acción, por lo tanto el programa generado por el

lex ignorará estos caracteres. Todo lo demás se copiará . Para cambiar cualquier

cadena de caracteres en blanco o tabuladores que queden en un solo espacio en

blanco, añada otra orden:

%%

[b\ t]+$ ;

[b\ t] + printf (“ ”);

 

 

 

La automatización generada por este fuente explora ambas órdenes a la

vez, observa la terminación de la cadena de espacios o tabuladores haya o no un

carácter newline, y después ejecuta la acción de la orden deseada. La primera

orden coincide con todas las cadenas de caracteres de espacios en blanco o

tabuladores hasta el final de las líneas, y la segunda orden coincide con todos los

literales restantes de espacios o tabuladores.

El lex se puede usar sólo para transformaciones sencillas, o por análisis o

estadísticas buscando en un nivel léxico. El lex también se puede usar con un

generador reconocedor para llevar a cabo la fase de análisis léxico; es

especialmente fácil hacer que el lex y el yacc funcionen juntos. Los programas

lex reconocen sólo expresiones regulares; yacc escribe reconocedores que

aceptan una amplia clase de gramáticas de texto libre, pero que requieren un

analizador de nivel bajo para reconocer tokens de input. Por lo tanto, a menudo

es conveniente una combinación del lex y del yacc. Cuando se usa como un

preprocesador para un generador, el lex se usa para dividir el input, y el

generador de reconocimiento asigna una estructura a las piezas resultantes.         Los usuarios del yacc se darán cuenta de que el nombre yylex es el que el yacc da a su analizador léxico, de forma que el uso de este nombre por el lex simplifica el interface.

El lex genera un autómata finito partiendo de expresiones regulares del

fuente. El autómata es interpretado, en vez de compilado, para ahorrar espacio.

El resultado es todavía un analizador rápido. En particular, el tiempo que utiliza

un programa lex para reconocer y dividir una cadena de input es proporcional a

la longitud del input. El número de órdenes lex o la complejidad de las órdenes

no es importante para determinar la velocidad, a no ser que las órdenes que

incluyan contexto posterior requieran una cantidad importante de exploración.

Lo que aumenta con el número y complejidad de las órdenes es el tamaño del

autómata finito, y por lo tanto el tamaño del programa generado por el lex.

En el programa escrito por el lex, los fragmentos del usuario

(representando acciones que se van a llevar a cabo a medida que se encuentra

cada expresión) se colectan como casos de un intercambio. El intérprete del

autómata dirige el flujo de control. Se proporciona la oportunidad al usuario para

insertar declaraciones o sentencias adicionales en la rutina que contiene las

acciones, o para añadir subrutinas fuera de esta rutina de acción.

El lex no está limitado a fuente que se puede interpretar sobre la base de

un posible carácter. Por ejemplo, si hay dos órdenes una que busca ab y la otra

que busca abcdefg, y la cadena de caracteres del input es abcdefh, el lex

reconocerá ab y dejará el puntero del input justo delante de cd. Tal precaución es

más costosa que el proceso de lenguajes más sencillos.

 

 

 

 

Expresiones del lex

Una expresión especifica un conjunto de literales que se van a comparar.

Esta contiene caracteres de texto (que coinciden con los caracteres

correspondientes del literal que se está comparando) y caracteres operador (estos

especifican repeticiones, selecciones, y otras características). Las letras del

alfabeto y los dígitos son siempre caracteres de texto. Por lo tanto, la expresión

integer

Coincide con el literal “integer” siempre que éste aparezca y la expresión

a57d

busca el literal a57d.

Los caracteres operador son:

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

Si cualquiera de estos caracteres se va a usar literalmente, es necesario

incluirlos individualmente entre caracteres barra invertida ( \ ) o como un grupo

dentro de comillas ( “ ).

El operador comillas ( “ ) indica que siempre que esté incluido dentro de

un par de comillas se va a tomar como un carácter de texto. Por lo tanto

xyz“++”

coincide con el literal xyz++ cuando aparezca. Nótese que una parte del literal

puede estar entre comillas. No produce ningún efecto y es innecesario poner

entre comillas caracteres de texto normal; la expresión

“xyz++”

es la misma que la anterior. Por lo tanto poniendo entre comillas cada carácter

no alfanumérico que se está usando como carácter de texto, no es necesario

memorizar la lista anterior de caracteres operador.

Un carácter operador también se puede convertir en un carácter de texto

poniéndole delante una barra invertida ( \ ) como en

xyz\+\+

el cual, aunque menos legible, es otro equivalente de las expresiones anteriores.

Este mecanismo también se puede usar para incluir un espacio en blanco dentro

de una expresión; normalmente, según se explicaba anteriormente, los espacios

en blanco y los tabuladores terminan una orden. Cualquier carácter en blanco

que no esté contenido entre corchete tiene que ponerse entre comillas.

Se reconocen varios escapes C normales con la barra invertida ( \ ):

\ n newline

\ t tabulador

\ b backspace

\ \ barra invertida

Puesto que el carácter newline es ilegal en una expresión, es necesario

usar n; no se requiere dar escape al carácter tabulador y el backspace. Cada

carácter excepto el espacio en blanco, el tabulador y el newline y la lista anterior

es siempre un carácter de texto.

 

Especificación de clases de caracteres.

Las clases de caracteres se pueden especificar usando corchetes: [y]. La

construcción:

[ abc ]

coincide con cualquier carácter, que pueda se una a, b, o c. Dentro de los

corchetes, la mayoría de los significados de los operadores se ignoran. Sólo tres

caracteres son especiales: éstos son la barra invertida ( \ ), el guión ( - ), y el

signo de intercalación ( ^ ). El carácter guión indica rangos, por ejemplo

[ a-z0-9<>_ ]

indica la clase de carácter que contiene todos los caracteres en minúsculas, los

dígitos, los ángulos y el subrayado. Los rangos se pueden especificar en

cualquier orden. Usando el guión entre cualquier par de caracteres que ambos no

sean letras mayúsculas, letras minúsculas, o dígitos, depende de la

implementación y produce un mensaje de aviso. Si se desea incluir el guión en

una clase de caracteres, éste deberá ser el primero o el último; por lo tanto

[ -+0-9 ]

coincide con todos los dígitos y los signos más y menos.

En las clases de caracteres, el operador ( ^ ) debe aparecer como el

primer carácter después del corchete izquierdo; esto indica que el literal

resultante va a ser complementado con respecto al conjunto de caracteres del

ordenador. Por lo tanto

[ ^abc ]

coincide con todos los caracteres excepto a, b, o c, incluyendo todos los

caracteres especiales o de control; o

[ ^a-zA-Z ]

es cualquier carácter que no sea una letra. El carácter barra invertida ( \ )

proporciona un mecanismo de escape dentro de los corchete de clases de

caracteres, de forma que éstos se pueden introducir literalmente precediéndolos

con este carácter.

Especificar expresiones opcionales.

El operador signo de interrogación ( ? ) indica un elemento opcional de

una expresión. Por lo tanto

ab?c

coincide o con ac o con abc. Nótese que aquí el significado del signo de

interrogación difiere de su significado en la shell.

 

 

Especificación de expresiones repetidas.

Las repeticiones de clases se indican con los operadores asterisco ( * ) y

el signo más ( + ). Por ejemplo

a*

coincide con cualquier número de caracteres consecutivos, incluyendo cero;

mientras que a+ coincide con una o más apariciones de a.

Por ejemplo,

[ a-z ]+

coincide con todos los literales de letras minúsculas, y

[ A-Za-z ] [A-Za-z0-9 ]*

coincide con todos los literales alfanuméricos con un carácter alfabético al

principio; ésta es una expresión típica para reconocer identificadores en

lenguajes informáticos.

Especificación de alternación y de  agrupamiento.

El operador barra vertical ( | ) indica alternación. Por ejemplo

( ab|cd )

coincide con ab o con cd. Nótese que los paréntesis se usan para agrupar, aunque

éstos no son necesarios en el nivel exterior. Por ejemplo

ab | cd

hubiese sido suficiente en el ejemplo anterior. Los paréntesis se deberán usar

para expresiones más complejas, tales como

( ab | cd+ )?( ef )*

la cual coincide con tales literales como abefef, efefef, cdef, cddd, pero no abc,

abcd, o abcdef.

Especificación de sensitividad de contexto

El lex reconoce una pequeña cantidad del contexto que le rodea. Los dos

operadores más simples para éstos son el signo de intercalación ( ^ ) y el signo

de dólar ( $ ). Si el primer carácter de una expresión es un signo ^, entonces la

expresión sólo coincide al principio de la línea (después de un carácter newline,

o al principio del input). Esto nunca se puede confundir con el otro significado

del signo ^, complementación de las clases de caracteres, puesto que la

complementación sólo se aplica dentro de corchetes. Si el primer carácter es el

signo de dólar, la expresión sólo coincide al final de una línea (cuando va

seguido inmediatamente de un carácter newline). Este último operador es un

caso especial del operador barra ( / ) , el cual indica contexto al final.

La expresión

ab/cd

coincide con el literal ab, pero sólo si va seguido de cd. Por lo tanto

ab$

es lo mismo que

ab/\n

Especificación de repetición de expresiones.

Las llaves ( { y } ) especifican o bien repeticiones ( si éstas incluyen

números) o definición de expansión (si incluyen un nombre). Por ejemplo

{dígito}

busca un literal predefinido llamado dígito y lo inserta en la expresión, en ese

punto.

 

 

Especificar definiciones.

Las definiciones se dan en la primera parte del input del lex, antes de las

órdenes. En contraste,

a{1,5}

busca de una a cinco apariciones del carácter “a”.

Finalmente, un signo de tanto por ciento inicial ( % ) es especial puesto

que es el separador para los segmentos fuente del lex.

Especificación de acciones.

Cuando una expresión coincide con un modelo de texto en el input el lex

ejecuta la acción correspondiente. Esta sección describe algunas características

del lex, las cuales ayudan a escribir acciones. Nótese que hay una acción por

defecto, la cual consiste en copiar el input en el output. Esto se lleva a cabo en

todos los literales que de otro modo no coincidirían. Por lo tanto el usuario del

lex que desee absorber el input completo, sin producir ningún output, debe

proporcionar órdenes para hacer que coincida todo. Cuando se está usando el lex

con el yacc, ésta es la situación normal. Se puede tener en cuenta qué acciones

son las que se hacen en vez de copiar el input en el output; por lo tanto, en

general, una orden que simplemente copia se puede omitir.

Una de las cosas más simples que se pueden hacer es ignorar el input.

Especificar una sentencia nula de C; como una acción produce este resultado.

La orden frecuente es

[ \ t \ n] ;

la cual hace que se ignoren tres caracteres de espaciado (espacio en blanco,

tabulador, y newline).

Otra forma fácil de evitar el escribir acciones es usar el carácter de

repetición de acción, | , el cual indica que la acción de esta orden es la acción

para la orden siguiente. El ejemplo previo también se podía haber escrito:

“ ” |

“\ t” |

“\ n” ;

con el mismo resultado, aunque en un estilo diferente. Las comillas alrededor de

\ n y \ t no son necesarias.

En acciones más complejas, a menudo se quiere conocer el texto actual

que coincida con algunas expresiones como:

[ a-z ] +

El lex deja este texto en una matriz de caracteres externos llamada

yytext. Por lo tanto, para imprimir el nombre localizado, una orden como

[ a-z ] + printf (“%s” , yytext);

imprime el literal de yytext. La función C printf acepta un argumento de formato

y datos para imprimir; en este caso , el formato es print literal donde el signo de

tanto por ciento ( % ) indica conversión de datos, y la s indica el tipo de literal, y

los datos son los caracteres de yytext. Por lo tanto esto simplemente coloca el

literal que ha coincidido en el output. Esta acción es tan común que se puede

escribir como ECHO. Por ejemplo

[ a-z ] + ECHO;

es lo mismo que el ejemplo anterior. Puesto que la acción por defecto es

simplemente imprimir los caracteres que se han encontrado, uno se puede

preguntar ¿Porqué especificar una orden, como ésta, la cual simplemente

especifica la acción por defecto? Tales órdenes se requieren a menudo para

evitar la coincidencia con algunas otras órdenes que no se desean. Por ejemplo,

si hay una orden que coincide con “read”, ésta normalmente coincidirá con las

apariciones de “read” contenidas en “bread” o en “readjust”; para evitar esto,

una orden de la forma

[ a-z ] +

es necesaria. Esto se explica más ampliamente a continuación.

A veces es más conveniente conocer el final de lo que se ha encontrado;

aquí el lex también proporciona un total del número de caracteres que coinciden

en la variable yyleng. Para contar el número de palabras y el número de

caracteres en las palabras del input, será necesario escribir

[ a-zA-Z ] + {words++ ; chars += yyleng;}

lo cual acumula en las variables chars el número de caracteres que hay en las

palabras reconocidas. Al último carácter del literal que ha coincidido se puede

acceder por medio de

yytext[ yyleng - 1]

Ocasionalmente, una acción lex puede decidir que una orden no ha

reconocido el alcance correcto de los caracteres. Para ayudar a resolver esta

situación hay dos rutinas. La primera, yymore( ) se puede llamar para indicar

que la siguiente expresión de input reconocida se va a añadir al final de este

input. Normalmente, el siguiente literal de input escribirá encima de la entrada

actual en yytext. Segundo, yyless( n ) se puede llamar para indicar que no todos

los caracteres que coinciden con la expresión actual se quieren en ese momento.

El argumento n indica el número de caracteres de yytext que se van a retener.

Otros caracteres que han coincidido previamente se devuelven al input. Esto

proporciona el mismo tipo de anticipación ofrecido por el operador barra ( / ),

pero en una forma diferente.

Por ejemplo, considere un lenguaje que define un literal como un

conjunto de caracteres entre comillas ( ‘ ), y proporciona ése para incluir una

marca comilla en un literal, tiene que ir precedido de un signo barra invertida (\).

La expresión que coincide con esto es bastante confusa, de forma que puede ser

preferible escribir

 

 

 

 

 

 

\ ” [ ^” ]* {

if (yytext [yyleng - 1] == ‘\\’)

yymore();

else

.... proceso del usuario normal

}

lo cual, cuando se compara con un literal tal como

“abc\”def”

coincidirá primero con los cinco caracteres

“abc\

y después la llamada a yymore() hará que se añada al final la siguiente parte del

literal,

“def

Téngase en cuenta que el signo de comillas final que se encuentra al final

del literal, se cogerá en el código marcado como proceso normal.

La función yyless( ) se deberá usar para reprocesar texto en diversas

circunstancias. Considere el problema en la sintaxis C antigua de distinguir la

ambigüedad de -a. Suponga que es deseable tratar esto como -a e imprimir un

mensaje. Una orden podría ser

-[ a-zA-Z ] {

printf (“Operator (-) ambiguous\n”);

yyless (yyleng –1 );

... acción para - ...

}

lo cual imprime un mensaje, devuelve las letras después del operador al input, y

trata el operador como - .

Alternativamente podría ser deseable tratar esto como -a. Para hacer

esto, simplemente se devuelve el signo menos así como la letra al input. Lo

siguiente lleva a cavo la interpretación:

- [ a-zA-Z ] {

printf (“Operator (-) ambiguious\n”);

yyless (yyleng – 2);

... acción para ...

}

 

Téngase en cuenta que la expresión para los dos casos se podría escribir

más fácilmente con

- / [ A-Za-z]

en el primer caso, y

/ - [ A-Za-z ]

en el segundo: en la orden de acción no se requerirá ningún backup. No es

necesario reconocer el identificador completo para observar la ambigüedad. La

posibilidad de -3, de todos modos hace de

-[^\ t\ n]

una orden aún mejor.

Además de estas rutinas, el lex también permite acceso a las rutinas de I/O

que usa. Estas incluyen:

1. input ( ) el cual devuelve el siguiente carácter de input;

2. output ( ) el cual escribe el carácter c en el output; y

3. unput (c) el cual mete el carácter c de nuevo dentro del input que se va a leer

después por input ( ).

                Estas rutinas definen la relación entre los ficheros externos y los caracteres internos, y todas

 se deben retener o modificar consistentemente. Estas se pueden redefinir, para

hacer que el input o el output sea transmitido a lugares extraños, incluyendo

otros programas o memoria internas pero el conjunto de caracteres que se usa

debe ser consistente en todas las rutinas; un valor de cero devuelto por input

tiene que significar final de fichero, y la relación entre unput o input debe ser

retenido o no funcionará el “loockahead”. Lex no mira hacia delante si no es

necesario, pero cada orden que contiene una barra ( / ) o que termina en uno de

los siguientes caracteres implica esto:

+ * ? $

El “loockahead” es también necesario para que coincida una expresión

que es un prefijo de otra expresión. La librería estándar del lex impone un

límite de 100 caracteres.

Otra rutina de la librería del lex que a veces es necesaria redefinir es

yywrap ( ) la cual se llama siempre que lex llega a final de fichero. Si yywrap

devuelve un 1, lex continúa con un wrapup normal al final del input. A veces, es

conveniente hacer que llegue más input de una nueva fuente. En este caso, el

usuario deberá proporcionar un yywrap que obtenga nuevo input que devuelva 0.

Esto indica al lex que continúe el proceso; yywrap por defecto siempre

devuelve 1.

Esta rutina es también un lugar conveniente para imprimir tabla

resúmenes, etc. al final del programa. Nótese que si no es posible escribir una

orden normal que reconozca el final del fichero; el único acceso a esta condición

es a través de yywrap ( ).

Manejo de órdenes fuentes ambiguas

El lex puede manejar especificaciones ambiguas. Cuando más de una

expresión puede coincidir con el input en curso, el lex selecciona de la forma

siguiente:

Se prefiere la coincidencia más larga.

De entre las órdenes que coinciden en el mismo número de

caracteres, se prefiere la primera orden especificada.

Por ejemplo: suponga que se especifican las órdenes siguientes:

integer keyword action ... ;

[ a-z ] + identifier action ... ;

Si el input es integer, se toma como un identificador, puesto que

[ a-z ] +

coincide con ocho caracteres mientras que integer

sólo coincide con siete. Si el input es integer, ambas órdenes coinciden en siete

caracteres, y se selecciona la orden keyword porque ésta ha sido especificada

primero. Cualquier cosa más corta ( por ejemplo, int) no coincide con la

expresión integer, por lo tanto se usa la interpretación identifier.

El principio de la preferencia de la coincidencia más larga hace que

ciertas construcciones sean peligrosas, tales como la siguiente:

.*

 

Por ejemplo

‘ .* ’

parece ser una buena forma de reconocer un literal que se encuentra entre

comillas. Pero es una invitación a que el programa lea más allá, buscando un

solo signo de comilla distante. Presentado el input

‘ first ’ quoted string here, ‘ second ‘ here

la expresión anterior coincide con

‘ first’ quoted string here, ‘ second’

lo que probablemente no es lo que se quería. Una orden mejor es de la forma

‘[^’\ n’] *’

lo cual, en el input anterior, se para después de ‘first’. Las consecuencias de

errores como éste están mitigadas por el hecho de que el operador punto ( . ) no

coincide con un newline. Por lo tanto, tales expresiones nunca coinciden con

más de una línea. No intente evitar esto usando expresiones como

[ .\ n ] +

o sus equivalentes: el programa generado por el lex intentará leer el fichero de

input completo, haciendo que el buffer interno se desborde.

Téngase en cuenta que normalmente el lex divide el input, y no busca

todas las posibles coincidencias de cada expresión. Esto quiere decir que cada

carácter sólo se cuenta una vez, y sólo una. Por ejemplo, suponga quw se desea

contar las apariciones de “she” y “he” en un texto de input. Algunas órdenes lex

para hacer esto podrían ser

she s++;

he h++;

\ n |

. ;

donde las últimas dos órdenes ignoran todo lo que no sea he y she. Recuerde que

el punto ( . ) no incluye el carácter newline. Puesto que she incluye a he, el lex

normalmente no reconocerá las apariciones de he incluidas en she, puesto que

una vez que ha pasado un she estos caracteres se han ido para siempre.

A veces el usuario quiere cancelar esta selección. La acción REJECT quiere

decir, “ ve y ejecuta la siguiente alternativa”. Esto hace que se ejecute cualquiera

que fuese la segunda orden después de la orden en curso. La posición del

puntero de input se ajusta adecuadamente. Suponga que el usuario quiere

realmente contar las apariciones incluidas en “she”:

 

she { s++; REJECT;}

he { h++; REJECT;}

\ n |

. ;

 

En general, REJECT es muy útil cuando el propósito de lex no es dividir

el input, sino detectar todos los ejemplares de algunos items del input, y las

apariciones de estos items pueden solaparse o incluirse uno dentro de otro.

Suponga que se desea una tabla diagrama del input; normalmente los diagramas

se solapan, es decir, la palabra “the” se considera que contiene a th y a he.

Asumiendo una matriz bidimensional llamada digram que se va a incrementar, el

fuente apropiado es

%%

[ a-z ] [ a-z ] {digram[yytext[0]] [yytext[1]] ++;

REJECT; }

. ;

\ n ;

donde el REJECT es necesario para coger un par de letras que comienzan en

cada carácter, en vez de en un carácter si y otro no.

Recuerde que REJECT no vuelve a explorar el input. En vez de esto

recuerda los resultados de la exploración anterior. Esto quiere decir que si se

encuentra una orden con un contexto, y se ejecuta REJECT, no debería haber

usado unput para cambiar los caracteres que vienen del input. Esta es la única

restricción de la habilidad de manipular el input que aún no ha sido manipulado.

Especificación de sensibilidad de contexto izquierdo

A veces es deseable aplicar varios grupos de órdenes léxicas en

diferentes ocasiones en el input. Por ejemplo, un compilador preprocesador

puede distinguir sentencias del preprocesador y analizarlas de forma diferente a

como hace con las sentencias ordinarias. Esto requiere sensitividad al contexto

previo, y hay varias formas de tratar tales problemas. El operador ( ^ ), por

ejemplo, es un operador de contexto previo, que reconoce inmediatamente

contexto que precede por la izquierda del mismo modo que el signo de dólar       ($)reconoce el contexto que va inmediatamente a la derecha. El contexto

adyacente a la izquierda se podría extender, para producir un dispositivo similar

al del contexto adyacente a la derecha, pero no es muy probable que sea de

utilidad, puesto que a menudo el contexto de la derecha relevante apareció algún

tiempo antes tal como al principio de una línea.

Esta sección describe tres formas de tratar con entornos diferentes:

 

1. El uso de flags, cuando de un entorno a otro sólo cambian unas pocas

órdenes.

2. El uso de condiciones start con órdenes.

3. El uso de diversos analizadores léxicos funcionando juntos.

En cada caso, hay órdenes que reconocen la necesidad de cambiar el

entorno en el cual se analiza el texto de input siguiente, y ponen varios

parámetros para reflejar el cambio. Esto puede ser un flag probado

explícitamente por el código de acción del usuario; tal flag es una forma más

sencilla de tratar con el problema, puesto que el lex no está relacionado. Puede

que sea más conveniente, hacer que el lex recuerde los flags como condiciones

iniciales de las órdenes. Cualquier orden puede estar relacionada con una

condición start. Sólo será reconocida cuando el lex esté en esa misma condición.

La condición de start en curso se puede cambiar en cualquier momento.

Finalmente, si los conjuntos de órdenes de los diferentes entornos son muy

diferentes, se puede lograr una mayor claridad escribiendo varios analizadores

léxicos distintos, y cambiar de uno a otro según se desee.

Considere el siguiente problema: copie el input en el output, cambiando

la palabra “magic” a “primero” en cada línea que comience con la letra a,

cambiando “magic” por “segundo” en cada línea que comience con la letra b, y

cambiando “magic” por “tercero” en cada línea que comience con la letra c.

Todas las demás palabras y todas las otras líneas no varían.

Estas órdenes son tan sencillas que la forma más fácil de hacer el trabajo,

es con un flag:

int flag;

%%

^a {flag = ‘a’ ; ECHO;}

^b {flag = ‘b’ ; ECHO;}

^c {flag = ‘c’ ; ECHO;}

magic

switch (flag)

{

case ‘a’: printf ( “first” ); break;

case ‘b’: printf ( “second” ); break;

case ‘c’: printf ( “third” ); break;

default : ECHO; break ;

}

}

deberá ser adecuado.

Para tratar el mismo problema con las condiciones start, cada condición

start debe ser introducida en el lex en la sección de definiciones con una línea

que diga

%Start nombre1, nombre2

donde las condiciones se pueden especificar en cualquier orden. La palabra start

se puede abreviar a s o S. Las condiciones se pueden referenciar al principio de

una orden incluyéndolas entre ángulos. Por ejemplo

nombre1 expresión

es una orden que sólo se reconoce cuando el lex está en la condición start

nombre1. Para introducir una condición start

BEGIN nombre1;

la cual cambia la condición start por nombre1, Para volver al estado inicial

BEGIN 0;

Restaura la condición del intérprete del autómata del lex. Una orden

puede estar activa en varias condiciones start; por ejemplo:

< nombre1, nombre2, nombre3 >

es un prefijo legal. Cualquier orden que no comience con el operador prefijo <>

está siempre activa.

El mismo ejemplo anterior se puede escribir:

%START AA BB CC

%%

^a {ECHO; BEGIN AA;}

^b {ECHO; BEGIN BB;}

^c {ECHO; BEGIN CC;}

\n {ECHO; BEGIN 0;}

<AA> magic printf (“primero”);

<BB> magic printf (“segundo”);

<CC> magic printf (“ tercero ”);

donde la lógica es exactamente la misma que en el método anterior de tratar el

problema, pero el lex hace el trabajo en vea de hacerlo el código del usuario.

Especificación de definiciones fuente

Recuerde el formato de la fuente lex

{ definiciones }

%%

{ órdenes }

%%

{ rutinas del usuario }

Hasta ahora sólo se han descrito las órdenes. Se necesitarán opciones

adicionales, para definir variables para usarlas en el programa y para que las use

el lex. Estas pueden ir bien en la sección de definiciones o en la sección de

órdenes.

1. Cualquier línea que no aparezca como una orden o acción de lex, la cual

comienza con un espacio en blanco o un tabulador se copia en el programa

generado. Tal input de fuente antes del primer delimitador %% será externo

a cualquier función del código; si aparece inmediatamente después del

primer %%, aparece en un lugar apropiado para las declaraciones en la

función escrita por el lex el cual contiene las acciones. Este material tiene

que buscar fragmentos de programas, y deberá ir delante de la primera orden

de lex.

Como efecto secundario de lo anterior, las líneas que comienzan con un

espacio en blanco o un tabulador, y las cuales contienen un comentario, se

pasan al programa generado. Esto se puede usar para incluir comentarios

bien en la fuente lex o bien en el código generado. Los comentarios deberán

seguir las convenciones del lenguaje C.

2. Cualquier cosa que vaya incluida entre líneas que sólo contienen % { y % }

se copia como en el anterior. Los delimitadores se desechan. Este formato

permite introducir texto como sentencias de preprocesador que deben

comenzar en la columna 1, o copiar líneas que no parecen programas.

 

3. Cualquier cosa que haya después del tercer delimitador %% sin tener en

cuenta los formatos, se copia después del output del lex.

Las definiciones pensadas para el lex se especifican antes del primer

delimitador %%. Cualquier línea de esta sección que no esté incluida entre %{ y

% }, y que comience en la columna 1, se asume que define los literales de

sustitución del lex. El formato de tales líneas es nombre interpretación y hace que el literal especificado como una interpretación sea asociado con el

nombre. El nombre y la interpretación tienen que estar separados por al menos

un espacio en blanco o un tabulador, y el nombre tiene que comenzar con una

letra. La interpretación se puede llamar entonces por la sintaxis nombre de una

orden. Usando D para los dígitos, y E para un campo exponencial, por ejemplo,

se puede abreviar las órdenes para que reconozcan números:

D [ 0-9 ]

E [ DEde][ - + ]? {D}+

%%

{D}+ pritnf (“integer”);

{D}+”.”{D}*({E})? |

{D}*”.”{D}+({E})? |

{D}+{E} printf (“real”);

Téngase en cuenta que las dos primeras órdenes para los números reales;

requieren un punto decimal y contienen un campo exponencial opcional, pero la

primera requiere que al menos un dígito antes del punto decimal, y el segundo

requiere al menos un dígito después del punto decimal. Para tratar correctamente

el problema creado por una expresión FORTRAN tal como 25.EQ.I, la cual no

contiene un número real, una orden sensitiva de contexto tal como

[ 0-9 ]+/”.”EQ printf(“integer”);

se podría usar además de la orden normal para números enteros.

La sección de definiciones puede también contener otros comandos,

incluyendo una tabla de caracteres, una lista de condiciones start, o ajustes al

tamaño por defecto de las matrices dentro del propio lex para programas fuentes

más largos.

 

 Lex y Yacc

Si se quiere usar el lex con el yacc, téngase en cuenta que el lex escribe

un programa llamado yylex( ), el nombre requerido por el yacc para su

analizador. Normalmente el programa main por defecto de la librería lex llama a

esta rutina, pero si yacc está cargado, y se usa su programa main, yacc llamará al

yylex( ). En este caso, cada orden lex deberá terminar con

return (token); donde se devuelve el valor de token apropiado. Una forma fácil de obtener acceso a los nombres del yacc para los tokens es compilar el fichero de output del lex como parte del fichero de output del yacc poniendo la línea

#include “lex.yy.c” en la última sección del input del yacc. Suponiendo que la gramática se llame “good” y las órdenes léxicas se llamen “better” , la secuencia de comandos XENIX puede ser:

yacc good

lex better

cc y.tab.c –ly –ll

La librería yacc (-ly) se deberá cargar antes de la librería lex para obtener

un programa main que llame al reconocedor yacc. La generación de programas

lex y yacc se puede hacer en cualquier orden.

Como problema trivial, considere copiar un fichero input mientras se

añade 3 a cada número positivo divisible por 7. Podemos desarrollar un

programa fuente lex que hace precisamente eso:

%%

int k;

[ 0-9 ]+ {

k = atoi(yytext);

if (k%7 == 0)

printf(“%d”,k+3);

else

printf(“%d”, k);

}

La orden [ 0-9 ]+ reconoce cadenas de dígitos; atoi( ) convierte los

dígitos en binario y almacena el resultado en k. El operador (%) se usa para

comprobar si k es divisible por 7; si lo es, se incrementa en 3 a medida que se va

escribiendo. Se puede objetar que este programa alterará input tal como 49.63 o

X7. Además incrementa el valor absoluto de todos los números negativos

divisible por 7. Para evitar esto, añada simplemente unas pocas más de órdenes

después de la orden activa, como:

%%

int k;

-? [ 0 –9 ]+ {

k = atoi(yytest);

printf(“%d”,k%7 == 0? K+3 : k);

}

-? [ 0-9 ]+ ECHO;

[A-Za-z] [A-Za-z0-9 ]+ ECHO;

Las cadenas de caracteres numéricos que contienen un punto decimal o

precedidas de una letra serán cogidas por una de las dos órdenes, y no se

cambiarán. Si el if-else ha sido cambiado por una expresión condicional C para

ahorrar espacio; la forma a?b:c quiere decir: si a entonces b, en caso contrario c.

Como ejemplo de obtención de estadísticas, aquí hay un programa que

hace histogramas de longitudes de palabras, donde una palabra está definida

como una cadena de letras.

int lengs[100];

%%

[ a-z ] + lengs[yyleng]++;

. |

\n ;

%%

yywrap( )

{

int i;

printf(“Length No. words\n”);

for(i=0; i<100; i++)

if (lengs[i] > 0)

printf(“%5d%10d\n”,i,lengs[i]);

return (1);

}

Este programa acumula el histograma, pero no produce output. Al final

del input imprime una tabla. La sentencia final return (1); indica que el lex va a

llevar a cabo un wrapup. Si yywrap( ) devuelve un valor cero (false) implica que

hay disponible más input y el programa va a continuar leyendo y procesando. Un

yywrap( ) que nunca devuelve un valor verdadero produce un bucle infinito.

Como un ejemplo más grande, aquí hay algunas partes de un programa

escrito para convertir FORTRAN de doble precisión en FORTRAN de precisión

simple. Puesto que FORTRAN no distingue entre letras mayúsculas y letras

minúsculas, esta rutina comienza definiendo un conjunto de clases que incluyen

ambos tipos de letras de cada letra:

a [aA]

b [bB]

c [cC]

. .

. .

. .

z [zZ]

una clase adicional reconoce espacio en blanco:

W [ \ t ]*

La primera orden cambia precisión doble a real, o DOBLE PRECISION

A REAL

{d}{o}{u}{b}{l}{e}{W}{p}{r}{e}{c}{i}{s}{i}{o}{n}{

printf(yytext [0] == ’d’ ? ”real” : “REAL”

}

A lo largo de este programa se tienen cuidado de conservar el tipo de

letra del programa original. El operador condicional se usa para seleccionar la

forma apropiada de la palabra reservada. La siguiente orden copia indicaciones

de la tarjeta de continuación para evitar confundirlos con las constantes:

^” “[ ^ 0] ECHO;

En la expresión regular, las comillas rodean los espacios en blanco. Esto

se interpreta como el principio de línea, después cinco espacios en blancos,

después nada excepto un espacio en blanco o un cero. Nótese los dos

significados diferentes del signo de intercalación ( ^ ). A continuación van

algunas órdenes para cambiar constantes de doble precisión por constantes de

precisión flotante.

[ 0-9 ]+ {W}{d}{W}[+-]?{W}[ 0-9 ]+ |

[ 0-9 ]+ {W}”.”{W}{d}{W}[+-]?{W}[ 0-9 ]+ |

“.”{W}[ 0-9 ]+ {W}{d}{W}[+-]?{W}[ 0-9 ]+ {

/* convert constants*/

for (p=yytext; *p ¡= 0; p++)

{

if (*p == ‘d’ 11 *p == ‘D’)

*p += ’e’ - ‘d’;

ECHO;

}

Después de que se ha reconocido la constante de punto flotante, el bucle

for la explora para localizar la letra “d” o “D”. El programa añade “ ‘e’ – ‘d’ “ lo

cual lo convierte en la siguiente letra del alfabeto. La constante modificada,

ahora de precisión simple, se escribe de nuevo. A continuación va una serie de

nombres que tienen que volverse a escribir para suprimir su “ d” inicial. Usando

la matriz yytext la misma acción es suficiente para todos los nombres ( aquí sólo

se especifica un ejemplo de una lista relativamente larga).

{d}{s}{i}{n} |

{d}{c}{o}{s} |

{d}{s}{q}{r}{t} |

{d}{a}{t}{a}{n} |

...

{d}{f}{l}{o}{a}{t} {printf(“%s”, yytext + 1);}

Otra lista de nombres debe cambiar la ‘d’ inicial por una ‘a’ inicial

{d}{l}{o}{g} |

{d}{l}{o}{g}10 |

{d}{m}{i}{n}1 |

{d}{m}{a}{x}1 {

yytext[0] += ‘a’ – ‘d’;

ECHO;

}

Si se cambia esta interpretación proporcionando rutinas I/O que traducen

los caracteres, es necesario decírselo al lex, dando una tabla de traducción. Esta

tabla tiene que estar en la sección de definiciones, y tienen que estar incluidas

por líneas que contenga sólo %T. La tabla contiene líneas de la forma

{entero}{cadena de caracteres}

%T

1 Aa

2 Bb

...

26 Zz

27 |n

28 +

29 –

30 0

31 1

...

39 9

%T

Esta tabla convierte las letras minúsculas y mayúsculas en los enteros del

1 al 26, el carácter newline en el número 27, los signos más (+) y menos(+) en

los números 28 y 29, y los dígitos en los números 30 a 39. Nótese el escape para

el caracteres newline. Si se proporciona una tabla, cada carácter que va a

aparecer o bien en las órdenes o en cualquier input válido tiene que estar

incluido en la tabla. Ningún carácter puede ser asignado al número 0, y ningún

carácter puede ser asignado a un número más grande que el tamaño del conjunto

de caracteres del hardware.

 

Las expresiones regulares del lex usan los operadores siguientes:

x El carácter “ x “

“x” Una “x”, incluso si x es un operador.

\x Una “x”, incluso si x es un operador.

[xy] El carácter x o y.

[x-z] Los caracteres x, y o z.

[^ x] Cualquier carácter salvo x.

. Cualquier carácter salvo newline.

^ x Una x al principio de la línea.

<y>x Una x cuando el lex está en la condición start y.

x$ Una x al final de una línea.

x? Una x opcional.

x* 0,1,2 .... apariciones de x.

x+ 1,2,3 .... apariciones de x.

x|y Una x o una y.

x/y Una x, pero sólo si va seguida de una y.

{xx} La traducción de xx de la sección de definiciones.

x{m,n} m a través de n ocurrencias de x.

 

 

Algunas notas sobre lex

El programa lex (o flex) genera analizadores léxicos a partir de una especificación

del tipo de cadenas a tratar en termino de expresiones regulares (en

el estilo de Unix); lex toma como entrada un fichero (con la extensión .l) y

produce un fichero en C, lex.yy.c, que contiene el analizador léxico. El formato

del fichero de entrada se podra especificar con las siguientes reglas:

1. Al principio del fichero puede aparecer una parte de definiciones auxiliares.

a) Una definición ocupa una línea y esta formada por

un identificador,uno o mas espacios en blanco o tabuladores y

una expresión regular.

La sintaxis de las expresiones regulares es similar a la utilizada por

awk. Se puede hacer referencia mas adelante a una definición regular

poniendo el identificador encerrado entre llaves.

b) En la parte de definiciones auxiliares pueden aparecer fragmentos

de código (que debe ser C o C++; lex no lo comprueba) encerrados

entre%f y%g. En esos fragmentos de código se pueden poner

declaraciones de variables globales y funciones que se utilicen mas

adelante.

2. Después de la parte de definiciones auxiliares (que puede no contener nada)

debe aparecer el símbolo %% y una secuencia de cero o mas pares expresion regular - accion. Estas expresiones regulares deben representar

los diferentes tipos de cadenas del lenguaje que se quiere reconocer. Cada

acción es un fragmento en C que debe estar encerrado entre llaves 1.

3. Después de todas las expresiones y sus acciones puede aparecer mas código

en C. En este caso debe aparecer el símbolo %% antes del código (que no

debe estar encerrado entre %f  y %g.

Nota:

           lex elimina las llaves y construye una función con un switch que ejecuta cada

           acción. Si es necesario declarar variables locales a esa función se puede hacer poniendo un fragmento de código encerrado entre%f y%g después del símbolo %%, antes de cualquier par expresi´on regular - acci´on.

 

 

 Lex no comprueba que el codigo sea C, C++ o cualquier otro

lenguaje; simplemente inserta en el lugar que corresponde en el analizador

lexico que va a generar. Este analizador lexico se construye a partir de un

esqueleto que suele estar escrito en C.

Expresiones regulares:

               Una expresion regular es un tipo de notacion matematica para representar los lenguajes.

 

El fichero lex y yacc se puede compilar, pero el linker dará error porque

necesita dos funciones: main y yywrap. Para solucionar este problema

se puede indicar al linker que utilice la libreria del lex (con la opción -ll

al final) o bien se pueden definir las funciones en la parte de código al

final de la especificación de expresiones regulares; en este caso, la función

yywrap debe devolver el entero 1 (su argumento es void).

Por defecto, el analizador léxico generado por lex lee caracteres de la

entrada estándar stdin. Si se desea cambiar este comportamiento basta

con hacer que la variable yyin (que es de tipo FILE*) apunte a otro

fichero antes de llamar a yylex.

Para compilar el programa habrá que hacer:

flex ej1.l

cc -o ej1 lex y yacc

3

= ¤ ej1:l ¤ =

D [0-9]

L [a-zA-Z]

LD [0-9a-zA-Z]

%f #include<string.h>;

#include<stdio.h>;

#include<stdlib.h>;

int total=0;

%g

% %

%f /* codigo local */

%g

[ ntnn] f/* eliminar espacios en blanco, tabuladores y nn */ g

fLg(fLDg)* f/* devolver longitud de un identificador */

return(strlen(yytext));

g

fDg+ f /* incrementar total con el valor del entero detectado */

total+=atoi(yytext);

g % %

int yywrap(void) freturn 1;g int main(int argc, char *argv[]) f if(argc==2)f yyin=fopen(argv[1],''rt'');

if(yyin)

printf(`` %dnn'',yylex());

else

fprintf(stderr,"Error: no puedo abrir el

fichero %snn",argv[1]);

gelse

fprintf(stderr,''Uso: ej1 <nombre de fichero>nn'');

g

 

Algunos ejemplos simples

En primer lugar veremos algunos ejemplos simples para una toma de contacto con el uso de lex. La siguiente entrada de lex especifica un escáner que siempre que encuentre la cadena "username" la reemplazará por el nombre de entrada al sistema del usuario:

%%
username    printf( "%s", getlogin() );

Por defecto, cualquier texto que no reconozca el analizador léxico de lex se copia a la salida, así que el efecto neto de este escáner es copiar su fichero de entrada a la salida con cada aparición de "username" expandida. En esta entrada, hay solamente una regla. "username" es el patrón y el "printf" es la acción. El "%%" marca el comienzo de las reglas.

Aquí hay otro ejemplo simple:

int num_lineas = 0, num_caracteres = 0;
 
%%
\n      ++num_lineas; ++num_caracteres;
.       ++num_caracteres;
 
%%
main()
{
yylex();
printf( "# de líneas = %d, # de caracteres. = %d\n",
num_lineas, num_caracteres );
}

Este analizador cuenta el número de caracteres y el número de líneas en su entrada (no produce otra salida que el informe final de la cuenta). La primera línea declara dos variables globales, "num_lineas" y "num_caracteres", que son visibles al mismo tiempo dentro de `yylex()' y en la rutina `main()' declarada después del segundo "%%". Hay dos reglas, una que empareja una línea nueva ("\n") e incrementa la cuenta de líneas y la cuenta de caracteres, y la que empareja cualquier caracter que no sea una línea nueva (indicado por la expresión regular ".").

 

Un ejemplo algo más complicado:

/* escáner para un lenguaje de juguete al estilo de Pascal */
 
%{
/* se necesita esto para la llamada a atof() más abajo */
#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]*"}"     /* se come una linea de comentarios */
 
[ \t\n]+          /* se come los espacios en blanco */
 
.           printf( "Caracter no reconocido: %s\n", yytext );
 
%%
 
main( argc, argv )
int argc;
char **argv;
{
++argv, --argc;  /* se salta el nombre del programa */
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
 
yylex();
}

Esto podría ser los comienzos de un escáner simple para un lenguaje como Pascal. Este identifica diferentes tipos de tokens e informa a cerca de lo que ha visto.

 

Además de caracteres y rangos de caracteres, las clases de caracteres pueden también contener expresiones de clases de caracteres. Son expresiones encerradas entre los delimitadores `[:' y `:]' (que también deben aparecer entre el `[' y el `]' de la clase de caracteres; además pueden darse otros elementos dentro de la clase de caracteres). Las expresiones válidas son:

[:alnum:] [:alpha:] [:blank:]
[:cntrl:] [:digit:] [:graph:]
[:lower:] [:print:] [:punct:]
[:space:] [:upper:] [:xdigit:]

Todas estas expresiones designan un conjunto de caracteres equivalentes a la correspondiente función estándar `isXXX' de C. Por ejemplo, `[:alnum:]' designa aquellos caracteres para los cuales `isalnum()' devuelve verdadero --es decir, cualquier caracter alfabético o numérico. Algunos sistemas no ofrecen `isblank()', así que lex define `[:blank:]' como un espacio en blanco o un tabulador.

Por ejemplo, las siguientes clases de caracteres son todas equivalentes:

[[:alnum:]]
[[:alpha:][:digit:]]
[[:alpha:]0-9]
[a-zA-Z0-9]

Si su escáner ignora la distinción entre mayúsculas y minúsculas (la bandera `-i'), entonces `[:upper:]' y `[:lower:]' son equivalentes a `[:alpha:]'.

Algunas notas sobre los patrones:

·                     Una clase de caracteres negada tal como el ejemplo "[^A-Z]" anterior emparejará una línea nueva a menos que "\n" (o una secuencia de escape equivalente) sea uno de los caracteres presentes explícitamente en la clase de caracteres negada (p.ej., "[^A-Z\n]"). Esto es diferente a cómo muchas de las otras herramientas de expresiones regulares tratan las clases de caracteres negadas, pero desafortunadamente la inconsistencia está fervientemente enrraizada históricamente. Emparejar líneas nuevas significa que un patrón como [^"]* puede emparejar la entrada completa a menos que haya otra comilla en la entrada.

·                     Una regla puede tener lo más una instancia del contexto posterior (el operador `/' o el operador `$'). La condición de arranque, los patrones `^', y "<<EOF>>" pueden aparecer solamente al principio de un patrón, y, al igual que con `/' y `$', no pueden agruparse dentro de paréntesis. Un `^' que no aparezca al principio de una regla o un `$' que no aparezca al final de una regla pierde sus propiedades especiales y es tratado como un caracter normal. Lo siguiente no está permitido:

·                            foo/bar$
·                            <sc1>foo<sc2>bar

Fíjese que la primera regla se puede escribir como "foo/bar\n". En el siguiente ejemplo un `$' o un `^' es tratado como un caracter normal:

foo|(bar$)
foo|^bar

Si lo que se desea es un "foo" o un "bar" seguido de una línea nueva, puede usarse lo siguiente (la acción especial `|' ):

foo      |
bar$     /* la acción va aquí */

Un truco parecido funcionará para emparejar un "foo" o, un "bar" al principio de una línea.

Cómo se empareja 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 más texto (para reglas de contexto posterior, se incluye la longitud de la parte posterior, incluso si se devuelve a la entrada). 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 lex.

Una vez que se determina el emparejamiento, el texto correspondiente al emparejamiento (denominado el token) está disponible en el puntero a caracter global yytext, y su longitud en la variable global entera yyleng. Entonces la acción correspondiente al patrón emparejado se ejecuta, y entonces la entrada restante se analiza para otro emparejamiento.

Si no se encuentra un emparejamiento, entonces se ejecuta la regla por defecto: el siguiente caracter en la entrada se considera reconocido y se copia a la salida estándar. Así, la entrada válida más simple de lex es:

%%

que genera un escáner que simplemente copia su entrada (un caracter a la vez) a la salida.

Fíjese que yytext se puede definir de dos maneras diferentes: bien como un puntero a caracter o como un array de caracteres.

La ventaja de usar `%pointer' es un análisis substancialmente más rápido y la ausencia de desbordamiento del buffer cuando se emparejen tokens muy grandes (a menos que se agote la memoria dinámica). La desventaja es que se encuentra restringido en cómo sus acciones pueden modificar yytext , y las llamadas a la función `unput()' destruyen el contenido actual de yytext, que puede convertirse en un considerable quebradero de cabeza de portabilidad al cambiar entre diferentes versiones de lex.

La ventaja de `%array' es que entoces puede modificar yytext todo lo que usted quiera, las llamadas a `unput()' no destruyen yytext (ver más abajo). Además, los programas de lex existentes a veces acceden a yytext externamente utilizando declaraciones de la forma:

extern char yytext[];

 

El escáner generado

La salida de lex es el fichero `lex.yy.c', que contiene la rutina de análisis `yylex()', un número de tablas usadas por esta para emparejar tokens, y un número de rutinas auxiliares y macros. Por defecto, `yylex()' se declara así

int yylex()
{
... aquí van varias definiciones y las acciones ...
}

(Si su entorno acepta prototipos de funciones, entonces este será "int yylex( void)"). Esta definición podría modificarse definiendo la macro "YY_DECL". Por ejemplo, podría utilizar:

#define YY_DECL float lexscan( a, b ) float a, b;

para darle a la rutina de análisis el nombre lexscan, que devuelve un real, y toma dos reales como argumentos. Fíjese que si pone argumentos a la rutina de análisis usando una declaración de función no-prototipada/tipo-K&R, debe hacer terminar la definición con un punto y coma (`;').

Siempre que se llame a `yylex()', este analiza tokens desde el fichero de entrada global yyin (que por defecto es igual a stdin). La función continúa hasta que alcance el final del fichero (punto en el que devuelve el valor 0) o una de sus acciones ejecute una sentencia return.

Si el escáner alcanza un fin-de-fichero, entonces el comportamiento en las llamadas posteriores está indefinido a menos que o bien yyin apunte a un nuevo fichero de entrada (en cuyo caso el análisis continúa a partir de ese fichero), o se llame a `yyrestart()'. `yyrestart()' toma un argumento, un puntero `FILE *' (que puede ser nulo, si ha preparado a YY_INPUT para que analice una fuente distinta a yyin), e inicializa yyin para que escanee ese fichero. Esencialmente no hay diferencia entre la asignación a yyin de un nuevo fichero de entrada o el uso de `yyrestart()' para hacerlo; esto último está disponible por compatibilidad con versiones anteriores de lex, y porque puede utilizarse para conmutar ficheros de entrada en medio del análisis. También se puede utilizar para desechar el buffer de entrada actual, invocándola con un argumento igual a yyin; pero mejor es usar YY_FLUSH_BUFFER. Fíjese que `yyrestart()' no reinicializa la condición de arranque a INITIAL.

Si `yylex()' para el análisis debido a la ejecución de una sentencia return en una de las acciones, el analizador podría ser llamado de nuevo y este reanudaría el análisis donde lo dejó.

Cuando el analizador reciba una indicación de fin-de-fichero desde YY_INPUT, entonces esta comprueba la función `yywrap()'. Si `yywrap()' devuelve falso (cero), entonces se asume que la función ha ido más allá y ha preparado yyin para que apunte a otro fichero de entrada, y el análisis continúa. Si este retorna verdadero (no-cero), entonces el analizador termina, devolviendo un 0 a su invocador. Fíjese que en cualquier caso, la condición de arranque permanece sin cambios; esta no vuelve a ser INITIAL.

Si no proporciona su propia versión de `yywrap()', entonces debe bien o usar `%option noyywrap' (en cuyo caso el analizador se comporta como si `yywrap()' devolviera un 1), o debe enlazar con `-lfl' para obtener la versión por defecto de la rutina, que siempre devuelve un 1.

Hay disponibles tres rutinas para analizar desde buffers de memoria en lugar de desde ficheros: `yy_scan_string()', `yy_scan_bytes()', e `yy_scan_buffer()'. El analizador escribe su salida con `ECHO' a la variable global yyout (por defecto, stdout), que el usuario podría redefinir asignándole cualquier otro puntero a FILE.

 

Las condiciones de arranque se declaran en la (primera) sección de definiciones de la entrada usando líneas sin sangrar comenzando con `%s' ó `%x' seguida por una lista de nombres. Lo primero declara condiciones de arranque inclusivas, lo último condiciones de arranque exclusivas. Una condición de arranque se activa utilizando la acción BEGIN.

 Un conjunto de reglas dependientes de la misma condición de arranque exclusiva describe un analizador que es independiente de cualquiera de las otras reglas en la entrada de flex. Debido a esto, las condiciones de arranque exclusivas hacen fácil la especificación de "mini-escáneres" que analizan porciones de la entrada que son sintácticamente diferentes al resto (p.ej., comentarios).

Si la distinción entre condiciones de arranque inclusivas o exclusivas es aún un poco vaga, aquí hay un ejemplo simple que ilustra la conexión entre las dos. El conjunto de reglas:

%s ejemplo
%%
 
<ejemplo>foo   hacer_algo();
 
bar            algo_mas();

es equivalente a

%x ejemplo
%%
 
<ejemplo>foo   hacer_algo();
 
<INITIAL,ejemplo>bar    algo_mas();

Sin el calificador `<INITIAL,example>', el patrón `bar' en el segundo ejemplo no estará activo (es decir, no puede emparejarse) cuando se encuentre en la condición de arranque `example'. Si hemos usado `<example>' para calificar `bar', aunque, entonces este únicamente estará activo en `example' y no en INITIAL, mientras que en el primer ejemplo está activo en ambas, porque en el primer ejemplo la condición de arranque `example' es una condición de arranque inclusiva (`%s').

Fíjese también que el especificador especial de la condición de arranque `<*>' empareja todas las condiciones de arranque. Así, el ejemplo anterior también pudo haberse escrito;

%x ejemplo
%%
 
<ejemplo>foo   hacer_algo();
 
<*>bar    algo_mas();

La regla por defecto (hacer un `ECHO' con cualquier caracter sin emparejar) permanece activa en las condiciones de arranque. Esta es equivalente a:

<*>.|\n     ECHO;

`BEGIN(0)' retorna al estado original donde solo las reglas sin condiciones de arranque están activas. Este estado también puede referirse a la condición de arranque "INITIAL", así que `BEGIN(INITIAL)' es equivalente a `BEGIN(0)'. (No se requieren los paréntesis alrededor del nombre de la condición de arranque pero se considera de buen estilo.)

Las acciones BEGIN pueden darse también como código sangrado al comienzo de la sección de reglas. Por ejemplo, lo que viene a continuación hará que el analizador entre en la condición de arranque "ESPECIAL" siempre que se llame a `yylex()' y la variable global entra_en_especial sea verdadera:

int entra_en_especial;
 
%x ESPECIAL
%%
if ( entra_en_especial )
BEGIN(ESPECIAL);
 
<ESPECIAL>blablabla
...más reglas a continuación...
 
 
 
 
 

Aquí está un analizador que reconoce (y descarta) comentarios de C mientras mantiene una cuenta de la línea actual de entrada.

%x comentario
%%
int num_linea = 1;
 
"/*"         BEGIN(comentario);
 
<comentario>[^*\n]*       /* come todo lo que no sea '*' */
<comentario>"*"+[^*/\n]*  /* come '*'s no seguidos por '/' */
<comentario>\n            ++num_linea;
<comentario>"*"+"/"       BEGIN(INITIAL);

Este analizador se complica un poco para emparejar tanto texto como le sea posible en cada regla. En general, cuando se intenta escribir un analizador de alta velocidad haga que cada regla empareje lo más que pueda, ya que esto es un buen logro.

Fíjese que los nombres de las condiciones de arranque son realmente valores enteros y pueden ser almacenados como tales.

 

Finalmente, aquí hay un ejemplo de cómo emparejar cadenas entre comillas al estilo de C usando condiciones de arranque exclusivas, incluyendo secuencias de escape expandidas (pero sin incluir la comprobación de cadenas que son demasiado largas):

%x str
 
%%
char string_buf[MAX_STR_CONST];
char *string_buf_ptr;
 
\"      string_buf_ptr = string_buf; BEGIN(str);
 
<str>\"        { /* se vio la comilla que cierra - todo está hecho */
BEGIN(INITIAL);
*string_buf_ptr = '\0';
/* devuelve un tipo de token de cadena constante y
* el valor para el analizador sintáctico
*/
}
 
<str>\n        {
/* error - cadena constante sin finalizar */
/* genera un mensaje de error */
}
 
<str>\\[0-7]{1,3} {
/* secuencia de escape en octal */
int resultado;
 
(void) sscanf( yytext + 1, "%o", &resultado );
 
if ( resultado > 0xff )
/* error, constante fuera de rango */
 
*string_buf_ptr++ = resultado;
}
 
<str>\\[0-9]+ {
/* genera un error - secuencia de escape errónea;
* algo como '\48' o '\0777777'
*/
}
 
<str>\\n  *string_buf_ptr++ = '\n';
<str>\\t  *string_buf_ptr++ = '\t';
<str>\\r  *string_buf_ptr++ = '\r';
<str>\\b  *string_buf_ptr++ = '\b';
<str>\\f  *string_buf_ptr++ = '\f';
 
<str>\\(.|\n)  *string_buf_ptr++ = yytext[1];
 
<str>[^\\\n\"]+        {
char *yptr = yytext;
 
while ( *yptr )
*string_buf_ptr++ = *yptr++;
 
}

A menudo, como en alguno de los ejemplos anteriores, uno acaba escribiendo un buen número de reglas todas precedidas por la(s) misma(s) condición(es) de arranque. Lex hace esto un poco más fácil y claro introduciendo la noción de ámbito de la condición de arranque. Un ámbito de condición de arranque comienza con:

<SCs>{

Donde `SCs' es una lista de una o más condiciones de arranque. Dentro del ámbito de la condición de arranque, cada regla automáticamente tiene el prefijo `<SCs>' aplicado a esta, hasta un `}' que corresponda con el `{' inicial. Así, por ejemplo,

<ESC>{
"\\n"   return '\n';
"\\r"   return '\r';
"\\f"   return '\f';
"\\0"   return '\0';
}

es equivalente a:

<ESC>"\\n"  return '\n';
<ESC>"\\r"  return '\r';
<ESC>"\\f"  return '\f';
<ESC>"\\0"  return '\0';

Los ámbitos de las condiciones de arranque pueden anidarse.

La pila de las condiciones de arranque crece dinámicamente y por ello no tiene asociada ninguna limitación de tamaño. Si la memoria se agota, se aborta la ejecución del programa.

Para usar pilas de condiciones de arranque, su analizador debe incluir una directiva `%option stack'

 

Reglas de fin-de-fichero

La regla especial "<<EOF>>" indica las acciones que deben tomarse cuando se encuentre un fin-de-fichero e yywrap() retorne un valor distinto de cero (es decir, indica que no quedan ficheros por procesar). La acción debe finalizar haciendo una de estas cuatro cosas:

·                     asignando a yyin un nuevo fichero de entrada (en versiones anteriores de flex, después de hacer la asignación debía llamar a la acción especial YY_NEW_FILE; esto ya no es necesario);

·                     ejecutando una sentencia return;

·                     ejecutando la acción especial `yyterminate()';

·                     o, conmutando a un nuevo buffer usando `yy_switch_to_buffer()'

 

Estas reglas son útiles para atrapar cosas tales como comentarios sin final. Un ejemplo:

%x comilla
%%
 
...otras reglas que tengan que ver con comillas...
 
<comilla><<EOF>>   {
error( "comilla sin cerrar" );
yyterminate();
}
<<EOF>>  {
if ( *++filelist )
yyin = fopen( *filelist, "r" );
else
yyterminate();
}

 

Valores disponibles al usuario

Esta sección resume los diferentes valores disponibles al usuario en las acciones de la regla.

·                     `char *yytext' apunta al texto del token actual. Este puede modificarse pero no alargarse (no puede añadir caracteres al final). Si aparece la directiva especial `%array' en la primera sección de la descripción del analizador, entonces yytext se declara en su lugar como `char yytext[YYLMAX]', donde YYLMAX es la definicion de una macro que puede redefinir en la primera sección si no le gusta el valor por defecto (generalmente 8KB). El uso de `%array' produce analizadores algo más lentos, pero el valor de yytext se vuelve inmune a las llamadas a `input()' y `unput()', que potencialmente destruyen su valor cuando yytext es un puntero a caracter. El opuesto de `%array' es `%pointer', que se encuentra por defecto. Usted no puede utilizar `%array' cuando genera analizadores como clases de C++ (la bandera `-+').

·                     `int yyleng' contiene la longitud del token actual.

·                     `FILE *yyin' es el fichero por el que flex lee por defecto. Este podría redefinirse pero hacerlo solo tiene sentido antes de que el análisis comience o después de que se haya encontrado un EOF. Cambiándolo en medio del análisis tendrá resultados inesperados ya que flex utiliza buffers en su entrada; use `yyrestart()' en su lugar. Una vez que el análisis termina debido a que se ha visto un fin-de-fichero, puede asignarle a yyin el nuevo fichero de entrada y entonces llamar al analizador de nuevo para continuar analizando.

·                     `void yyrestart( FILE *new_file )' podría ser llamada para que yyin apunte al nuevo fichero de entrada. El cambio al nuevo fichero es inmediato (cualquier entrada contenida en el buffer previamente se pierde). Fíjese que llamando a `yyrestart()' con yyin como argumento de esta manera elimina el buffer de entradda actual y continúa analizando el mismo fichero de entrada.

·                     `FILE *yyout' es el fichero sobre el que se hacen las acciones `ECHO'. Este puede ser reasignado por el usuario.

·                     YY_CURRENT_BUFFER devuelve un handle YY_BUFFER_STATE al buffer actual.

·                     YY_START devuelve un valor entero correspondiente a la condición de arranque actual. Posteriormente puede usar este valor con BEGIN para retornar a la condición de arranque.

Interfaz con YACC

Uno de los usos principales de lex es como compañero del generador de analizadores sintácticos yacc. Los analizadores de yacc esperan invocar a una rutina llamada `yylex()' para encontrar el próximo token de entrada. La rutina se supone que devuelve el tipo del próximo token además de poner cualquier valor asociado en la variable global yylval. Para usar lex con yacc, uno especifica la opción `-d' de yacc para instruirle a que genere el fichero `y.tab.h' que contiene las definiciones de todos los `%tokens' que aparecen en la entrada de yacc. Entonces este archivo se incluye en el analizador de lex. Por ejemplo, si uno de los tokens es "TOK_NUMERO", parte del analizador podría parecerse a:

%{
#include "y.tab.h"
%}
 
%%
 
[0-9]+        yylval = atoi( yytext ); return TOK_NUMERO;

Invocando a Flex

Sinopsis

flex [-bcdfhilnpstvwBFILTV78+? -C[aefFmr] -osalida -Pprefijo -Sesqueleto]
[--help --version] [nombrefichero ...]

 

 

Incompatibilidades con lex y POSIX

lex es una reescritura de la herramienta lex del Unix de AT&T (aunque las dos implementaciones no comparten ningún código), con algunas extensiones e incompatibilidades, de las que ambas conciernen a aquellos que desean escribir analizadores aceptables por cualquier implementación. Lex sigue completamente la especificación POSIX de lex, excepto que cuando se utiliza `%pointer' (por defecto), una llamada a `unput()' destruye el contenido de yytext, que va en contra de la especificación POSIX.

La opción `-l' de lex activa la máxima compatibilidad con la implementación original de lex de AT&T, con el coste de una mayor pérdida de rendimiento en el analizador generado. Indicamos más abajo qué incompatibilidades pueden superarse usando la opción `-l'.

  Lex es totalmente compatible con las siguientes excepciones:

 

·                     La variable interna del analizador de lex sin documentar yylineno no se ofrece a menos que se use `-l' ó `%option yylineno'. yylineno debería gestionarse por buffer, en lugar de por analizador (simple variable global). yylineno no es parte de la especificación POSIX.

·                     La rutina `input()' no es redefinible, aunque podría invocarse para leer los caracteres que siguen a continuación de lo que haya sido reconocido por una regla. Si `input()' se encuentra con un fin-de-fichero se realiza el procesamiento de `yywrap()' normal. `input()' retorna un fin-de-fichero "real" como EOF. La entrada en su lugar se controla definiendo la macro YY_INPUT. La restricción de flex de que `input()' no puede redefinirse va de acuerdo a la especificación POSIX, que simplemente no especifica ninguna manera de controlar la entrada del analizador que no sea haciendo una asignación inicial a yyin.

·                     La rutina `unput()' no es redefinible. Esta restricción va de acuerdo a POSIX.

·                     Los analizadores de flex no son tan reentrantes como los analizadores de lex. En particular, si tiene un analizador interactivo y un gestor de interrupción con long-jumps fuera del analizador, y el analizador a continuación se invoca de nuevo, podría obtener el siguiente mensaje:

·                            fatal flex scanner internal error--end of buffer missed

Para volver al analizador, primero utilice

yyrestart( yyin );

Vea que esta llamada eliminará cualquier entrada en el buffer; normalmente esto no es un problema con un analizador interactivo. Dese cuenta también de que las clases analizadoras en C++ son reentrantes, así que si usar C++ es una opción para usted, debería utilizarla.

·                     `output()' no se provee. La salida desde la macro `ECHO' se hace al puntero de fichero yyout (por defecto a stdout). `output()' no es parte de la especificación POSIX.

·                     lex no acepta condiciones de arranque exclusivas (%x), aunque están en la especificación POSIX.

·                     Cuando se expanden las definiciones, flex las encierra entre paréntesis. Con lex, lo siguiente:

·                            NOMBRE    [A-Z][A-Z0-9]*
·                            %%
·                            foo{NOMBRE}?      printf( "Lo encontró\n" );
·                            %%

no reconocerá la cadena "foo" porque cuando la macro se expanda la regla es equivalente a "foo[A-Z][A-Z0-9]*?" y la precedencia es tal que el `?' se asocia con "[A-Z0-9]*". Con flex, la regla se expandirá a "foo([A-Z][A-Z0-9]*)?" y así la cadena "foo" se reconocerá. Fíjese que si la definición comienza con `^' o finaliza con `$' entonces no se expande con paréntesis, para permitir que estos operadores aparezcan en las definiciones sin perder su significado especial. Pero los operadores `<s>, /', y `<<EOF>>' no pueden utilizarse en una definición de flex. El uso de `-l' produce en el comportamiendo de lex el no poner paréntesis alrededor de la definición. La especificación de POSIX dice que la definición debe ser encerrada entre paréntesis.

·                     Algunas implementaciones de lex permiten que la acción de una regla comience en una línea separada, si el patrón de la regla tiene espacios en blanco al final:

·                            %%
·                            foo|bar<espacio aquí>
·                            { foobar_action(); }

flex no dispone de esta propiedad.

·                     La opción `%r' de lex (generar un analizador Ratfor) no se ofrece. No es parte de la especificación de POSIX.

·                     Después de una llamada a `unput()', el contenido de yytext está indefinido hasta que se reconozca el próximo token, a menos que el analizador se haya construido usando `%array'. Este no es el caso de lex o la especificación de POSIX. La opción `-l' elimina esta incompatibilidad.

·                     La precedencia del operador `{}' (rango numérico) es diferente. lex interpreta "abc{1,3}" como "empareja uno, dos, o tres apariciones de 'abc'", mientras que flex lo interpreta como "empareja 'ab' seguida de una, dos o tres apariciones de 'c'". Lo último va de acuerdo con la especificación de POSIX.

·                     La precedencia del operador `^' es diferente. lex interpreta "^foo|bar" como "empareja bien 'foo' al principio de una línea, o 'bar' en cualquier lugar", mientras que flex lo interpreta como "empareja 'foo' o 'bar' si vienen al principio de una línea". Lo último va de acuerdo con la especificación de POSIX.

·                     Las declaraciones especiales del tamaño de las tablas tal como `%a' que reconoce lex no se requieren en los analizadores de flex; flex los ignora.

·                     El identificador FLEX_SCANNER se #define de manera que los analizadores podrían escribirse para ser procesados con flex o con lex. Los analizadores también incluyen YY_FLEX_MAJOR_VERSION y YY_FLEX_MINOR_VERSION indicando qué versión de flex generó el analizador (por ejemplo, para la versión 2.5, estas definiciones serán 2 y 5 respectivamente).

Las siguientes propiedades de flex no se incluyen en lex o la especificación POSIX:

analizadores en C++
%option
ámbitos de condiciones de arranque
pilas de condiciones de arranque
analizadores interactivos/no-interactivos
yy_scan_string() y sus amigas
yyterminate()
yy_set_interactive()
yy_set_bol()
YY_AT_BOL()
<<EOF>>
<*>
YY_DECL
YY_START
YY_USER_ACTION
YY_USER_INIT
directivas #line
%{}'s alrededor de acciones
varias acciones en una línea

más casi todas las banderas de flex. La última propiedad en la lista se refiere al hecho de que con flex puede poner varias acciones en la misma línea, sepradas con punto y coma, mientras que con lex, lo siguiente

foo    handle_foo(); ++num_foos_seen;

se trunca (sorprendentemente) a

foo    handle_foo();

flex no trunca la acción. Las acciones que no se encierran en llaves simplemente se terminan al final de la línea.

Diagnósticos

`aviso, la regla no se puede aplicar'

indica que la regla dada no puede emparejarse porque sigue a otras reglas que siempre emparejarán el mismo texto que el de esta. Por ejemplo, en el siguiente ejemplo "foo" no puede emparejarse porque viene después de una regla "atrápalo-todo" para identificadores:

[a-z]+    obtuvo_identificador();
foo       obtuvo_foo();

El uso de REJECT en un analizador suprime este aviso.

`aviso, se ha especificado la opción -s pero se puede aplicar la regla por defecto'

significa que es posible (tal vez únicamente en una condición de arranque en particular) que la regla por defecto (emparejar cualquier caracter simple) sea la única que emparejará una entrada particular. Ya que se indicó `-s', presumiblemente esto no es lo que se pretendía.

`definición no definida reject_used_but_not_detected'

`definición no definida yymore_used_but_not_detected'

Estos errores pueden suceder en tiempo de compilación. Indican que el analizador usa REJECT o `yymore()' pero que flex falló en darse cuenta del hecho, queriendo decir que flex analizó las dos primeras secciones buscando apariciones de estas acciones y falló en encontrar alguna, pero que de algún modo se le han colado (por medio de un archivo #include, por ejemplo). Use `%option reject' ó `%option yymore' para indicar a flex que realmente usa esta funcionalidad.

`flex scanner jammed'

un analizador compilado con `-s' ha encontrado una cadena de entrada que no fue reconocida por niguna de sus reglas. Este error puede suceder también debido a problemas internos.

`token too large, exceeds YYLMAX'

su analizador usa `%array' y una de sus reglas reconoció una cadena más grande que la constante YYLMAX (8K bytes por defecto). Usted puede incrementar el valor haciendo un #define YYLMAX en la sección de definiciones de su entrada de flex.

`el analizador requiere la opción -8 para poder usar el carácter 'x''

La especificación de su analizador incluye el reconocimiento del caracter de 8-bits x y no ha especificado la bandera -8, y su analizador por defecto está a 7-bits porque ha usado las opciones `-Cf' ó `-CF' de compresión de tablas. El comentario de la bandera `-7' para los detalles.

`flex scanner push-back overflow'

usted utilizó `unput()' para devolver tanto texto que el buffer del analizador no pudo mantener el texto devuelto y el token actual en yytext. Idealmente el analizador debería ajustar dinámicamente el buffer en este caso, pero actualmente no lo hace.

`input buffer overflow, can't enlarge buffer because scanner uses REJECT'

el analizador estaba intentando reconocer un token extremadamente largo y necesitó expandir el buffer de entrada. Esto no funciona con analizadores que usan REJECT.

`fatal flex scanner internal error--end of buffer missed'

Esto puede suceder en un analizador que se reintroduce después de que un long-jump haya saltado fuera (o sobre) el registro de activación del analizador. Antes de reintroducir el analizador, use:

yyrestart( yyin );

o, cambie y use el analizador como clase de C++.

`too many start conditions in <> construct!'

ha listado más condiciones de arranque en una construcción <> que las que existen (así que tuvo que haber listado al menos una de ellas dos veces).

 

 

 

Ficheros

`-lfl'

librería con la que los analizadores deben enlazarse.

`lex.yy.c'

analizador generado (llamado `lexyy.c' en algunos sistemas).

`lex.yy.cc'

clase generada en C++ con el analizador, cuando se utiliza `-+'.

`<FlexLexer.h>'

fichero de cabecera definiendo la clase base del analizador en C++, FlexLexer, y su clase derivada, yyFlexLexer.

`flex.skl'

esqueleto del analizador. Este fichero se utiliza únicamente cuando se construye flex, no cuando flex se ejecuta.

`lex.backup'

información de los retrocesos para la bandera `-b' (llamada `lex.bck' en algunos sistemas).

Deficiencias / Errores

Algunos patrones de contexto posterior no pueden reconocerse correctamente y generan mensajes de aviso ("contexto posterior peligroso"). Estos son patrones donde el final de la primera parte de la regla reconoce el comienzo de la segunda parte, tal como "zx*/xy*", donde el 'x*' reconoce la `x' al comienzo del contexto posterior. (Fíjese que el borrador de POSIX establece que el texto reconocido por tales patrones no está definido.)

Para algunas reglas de contexto posterior, partes que son de hecho de longitud fija no se reconocen como tales, resultando en la pérdida de rendimiento mencionada anteriormente. En particular, las partes que usan `|' o {n} (tales como "foo{3}") siempre se consideran de longitud variable.

La combinación de contexto posterior con la acción especial `|' puede producir que el contexto posterior fijo se convierta en contexto posterior variable que es más caro. Por ejemplo, en lo que viene a continuación:

%%
abc      |
xyz/def

El uso de `unput()' invalida yytext e yyleng, a menos que se use la directiva `%array' o la opción `-l'.

La concordancia de patrones de NUL's es substancialmente más lento que el reconocimiento de otros caracteres.

El ajuste dinámico del buffer de entrada es lento, ya que conlleva el reanálisis de todo el texto reconocido hasta entonces por el (generalmente enorme) token actual.

Debido al uso simultáneo de buffers de entrada y lecturas por adelantado, no puede entremezclar llamadas a rutinas de <stdio.h>, tales como, por ejemplo, `getchar()', con reglas de flex y esperar que funcione. Llame a `input()' en su lugar.

La totalidad de las entradas de la tabla listada por la bandera `-v' excluye el número de entradas en la tabla necesarias para determinar qué regla ha sido emparejada. El número de entradas es igual al número de estados del DFA si el analizador no usa REJECT, y algo mayor que el número de estados si se usa.

REJECT no puede usarse con las opciones `-f' ó `-F'.

El algoritmo interno de flex necesita documentación

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

LENGUAJE YACC

 

Es un generador de analisis de propósito general que convierte una descripción de gramatica para una gramática de libre-contexto LALR en un programa en lenguaje C para analizar esa gramática.
Yacc lee la especificación de la gramática del archivo "filename" y genera un LR(1) analizador para el. Los analizadores consisten en un set de LALR(1) tablas de analisis y una rutina controladora escrita en el lenguale de programación C. Yacc normalmente escribe las tablas de analisis y la rutina controladora al archivo y.tab.c.
El programa Yacc ha ido siendo reemplazado por Bison.

 

 

1. Acciones en Yacc

Las acciones en Yacc son, como ya hemos visto, código c encerrado entre llaves asociado a cada regla. Cada acción se ejecuta cuando se aplica durante el análisis la regla a la que esta asociada. Las acciones pueden devolver valores y usar los obtenidos en acciones anteriores, en particular los devueltos por Lex como valores léxicos de los componentes reconocidos.

Ejemplo1:

           El siguiente ejemplo implanta una gramática de paréntesis anidados y muestra el mensaje “Correcto” cuando se consigue aplicar la primera regla, es decir, cuando se consigue el árbol de derivación completo.

%{

#include <stdio.h>

yyerror (char *s) {

fprintf (stderr, “%s\n”, s) ;

}

%}

%%

I : S ‘\n’ {printf (“Correcto\n”);}

;

S : ‘(‘ S ‘)’ S

|

;

%%

yylex() { /* código de yylex proporcionado directamente */

return (getchar()) ; /* devuelve el propio código (ASCII) del

carácter */

}

main() {

yyparse();

}

Ejemplo2:

           El ejemplo siguiente muestra las reglas empleadas en la derivación. Como el análisis realizado por un analizador construido can Yacc es ascendente las reglas aparecen en orden inverso al empleado. Probando con las entradas () () y (()) podrá detectarse que la derivación reflejada es más a la derecha.

%{

#include <stdio.h>

yyerror (char *s) {

fprintf (stderr, “%s\n”, s) ;

}

%}

2

%%

I : S ‘\n’ {printf (“Correcto\n”);}

;

S : ‘(‘ S ‘)’ S {printf (“S -> (S)S\n”);}

| {printf (“S -> epsilon\n”);}

;

%%

yylex() { /* código de yylex proporcionado directamente */

return (getchar()) ; /* devuelve el propio código (ASCII) del

carácter */

}

main() {

yyparse();

}

 

 

 Reglas Semánticas

Se pueden devolver valores en la parte izquierda de una regla utilizando unas variables especiales de Yacc a la vez que se aplica una regla de derivación. Esto permite mover valores de forma ascendente, a la vez que se realiza el análisis, por el árbol de derivación obtenido para el análisis de una expresión. Estas variables almacenan el “valor semántico” de cada uno de los símbolos de cada regla, estan definidas por Yacc y sus nombre nombres identificadores son invariables. Son las

siguientes:

$$ representa la parte izquierda de una regla

$1, $2,... representan a los valores asociados a los símbolos de la parte derecha de una regla.

Así $n almacena el valor asociado al símbolo que ocupa la posición n en la parte derecha de la regla.

Las asignaciones que permiten este movimiento de valores semánticos aparecen como parte de la acción asociada a una regla y se denominan reglas semánticas.

Ejemplo3:

            El ejemplo siguiente muestra la sección de reglas de un programa Yacc para una gramática que reconoce el lenguaje formado por las expresiones aritméticas de suma y resta y además devuelve el valor obtenido de evaluar la expresión aritmética de entrada.

%%

S : exp ‘\n’ {printf (“Resultado: %d\n”, $1);}

;

exp : exp ‘+’ exp {$$ = $1+$3}

| exp ‘-’ exp {$$ = $1-$3}

| ’(‘ exp ‘)’ {$$ = $2}

| NUM {$$ = $1}

;

%%

 

Asociatividad y Precedencia

Por defecto Yacc es asociativo a la derecha pero esto puede modificarse en la sección de definiciones utilizando las siguientes directivas:

%left asocia a la izquierda

%right asocia a la derecha

Supongamos el siguiente fragmento de programa Yacc para una gramática que reconoce expresiones de sumas de números:

3

%token NUM

%left ‘+’

%%

exp : exp ‘+’ exp {$$ = $1+$3}

| NUM {SS = $!}

;

Si la entrada fuese 5+6+8 por defecto se resolvería como 5+(6+8) (asociación por la derecha),

pero al haber definido %left al símbolo ‘+’ en la sección de definiciones el resultado es

(5+6)+8 (asociación por la izquierda).

Los árboles de análisis obtenidos de una manera o de otra serían bastante diferentes:

Asociación por la derecha Asociación por la izquierda

%left, %right y %nonassoc Además de indicar asociatividad se utilizan en la sección de definiciones para indicar precedencia de los operadores teniendo mayor precedencia cuanto más alejados estén del principio del fichero. La última de las tres directivas no indica asociatividad solo precedencia.

 

 

%pred Se utiliza en una regla para dar distinta prioridad al primer símbolo de esa regla, solo para la aplicación de esa regla. Se usa cuando un mismo símbolo puede tener significados distintos con prioridades diferentes. Por ejemplo el símbolo ‘-‘ puede ser unario y binario, cuando es binario tiene la misma prioridad que ‘+’, pero cuando es unario tiene mayor prioridad. En este caso se le puede asignar la misma prioridad que a ‘*’, tal y como se muestra en el ejemplo siguiente.

%right ‘=’ /*menor precedencia*/

%left ‘+’, ‘-‘

%left ‘*’, ‘/’ /*mayor precedencia*/

%%

exp : exp ‘=’ exp

| exp ‘+’ exp

| exp ‘-’ exp

| exp ‘*’ exp

| exp ‘/’ exp

| ‘-‘ exp %pred ‘*’

| CAR

;

Así frente a la entrada a=b=c*d-e-f*g se analizaría como a=(b=(((c*d)-e)-(f*g)))

 

Conflictos y Ambigüedad

Cuando la gramática de entrada no es LALR(1), Yacc informará de que ha encontrado “conflictos”. Los conflictos se producen cuando el algoritmo de construcción de las tablas no ha permitido, en un momento dado, que se sepa si la acción adecuada es desplazar o reducir (conflicto shift/reduce),

o bien cuando haya varias posibilidades de reducción (conflicto reduce/reduce).

Se podrá encontrar cuales son los conflictos aparecidos examinando el contenido de y.output.

exp

exp exp +

exp exp + 5

6 8 5 6

exp

exp exp +

exp exp + 8

 

A veces es conveniente conocer cuales son los conflictos que provoca nuestra gramática y tratar de evitarlos, para ello puede ser útil utilizar la opción –v de Yacc para examinar el autómata descrito

en el fichero y.output.

Independientemente de la información mostrada Yacc continua el proceso, generando un programa que resuelve sistemáticamente los conflictos aplicando las siguientes normas:

Entre desplazar y reducir, elige desplazar.

Entre dos reducciones distintas, elige la correspondiente a la regla que aparezca en primer lugar

 

 Conflicto Reducción-Reducción

La siguiente especificación, por ejemplo, produce un conflicto reducción-reducción.

%token CART PLOW AND HORSE GOAT OX

%%

phrase : cart_animal AND CART

| work_animal AND PLOW

;

cart_animal : HORSE

| GOAT

;

work_animal : HORSE

| OX

;

Al llamar a Yacc con este programa fuente aparecerán los siguientes mensajes:

yacc: 1 rule never reduced

yacc: 1 reduce/reduce conflict

cuyo significado se explica un poco más en el fichero y.output.

El problema aparece ante una frase como HORSE AND PLOW

PILA ENTRADA ACCIÓN

$ HORSE AND PLOW desplazar

$ HORSE AND PLOW $ reducir ¿por cart_animal (regla 3) o work_animal (regla 5)?

(no se sabe que HORSE es un work_animal porque aún no se ve

PLOW)

Obsérvese que en este ejemplo el método de resolución de conflictos de Yacc (en este caso, reducción-reducción, reducir por la primera regla) da lugar a que se considere la frase como incorrecta aún siendo correcta.

La siguiente gramática es equivalente pero LALR(1):

phrase : cart_animal CART

| work_animal PLOW

;

cart_animal : HORSE AND

| GOAT AND

;

work_animal : HORSE AND

| OX AND

;

 

Conflicto Desplazamiento-Reducción

Un ejemplo clásico de conflicto desplazamiento/reducción es la provocada por los lenguajes de programación con la estructura condicional simple y compuesta. Por ejemplo supongamos la siguiente gramática:

stat : IF ‘(‘ cond ‘)’ stat

: IF ‘(‘ cond ‘)’ stat ELSE stat

;

Si la entrada fuese IF (a<3) a=0 ELSE a++ hay conflicto desplazamiento-reducción, se puede desplazar por la regla2 o reducir por la regla1. Se podría reducir por la primera regla una vez leído IF (a<3) a=0 , lo que sería incorrecto. Yacc continúa para comprobar si puede aplicar la segunda regla (frente a un conflicto desplazar-reducir, Yacc siempre desplaza).

La entrada IF c1 IF c2 s1 ELSE s2 puede interpretarse como IF c1 {IF c2 s1} ELSE s2 o como IF c1 {IF c2 s1 ELSE s2} que es la más usada en lenguajes de programación, se toma el ELSE como asociado al IF más cercano. Comprobar como lo resuelve Yacc.

Otro ejemplo de conflicto desplazamiento-reducción lo tenemos en la gramática siguiente:

%token DIG

%%

E : E ‘+’ E

| DIG

;

En este caso la gramática es ambigua y eso produce los conflictos como podemos ver en las tablas de desplazamiento-reducción siguientes:

ACCIÓN DIG + $end Ir_A E

estado significado

0 $accept : . E $end (0) shift 1 2

1 E : DIG . (2) reduce 2 reduce 2 reduce 2

2 $accept : E . $end (0)

E : E . ‘+’ E (1)

shift 3 accept

3 E : E ‘+’ . E (1) shift 1 4

4 E : E . ‘+’ E (1)

E : E ‘+’ E . (1)

shift 3

(reduce 1)

reduce1

Comprobar cómo resuelve Yacc los conflictos en este caso.

 

 

 

 

Diseño de Compiladores

 

 

 

Yacc provee una herramienta general para analizar estructuralmente una entrada. El usuario de Yacc prepara una especificación que incluye:

·                    un conjunto de reglas que describen los elementos de la entrada

·                    un código a ser invocado cuando una regla es reconocida

·                    una o más rutinas para examinar la entrada

Luego Yacc convierte la especificación en una función en C que examina la entrada. Esta función, un parser, trabaja mediante la invocación de un analizador léxico que extrae tokens de la entrada. Los tokens son comparados con las reglas de construcción de la entrada, llamadas reglas gramaticales. Cuando una de las reglas es reconocida, el código provisto por el usuario para esa regla (una acción) es invocado. Las acciones son fragmentos de código C, que pueden retornar valores y usar los valores retornados por otras acciones.

Tanto el analizador léxico como el sintáctico pueden ser escritos en cualquier lenguaje de programación. A pesar de la habilidad de tales lenguajes de propósito general como C, lex y yacc son más flexibles y mucho menos complejos de usar.

Lex genera el código C para un analizador léxico, y yacc genera el código para un parser. Tanto lex como yacc toman como entrada un archivo de especificaciones que es típicamente más corto que un programa hecho a medida y más fácil de leer y entender. Por convención, la extensión del archivo de las especificaciones para lex es .l y para yacc es .y. La salida de lex y yacc es código fuente C. Lex crea una rutina llamada yylex en un archivo llamado lexyy.c. Yacc crea una rutina llamada yyparse en un archivo llamado y_tab.c.

Estas rutinas son combinadas con código fuente C provisto por el usuario, que se ubica típicamente en un archivo separado pero puede ser ubicado en el archivo de especificaciones de yacc. El código provisto por el usuario consiste de una rutina main que llama a yyparse, que en su momento, llama a yylex. Todas estas rutinas deben ser compiladas, y en la mayoría de los casos, las librerías lex y yacc deben ser cargadas en tiempo de compilación. Estas librerías contienen un número de rutinas de soporte que son requeridas, si no son provistas por el usuario.

El siguiente diagrama permite observar los pasos en el desarrollo de un compilador usando lex y yacc:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Los elementos de una gramática

 

La sintaxis de un programa puede ser definida por una gramática libre de contexto. Ésta es esencialmente una estructura jerárquica que indica las relaciones de las construcciones del lenguaje. La notación más común usada para describir una gramática libre de contexto es BNF. La especificación de YACC se hace en BNF.

La descripción se hace en la forma de reglas de producción, que consisten de un nombre de no terminal, el lado izquierdo, seguido por su definición. La definición, o lado derecho, consiste de cero a más símbolos que son no terminales que apuntan a otras reglas o terminales que corresponden a tokens. Por ejemplo, una gramática simple:

lista  objeto | lista objeto

objeto  cadena | numero

cadena  texto | comentario | comando

numero  numero | ´+´ numero | ´-´ numero | numero ´.´ numero

 

En este ejemplo, las palabras en negrita representan los terminales y el resto los no terminales. La primera regla establece que una lista se forma de un objeto o de una lista y un objeto.

La segunda forma de la regla es una definición recursiva. Esto permite que un concepto complejo, como una lista, sea descripto en una forma compacta. Puesto que no sabemos de antemano cuántos elementos formarán la lista, no podríamos definirla convenientemente sin esta forma recursiva. Así, se establece que una lista es una secuencia de objetos, uno después de otro. Si quisiéramos describir una lista separada por comas, la regla sería:

lista  objeto | lista ´,´ objeto

 

|  es un operador de unión. Notar por ejemplo, su uso en la última regla. Así, un número es o un numero, o un numero con un mas (+) adelante, un numero con un menos (-) adelante, o dos números separados por un punto decimal (.). Así, se pueden listar muchas elecciones posibles en una forma compacta.

La construcción de una gramática es un proceso botton-up, incluyendo cada grupo en grupos más grandes hasta llegar a un solo grupo de más alto nivel que incluye a todos los otros grupos. Esta construcción de más alto nivel se llama el símbolo start. En el ejemplo, este símbolo es ¨lista¨. Cuando este símbolo es reconocido y no hay más entrada, el parser sabe que ha visto un programa completo. El parser creado por yacc devuelve un 0 si toda la entrada es válida, y un 1 si se ha encontrado un error de sintaxis.

Se puede hacer un parser que haga algo más que reconocer la sintaxis correcta de un programa. Se puede hacer que reconozca secuencias erróneas, y emita mensajes de error razonables.

 

Interacción entre las rutinas Léxica y de Parsing

 

Una rutina main invoca a yyparse para evaluar si la entrada es válida o no. yyparse invoca a una rutina llamada yylex cada vez que necesita un token. (yylex puede ser generado manualmente o generado por lex). Esta rutina léxica lee la entrada, y por cada token que reconoce, retorna el número de token al parser. El léxico puede también pasar el valor del token usando la variable externa yylval. Las rutinas de acción del parser, así como la rutinas provistas por el usuario pueden usar ese valor. Las rutinas de acción pueden llamar a otras funciones que pueden estar ubicadas en la sección de código del usuario o en otros archivos de código fuente.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Veamos cómo la rutina léxica y el parser trabajan juntos analizando un pequeño fragmento de código C.

if (i)

return (i);

 

El analizador léxico convierte esta entrada de bytes en tokens reconociendo patrones particulares. Por ejemplo, cuando el analizador léxico ve ¨return (i)¨, podría reconocer los siguientes elementos:

return                        token RETURN

(                      literal ´(´

i                      token ID

)                      literal ´)´

;                       literal ´;´

 

Si el analizador léxico ve “i” retornará el token ID al parser, y podrá pasarle también el valor real del token (en este caso “i”). El parser podría pasar el nombre de la variable a una rutina como acción, que buscaría en la tabla de símbolos para determinar si el identificador era válido.

La especificación yacc podría tener la siguiente regla para definir una sentencia válida:

sent:    RETURN expr ´;´

;

 

El token RETURN  es un símbolo terminal identificado por el analizador léxico. expr es un no terminal definido por una regla de la gramática. Una regla para expr sería:

expr:   ID

|  ´(´ expr ´)´

;

 

La barra vertical indica que hay definiciones alternativas para la misma regla. Esta regla establece que una expr puede ser un ID o una expr entre paréntesis.

Cualquier regla de la gramática puede tener una acción asociada para evaluar los tokens que fueron reconocidos. Una acción es una o más sentencias C que pueden ejecutar una variedad de tareas, incluyendo producir salidas o alterar variables externas. Frecuentemente, la acción actúa sobre el valor de los tokens de la construcción.

El analizador léxico asigna el valor de cada token a la variable externa yylval. Yacc provee una notación posicional, $n, para acceder al valor del enésimo token en una expresión:

expr:   NUM ´+´ NUM                    { printf (¨%d¨, $1 + $3); }

 

En este caso, la acción imprime la suma del valor del primero y tercer token. El valor retornado por una acción puede ser asignado a la variable ¨$$¨. Veamos el siguiente ejemplo:

expr:   ID                                          { $$ = $1; }

|  ´(´ expr ´)´                         { $$ = $2; }

;

 

La primera acción es invocada cuando se reconoce ¨ID¨, y retorna el valor del token ID como el valor de la regla expr. Realmente, esta el la acción por defecto, y puede ser omitida opcionalmente. La segunda acción selecciona el valor de expr que es el segundo elemento en la construcción.

 

Tokens

 

La función básica de la rutina léxica es detectar un token y retornar un número de token a la rutina del parser que llamó a aquélla. El número de token es definido por un símbolo que el parser usa para identificar un token. Además, la rutina léxica puede pasar el valor real del token mismo.

Las acciones de la especificación lex consiste de sentencias C que retornan el número de token y su valor. Los números de token son definidos por yacc cuando éste procesa los tokens declarados en la especificación yacc. La sentencia #define es usada para definir los números de tokens:

#define          NUMERO 257

Estas definiciones son ubicadas en el archivo y_tab.c, junto con la rutina yyparse. (Cada carácter ASCII es definido como un token cuyo número es su valor ASCII (0 a 256); así, los tokens definidos por el usuario comienzan en 257). El parser y el léxico deben usar el mismo conjunto de símbolos para identificar tokens; por lo tanto el léxico debe tener acceso a los símbolos definidos por el parser. Una forma de hacer esto es decir a yacc que cree el archivo de encabezamiento y_tab.h que puede ser incluido en la especificación lex. Por supuesto, se podría definir explícitamente estos símbolos en la especificación lex, asegurándose que se correspondan con los números de tokens asignados en yacc.

Para retornar el número de token en una acción, se debe usar la sentencia return. Por ejemplo, la siguiente regla que aparea cualquier número y la acción retorna el token NUMERO:

[0-9] +            { return NUMERO; }

Para pasar el valor del token al parser, lex crea una variable externa llamada yytext que contiene la cadena de caracteres que son reconocidas por la expresión regular. Una variable externa llamada yylval es seteada por yacc para pasar el valor del token desde el analizador léxico al parser. El tipo de yylval es int, por defecto. Por lo tanto, para asignar el valor de yytext a yylval, se debe convertir el valor desde una string a un int. Se puede cambiar el tipo de yylval o, como se verá, definir una unión de tipos de datos múltiples para yylval.

Por ejemplo, se puede usar la función atoi para convertir un número almacenado como una cadena en yytext a un int y asignarlo a yylval:

[0-9] +

{           yylval = atoi (yytext);

return NUMERO;

}

 

Autómatas Pushdown

 

Los autómatas finitos son suficientes para lex. Sin embargo, cuando se intenta modelar los lenguajes que yacc maneja, no son suficientes, porque no tienen el concepto de estado anterior. Los autómatas son incapaces de usar el conocimiento de cuál fue el token previo. Esto hará imposible el reconocimiento de algunos lenguajes.

Un autómata pushdown es similar al autómata finito. Tiene un número finito de estados, una función de transición, y una entrada. La diferencia es que el autómata pushdown está equipado con una pila. Y este es el tipo de autómata que genera yacc. La función de transición trabaja sobre el estado actual, el elemento en el tope de la pila, y el token de entrada actual, produciendo un nuevo estado.

Esta capacidad hace al autómata pushdown más útil. Por ejemplo, recordar el estado anterior permite a yacc reconocer gramáticas conocidas como la clase de lenguajes LALR (LookAhead Left Recursive, que pueden ver anticipadamente un token, y son muy similares a una clase de lenguajes llamados gramáticas libres de contexto). Los lenguajes LALR son esencialmente una clase de lenguajes que dependen del contexto sobre no más que un solo token.

El parser generado por yacc también es capaz de leer y recordar el próximo token en la entrada (token anticipado). El estado actual es siempre el del tope de la pila. Inicialmente, la máquina de estados está en el estado 0 (la pila contiene sólo el estado 0) y no se ha leído ningún token anticipado.

El autómata tiene sólo cuatro acciones disponibles: shift, reduce, accept, y error. Un paso en el parser se hace de la siguiente manera:

De acuerdo con el estado actual, el parser decide si necesita un token anticipado para decidir la próxima acción. Si necesita un token y no lo tiene, llama a yylex para obtener el próximo token.

De acuerdo con el estado actual y el token anticipado, si es necesario, el parser decide su próxima acción y la lleva a cabo. Esto puede provocar que se apilen y desapilen estados en la pila, y que el token anticipado sea procesado o no.

Cuando se lleva a cabo la acción shift, hay siempre un token anticipado. Por ejemplo, en el estado 56, puede haber una acción:

IF        shift 34

que dice que si el token anticipado es IF, el estado 34 se convertirá en el estado actual (en el tope de la pila), cubriendo al estado actual (56). El token anticipado se borra.

La acción reduce evita que la pila crezca sin límites. Las acciones reduce son apropiadas cuando el parser ha visto el lado derecho de un regla de la gramática y está preparado para anunciar que ha visto una instancia de la regla reemplazando el lado derecho con el izquierdo. Puede ser necesario consultar el token anticipado para decidir si reducir o no. Usualmente, esto no es necesario. En efecto, la acción por defecto (representada mediante un punto) es a menudo una acción reduce.

Las acciones reduce son asociadas con reglas individuales de la gramática.

Debido a que un mismo número puede ser usado para identificar a una regla y también a un estado, puede producirse alguna confusión. La acción:

.           reduce 18

se refiere a la regla 18 de la gramática, mientras que la acción:

IF        shift 34

se refiere al estado 34.

Supongamos que la regla:

A   :     x   y   z    ;

está siendo reducida. La acción reduce depende del símbolo a la izquierda (A, en este caso) y el número de símbolos en el lado derecho (tres, en este caso). Al reducir, las tres estados en el tope de la pila se desapilan. (En general, el número de estados desapilados iguala al número de símbolos en el lado derecho de la regla). En efecto, estos estados eran los que se apilaron al reconocer x, y y z, y ya no servirán para ningún propósito. Al desapilar estos estados, queda descubierto el estado en que el parser estaba al comenzar a procesar la regla. Usando esta estado y el símbolo del lado izquierdo de la regla, se ejecuta un shift de un nuevo estado a pila, y el parsing continúa. Sin embargo, hay diferencias entre un shift normal y el procesamiento del símbolo del lado izquierdo, así que a esta acción se la llama goto. En particular, el token anticipado es borrado por un shift, pero no es afectado por un goto. Así que el estado descubierto al hacer el reduce contendrá una acción como la siguiente:

A         goto 20

que produce que el estado 20 se apile y se convierta en el estado actual.

En efecto, la acción reduce vuelve atrás el reloj del parser, desapilando estados hasta descubrir el estado en el que el lado derecho de la regla fue visto por primera vez. El parser se comporta, entonces, como si hubiera visto el lado izquierdo en ese momento.

Las otras dos acciones del parser son conceptualmente mucho más simples. La acción accept indica que el parser ha visto la entrada completa y que ésta cumple con la especificación. Esta acción aparece sólo cuando el token anticipado es la marca de fin de archivo, e indica que parser ha completado su trabajo. La acción error representa un lugar donde el parser no puede continuar el proceso de acuerdo con la especificación. Los tokens que ha visto, junto con el anticipado, no pueden ser seguidos por nada que constituya una entrada legal. El parser reporta el error e intenta recuperar la situación y continuar con el parsing.

Sea la siguiente especificación yacc:

%token    A   B   C

%%

lista    :           inicio   fin

;

inicio  :           A   B

;

fin       :           C

;

Cuando yacc es ejecutado con la opción -v, produce un archivo llamado y.output (y.out para DOS) que contiene una descripción legible del parser. El archivo y.output correspondiente a la gramática anterior (con algunas estadísticas al final) es el siguiente:

 

state 0

$accept   :   _lista   $end

 

A   shift  3

.   error

 

lista   goto  1

inicio  goto  2

 

 

 

state 1

$accept   :   lista_$end

 

$end   accept

.   error

 

state 2

lista   :   inicio_fin

 

C   shift  5

.   error

 

fin   goto  4

 

state 3

inicio   :   A_B

 

B   shift  6

.   error

 

state 4

lista   :   inicio  fin_  (1)

 

.   reduce  1

 

state 5

fin   :   C_                   (3)

 

.   reduce 3

 

state 6

inicio   :   A  B_                     (2)

 

.   reduce  2

 

Para cada estado se especifican las acciones y las reglas procesadas. El carácter _ se usa para indicar que parte de la regla ya ha sido vista y qué tiene que venir.

Vamos a analizar el comportamiento del parser ante la siguiente entrada:

A   B   C

Inicialmente, el estado actual es el estado 0. El parser necesita referirse a la entrada para decidir entre las acciones disponibles en ese estado. El primer token, A, es leído y se convierte en el token anticipado. La acción en el estado 0 para A es shift 3; se apila el estado 3, y se borra el token anticipado. El estado 3 se convierte en el estado actual. Se lee el próximo token, B, que se convierte en token anticipado. La acción en el estado 3 para el token B es shift 6; se apila el estado 6, y se borra el token anticipado. La pila ahora contiene los estados 0, 3, y 6. En el estado 6, sin consultar el token anticipado, el parser reduce por:

inicio   :   A   B

que es la regla 2. Dos estados, el 6 y el 3, son desapilados, dejando descubierto el estado 0. La acción en ese estado para inicio es un goto:

inicio   goto  2

Se apila el estado 2 que se convierte en el estado actual. En el estado 2, el próximo token, C, debe ser leído. La acción es shift 5, así que el estado 5 es apilado, así que ahora la pila tiene los estados 0, 2, y 5, y se borra el token anticipado. En el estado 5, la única acción es reducir por la regla 3. Esta tiene un símbolo en el lado derecho, así que un estado, el 5, es desapilado, y el estado 2 queda descubierto. La acción para fin (el lado izquierdo de la regla 3) en el estado 2 es un goto al estado 4. Ahora, la pila contiene los estados 0, 2, y 4. En el estado 4, la única acción es reducir por la regla 1. Hay dos símbolos a la derecha, así que los dos estados de arriba son desapilados, descubriendo de nuevo el estado 0. En el estado 0, hay un goto para lista; causando que el parser entre al estado 1. En este estado, se lee la entrada, y se obtiene la marca de fin de archivo, indicada por $end en el archivo y.output. La acción en el estado 1 (cuando se encuentra la marca de fin) finaliza exitosamente el parsing.

 

 

Usando Yacc

 

Hay cuatro pasos para crear un parser:

1.                  Escribir una especificación yacc que describe la gramática. Este archivo usa la extensión .y por convención.

2.                  Escribir un analizador léxico que puede producir una corriente de tokens. Esta rutina puede ser generada por lex o codificada a mano en C. El nombre de la rutina léxica es yylex.

3.                  Ejecutar yacc sobre la especificación para generar el código fuente del parser. El archivo de salida es nombrado y_tab.c por yacc.

4.                  Compilar y vincular los archivos fuentes del parser y del analizador léxico y cualquier archivo de programa relacionado.

El archivo de salida y_tab.c contiene una rutina de parsing llamada yyparse que llama a la rutina léxica yylex cada vez que necesita un token. Como lex, yacc no genera un programa completo; yyparse debe ser llamado desde una rutina main. Un programa completo también requiere una rutina de errores llamada yyerror que es llamada cuando yyparse encuentra un error. Tanto la rutina main como yyerror pueden ser  provistas por el programador, aunque se proveen versiones por defecto de esas rutinas en las librerías de yacc, y estas librerías pueden ser vinculadas al parser usando la opción -ly durante la compilación.

 

Escribiendo una Especificación Yacc

 

Una especificación yacc describe una gramática libre de contexto que puede ser usada para generar un parser. Esta gramática tiene cuatro clases de elementos:

1.                  Tokens, que son un conjunto de símbolos terminales

2.                  Elementos sintácticos, que son un conjunto de símbolos no terminales

3.                  Reglas de producción que definen un símbolo no terminal (el lado izq.) en términos de una secuencia de no terminales y terminales (lado derecho)

4.                  Una regla start que reduce todos los elementos de la gramática a una sola regla.

El corazón de una especificación yacc es un conjunto de reglas de producción de la siguiente forma:

 

 

 

símbolo:                    definición

{acción}

;

Un (:) separa el lado izq. del derecho de la regla, y un (;) termina la regla. Por convención, la definición sigue dos tabs después del (:). También por legibilidad, el (;) se ubica solo en una línea.

Cada regla de la gramática lleva el nombre de un símbolo, un no terminal. La definición consiste  de cero o más nombres de terminales, tales como tokens o caracteres literales, y otros símbolos no terminales. Los tokens, que son símbolos terminales reconocidos por el analizador léxico, son permitidos sólo en el lado derecho. Cada definición puede tener una acción escrita en C asociada con ella. Esta acción es ubicada entre llaves.

Las reglas que comparten el mismo lado izquierdo pueden ser combinadas usando una barra vertical (|). Esto permite definiciones alternativas dentro de una regla.

El nombre de un símbolo puede ser de cualquier longitud, consistiendo en letras, punto, underscore, y dígitos (en cualquier lugar excepto en la primera posición). Se distingue entre mayúsculas y minúsculas. Los nombres de símbolos no terminales van en minúsculas y los tokens en mayúsculas por convención.

Si la entrada no responde a la gramática, entonces el parser imprimirá el mensaje ¨syntax error¨. Este mensaje emitido por la rutina yyerror, que puede ser redefinida por el programador para proveer más información.

La mínima especificación yacc consiste en una sección de reglas precedidas por una declaración de los tokens usados en la gramática.

El formato completo tiene los siguientes elementos:

declaraciones

%%

reglas gramaticales

%%

código C

 

 

 

 

 

 

 

 

 

 

 

Sección de declaraciones:

 

La sección de declaraciones contiene información que afecta la operación de yacc. Esta sección usa varias palabras claves para definir tokens y sus características. Cada una de estas palabras claves es seguida por una lista de tokens o caracteres literales entre apóstrofes.

% union        Declara múltiples tipos de datos para valores semánticos (tokens)

Ejemplo:

% union {

int entero;

char *cadena;

}

% token         Declara los nombres de los tokens. Si se usa union la sintaxis es:

% token <elem. de la union que corresponde a este grupo de tokens > lista de tokens

% left             Define operadores asociativos a izquierda

% right          Define operadores asociativos a derecha

El orden en que se pongan estas declaraciones indica la precedencia (mayor precedencia a medida que bajamos) Si se utiliza esta declaración, declarar los operadores como tokens sería redundante

% nonassoc  Define operadores no asociativos

% type           Declara el tipo de no terminales, cuando se uso union, y en las acciones  asociadas a las reglas, se hacen asignaciones a $$

% start           Declara el símbolo de start. El defecto es la primera regla

% prec           Asigna precedencia a una regla

La sección de declaraciones también puede contener código C para declarar variables o tipos así como macros definidas. Puede también contener sentencias #include para incluir archivos de encabezamiento. Esto se hace del modo siguiente:

%{

declaraciones C

%}

Cualquier cosa entre %{ y %} es copiada directamente al archivo generado por yacc.

 

Sección de reglas:

 

La sección de reglas contiene las reglas de producción que describen la gramática. En general una regla consiste de uno o más conjuntos de tokens y no terminales con una acción opcional para cada conjunto de tokens. En estas reglas, un carácter literal se encierra entre apóstrofes. La \ tiene un significado especial, como en C, para secuencias escape:

´\n´                newline

´\r´                 return

´\´´                 comilla simple

´\\´                barra invertida

´\t´                 tab

´\b´                backspace

´\f´                 form feed

´\xxx´             carácter cuyo valor es xxx

 

Token error

 

Se puede usar en las reglas un símbolo llamado error. No existe una regla que lo defina, ni se incluye en la declaración de tokens. Es un token definido especialmente por yacc que significa que cualquier token que no aparee ninguna de las otras reglas, apareará la que contiene error.

Conviene utilizarlo con otro token, que sirve de carácter de sincronización. A partir del token erróneo, yacc tirará todos hasta encontrar ese carácter (por ej. un newline). Esto permite, de algún modo, recuperar errores. Se puede asociar una acción que permita informar que el token es erróneo, y toda la información que se desee agregar.

 

Acciones

 

El parser generado por yacc guarda los valores de cada token en una variable de trabajo (yyval del mismo tipo que yylval). Estas variables de trabajo están disponibles para ser usadas dentro de las acciones de las reglas. En el código real, son reemplazadas con las referencias yacc correctas. Las variables son rotuladas $1, $2, $3, etc. La pseudo-variable $$ es el valor a ser retornado por esa invocación de la regla.

Se pueden ejecutar acciones después de cualquier elemento de un conjunto de tokens (no sólo al final)

 

 

 

Sección de código:

 

La sección de código C es opcional, pero puede contener cualquier código C provisto por el usuario. Allí se pueden especificar la rutina de análisis léxico yylex, una rutina main, o subrutinas usadas por acciones de la sección de reglas.

Tres rutinas son requeridas: main, yylex, y yyerror, aunque estas también pueden ser vinculadas externamente.

Se pueden usar comentarios como en C (/* ... */). Blancos, tabs, y newlines se ignoran.

Veamos una simple gramática con un solo token: ENTERO. La función de esta especificación es generar un programa que imprime cualquier número que reciba como entrada:

 

% token ENTERO

%%

lineas:                        /* vacía */

| lineas linea

{ printf (¨= %d\n¨, $2); }

;

linea:              ENTERO ´\n´

{ $$ = $1; }

;

%%

#include ¨lex.yy.c¨

 

En la sección de declaraciones, se declara el token ENTERO. Este se traducirá en una sentencia #define que asocia una constante numérica con este símbolo. Este símbolo es usado para comunicación entre el analizador léxico y el parser.

En la sección de reglas, se especifica una gramática hecha de dos grupos: líneas y línea. La primera regla define lineas como cero o más líneas de entrada. La primera de las dos definiciones alternativas es vacía. Esta es una definición convencional que significa que la cadena vacía es permitida como entrada. (Eso no significa que las líneas en blanco sean válidas). La segunda definición alternativa es recursiva, estableciendo que la entrada consiste de una o más líneas. El símbolo no terminal linea está definido en la segunda regla. Esta consiste de un token ENTERO seguido por un newline.

Ahora consideremos los acciones asociadas con estas reglas. Yacc provee pseudo variables adicionales que hace más fácil obtener el valor de un símbolo en una acción o setear el valor del símbolo retornado por la acción. El signo $ tiene un significado especial para yacc. El valor de cada elemento de una definición puede ser recuperado usando notación posicional: $1 para el primer token, $2 para el segundo, etc. El valor retornado por la acción es seteado asignando ese valor a $$. Miremos la acción asociada con la regla linea. Esta acción retorna el valor del token ENTERO. Hay dos elementos en la definición, pero el newline no es retornado. El valor del token ENTERO es pasado a la acción asociada con la regla lineas. En la acción de ésta, $2 se refiere al valor de linea.

La tercera parte del ejemplo contiene una sentencia #include que incluye el código fuente del analizador léxico.

 

Una especificación para una simple Máquina de Sumar

 

Se trata de una máquina que lleva una cuenta total y permite sumar o restar de ese total. También se puede resetear el total a cero o a cualquier otro valor. La entrada consiste en un número opcionalmente precedido por un +, un -, o un =. Por ejemplo, si la primera entrada es 4 o +4, se imprime =4. Si la próxima entrada es -3, se imprime =1. Si la entrada es = o =0, el total se resetea a 0, y se imprime =0.

Especificación para yacc:

 

%{

int sum_total = 0;

%}

 

%token ENTERO

 

%%

 

lineas:      /*  vacía  */

| lineas linea

;

 

linea:  ´\n´

| expr´\n´

{ printf(¨= %d\n¨, sum_total);  }

;

expr:   ENTERO                   {sum_total += $1; }

| ´+´ ENTERO                     {sum_total += $2; }

| ´-´ ENTERO                      {sum_total -= $2; }

| ´=´ ENTERO                     {sum_total = $2; }

| ´=´                           {sum_total = 0; }

;

%%

#include ¨lexyy.c¨

 

La acción principal en esta especificación es setear la variable sum_total de acuerdo con la entrada y luego imprimir el nuevo valor. La sección de declaraciones contiene la declaración e inicialización de sum_total. Se crea esta variable para llevar el total. Luego, se declara un único token, ENTERO.

La primera regla es la misma que la del ejemplo anterior. Esta vez, sin embargo, no hay acción asociada. Permite leer una serie de líneas, no sólo una.

La regla para linea tiene definiciones alternativas. Un newline o una expr seguida por un newline son aceptadas. Así, se pueden ingresar líneas en blanco al programa sin causar un error de sintaxis. Un  newline o una expr seguida por un newline ejecuta la acción de imprimir el total actual.

La regla para expr también tiene definiciones alternativas. Un token ENTERO, un +, un -, o un = seguido por un token ENTERO, y un = solo son aceptados. Cada acción asociada con una definición asigna un nuevo valor a sum_total. Notar que no asignamos el nuevo valor a ¨$$¨, porque necesitamos acumular este valor desde una entrada a la próxima.

 

Ambigüedades y Conflictos en gramáticas Yacc

 

Un conjunto de reglas gramaticales es ambiguo si hay alguna cadena de entrada que puede ser estructurada en dos o más formas diferentes. Por ejemplo, la regla:

expr    :     expr   ´-´   expr

es una forma natural de expresar que una forma de construir una expresión aritmética es juntar otras dos expresiones con un signo menos. Desafortunadamente, esta regla no especifica completamente como se deberían estructurar las entradas complejas. Por ejemplo, si la entrada es:

expr   -   expr   -   expr

la regla permite que esta entrada sea estructurada como:

(   expr   -   expr   )   -   expr

o como

expr   -   (   expr   -   expr   )

(La primera es llamada asociatividad a izquierda; la segunda, asociatividad a derecha)

 

El programa yacc detecta tales ambigüedades cuando intenta construir el parser. Dada la entrada:

expr   -   expr   -   expr

el parser enfrenta el siguiente problema. Cuando el parser ha leído la segunda expresión expr, la entrada visible

expr   -   expr

aparea el lado derecho de la regla de arriba. El parser podría reducir la entrada aplicando esta regla. Después de aplicarla, la entrada es reducida a expr (el lado izquierdo de la regla). El parser lee entonces la parte final de la entrada:

-   expr

y reduce nuevamente. El efecto de esto es tomar la interpretación correspondiente a la asociatividad a izquierda.

 

Alternativamente, si el parser ve:

expr   -   expr

podría diferir la aplicación inmediata de la regla, y continuar leyendo la entrada hasta que ve:

expr   -   expr   -   expr

El parser podría entonces aplicar la regla a los tres símbolos de más a la derecha, reduciendo entonces a expr, dejando:

expr   -   expr

Ahora la regla puede ser reducida una vez más. El efecto es tomar la interpretación correspondiente a la asociatividad a derecha. Así, habiendo leído:

expr   -   expr

el parser puede hacer una de dos acciones legales, un shift o una reducción. No tiene forma de decidir entre ambas. Esto es un conflicto shift-reduce. El parser puede también tener que elegir entre dos reducciones legales. Este es un conflicto reduce-reduce. Notar que nunca hay conflictos shift-shift.

 

Cuando hay conflictos shift-reduce o reduce-reduce, yacc de todos modos produce un parser. Lo hace seleccionando una de las acciones legales cuando tiene que elegir. Para ello, el programa yacc provee dos reglas de desambiguación:

 

1.                  En un conflicto shift-reduce, la acción por defecto es el shift

 

2.                  En un conflicto reduce-reduce, el defecto es reducir por la primera regla (en la especificación yacc)

 

La regla 1 implica que las reducciones son diferidas en favor de los shifts cuando es necesario elegir entre ambas acciones. La regla 2 le da al usuario el control sobre el comportamiento del parser en esta situación, aunque los conflictos reduce-reduce deberían ser evitados en lo posible.

El uso de acciones dentro de las reglas puede también causar conflictos si la acción debe hacerse antes que el parser pueda estar seguro de cual regla está reconociendo. En estos casos, la aplicación de las reglas de desambiguación es inapropiada, y llevaría a un parser incorrecto. Por esta razón, yacc siempre reporta el número de conflictos shift-reduce y reduce-reduce resueltos por la Regla 1 y por la Regla 2.

En general, si es posible aplicar las reglas de desambiguación para producir un parser correcto, también es posible reescribir las reglas de la gramática de modo que las mismas entradas puedan ser leídas sin conflictos. Por esta razón, la mayoría de los generadores de parsers previos, consideraban los conflictos como errores fatales. Sin embargo, yacc producirá parsers aún en presencia de conflictos.

Como un ejemplo del poder de las reglas de desambiguación, consideremos:

sent     :   IF   ´(´   cond   ´)´   sent

|   IF   ´(´   cond   ´)´   sent   ELSE   sent

;

 

que es un fragmento de un lenguaje de programación correspondiente a una sentencia if-then-else. En estas reglas, IF y ELSE son tokens, cond es un símbolo no terminal describiendo expresiones condicionales (lógicas), y sent es un símbolo no terminal describiendo sentencias. Llamaremos regla if simple a la primera, y regla if-else, a la segunda.

Estas dos reglas forman una construcción ambigua porque una entrada de la forma:

IF   (   C1   )   IF   (   C2   )   S1   ELSE   S2

puede ser estructurada de acuerdo con las reglas anteriores como:

IF   (   C1   )                o como:                     IF   (   C1   )

{                                                                     {

IF   (   C2   )                                       IF   (   C2   )

S1                                                              S1

}                                                                     ELSE

ELSE                                                        S2

S2                                                       }

 

donde la segunda interpretación es la que consideran la mayoría de los lenguajes de programación que incluyen esta construcción; cada ELSE se asocia con el último IF sin ELSE precedente. En este ejemplo, consideremos la situación cuando el parser ha visto:

IF   (   C1   )   IF   (   C2   )   S1

 

y está viendo el ELSE. Puede reducir inmediatamente por la regla if simple para obtener:

IF   (   C1   )   sent

y luego leer la entrada restante

ELSE   S2

y reducir:

IF   (   C1   )   sent   ELSE   S2

por la regla if-else. Esto conduce a la primera de las interpretaciones anteriores.

De otro modo, su puede hacer un shift del ELSE y entonces leer S2; entonces la porción de la derecha de:

IF   (   C1   )   IF   (   C2   )   S1   ELSE   S2

puede ser reducida por la regla if-else para obtener:

IF   (   C1   )   sent

que pude ser reducido por la regla if simple, conduciendo a la segunda de las interpretaciones anteriores, que es la deseada usualmente.

Nuevamente, el parser puede ejecutar dos acciones válidas; hay un conflicto shift-reduce. La aplicación de la regla 1 de desambiguación, en este caso, le dice al parser que ejecute el shift, que lleva a la interpretación deseada.

Este conflicto shift-reduce surge sólo cuando hay un símbolo de entrada particular, ELSE, y en la entrada se ha visto una combinación particular, como:

IF   (   C1   )   IF   (   C2   )   S1

En general, puede haber muchos conflictos, y cada uno se asociará con un símbolo de entrada y un conjunto de entradas leídas previamente. Estas son caracterizadas por el estado del parser.

Los mensajes de conflicto de yacc son entendidos mejor examinando el archivo de salida generado con la opción -v. Por ejemplo, la salida correspondiente al estado de conflicto anterior podría ser:

 

23:  shift-reduce conflict (shift 45, reduce 18) on ELSE

 

state 23

 

sent   :   IF   (   cond   )   sent_         (18)

sent   :   IF   (   cond   )   sent_ELSE   sent

 

ELSE   shift  45

.           reduce  18

 

donde la primera línea describe el conflicto; dando el estado y el símbolo de entrada. La descripción normal del estado da las reglas gramaticales activas en el estado y las acciones del parser. El símbolo _ marca la porción de las reglas que ya se ha visto. Así, en el ejemplo, en el estado 23, el parser ha visto la entrada correspondiente a:

IF   (   cond   )   sent

y las dos reglas gramaticales que aparecen están activas en ese momento. El parser puede hacer dos cosas. Si el símbolo de entrada es ELSE, es posible hacer un shift al estado 45. El estado 45 tendrá, como parte de su descripción, la línea:

sent   :   IF   (   cond   )   sent   ELSE_sent

porque el ELSE habrá producido un shift a este estado. En el estado 23, la acción alternativa, indicada con un punto, tiene que ser ejecutada si el símbolo de entrada no se menciona explícitamente en las acciones. En este caso, si el símbolo de entrada no es ELSE, el parser reduce a:

sent     :   IF   ´(´   cond   ´)´   sent

por la regla gramatical 18.

Nuevamente, notar que los números que siguen a los comandos shift se refieren a otros estados, mientras que los números que siguen a comandos reduce se refieren a reglas. En el archivo y.output, los números de regla aparecen entre paréntesis después de aquellas reglas que pueden ser reducidas. En la mayoría de los estados, una acción reduce es posible en el estado, y este es el comando por defecto. El usuario que encuentra conflictos shift-reduce inesperados probablemente deseará el archivo y.output para decidir si las acciones por defecto son las adecuadas.

 

Precedencia

 

Hay una situación común donde las reglas dadas anteriormente para resolver conflictos no son suficientes. Esto es en el parsing de expresiones aritméticas. La mayoría de las construcciones comúnmente usadas para expresiones aritméticas pueden ser naturalmente descriptas por la noción de niveles de precedencia para los operadores, junto con información acerca de la asociatividad a izquierda o derecha. Esto hace que gramáticas ambiguas con reglas de desambiguación apropiadas puedan ser usadas  para crear parser que son más rápidos y más fáciles de escribir que aquellos construidos desde gramáticas no ambiguas. La noción básica es escribir reglas de la forma:

expr    :   expr   OP   expr

y:

expr    :   UNARY   expr

para todos los operadores binarios y unarios. Esto crea una gramática muy ambigua con muchos conflictos de parsing. Para evitar ambigüedad, el usuario especifica la precedencia de todos los operadores y la asociatividad de los operadores binarios. Esta información es suficiente para permitir a yacc resolver los conflictos de parsing de acuerdo con estas reglas, y construir un parser que tenga en cuenta las precedencias y asociatividades.

Las precedencias y asociatividades se conectan a los tokens en la sección de declaraciones. Esto se hace con una serie de líneas, comenzando con una palabra clave yacc: %left, %right, o %nonassoc, seguidas por una lista de tokens. Todos los tokens en la misma líneas se considera que tienen el mismo nivel de precedencia y asociatividad; las líneas se listan en orden de precedencia creciente. Así:

 

%left   ´+´   ´-´

%left   ´*´   ´/´

 

describe la precedencia y asociatividad de los cuatro operadores aritméticos. Más y menos son asociativos a izquierda y tienen menor precedencia que multiplicación y división, que son también asociativos a izquierda. La palabra clave %right es usada para describir operadores asociativos a derecha, y la palabra clave %nonassoc es usada para describir operadores, como .LT. en FORTRAN, que no pueden asociarse con ellos mismos.

Como un ejemplo del comportamiento de estas declaraciones, la descripción:

 

%right   ´=´

%left   ´+´   ´-´

%left   ´*´   ´/´

 

%%

 

expr    :   expr   ´=´   expr

|   expr   ´+´   expr

|   expr   ´-´   expr

|   expr   ´*´   expr

|   expr   ´/´   expr

|   NAME

;

 

podría usarse para estructurar la siguiente entrada:

a   =   b   =   c*d   -   e   -   f*g

como sigue:

a   =   (   b   =   (   ( (c*d)  -   e)   -   (f*g)   )   )

para lograr la precedencia correcta de los operadores. Cuando se usa este mecanismo, se debe dar en general, a los operadores unarios, una precedencia. A veces un operador binario y un operador unario tienen la misma representación simbólica pero distinta precedencia. Un ejemplo es el menos unario y el menos binario (-).

Al menos unario se le debe dar la misma precedencia que a la multiplicación, o aún más alta, mientras que el menos binario tiene una precedencia más baja que la multiplicación. la palabra clave %prec cambia el nivel de precedencia asociado con una regla particular. La palabra clave %prec aparece inmediatamente después del cuerpo de la regla, antes de la acción o punto y coma de cierre, y es seguido por un nombre de token o literal. Esto hace que la precedencia de la regla se haga igual a la del nombre de token o literal que se indica.

Por ejemplo, las reglas:

 

%left   ´+´   ´-´

%left   ´*´   ´/´

 

%%

 

expr    :   expr   ´+´   expr

|   expr   ´-´   expr

|   expr   ´*´   expr

|   expr   ´/´   expr

|   ´-´   expr   %prec   ´*´

|   NAME

;

 

podrían ser usadas para dar al menos unario la misma precedencia que la multiplicación.

Un token declarado por %left, %right, y %nonassoc no necesitan ser declaradas por %token.

Las precedencias y asociatividades son usadas por yacc para resolver conflictos de parsing. Esto dan lugar a las siguientes reglas de desambiguación:

1.                  Se registran las precedencias y asociatividades para aquellos tokens y literales que las tengan

2.                  Una precedencia y asociatividad es asociada con cada regla de la gramática. Esta será la precedencia y asociatividad del último token o literal en el cuerpo de la regla. Si se usa la construcción %prec, esto sobreescribe el defecto. Algunas reglas de la gramática pueden no tener precedencia y asociatividad asociadas con ellas.

3.                  Cuando hay un conflicto reduce-reduce o un conflicto shift-reduce y, ni el símbolo de entrada ni la regla tienen precedencia y asociatividad, entonces se usan las dos reglas de desambiguación descriptas anteriormente, y los conflictos son reportados.

4.                  Si hay un conflicto shift-reduce, y tanto la regla de la gramática como el carácter de entrada tienen precedencia y asociatividad asociadas con ellos, el conflicto se resuelve en favor de la acción (shift o reduce) asociada con la precedencia más alta. Si las precedencias son iguales, se usa la asociatividad. La asociatividad a izquierda implica reduce; la asociatividad a derecha implica shift; la no asociatividad implica error.

 

Los conflictos que se resuelven por precedencia no se cuentan en el número de conflictos shift-reduce y reduce-reduce reportados por yacc. Esto significa que errores en la especificación de la precedencia puede disimular errores en la gramática. El archivo y.output es muy útil para decidir si el parser está haciendo realmente lo que se desea.cción a los generadores Lex y Yacc

Generalidades


Un generador de analizadores es un programa que acepta como entrada la especificación de las ca­racterísticas de un lenguaje L y produce como salida un analizador para L. La especificación de en­trada puede referirse a la lexicografía, la sintaxis o la semántica; el analizador resultante servirá para analizar las características especificadas.

E   Especificación de las características del lenguaje L

A   Analizador para L

Los generadores Lex y Yacc sirven, respectivamente, para generar analizadores lexicográficos y analizadores sintácticos para su aprovechamiento como partes de los compiladores de los lenguajes de programación; estos usos de Lex y Yacc no son los únicos, aunque sí son los que aquí se consi­deran principalmente.

Para entender cabalmente el funcionamiento de los generadores de analizadores, hay que co­nocer la teoría de compiladores relacionada con las tareas de análisis de lenguajes.

Cuando se emplea el término Lex, se mencionan dos posibles significados:

a) una notación para especificar las características lexicográficas de un lenguaje de programación,

b) un traductor de especificaciones lexicográficas.

Esta misma dualidad también es de aplicación al término Yacc.

Esquema de uso

El esquema de la página siguiente ilustra la manera de usar los generadores Lex y Yacc para obte­ner un analizador léxico-sintáctico de un lenguaje de programación L, y de ejecutar el analizador ob­tenido. Los nombres que aparecen en el esquema significan:

eLexic.l
es la especificación de las características lexicográficas del lenguaje L, escrita en Lex

eSint.y
es la especificación de las características sintácticas del lenguaje L, escrita en Yacc

lex.yy.c
es el analizador lexicográfico de L generado por Lex; está constituido, en su parte principal, por una función escrita en C que realiza las tareas de análisis lexicográfico basándose en autómatas re­gulares reconocedores de la forma de las piezas sintácticas de L

libl
es una librería asociada a Lex que contiene estructuras de datos y funciones a las que se puede hacer referencia desde el código generado

liby
es una librería asociada a Yacc con la misma utilidad que la anterior

y.tab.c
es el analizador sintáctico generado por Yacc; está constituido, en su parte principal, por una función escrita en C que realiza las tareas de análisis sintáctico según el método ascendente LALR(1), basado en tablas

anLeSi
es el analizador generado; analiza las características lexicográficas y sintácticas especificadas del lenguaje L; acepta como entrada un programa escrito en L y comprueba si está codificado según las especificaciones dadas


P
programa escrito en el lenguaje L

No es preciso que los nombres de los ficheros de entrada para Lex y Yacc  tengan una extensión de­terminada; los nombres de los ficheros generados por Lex y Yacc son siempre los indicados, con independencia de cuál sea el nombre de los ficheros de entrada.

 

 

Obtención y ejecución del analizador

El analizador léxico-sintáctico se obtiene tras la realización de los siguientes pasos:

1)   vi eLexic.l
              edición del fichero con las características lexicográficas

2)   vi eSint.y
              edición del fichero con las características sintácticas

3)   lex eLexic.l
              traducción de las características lexicográficas

4)   yacc eSint.y
              traducción de las características sintácticas

5)   cc lex.yy.c  y.tab.c  –ll  –ly  –o  anLeSi
              compilación del código de los analizadores generados

(El orden de pasos citado es una posibilidad, no una necesidad; se ha supuesto el uso del editor vi).

Los ficheros sobre los que actúa el analizador léxico-sintáctico generado son (salvo que de manera explícita se indique otra cosa) los pre-definidos de entrada y de salida; así pues, la ejecución del ana­lizador obtenido puede hacerse de una las siguientes formas:

anLeSi

anLeSi <Entrada

anLeSi <Entrada >Salida

según que se haga o no re-direccionamiento de los ficheros de entrada y de salida pre-definidos.

En el fichero de entrada se proporciona un programa escrito en L. La salida, que debe de informar sobre el resultado del análisis, puede ser más o menos elaborada; por ahora se considera la posibili­dad más sencilla. Si el programa analizado es correcto en lo que respecta al léxico y a la sintaxis, no se emite indicación alguna; si el programa no es correcto porque tiene algún error lexicográfico o sintáctico, se emite el mensaje syntax error (más adelante se justificará la razón por la que se emite este mensaje, tanto si se trata de un error lexicográfico como si es uno sintáctico).

Ejemplo 1

Con este ejemplo inicial se muestra, antes de empezar el estudio detallado, una aplicación de los ge­neradores Lex y Yacc para obtener un analizador léxico-sintáctico de un lenguaje simple. Se pro­porciona la solución sin explicación alguna; lo único que se pretende ahora es obtener automática­mente un analizador, y probar su funcionamiento.

Se trata de una clase sencilla de expresiones aritméticas en las que pueden encontrarse:

- variables (nombres escritos en minúsculas, de cualquier longitud),

- constantes (números con cifras decimales de cualquier longitud),

- operadores ( +, *),

- paréntesis.

La sintaxis de las expresiones se define mediante la siguiente gramática (escrita en notación BNF-Ampliada):

<Expresion> ::= <Termino> { +  <Termino> }

<Termino>   ::= <Factor> { *  <Factor> }

<Factor>    ::= ( <Expresion> )

|  id

|  cte

La entrada a Lex (la especificación lexicográfica), si se emplean los nombres pId, pCte, pSum, pMul, pAbr y pCer para representar las distintas piezas sintácticas del lenguaje, es:

│%{

│#define pId  1

│#define pCte 2

│#define pSum 3

│#define pMul 4

│#define pAbr 5

│#define pCer 6

│#define Error  999

│%}

│%%

│[a-z]+     { return pId;   }

│[0-9]+     { return pCte;  }

│"+"        { return pSum;  }

│"*"        { return pMul;  }

│"("        { return pAbr;  }

│")"        { return pCer;  }

│[\ \t\n]   { ;             }

│.          { return Error; }

La entrada a Yacc (la especificación sintáctica) es, considerada a partir de una gramática equivalente a la dada, pero escrita en notación BNF-No ampliada, es:

│%token pId  1

│%token pCte 2

│%token pSum 3

│%token pMul 4

│%token pAbr 5

│%token pCer 6

│%start Expresion

│%%

│Expresion : Termino RestoExpr ;

│RestoExpr : pSum Termino RestoExpr ;

│          |  ;

│Termino : Factor RestoTerm ;

│RestoTerm : pMul Factor RestoTerm ;

│          |  ;

│Factor : pId ;

│       | pCte ;

│       | pAbr Expresion pCer ;

│%%

│main () {

│  yyparse ();

│}

La raya vertical puesta a la izquierda de las dos especificaciones representa la posición de la primera columna de las líneas de los ficheros de tipo texto.

Si el analizador obtenido se aplica a la entrada (x + y) * cota, que es una expresión correcta, no se obtiene mensaje alguno como resultado del análisis; si se aplica a la entrada x+y*+z, que es una expresión incorrecta, se obtiene como salida la indicación syntax error; si se aplica a la en­trada x + y? – z, que contiene un carácter que no pertenece al alfabeto (error lexicográfico), tam­bién se obtiene el resultado syntax error.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

CONCLUSION

 

Lex es una herramienta para generar escáneres: programas que reconocen patrones léxicos en un texto. Lex 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. lex genera como salida un fichero fuente en C, `lex y yacc, que define una rutina `yylex()'. Este fichero se compila y se enlaza con la librería `-lfl' 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.

Lenguaje Yacc

Es un generador de analisis de propósito general que convierte una descripción de gramatica para una gramática de libre-contexto LALR en un programa en lenguaje C para analizar esa gramática.
Yacc lee la especificación de la gramática del archivo "filename" y genera un LR(1) analizador para el. Los analizadores consisten en un set de LALR(1) tablas de analisis y una rutina controladora escrita en el lenguale de programación C. Yacc normalmente escribe las tablas de analisis y la rutina controladora al archivo y.tab.c.
El programa Yacc ha ido siendo reemplazado por Bison.

 

 

Si se quiere usar el lex con el yacc, téngase en cuenta que el lex escribe

un programa llamado yylex( ), el nombre requerido por el yacc para su

analizador. Normalmente el programa main por defecto de la librería lex llama a

esta rutina, pero si yacc está cargado, y se usa su programa main, yacc llamará al

yylex( ). En este caso, cada orden lex deberá terminar con

return (token); donde se devuelve el valor de token apropiado. Una forma fácil de obtener acceso a los nombres del yacc para los tokens es compilar el fichero de output del lex como parte del fichero de output del yacc poniendo la línea

#include “lex.yy.c” en la última sección del input del yacc.