ANÁLISIS LÉXICO

LÉXICO

ANÁLISIS

AUTÓMATAS Y LENGUAJES FORMALES

análizador léxico

¿QUE ES?

la principal tarea del analizador léxico es leer los caracteres de la entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens para cada lexema en el programa fuente. El flujo de tokens se envía al analizador sintáctico para su análisis. Con frecuencia el analizador léxico interactúa también con la tabla de símbolos. Cuando el analizador léxico descubre un lexema que constituye a un identificador, debe introducir ese lexema en la tabla de símbolos. En algunos casos, el analizador léxico puede leer la información relacionada con el tipo de información de la tabla de símbolos, como ayuda para determinar el token apropiado que debe pasar al analizador sintáctico.

Siguiente

análisis léxico y análisis sintáctico

COMPARACIÓN

Existen varias razones por las cuales la parte correspondiente al análisis de un compilador se separa en fases de análisis léxico y análisis sintáctico (parsing).1. La sencillez en el diseño es la consideración más importante. La separación del análisis léxico y el análisis sintáctico a menudo nos permite simplificar por lo menos una de estas tareas. 2. Se mejora la eficiencia del compilador. Un analizador léxico separado nos permite aplicar técnicas especializadas que sirven sólo para la tarea léxica, no para el trabajo del análisis sintáctico. Además, las técnicas de búfer especializadas para leer caracteres de entrada pueden agilizar la velocidad del compilador en forma considerable. 3. Mejora la portabilidad del compilador. Las peculiaridades específicas de los dispositivos de entrada pueden restringirse al analizador léxico.

Tokens, patrones y lexemas

• Un token es un par que consiste en un nombre de token y un valor de atributo opcional. El nombre del token es un símbolo abstracto que representa un tipo de unidad léxica; por ejemplo, una palabra clave específica o una secuencia de caracteres de entrada que denotan un identificador. Los nombres de los tokens son los símbolos de entrada que procesa el analizador sintáctico. A partir de este momento, en general escribiremos el nombre de un token en negrita. Con frecuencia nos referiremos a un token por su nombre. • Un patrón es una descripción de la forma que pueden tomar los lexemas de un token. En el caso de una palabra clave como token, el patrón es sólo la secuencia de caracteres que forman la palabra clave. Para los identificadores y algunos otros tokens, el patrón es una estructura más compleja que se relaciona mediante muchas cadenas. • Un lexema es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de ese token.

EJEMPLO

El ejemplo de abajo proporciona algunos tokens comunes, sus patrones descritos de manera informal y algunos lexemas de ejemplo. La siguiente instrucción en C nos servirá para ver cómo se utilizan estos conceptos en la práctica:

printf("Total = %d\n", puntuacion);

Tanto printf como puntuacion son lexemas que coinciden con el patrón para el token id, y "Total = %d\n" es un lexema que coincide con literal. En muchos lenguajes de programación, las siguientes clases cubren la mayoría, si no es que todos, los tokens:

Siguiente

ATRIBUTOS PARA LOS TOKENS

TERMINACIÓN

Cuando más de un lexema puede coincidir con un patrón, el analizador léxico debe proporcionar a las subsiguientes fases del compilador información adicional sobre el lexema específico que coincidió. Por ejemplo, el patrón para el token numero coincide con 0 y con 1, pero es en extremo importante para el generador de código saber qué lexema se encontró en el programa fuente. Por ende, en muchos casos el analizador léxico devuelve al analizador sintáctico no sólo el nombre de un token, sino un valor de atributo que describe al lexema que representa ese token; el nombre del token influye en las decisiones del análisis sintáctico, mientras que el valor del atributo influye en la traducción de los tokens después del análisis sintáctico.

Siguiente

Problemas difíciles durante el reconocimiento de tokens

Por lo general, dado el patrón que describe a los lexemas de un token, es muy sencillo reconocer los lexemas que coinciden cuando ocurren en la entrada. No obstante, en algunos lenguajes no es tan evidente cuando hemos visto una instancia de un lexema que corresponde a un token. El siguiente ejemplo se tomó de Fortran, en el formato fijo todavía permitido en Fortran 90. En la siguiente instrucción:

DO 5 I = 1.25

no es evidente que el primer lexema es DO5I, una instancia del token identificador, hasta que vemos el punto que va después del 1. Observe que los espacios en blanco en el lenguaje Fortran de formato fijo se ignoran (una convención arcaica). Si hubiéramos visto una coma en vez del punto, tendríamos una instrucción do:

DO 5 I = 1,25

Siguiente

en donde el primer lexema es la palabra clave DO.

ERRORES LÉXICOS

