El analizador léxico del lenguaje m2k2

Introducción

En este post vamos a seguir todos los pasos necesarios para diseñar e implementar un intérprete. Un intérprete es un programa que recibe como entrada un programa en un lenguaje determinado y que produce como salida el resultado de su ejecución. El lenguaje aceptado como entrada por el intérprete es el denominado m2k2, definido formalmente en el primer post.

El intérprete de m2k2 se implementará íntegramente con el lenguaje de programación Python. Python es un lenguaje de programación fácil de aprender y potente. Tiene eficaces estructuras de datos de alto nivel (listas, tuplas, cadenas y diccionarios) y una solución de programación orientada a objetos simple pero eficaz. La elegante sintaxis de Python, su gestión de tipos dinámica y su naturaleza interpretada hacen de él el lenguaje ideal para la implementación del intérprete para el lenguaje micro2k2 especificado en el post anterior.

Cuando se leen ordenes desde una tty, se dice que el intérprete está en modo interactivo. El intérprete de m2k2 se presenta al usuario de forma interactiva como una orden directamente ejecutable desde el intérprete de comandos de cualquier sistema Unix/Linux.

    $ m2k2

En este modo, el intérprete espera la siguiente orden con el indicador principal, que suele ser tres signos mayor ('>>>'). El intérprete muestra un mensaje de bienvenida con su número de versión, antes de mostrar el primer indicador, algo similar a esto:

    m2k2 1.4.2 (Mar 5 2002, 15:17:54) on devnull
    Wittylabs, 2015. Castellón, Spain
    >>>

El intérprete de m2k2 no solo puede utilizarse de forma interativa. A su entrada también puede redireccionarse un fichero, o incluso la salida de otro programa, como se muestra en estos ejemplos:

    $ cat programa.2k2 | m2k2
    $ m2k2 < programa.2k2

Entrando ya en materia, el diseño del intérprete se estructura en cuatro partes claramente diferenciadas que a su vez configuran la estructura principal de este documento:

• Análisis léxico
• Análisis sintáctico
• Análisis semántico
• Generación de resultados

En este post se expone el diseño y la implementación del analizador léxico. En los siguientes post hablaremos de los analizadores sintáctico, semántico y de la generación de resultados.

Analisis léxico

Al iniciarse el proceso de interpretación, el código fuente de un programa no es mas que un flujo de caracteres. El analizador léxico lee caracteres del programa de entrada y produce secuencias de simbolos elementales del lenguaje de programación de entrada, conocidos como tokens. Los tokens son posteriormente analizados sintácticamente por el analizador sintáctico. Por consiguiente, el proceso de analisis léxico puede entenderse como la transformación de un flujo de caracteres de entrada en un flujo de tokens de salida. La entrada es filtrada para eliminar aquellos elementos del programa de entrada que son superfluos para realizar el analisis sintáctico. En concreto se eliminan espacios y tabuladores.

Especificación léxica del lenguaje de entrada

La especificación del analizador léxico incluye por cada categoría léxica del lenguaje, su patron, sus atributos y las acciones asociadas. El formalismo de las expresiones regulares tiene la capacidad suficiente para especificar el patron de las categorías léxicas.

Categoría	Expresión regular	Acciones	Atributos
Ident	[a-zA-Z][a-zA-Z0-9_]*	Copiar lexema Comprobar reservada emitir (( tkIdent, | tkTpoEnter | tkTpoReal)	caracter1 lexema
TpoReal	[rR][eE][aA][lL]		caracter1
TpoEnter	[eE][nN][tT][eE][rR]		caracter1
NrEnter	[0-9][0-9]* | #[0-9a-fA-F][0-9a-fA-F]*	Calcular valor Comprobar rango emitir tkNrEnter	caracter1 valor
NrReal	[0-9][0-9]*\.[0-9][0-9]* | [0-9][0-9]*\.[0-9][0-9]*[eE][+-]?[0-9][0-9]*	Calcular valor Comprobar rango emitir tkNrReal	caracter1 valor
AbrPar	\(	emitir tkAbrPar	caracter1
CiePar	\)	emitir tkCiePar	caracter1
PtoPto	\.\.	emitir tkPtoPto	caracter1
Space	[ \t][ \t]*	omitir	caracter1
Coma	,	emitir tkComa	caracter1
EOL	\n	emitir tkEOL	caracter1
Asign	<\-	emitir tkAsign	carácter1
Mas	\+	emitir tkMas	carácter1
Menos	\-	emitir tkMenos	carácter1
Mul	\*	emitir tkMul	carácter1
Div	/	emitir tkDiv	carácter1
PorCien	%	emitir tkPorCien	carácter1
Y	&	emitir tkY	carácter1
O	\|	emitir tkO	carácter1
No	!	emitir tkNo	carácter1
Cmp	=|!=|<>|<|>|<=|>=	copiar lexema emitir tkCmp	carácter1 lexema
OpTorio	\([\+ \- \* / % & \| ]\)	copiar lexema emitir tkOpTorio	carácter1 lexema

Para diferenciar los identificadores de las palabras reservadas enter y real (con todas sus variantes en mayúsculas y en minúsculas), las acciones de la categoría léxica Ident comprueban si el lexema del identificador es una palabra reservada o no lo es. En caso de ser una palabra reservada, se emite el tkTpo adecuado. En caso de no serlo, se emite un tkIdent.

El salto de línea cumple en m2k2 la función de terminador, por lo que no se incluye en la categoría léxica Spc (los blancos). Se le asigna la categoría léxica EOL.

Los operadores de comparación se agrupan en la categoría léxica Cmp. Esto se hace así porque todos los operadores de comparación tienen el mismo nivel de precedencia y la misma aridad (número de argumentos). Por la misma razón, los operadores de operatorio se agrupan en la categoría léxica OpTorio.

Los operadores aritméticos no se agrupan en una sola categoría léxica porque los operadores + y - tienen dos aridades posibles (unaria o binaria), mientras que los operadores * / y % solo tienen una única aridad posible (binaria). En caso de agrupar los cinco operadores en una sola categoría léxica, es imposible diferenciar en el nivel sintáctico los operadores binarios de los operadores unarios. En este supuesto, el analizador sintáctico parsea como correctos los operadores * / y % cuando actúan como operadores unarios. Para evitar este problema, lo mejor es tener categorías léxicas distintas para los operadores aritméticos, y así poder diferenciar en las reglas de la gramática del analizador sintáctico los operadores unarios de los operadores binarios.

Nótese que los operadores aritméticos * / y % si se pueden agrupar en una sola categoría léxica, ya que los tres son operadores binarios. Sin embargo, la categoría léxica resultante de agrupar estos tres operadores aritméticos es poco representativa a nivel conceptual. Por ello finalmente se opta por crear una categoría léxica distinta para cada operador aritmético.

Con los operadores lógicos ocurre algo parecido a los operadores aritméticos. El operador ! es unario, mientras que los operadores & y | son binarios. Por ello no se agrupan los operadores lógicos en una sola categoría léxica. Los operadores & y | si puede agruparse en una sola categoría léxica, ya que los dos son operadores binarios. Sin embargo, la categoría léxica resultante de agrupar estos dos operadores lógicos es poco representativa a nivel conceptual. Por ello finalmente se opta por crear una categoría léxica distinta para cada operador lógico.

Diagrama de la máquina discriminadora determinista

Para dividir la entrada en una serie de tokens se utiliza una maquina discriminadora determinista o MDD en adelante. Se trata de un tipo de automata muy similar a los automatas finitos deterministas, con dos diferencias básicas. Por un lado no reconoce la entrada completa, sino prefijos de la entrada. Por otro lado tiene acciones asociadas a cada uno de los estados finales. El diagrama de la MDD se muestra en la siguiente imagen. En las siguientes secciones veremos los detalles del funcionamiento y de la implementación de esta MDD.

Errores léxicos

Para gestionar los errores léxicos, se implementa la clase LexError en el módulo lexico.py.

    class LexError:
      def __init__( fis, sentence, sentenceNr, chr1, message )
      def __str__( )

El constructor de esta clase recibe como parámetros el nombre del fichero de entrada (fis, file input stream), la línea actual (sentence), el número de la línea actual (sentenceNr), el puntero al carácter de la línea actual que ha provocado el error léxico (chr1) y finalmente un mensaje informativo del error (message). El método __str__ se encarga de combinar los parámetros anteriores para construir el mensaje de error que se imprime por el stderr al imprimir un objeto de esta clase.

El analizador léxico detecta un error cuando lee de la entrada algun carácter que no pertenece al alfabeto del lenguaje (ñ $ ;) o cuando lee una secuencia de caracteres pertenecientes al alfabeto del lenguaje con los cuales no se puede formar ningún token válido en el orden en el que aparecen. En cualquier caso, el analizador léxico lanza una excepción LexError junto con un mensaje de error construido por la clase LexError

    raise LexError, LexError( fis, s, sNr, cPtr, message )

La excepción es capturada en el programa principal, donde el mensaje de error es mostrado por el stderr. Sirvan las dos situaciones siguientes a modo de ejemplo:

    >>> i + 1;
    File “”, line 34
    i + 1;
    ^
    Lexic Error: invalid syntax

    >>> enter _i
    File “”, line 57
    enter _i
    ^
    Lexic Error: invalid syntax

Como se observa, el mensaje de error contiene el nombre del fichero donde se ha detectado el error, la línea donde se ha detectado el error, el número de línea dentro del fichero de entrada, un puntero '^' señalando el carácter inesperado, y un mensaje indicando el error cometido. Después de atender el error léxico y mostrar por el stderr el mensaje informativo del error, se omite todo el procesamiento posterior sobre la línea actual y se continua atendiendo la siguiente línea del stdin.

Un error que también se podría detectar a nivel léxico es el de los desbordamientos de rango, ya que en principio es posible escribir una expresión regular para (por ejemplo) los enteros. En la práctica no es una solución aceptable: la expresión regular resulta demasiado complicada e incluso puede ser dependiente de la arquitectura sobre la que se ejecute el intérprete. La solución adoptada para tratar con este tipo de errores consiste en capturar la excepción ValueError en el programa principal. Trataremos esto mas adelante en una sección dedicada al tratamiento de los errores de ejecución.

Implementación del analizador léxico

En la implementación del analizador léxico se utiliza la clase LexAnalyser y la clase Token. Ambas estan implementadas en el módulo lexico.py.

    class LexAnalyser:
      def __init__( fis, sentence, sentenceNr )
      def getCurrentChar( )
      def pointNextChar( )
      def pointPreviousChar( )
      def getNextToken( )

    class Token:
      def __init__( cat, lex, chr1 )

El analizador léxico debe dividir la entrada en una serie de tokens. Para este fin se utiliza la MDD que hemos introducido antes. La implementación de la MDD se puede hacer mediante tablas o mediante control de flujo. Se opta por la implementación mediante tablas. Para implementar la MDD con tablas, son necesarias las cuatro tablas siguientes, implementadas en el módulo léxico.py como diccionarios globales al módulo:

    movement [ (state, char) ]
    final[ state ]
    action[ state ]
    category[ state ]

La tabla "movement" contiene, por cada estado y cada posible carácter de la entrada, el estado siguiente de la maquina determinista al que se transita. Es una tabla realmente grande, pero al estar implementada con diccionarios proporciona un acceso rapidísimo. La tabla "final" indica, por cada estado de la MDD, si es final o no. La tabla "action" contiene, por cada estado de la MDD, la acción asociada (emitir u omitir). Por último, se usa la tabla "category" para conocer la categoría léxica asociada a cada estado final de la MDD.

La MDD se implementa en la clase LexAnalyser con ayuda de los métodos getNextToken(), getCurrentChar(), pointNextChar() y pointPreviousChar(). El método getNextToken() parte del estado inicial y del primer carácter a analizar y actúa repetidamente sobre la cadena de entrada, empezando en cada caso en un punto distinto de la misma pero siempre desde su estado inicial. El método getNextToken() utiliza pointNextChar() para transitar entre estados avanzando sobre la cadena de caracteres mientras el carácter obtenido con getCurrentChar tenga algún movimiento posible en la tabla movement. A medida que getNextToken() avanza, va tomando nota del último estado final por el que ha pasado. Cuando no puede avanzar, detiene el avance.

Si ha pasado por algún estado final, pointPreviousChar() devuelve los caracteres sobrantes a la entrada y getNextToken() ejecuta las acciones asociadas al último estado final por el que ha transitado. Si la acción asociada al último estado final es emitir, la clase Token construye el token adecuado en función de los parámetros enviados a su constructor, y getNextToken() envía ese token recién construido al analizador sintáctico. El método getNextToken() actúa por tanto de interfaz entre el analizador léxico y el analizador sintáctico, permitiendo a éste último obtener el token actual de la entrada. Si la acción asociada al último estado final es omitir, se continua analizando la cadena en busca del siguiente token.

Si no ha pasado por ningún estado final, getNextToken() ha detectado un error léxico. En ese caso lanza una excepción LexError y el programa principal la captura y la muestra por stderr.

Continuar leyendo el analizador sintáctico