Analisis Lexico

  

Análisis Léxico 

Analizador sintáctico PLY (Python Lex Yacc) de Python.

Creación y generalidades:El metacompilador hecho en lenguaje Python PLY es originario de la universidad de Chicago, por el profesor de ciencias de la computación David Beazly, esta api presenta una integrativa de Lex y Yacc que son dos apis que permiten la creación de analizadores léxicos, ambos escritos en lenguaje C.

Fue creado como una herramienta de instrucción primeramente para usuarios iniciados, pero la herramienta demostró ser robusta y por ello también es usada por usuarios experimentados, esto tampoco implica la creación de árboles sintácticos y la generación de herramientas avanzadas, si no tomado como una herramienta de análisis.

En general PLY presenta dentro de sí dos scripts que no son más que Lex y Yacc escritos en Python (Lex.py y Yacc.py), de manera que se permite la integración de ambos en programas en los que se desee desarrollar análisis léxico de otros scripts o instrucciones, estas instrucciones se evalúan en una colección de tokens suministrados y reglas de expresiones regulares, Yacc.py se utiliza para reconocer la sintaxis del lenguaje que se ha especificado en la forma de una gramática libre de contexto.

Las dos herramientas están destinadas a trabajar juntos. En concreto, lex.py proporciona una interfaz externa en forma de un símbolo () función que devuelve el siguiente token válido del flujo de entrada. Yacc.py llama a esto varias veces para recuperar los símbolos e invocar las reglas gramaticales.

Yacc está dentro de Unix por eso al usar un sistema basado en Unix (alguna distribución de Linux) encontraremos el programa Yacc, sin embargo Yacc.py tiene algunas diferencias con este, la principal entre yacc.py y Unix Yacc es que yacc.py no implica un proceso de generación de código independiente, a diferencia tradicional lex / yacc que requieren un archivo de entrada especial que se convierte en un archivo fuente separado, las especificaciones dadas para ejercer son programas Python válidos. Esto significa que no hay archivos de origen adicionales ni hay un paso especial construcción del compilador (por ejemplo, correr yacc para generar código Python para el compilador).

Lex:

lex.py se utiliza para dividir una cadena de entrada. Por ejemplo, supongamos que usted está escribiendo un lenguaje de programación y un usuario se suministra la siguiente cadena de entrada:

x = 3 + 42 * (s - t)

            Lex separa en tokens la cadena de texto ingresada.

'X', '=', '3', '+', '42', '*', '(', 's', '-', 't', ')'

Los créditos son por lo general dan nombres para indicar cuáles son. Por ejemplo:

"ID", "iguales", "Número", "más", "Número", "tiempos",

'LPAREN', 'ID', 'menos', 'ID', 'RPAREN'

Más específicamente, la entrada se divide en pares de tipos y valores de tokens. Por ejemplo:

( 'ID', 'x'), ( 'es igual a', '='), ( 'Cantidad', '3'),

( 'PLUS', '+'), ( 'Cantidad', '42), (' TIMES ',' * '),

( 'LPAREN', '('), ( 'ID', 's'), ( 'MENOS', '-'),

( 'ID', 't'), ( 'RPAREN', ')'

           

(Writing Parsers and Compilers with PLY, David Beazley, 2007)

            Estructura del Script del analizador personalizado.

            PLY nos permite crear un analizador personalizado, en el cual podemos crear una serie de definiciones que nos permitirán evaluar las expresiones que ingresemos en un script o en la consola de comandos, el cual recibirá una evaluación certera o negada, en cada uno de sus tokens, en este caso serán presentados una serie de ejemplos y directrices necesarias para la construcción de un analizador léxico personalizado, no contemplan el todo de la api a usar, en el caso que se requiera toda la información, se puede dirigir a la documentación oficial de dicha interfaz de programación de aplicaciones (API).

Se debe proporcionar una lista de tokens: en dicha lista se deben definir un grupo de nombres simbólicos que se pueden producir por el analizador léxico, esta lista también es usada por el Yacc.py. Ejemplo:

tokens = (

   'NÚMERO',

   'MÁS',

   'MENOS',

   'VECES',

   'DIVIDIR',

   'LPAREN',

   'RPAREN',

)

Se agrega una definición a los tokens: se crean fichas, o definiciones de cada uno de los tokens, estableciendo una expresión regular para cada uno, en esta api se debe identificar con un prefijo ‘t_’ que indica que es una definición de token, el calor siguiente debe coincidir exactamente con un valor suministado en la lista de tokens. Ejemplo.

t_MAS = r’\ +’

Palabras reservadas: Para manejar las palabras reservadas, se debe escribir una sola regla para que coincida con un identificador y hacer una búsqueda de nombre especial en una función. Ejemplo.

reserved = {

   'if' : 'IF',

   'then' : 'THEN',

   'else' : 'ELSE',

   'while' : 'WHILE',

   ...

}

tokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values())

def t_ID(t):

    r'[a-zA-Z_][a-zA-Z_0-9]*'

    t.type = reserved.get(t.value,'ID')  

    return t

Comentarios: Para descartar una ficha, tal como un comentario, sólo se tiene que definir una regla de token que no devuelve nada. Ejemplo:

def T_COMMENT (t):

    r '\ #. *'

    pass

    # No hay valor de retorno. Token descartados

Numeros de línea e información posicional: Para actualizar esta información, se debe escribir una regla especial. En el ejemplo, el t_newline () regla muestra cómo hacer esto.

def t_newline(t):

    r'\n+'

    t.lexer.lineno += len(t.value)

               La palabra reservada lineno, toma el número de las líneas y esta información se le asigna más el valor de la línea actual, en resultado un incremento progresivo de las líneas de código escritas.

            Caracteres literales: Los caracteres literales se pueden especificar mediante la definición de una variable literal en su módulo léxico. Por ejemplo:

               literals = [ '+','-','*','/' ]

O alternativamente

               literals = "+ - * /"

Un carácter literal es simplemente un único carácter que se devuelve tal cual cuando se encuentran por el analizador léxico. Los literales se comprueban después de todas las reglas de expresiones regulares definidas. Por lo tanto, si una norma comienza con uno de los caracteres literales, siempre tendrá prioridad.

Errores de manipulación: se debe agregar una función que se utiliza para controlar los errores léxicos, que se producen cuando se detectan caracteres no válidos. Su definición se da de la siguiente manera:

def t_error(t):

    print("Caracter ilegal '%s'" % t.value[0])

    t.lexer.skip(1)

Fin de archivo: la función de fin de archivo denota que no se ingresó más contenido para ser analizado o que el script que se proporcionó llego a su fin. Ejemplo:

def t_eof(t):

    more = raw_input('... ')

    if more:

        self.lexer.input(more)

        return self.lexer.token()

    return None

               Construccion y utilización del léxico: para la construcción del analizador, se usa la función lex.lex()

               Lexer = lex.lex()

               Esta función inspecciona las reglas de expresiones regulares, fuera del contexto de llamada y construye el analizador léxico, una vez este esta construido se utilizan dos métodos para controlarlo.

               Lexer.input(datos): restablece el analizador y almacena una nueva cadena de entrada.

               Lexer.token(): devuelve el siguiente token, devuelve una respuesta de éxito o fracaso en el análisis de la entrada.

               (Documentación de PLY Python; Teaching Compilers with Python, Matthieu Amiguet, 2010)

2.    Analizador léxico para lenguaje de expresiones matemáticas básicas.

Se eligió para esta asignación el lenguaje de programación Python, debido a su sintaxis bastante simple y a su dinámica de código, en esta ocasión se presenta la estructura del analizador léxico personalizado de expresiones matemáticas simples.

·         Importacion de la API contenedora de Lex y Yacc, en este caso solo usaremos lex debido a que solo se pide un analizador léxico, hacemos la abreviación “as lex” para usar la api en el script con el nombre de “lex”

·         Paso siguiente, se agrega la lista de tokens.

·         Luego se agregan las expresiones regulares para cada token declarado en la lista anterior que sea una expresión simple.

·         Se agregan las expresiones regulares de los tokens que representan una definición mayor, en este caso para el token “NUMBER” que representa una expresión numérica o un número entero.

·         Se agrega la definición de saltos de línea lo cual nos permite evaluar varias expresiones.

·         Se agrega posteriormente la definición de caracteres ignorados, esto nos permite incluir espacios y tabulaciones

·         Gestión de errores, dada por la función que permite mostrar caracteres ilegales no presentes en la lista inicial de tokens.

·         Finalizando las definiciones tenemos la construcción del analizador, creando así un objeto analizador.

                        Todo el script presentado, estará adjunto a este documento, el paso siguiente es la construcción de expresiones que puedan ser leídas por el analizador, estas nos permitirán ver la precisión de dicho lexema y su contenido.

Para la evaluación de las expresiones matemáticas y los ejemplos, creamos otro script en el cual incluimos la llamada de un archivo .txt y la integración del analizador antes creado, los comentarios nos permiten entender más el script.

3.    5 Ejemplos, en prueba del analizador.

Se ejecutaron varios ejemplos guardados en el archivo textlex.txt, los cuales se presentan a continuación

·         Expresión: x = (1 + 5) * 20 / 5

Esta expresión como es de notarse tiene correspondencia con tokens, y por ende no arroja errores léxicos.

Es notorio mostrar la secuencia de verificación que nos va indicando, a que token pertenece cada elemento ingresado, cuando llega al final de la expresión no existen errores, recordemos y tengamos en cuenta que el resultado será aceptación del léxico, y no un resultado matemático ponderado, así ajustándose a los requerimientos pedidos.

·         Expresión: y = 25 + (5 / 6) - 100 + w

En esta expresión podemos notar un elemento en una posición que podría causar un poco de incertidumbre, el elemento w no debería permitir la operación, pero recordemos que es un análisis léxico, es saber si la expresión tiene correspondencia con lo definido, y por ende está bien definido y no contiene errores.

·         Expresión: y = 45 - (30/2) * 12

En este tercer caso también se presenta una expresión válida para nuestro analizador y como vemos el resultado es válido en la consola, en donde recibimos el resultado.

·         Expresión: z = {23}{23}

En este caso la expresión no tiene sentido matemático, pero no es por esto que sea errónea para el analizador, si no que no tiene correspondencia con los tokens definidos.

Y en el resultado podemos observar que nos devuelve los 4 caracteres ilegales que no tienen correspondencia.

·         Expresión: w= 32 # 5

En este caso esta expresión no es válida, los números si lo son pero el elemento “#” no está dentro de los tokens.

Como vemos en la evaluación es devuelto como carácter ilegal.

Referencias Bibliográficas.

Writing Parsers and Compilers with PLY, David Beazley, 2007

Documentación de PLY Python.

Teaching Compilers with Python, Matthieu Amiguet, 2010.