Sin la ayuda de los demás componentes es difícil para un analizador léxico saber que hay un error en el código fuente. Por ejemplo, si la cadena fi se encuentra por primera vez en un programa en C en el siguiente contexto:

fi ( a == f(x)) ...

un analizador léxico no puede saber si fi es una palabra clave if mal escrita, o un identificador de una función no declarada. Como fi es un lexema válido para el token id, el analizador léxico debe regresar el token id al analizador sintáctico y dejar que alguna otra fase del compilador (quizá el analizador sintáctico en este caso) mande un error debido a la transposición de las letras.

Otras de las posibles acciones de recuperación de errores son: 1. Eliminar un carácter del resto de la entrada. 2. Insertar un carácter faltante en el resto de la entrada. 3. Sustituir un carácter por otro. 4. Transponer dos caracteres adyacentes.

Siguiente

Uso de búfer en la entrada

Antes de hablar sobre el problema de reconocer lexemas en la entrada, vamos a examinar algunas formas en las que puede agilizarse la simple pero importante tarea de leer el programa fuente. Esta tarea se dificulta debido a que a menudo tenemos que buscar uno o más caracteres más allá del siguiente lexema para poder estar seguros de que tenemos el lexema correcto.

Pares de búferes

Debido al tiempo requerido para procesar caracteres y al extenso número de caracteres que se deben procesar durante la compilación de un programa fuente extenso, se han desarrollado técnicas especializadas de uso de búferes para reducir la cantidad de sobrecarga requerida en el procesamiento de un solo carácter de entrada. Un esquema importante implica el uso de dos búferes que se recargan en forma alterna, como se sugiere en la página siguiente.

Siguiente

Cada búfer es del mismo tamaño N, y por lo general N es del tamaño de un bloque de disco (es decir, 4 096 bytes). Mediante el uso de un comando de lectura del sistema podemos leer N caracteres y colocarlos en un búfer, en vez de utilizar una llamada al sistema por cada carácter. Si quedan menos de N caracteres en el archivo de entrada, entonces un carácter especial, representado por eof, marca el final del archivo fuente y es distinto a cualquiera de los posibles caracteres del programa fuente.Se mantienen dos apuntadores a la entrada: 1. El apuntador inicioLexema marca el inicio del lexema actual, cuya extensión estamos tratando de determinar. 2. El apuntador avance explora por adelantado hasta encontrar una coincidencia en el patrón; durante el resto del capítulo cubriremos la estrategia exacta mediante la cual se realiza esta determinación.

Siguiente

Centinelas

Si utilizamos el esquema de la sección 3.2.1 en la forma descrita, debemos verificar, cada vez que movemos el apuntador avance, que no nos hayamos salido de uno de los búferes; si esto pasa, entonces también debemos recargar el otro búfer. Así, por cada lectura de caracteres hacemos dos pruebas: una para el final del búfer y la otra para determinar qué carácter se lee (esta última puede ser una bifurcación de varias vías). Podemos combinar la prueba del final del búfer con la prueba del carecer actual si extendemos cada búfer para que contenga un valor centinela al final. El centinela es un carácter especial que no puede formar parte del programa fuente, para lo cual una opción natural es el carácter eof.

Especificación de los tokens

Las expresiones regulares son una notación importante para especificar patrones de lexemas. Aunque no pueden expresar todos los patrones posibles, son muy efectivas para especificar los tipos de patrones que en realidad necesitamos para los tokens.

Cadenas y lenguajes

Un alfabeto es un conjunto finito de símbolos. Algunos ejemplos típicos de símbolos son las letras, los dígitos y los signos de puntuación. El conjunto {0, 1} es el alfabeto binario. ASCII es un ejemplo importante de un alfabeto; se utiliza en muchos sistemas de software.

Siguiente

- Código de lectura por adelantado con centinelas:

switch ( *avance++) { case eof : if (avance está al final del primer búfer ) { recargar el segundo búfer; avance = inicio del segundo búfer; } else if (avance está al final del segundo búfer ) { recargar el primer búfer; avance = inicio del primer búfer; } else /* eof dentro de un búfer marca el final de la entrada */ terminar el análisis léxico; break; Casos para los demás caracteres }

Siguiente

Términos para partes de cadenas

