A.2.1 Descripción del problema

En la tarea del tratamientos de lenguajes, se reserva al analizador léxico un papel muy importante, pues será el encargado de reconocer las palabras que posteriormente serán pasadas a los analizadores sintáctico y semántico.

En el análisis de los lenguajes de programación, que es el entorno más común en el cual se hace uso de los analizadores léxicos, cada palabra del lenguaje se corresponde únivocamente con un sólo componente léxico posible. Por ejemplo, en un lenguaje como el Pascal la palabra clave IF se hace corresponder con un único componente léxico. Entre cada palabra clave del lenguaje y cada componente léxico existe un relación biyectiva. Lo mismo puede decirse del resto de los lenguajes de programación.

Sin embargo, en el contexto del procesamiento de lenguajes naturales, una misma palabra puede corresponderse con varios componentes léxicos distintos. Esto quiere decir que para un componente léxico dado, su materialización en el texto, la cadena de caracteres que se debe escribir para que sea reconocido como tal componente léxico, no es exclusiva, sino que pueden existir otros componentes léxicos cuyo texto coincide con el dado. Un ejemplo en castellano lo tenemos en la palabra casa, que puede ser reconocida como dos formas verbales distintas o como un sustantivo.

Para solucionar este problema, el analizador léxico debe mostrar un comportamiento no determinista, esto es, debe dar todos los posibles reconocimientos para una palabra dada y no debe pasar a reconocer un nuevo componente léxico hasta que no se han agotado todas las posibilidades para el componente léxico precedente. Sólo de esta manera se puede asegurar que el posterior análisis sintáctico y semántico será capaz de analizar correctamento el texto, seleccionando de entre todas las opciones a nivel léxico, aquellas que concuerdan con el resto de la estructura sintáctica del texto.

Otra diferencia con respecto a los lenguajes de programación está en la forma en que se reconocen los componentes léxicos. En éstos últimos cada palabra clave o identificador tiene una única forma escrita, sin variaciones, y su número es limitado. Sin embargo, en una lengua como el castellano existen decenas de miles de lemas, que se corresponden con las entradas en el diccionario. Cada lema se corresponde con lo que podríamos llamar la forma canónica de un conjunto de palabras. Por ejemplo, el lema de un sustantivo lo constituye la forma masculina singular. Las demás formas (el femenino y los plurales en masculino y singular) pueden ser derivadas a partir de la forma canónica utilizando las reglas léxicas correspondientes al tipo de sustantivo de que se trate. En el caso de los verbos la utilización de reglas léxicas es mucho más acusada. En los verbos regulares, nos basta con conocer la forma del infinitivo para poder conjugar todos los posibles tiempos verbales. Los verbos irregulares no son totalmente irregulares, sino que pueden ser agrupados en una serie de grupos verbales (en torno a la treintena) que siguen sus propias reglas léxicas, aunque puede ser preciso utilizar más de una raiz para su conjugación.

Una forma de solucionar los problemas planteados consiste en utilizar una inmensa base de datos en la cual estén almacenadas todas las formas de todas las palabras. Cada vez que se tenga que reconocer una palabra, se accede a esta base de datos y se recuperan todas las posibles alternativas. Este enfoque presenta serios inconvenientes:

• El tamaño desproporcionado que debería tener la base de datos para ser capaz de obtener buenos resultados con textos grandes, obliga a que resida en almacenamiento secundario. La necesidad de acceder continuamente al disco degrada mucho el rendimiento del sistema.
• Cada vez que se encuentre una nueva palabra, se deben introducir todas las formas derivadas de su lema, si queremos que la base de datos sea consistente. Por ejemplo, para cada verbo es necesario introducir entera toda su conjugación. Se puede evitar la entrada manual mediante un generador de formas derivadas, pero aún así se tiene el problema del crecimiento exponencial del tamaño de la base de datos con respecto al número de lemas, lo que degrada el rendimiento ya que introduce retardos en el tiempo de acceso, siempre considerando que se posee una buena estructura de índices.
• No hace uso del conocimiento, expresado en forma de reglas léxicas, que se posee del léxico.

Para evitar esos inconvenientes hemos considerado que la mejor solución es utilizar un generador de analizadores léxicos en el que se puedan incorporar las reglas léxicas y el comportamiento no determinista. El resultado es un programa ejecutable que se encarga de realizar las labores de análisis léxico en un tiempo muy pequeño y con un bajo consumo de memoria.

Se ha optado por utilizar el generador de analizadores léxicos llamado Flex [Paxon 94]. Esta herramienta es un derivado de Lex, el generador de analizadores léxicos estándar incluido en el sistema operativo Unix. Flex presenta como ventajas sobre Lex una mayor velocidad y una mayor flexibilidad, conservando la compatibilidad. Cualquier programa escrito en Lex funcionará sin problemas con Flex. Sin embargo, un programa escrito para Flex que haga uso de las características ampliadas de éste, no podrá ser compilado con Lex, como resulta evidente.