| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III Introducción 3.1 Token y Lexemas 3.2 Algoritmo de los dos Buffers 3.3 Expresiones regulares

3.4 Definición y ejemplos de AFN

3.5 Definición y ejemplos de AFD

3.6 Construcción de un AFN a partir de una expresión regular

3.7 Conversión de un AFN a AFD (Construcción de subconjuntos)

3.8 Lenguaje LEX

3.9 Escritura de Programas LEX

UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

3.9 Escrituras de Programas LEX

> Formato fuente del lex

> El formato general de la fuente lex es:

> {definiciones}
> %%
> {instrucciones}
> %%
> {subrutinas del usuario}

> donde las definiciones y las subrutinas del usuarios se omiten a menudo, el segundo %% es opcional, pero el primero se requiere para marcar el principio de las instrucciones. El programa lex mínimo absoluto es por lo tanto:

> %% (sin definiciones, ni instrucciones) lo cual se traduce en un programa que copia la entrada en la salida sin variar.

> En el formato del programa lex que se mostró anteriormente, las instrucciones representan las decisiones de control del usuario, estas forman una tabla en la cual la columna izquierda contiene expresiones regulares y la columna derecha contiene decisiones, fragmentos de programas que se ejecutarán cuando se reconozcan las expresiones. Por lo tanto la siguiente orden individual puede aparecer:

> integer printf(“ localizada palabra reservada INT ”);

> Esto busca el literal “integer” en la entrada e imprime el mensaje: “Localizada palabra reservada INT”, siempre que aparezca en el texto de entrada, en este ejemplo la función de librería printf() se usa para imprimir la cadena de caracteres o literal. El final de la expresión regular lex se indica por medio del primer carácter espacio en blanco o tabulador. Si la acción es simplemente una sola expresión C, se puede especificar en el lado derecho de la línea; si es compuesta u ocupa más de una línea, deberá incluirse entre llaves.

> Como ejemplo, suponga que se desea cambiar un número de palabras de la ortografía Británica a la Americana. Las instrucciones de lex son tales como:

> colour printf (“color”);
> mechanise printf (“mechanize”);
> petrol printf (“gas”);

> Será una forma de empezar. Estas instrucciones no son suficientes, puesto que la palabra petroleum se convertirá en gaseum.

> 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, los cuales 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, lo cual 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 instrucción. 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.

> Llamar al lex

> Hay dos pasos al compilar un programa fuente lex, primero, el programa lex fuente tiene que ser convertido en un programa regenerado en el lenguaje de propósito general, entonces éste programa tiene que ser compilado y cargado, normalmente con una librería de subrutinas lex. El programa generado está en un archivo llamado lex.yy., la librería I/O está definida en términos de la librería estándar C.

> A la librería se accede por medio del flag de la carga –ll, por lo tanto un conjunto de comandos apropiados es:

> lex source
> cc lex.yy.c –ll

> El programa resultante se pone en el archivo usual a.out para ser ejecutado posteriormente. “Yacc: el Compilador-Compilador”, Aunque las rutinas I/O por defecto del lex usan la librería estándar C, el autómata del lex no lo hace. Si se especifican las versiones privadas de input, output, y unput, la librería se puede evitar.

> Especificación de clases de caracteres.

> Las clases de caracteres se pueden especificar usando corchetes: [y]. La construcción [abc], la cual 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, de aquí que 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 de la computadora. 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.

> Especificación de un carácter arbitrario

> Para hacer coincidir casi con cualquier carácter, el punto (.) designa la clase de todos los caracteres excepto un carácter newline. Realizar el proceso de escape en octal es posible, aunque no es portable. Por ejemplo:

> [ \ 40 - \ 176 ]

> La expresión anterior coincide con todos los caracteres imprimibles del conjunto de caracteres ASCII, desde el octal 40 (espacio en blanco) hasta el octal 176 (la tilde).

> 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 el 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-Z, a-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, ya que 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, en donde, 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). No se debe confundir con el otro significado del signo ^, que significa 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 pesos, 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.

> El contexto de la izquierda se maneja en el lex especificando las condiciones start según se explica en la sección “Especificación de sensibilidad de contexto izquierdo“, si una orden sólo se va a ejecutar cuando el intérprete del autómata del lex está en la condición x start, la orden se deberá incluir entre corchetes de ángulos:

> <x>

> Si consideramos que estamos al comienzo de una línea que es el comienzo de la condición ONE, entonces el operador (^) será equivalente a <ONE>.

> 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 la entrada en la salida, esto se lleva a cabo en todos los literales que de otro modo no coincidirían.

> Por lo tanto el usuario de lex que desee absorber la entrada completa, sin producir ninguna salida, debe proporcionar instrucciones 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 la entrada en la salida; por lo tanto, en general, una instrucción que simplemente copia se puede omitir.

> Una de las cosas más simples que se pueden hacer es ignorar la entrada.

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

> La instrucción 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, eñ ejemplo anterior 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 ] +

> Lex deja este texto en una matriz de caracteres externos llamada yytext. Por lo tanto, para imprimir el nombre localizado, una instrucción 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 printf 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 la salida. 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?, la respuesta a esta pregunta enfatiza que tales órdenes se requieren a menudo para evitar la coincidencia con algunas otras instrucciones que no se desean. Por ejemplo, si hay una instrucción que coincide con “read”, ésta normalmente coincidirá con las apariciones de “read” contenidas en “bread” o en “readjust”; para evitar esto, una instrucción 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 instrucción no ha reconocido el alcance correcto de los caracteres, para resolver esta situación hay dos rutinas, la primera, yymore( ) se puede llamar para indicar que la siguiente expresión de entrada reconocida se va a añadir al final de esta entrada. Normalmente, el siguiente literal de entrada 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, donde el argumento n indica el número de caracteres de yytext que se van a retener. Otros caracteres que han coincidido previamente se devuelven a la entrada, 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, este 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 considerará 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 del lenguaje C antigua, referente a 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 anterior se puede expresar como:

> =- [ 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 caso, 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 instrucción aún mejor. Además de estas rutinas, el lex también permite acceso a las rutinas de I/O que usa, las cuales 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().

> Por defecto, estas rutinas se proporcionan como definiciones de macro, pero el usuario puede contrarrestarlas y proporcionar versiones privadas. Estas rutinas definen la relación entre los archivos externos y los caracteres internos, y todas se deben retener o modificar consistentemente. Estas se pueden redefinir, para hacer que la entrada o la salida sea transmitido a o de 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 archivo, y la relación entre salida o entrada debe ser retenido o no funcionará el “loockahead”. Lex no ve 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, para analizar esto, hay que ver a continuación una explicación del conjunto de caracteres que usa el lex. 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 archivo. 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 la entrada 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 archivo; el único acceso a esta condición es a través de yywrap(). De hecho, a no ser que se proporcione una versión privada de input() no se puede manejar un archivo que contenga datos nulos, puesto que el valor 0 que input() devuelve se toma como el final de archivo.

Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello