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.