Los siguientes términos relacionados con cadenas son de uso común:1. Un prefijo de la cadena s es cualquier cadena que se obtiene al eliminar cero o más símbolos del final de s. Por ejemplo, ban, banana y son prefijos de banana. 2. Un sufijo de la cadena s es cualquier cadena que se obtiene al eliminar cero o más símbolos del principio de s. Por ejemplo, nana, banana y son sufijos de banana. 3. Una subcadena de s se obtiene al eliminar cualquier prefijo y cualquier sufijo de s. Por ejemplo, banana, nan y son subcadenas de banana. 4. Los prefijos, sufijos y subcadenas propios de una cadena s son esos prefijos, sufijos y subcadenas, respectivamente, de s que no son ni son iguales a la misma s. 5. Una subsecuencia de s es cualquier cadena que se forma mediante la eliminación de cero o más posiciones no necesariamente consecutivas de s. Por ejemplo, baan es una subsecuencia de banana.

Siguiente

Operaciones en los lenguajes

En el análisis léxico, las operaciones más importantes en los lenguajes son la unión, la concatenación y la cerradura, las cuales se definen de manera formal en la figura 3.6. La unión es la operación familiar que se hace con los conjuntos. La concatenación de lenguajes es cuando se concatenan todas las cadenas que se forman al tomar una cadena del primer lenguaje y una cadena del segundo lenguaje, en todas las formas posibles. La cerradura (Kleene) de un lenguaje L, que se denota como L*, es el conjunto de cadenas que se obtienen al concatenar L cero o más veces. Observe que L0, la “concatenación de L cero veces”, se define como {}, y por inducción, Li es Li−1 L. Por último, la cerradura positiva, denotada como L+, es igual que la cerradura de Kleene, pero sin el término L0. Es decir, no estará en L+ a menos que esté en el mismo L.

Expresiones regulaRES

Suponga que deseamos describir el conjunto de identificadores válidos de C. Es casi el mismo lenguaje descrito en el punto (5) anterior; la única diferencia es que se incluye el guión bajo entre las letras. En el ejemplo 3.3, pudimos describir los identificadores proporcionando nombres a los conjuntos de letras y dígitos, y usando los operadores de unión, concatenación y cerradura del lenguaje. Este proceso es tan útil que se ha empezado a utilizar comúnmente una notación conocida como expresiones regulares, para describir a todos los lenguajes que puedan construirse a partir de estos operadores, aplicados a los símbolos de cierto alfabeto.En esta notación, si letra_ se establece de manera que represente a cualquier letra o al guión bajo, y dígito_ se establece de manera que represente a cualquier dígito, entonces podríamos describir el lenguaje de los identificadores de C mediante lo siguiente:

La barra vertical de la expresión anterior significa la unión, los paréntesis se utilizan para agrupar las subexpresiones, el asterisco indica “cero o más ocurrencias de”, y la yuxtaposición de letra_ con el resto de la expresión indica la concatenación.

letra_( letra_ | dígito )*

Las expresiones regulares se construyen en forma recursiva a partir de las expresiones regulares más pequeñas, usando las reglas que describiremos a continuación. Cada expresión regular r denota un lenguaje L(r), el cual también se define en forma recursiva, a partir de los lenguajes denotados por las subexpresiones de r. He aquí las reglas que definen las expresiones regulares sobre cierto alfabeto Σ, y los lenguajes que denotan dichas expresiones.BASE: Hay dos reglas que forman la base: 1. es una expresión regular, y L() es {}; es decir, el lenguaje cuyo único miembro es la cadena vacía. 2. Si a es un símbolo en Σ, entonces a es una expresión regular, y L(a) = {a}, es decir, el lenguaje con una cadena, de longitud uno, con a en su única posición. Tenga en cuenta que por convención usamos cursiva para los símbolos, y negrita para su correspondiente expresión regular.

INDUCCIÓN: Hay cuatro partes que constituyen la inducción, mediante la cual las expresiones regulares más grandes se construyen a partir de las más pequeñas.

Siguiente

Suponga que r y s son expresiones regulares que denotan a los lenguajes L(r) y L(s), respectivamente.1. (r)|(s) es una expresión regular que denota el lenguaje L(r) ∪ L(s). 2. (r)(s) es una expresión regular que denota el lenguaje L(r)L(s). 3. (r)* es una expresión regular que denota a (L(r))*. 4. (r) es una expresión regular que denota a L(r). Esta última regla dice que podemos agregar pares adicionales de paréntesis alrededor de las expresiones, sin cambiar el lenguaje que denotan. Según su definición, las expresiones regulares a menudo contienen pares innecesarios de paréntesis. Tal vez sea necesario eliminar ciertos pares de paréntesis, si adoptamos las siguientes convenciones: a) El operador unario * tiene la precedencia más alta y es asociativo a la izquierda. b) La concatenación tiene la segunda precedencia más alta y es asociativa a la izquierda. c) | tiene la precedencia más baja y es asociativo a la izquierda.

Siguiente

Por ejemplo, bajo estas convenciones podemos sustituir la expresión regular (a)|((b)*(c)) por a|b*c. Ambas expresiones denotan el conjunto de cadenas que son una sola a o cero o más bs seguidas por una c. Ejemplo: Sea Σ = {a, b}. 1. La expresión regular a|b denota el lenguaje {a, b}. 2. (a|b)(a|b) denota a las cadenas {aa,ab, ba, bb}, el lenguaje de todas las cadenas de longitud dos sobre el alfabeto Σ. Otra expresión regular para el mismo lenguaje sería aa|ab|ba|bb.3. a* denota el lenguaje que consiste en todas las cadenas de cero o más as, es decir, {, a, aa, aaa, …}.4. (a|b)* denota el conjunto de todas las cadenas que consisten en cero o más instancias de a o b, es decir, todas las cadenas de as y bs: {,a, b,aa,ab, ba, bb,aaa, …}. Otra expresión regular para el mismo lenguaje es (a*b*)*.5. a|a*b denota el lenguaje {a, b,ab,aab,aaab, …}, es decir, la cadena a y todas las cadenas que consisten en cero o más as y que terminan en b.

Siguiente

Leyes algebraicas para expresiones regulares

A un lenguaje que puede definirse mediante una expresión regular se le llama conjunto regular. Si dos expresiones regulares r y a denotan el mismo conjunto regular, decimos que son equivalentes y escribimos entonces r = s. Por ejemplo, (a|b) = (b|a). Hay una variedad de leyes algebraicas para las expresiones regulares; cada ley afirma que las expresiones de dos formas distintas son equivalentes. La ilustración de abajo muestra parte de las leyes algebraicas para las expresiones regulares arbitrarias r, s y t.

Expresiones regulaRES

Por conveniencia de notación, tal vez sea conveniente poner nombres a ciertas expresiones regulares, y utilizarlos en las expresiones subsiguientes, como si los nombres fueran símbolos por sí mismos. Si Σ es un alfabeto de símbolos básicos, entonces una definición regular es una secuencia de definiciones de la forma:

d1 → r1d2 → r2 ··· dn → rn

en donde: 1. Cada di es un nuevo símbolo, que no está en Σ y no es el mismo que cualquier otro d. 2. Cada ri es una expresión regular sobre el alfabeto Σ ∪ {d1, d2, …, di−1}.

Al restringir ri a Σ y a las ds definidas con anterioridad, evitamos las definiciones recursivas y podemos construir una expresión regular sobre Σ solamente, para cada ri. Para ello, primero sustituimos los usos de d1 en r2 (que no puede usar ninguna de las ds, excepto d1), después sustituimos los usos de d1 y d2 en r3 por r1 y (la sustitución de) r2, y así en lo sucesivo. Por último, en rn sustituimos cada di, para i = 1, 2, …, n − 1, por la versión sustituida de ri, cada una de las cuales sólo tiene símbolos de Σ.

Siguiente

Extensiones de las expresiones regulares

Desde que Kleene introdujo las expresiones regulares con los operadores básicos para la unión, la concatenación y la cerradura de Kleene en la década de 1950, se han agregado muchas extensiones a las expresiones regulares para mejorar su habilidad al especificar los patrones de cadenas. Aquí mencionamos algunas extensiones rotacionales que se incorporaron por primera vez en las herramientas de Unix como Lex, que son muy útiles en la especificación de los analizadores léxicos.

1. Una o más instancias. El operador unario postfijo + representa la cerradura positivo de una expresión regular y su lenguaje. Es decir, si r es una expresión regular, entonces (r)+ denota el lenguaje (L(r))+. El operador + tiene la misma precedencia y asociatividad que el operador *. Dos leyes algebraicas útiles, r* = r+| y r+ = rr * = r *r relacionan la cerradura de Kleene y la cerradura positiva. 2. Cero o una instancia. El operador unario postfijo ? significa “cero o una ocurrencia”. Es decir, r? es equivalente a r|, o dicho de otra forma, L(r?) = L(r) ∪ {}. El operador ? tiene la misma precedencia y asociatividad que * y +. 3. Clases de caracteres. Una expresión regular a1|a2|· · ·|an, en donde las ais son cada una símbolos del alfabeto, puede sustituirse mediante la abreviación [a1a2 ···an ]. Lo que es más importante, cuando a1, a2, …, an forman una secuencia lógica, por ejemplo, letras mayúsculas, minúsculas o dígitos consecutivos, podemos sustituirlos por a1-an; es decir, sólo la primera y última separadas por un guión corto. Así, [abc] es la abreviación para a|b|c, y [a-z] lo es para a|b|· · ·|z.