Lex es una herramienta que permite generar analizadore léxicos a partir de un conjunto de reglas y expresiones regulares. Desarrollado por Eric Schmidt y Mike Lesk para los sistemas Unix. Escrito en C para C, su implementación para C++ es posible, aunque no es segura ya que está mas enfocado en el trabajo con C. La principal tarea de un analizador léxico es leer los caracteres de entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens.
Un token es un par que consiste en un nombre de token y un valor de atributo opcional.
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 este token.
Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.
Para obtener más información de Lex, es recomendable visitar su página oficial.
Yacc
Yacc es un generador de analizadores sintácticos ascendentes escrito en C para C. Las siglas Yacc significan Yet Another Compiler-Compiler. Desarrollado por Stephen C. Jhonson en AT&T para el sistema operativo Unix.
El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generase con la gramática para el lenguaje fuente. Una gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación.
Para obtener más información de Lex, es recomendable visitar su página oficial.
Pre-requisitos
Para este ejemplo neceistamos las siguientes herramientas:
Lo primero que haremos será instalar Lex, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl + Alt + t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando:
1
sudo apt-get install flex
Autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Lex. Como nos pudimos dar cuenta, la instalación de Lex se hace a través Flex que es otra herramienta de analisis léxico.
Luego instalamos Yacc, ejecutando el comando:
1
sudo apt-get install bison
Autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Yacc. Como nos pudimos dar cuenta, la instalación de Yacc se hace a través de Bison que es otra herramienta de análisis sintáctico.
Crear nuestro proyecto Creamos un nuevo folder el cual será nuestro espacio de trabajo, para crearlo abrimos una terminal y ejecutamos el comando:
1
mkdir ProyectoLexYacc
Luego ingresamos a nuestro folder con el comando:
1
cd ProyectoLexYacc
Ahora nos pasamos a el editor de código, en este caso usaremos Visual Studio Code. Para abrir nuestro directorio de trabajo en Visual Studio Code ejecutamos desde la terminal el comando:
1
code .
El punto al final es importante, ya que le indica a Visual Studio Code que abra una nueva ventana en el directorio actual.
Esto desplegará una ventana de Visual Studio Code, con nuestro proyecto llamado ProyectoLexYacc.
Definimos la estructura de nuestro espacio de trabajo creando un directorio llamado src en donde estará todo nuestro código fuente. Dentro del directorio src creamos un directorio analizador, en este directorio estará todo el código relacionado con Yacc y Lex.
Código fuente para el analizador léxico
En el archivo lexer.l incluiremos todo el código que le indicará a Lex lo que debe de hacer. El código se muestra a continuación:
Explicación código fuente para el analizador léxico
En las primeras lineas incluimos stdio.h para la lectura de archivos, luego incluimos la cabecera y.tab.h que es el archivo que genera Yacc para nuestro analizador sintáctico. Por último declaramos la función yyerror, función propia de Lex y Yacc para el manejo de errores léxicos.
Establecemos una lista de directivas propias de Lex:
La directiva noyywrap le indica a Lex que unicamente leera un archivo de entrada.
1
%option noyywrap
Luego se escriben algunas expresiones regulares para identificar enteros y decimales.
1 2
DIGIT [0-9] NUM {DIGIT}+("."{DIGIT}+)?
Por último definimos todas las reglas léxicas, en las que indicamos los patrones que reconocerá y dentro de llaves lo que debe hacer cuando los reconozca. Para retornar nuestras reglas como tokens y que puedan ser utilizadas en el analizador sintáctico retornamos un id que le asignaremos a cada token, para los tokens de tipo símbolo retornamos la variable yytext para tener una definición más limpia y corta. En el caso de NUM adicional al token debemos regresar el valor numérico reconocido, por lo que es necesario hacer una conversión con la función atoi que convierte una cadena a un número y lo almacenamos en yyval. Para los espacios en blanco, Lex cuenta con una directiva [[:blank]] donde podemos ver que no retornamos ningún simbolo, ya que ignoramos los espacios en blanco. Luego indicamos con un punto que todo lo que no fue reconocido en las reglas anteriores será un error léxico.
Explicación código fuente para el analizador sintáctico
En las primeras lineas incluimos el ficherio stdio.h para la lectura de archivos, luego declarramos la función yylex, que es la encargada del analizador léxico, también declaramos la función yyerror, que utiliza Yacc para el manejo de errores sintácticos. Por último declaramos una variable de tipo FILE llamada yyin, en esta indicaremos el archivo de entrada que será analizado.
Luego se definen los no terminales, a estos se les puede indicar o no un tipo, por defecto es de tipo int. Los terminales que son símbolos y no retornan ningún identificador asociado al token en el analizador léxico no se agregan en esta sección.
1 2
/******* TERMINALES ********/ %token NUMBER EVALUAR
Posteriormente podemos indicar la precedencia de operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto. El nivel de precendencia se define del mas bajo al mas alto. La precendencia mas baja la tienen la suma y la resta, seguido por la multiplicación y división y por último tenemos el signo menos de las expresiones negativas.
1 2 3
%left '+''-' %left '*''/' %left NEG
A continuación tenemos el conjunto de reglas de escritura de la gramática o producciones. Escribimos nuestras producciones, para asignar reglas de producción lo hacemos mediante llaves “{ }”, en esta sección podemos escribir código de C. Ya que los analizadores que utiliza Yacc son ascenentes, nos permiten sintetizar atributos, para sintentizar un atributo lo hacemos a traves del identificador “$$”.
Como último paso, definimos la función que será llamada para inciar el análisis sintáctico, que en este caso es la función parse, esta recibe como parámetro un FILE, que será nuestro archivo de entrada a ser analizado. Por último definimos la función yyerror, la cúal será llamada si existiera un error sintáctico, esta función es propia de Yacc.
En el archivo compilar.sh, ejecutamos dos lineas, la primera indica a Lex que debe generar un analizador léxico en base al código fuente que se encuentra en el archivo Léxico. La segunda linea le indica a Yacc que genere los archivos de compilación para el analizador sintáctico en base al archvio Parser.
1 2
lex lexer.l yacc parser.y -d
Para ejecutar abrimos una terminal sobre el directorio analizador y ejecutamos lo siguiente:
1
./compilar.sh
Nota: Si el comando genera error, asegurese de que el archivo tenga permisos de ejecución.
Este comando genera una serie de archivos que se han mencionado ya anteriormente. Los archivos que genera son los siguientes:
y.tab.c
y.tab.h
lex.yy.c
Archivo de entrada
Dentro de la carpeta src del proyecto, creamos un archivo de entrada llamado entrada.txt, que contendrá el archivo de enetrada que reconocerán nuestros analizadores.
Dentro del archivo main.c, declaramos el método parse, el cúal fue definido en el analizador sintáctico. Definimos nuestro método main, en este creamos abrimos un archivo a través de FILE, indicamos la ruta del archivo de entrada y por último llamamos a nuestro método parse y le pasamos como parámetro el archivo de entrada.
Para ejecutar nuestra aplicación necesitamos compilar todos los archivos y generar el ejecutable. Esto lo realizamos con el compilador GCC ejecutando desde consola el siguiente comando:
1
gcc main.c ./analizador/*.c
Este nos genera un archivo a.out, que es el binario resultante de la compilación, este archivo lo ejecutamos desde consola y obtenemos la salida de nuestro proyecto.
1
./a.out
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Erik Flores y revisado por el Catedrático Erick Navarro, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.
Fuentes Consultadas
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
En este tutorial se desarrolla un intérprete que recibe como entrada un archivo de texto que contiene varias sentencias de un lenguaje de programación diseñado especialmente para esta aplicación. Primero se hace análisis léxico y sintáctico de dicha entrada, durante el análisis sintáctico se carga en memoria un Árbol de Sintaxis Abstracta (AST) que se utiliza posteriormente para ejecutar las sentencias. El analizador se genera con PLY utilizando Python 3 en Ubuntu 18.04. El proyecto completo puede descargarse del siguiente enlace:
Todo el código del proyecto está documentado con comentarios que contienen los detalles de su funcionamiento.
Si se desea una introducción sobre el uso de PLY con Python pueden visitar el post: Mi primer proyecto utilizando PLY con Python 3, en el cual se describen los pre-requisitos y los pasos para la creación del proyecto.
El lenguaje de entrada
Dentro de la carpeta del proyecto, hay un archivo de entrada llamado entrada.txt en el cual se muestran ejemplos de todas las funciones del lenguaje diseñado para esta aplicación, al leerlo se puede tener una idea clara de las funciones con las que el lenguaje cuenta, este archivo contiene lo siguiente:
//Se imprime el encabezado imprimir("Tablas de" & " multiplicar");
//Se declara la variable a, de tipo numero numero a; //Se asigna a la variable a el valor 0 a=0; //Se declara la variable c, de tipo numero numero c; //Se asigna a la variable c el valor 0 c=1; //Se imprime un separador imprimir("----------------"); /** * Se imprimen las tablas del 1 al 5 y * para cada tabla, se imprimen los resultados * desde el uno hasta el 5, esto se hace con * dos ciclos while anidados. **/ mientras(a<4+c){ a=a+1; numero b; b=0; mientras(b<4+c){ b=b+1; imprimir(a & " * " & b & " = " & a * b); } imprimir("----------------"); }
//Se asigna a la variable a el valor de 11 a=11; /** * La variable b ya había sido declarada pero * dentro del ámbito del primer ciclo while, * entonces no existe en este ámbito por lo que * debe declararse. **/ numero b; //Se asigna valor de 12 a b y valor de 13 a c b=12; c=13; /** * Se evalua si el valor de la variable a es * mayor que 10, si el b es mayor que 11 y si * el de c es mayor que 12. **/ If(a>10){ imprimir("a es mayor que 10."); if(b>11){ imprimir("a es mayor que 10 y b es mayor que 11."); if(c>12){ imprimir("a es mayor que 10, b es mayor que 11 y c es mayor que 12."); } } }else{ imprimir("a es menor o igual que 10."); }
Como se puede observar, el lenguaje acepta:
Comentarios simples, es decir de una sola línea (//)
Comentarios múltiples, es decir de más de una línea (//)
Concatenación de cadenas mediante el operador &
Función Imprimir. Recibe como parámetro una cadena e imprime su valor en consola.
Declaración de variables. Únicamente se acepta definición de variables de tipo numero incluyendo enteros y decimales.
Asignación de variables. A cualquier variable se le puede asignar cualquier expresión que tenga como resultado un número.
Instrucción Mientras. Tiene el comportamiento clásico del ciclo while, ejecuta el ciclo mientras la expresión booleana que recibe sea verdadera. Esta instrucción soporta anidamiento.
Instrucción If e If-Else. Tiene el comportamiento clásico de las sentencias de selección If e If-Else, evalúa la expresión booleana y ejecuta el bloque de instrucciones en If si es verdadera. En caso contrario y si existe un bloque Else se ejecuta este bloque de instrucciones. Estas instrucciones también soportan anidamiento.
Expresiones aritméticas. Se soportan las expresiones aritméticas binarias: suma, resta, multiplicación y división. También la expresión unaria: negación. Adicionalmente se soporta expresiones agrupadas en paréntesis. Se maneja la precedencia habitual de las expresiones aritméticas.
Expresiones booleanas. Comparan dos expresiones que tengan como resultado un número y soportan unicamente los operados Mayor Que y Menor que (<, >).
El analizador léxico y sintáctico
En el archivo gramatica.py detallamos la estructura del lenguaje utilizando PLY. A continuación detallaremos los aspectos más relevantes.
Sobre el analizador léxico
El analizador léxico define los patrones para los tokens que deseamos reconocer. Hacemos uso de expresiones regulares para identificar números, cadenas y comentarios. Para esto hacemos uso del módulo re de Python
# Construyendo el analizador léxico import ply.lex as lex lexer = lex.lex()
Nótese que los comentarios, saltos de líneas y espacios en blanco son ignorados (no retornan ningún valor).
Otro aspecto importante a destacar es que las palabras reservadas son tratadas como Identificadores, esto se debe a que PLY da precedencia a las expresiones regulares más generales. Por ejemplo, la palabra reservada “Imprimir” siempre hará match con la expresión regular de Identificador, por lo que si se define de la forma t_IMPRIMIR = r'imprimir' nunca será alcanzado. Esto lo hace con la finalidad de hacer el proceso de parsing más eficiente al tener menos expresiones regulares que evaluar.
Sobre el analizador sintáctico
El objetivo principal de nuestro analizador sintáctico es validar que la entrada sea válida y, si lo es, construir el AST. Para lograr esto hacemos uso de la programación orientada a objetos. Específicamente haremos uso del polimorfismo para la construcción de nuestro árbol. Las clases utilizadas para construir las diferentes instrucciones que componen nuestro AST, están definidas en el archivo instrucciones.py.
Clases para Instrucciones
Primero definimos una clase abstracta Instruccion, esto nos permitirá abstraer las Instrucciones que soporta nuestro lenguaje:
1 2
class Instruccion: '''This is an abstract class'''
Seguidamente, definimos una clase concreta para cada una de las formas posibles que puede tomar Instruccion:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class Imprimir(Instruccion) : ''' Esta clase representa la instrucción imprimir. La instrucción imprimir únicamente tiene como parámetro una cadena '''
def __init__(self, cad) : self.cad = cad
class Mientras(Instruccion) : ''' Esta clase representa la instrucción mientras. La instrucción mientras recibe como parámetro una expresión lógica y la lista de instrucciones a ejecutar si la expresión lógica es verdadera. '''
Por ejemplo, para la clase Imprimir vemos que extiende de Instruccion y que su única propiedad es la cadena que se va imprimir. Esta propiedad, cadena, es de tipo ExpresionCadena como veremos más adelante.
De la misma forma, la instrucción Mientras extiende de Instruccion y sus propiedades son la expresión lógica a evaluar y el set de instrucciones a ejecutar mientras la condición sea verdadera. expLogica es de tipo ExpresionLogica e instrucciones es una lista, y sus elementos son de tipo Instrucción.
El proceso es similar para las instrucciones de Definición y Asignación
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
class Definicion(Instruccion) : ''' Esta clase representa la instrucción de definición de variables. Recibe como parámetro el nombre del identificador a definir '''
def __init__(self, id) : self.id = id
class Asignacion(Instruccion) : ''' Esta clase representa la instrucción de asignación de variables Recibe como parámetro el identificador a asignar y el valor que será asignado. '''
class If(Instruccion) : ''' Esta clase representa la instrucción if. La instrucción if recibe como parámetro una expresión lógica y la lista de instrucciones a ejecutar si la expresión lógica es verdadera. '''
class IfElse(Instruccion) : ''' Esta clase representa la instrucción if-else. La instrucción if-else recibe como parámetro una expresión lógica y la lista de instrucciones a ejecutar si la expresión lógica es verdadera y otro lista de instrucciones a ejecutar si la expresión lógica es falsa. '''
De la misma manera que manejamos las instrucciones manejaremos las expresiones. Definimos 3 clases abstractas que representan los 3 tipos de expresiones soportadas por nuestro lenguaje: Expresiones Aritméticas, Expresiones con Cadenas y Expresiones Lógicas, todas ellas definidas dentro del archivo expresiones.py.
También haremos uso de enumeraciones para definir constantes de nuestras operaciones, esto es altamente recomendado para evitar bugs durante el desarrollo.
1 2 3 4 5 6 7 8 9 10 11 12 13
from enum import Enum
class OPERACION_ARITMETICA(Enum) : MAS = 1 MENOS = 2 POR = 3 DIVIDIDO = 4
class OPERACION_LOGICA(Enum) : MAYOR_QUE = 1 MENOR_QUE = 2 IGUAL = 3 DIFERENTE = 4
Iniciamos definiendo nuestra clase ExpresionNumerica de tipo abstracta y será nuestra clase base para las expresiones numéricas.
1 2 3 4
class ExpresionNumerica: ''' Esta clase representa una expresión numérica '''
Las formas que puede tomar nuestra clase ExpresionNumerica son las siguientes:
ExpresionBinaria. Representa una operación aritmética binaria, la clase recibe los 2 operados: exp1 y exp2, ambos de tipos ExpresionNumérica. Y recibe el operador el cual es un calor de nuestro enum definidos anteriormente.
ExpresionNegativo. Representa la operación aritmética unaria de negación. Únicamente recibe como parámetro la expresión que se negara, esta es también de tipo ExpresionNumerica
ExpresionNumero. Representa un valor terminal numérico. El parámetro val contiene el valor extraído por el analizador léxico.
ExpresionIdentificador. Representa un identificador. El parámetro id representa el nombre de la variable que se desea operar.
class ExpresionBinaria(ExpresionNumerica) : ''' Esta clase representa la Expresión Aritmética Binaria. Esta clase recibe los operandos y el operador '''
class ExpresionNegativo(ExpresionNumerica) : ''' Esta clase representa la Expresión Aritmética Negativa. Esta clase recibe la expresion ''' def __init__(self, exp) : self.exp = exp
class ExpresionNumero(ExpresionNumerica) : ''' Esta clase representa una expresión numérica entera o decimal. '''
def __init__(self, val = 0) : self.val = val
class ExpresionIdentificador(ExpresionNumerica) : ''' Esta clase representa un identificador. '''
def __init__(self, id = "") : self.id = id
Ahora, siguiendo el proceso anterior, definimos nuestras expresiones con cadenas.
class ExpresionCadena : ''' Esta clase representa una Expresión de tipo cadena. '''
class ExpresionConcatenar(ExpresionCadena) : ''' Esta clase representa una Expresión de tipo cadena. Recibe como parámetros las 2 expresiones a concatenar '''
class ExpresionDobleComilla(ExpresionCadena) : ''' Esta clase representa una cadena entre comillas doble. Recibe como parámetro el valor del token procesado por el analizador léxico '''
def __init__(self, val) : self.val = val
class ExpresionCadenaNumerico(ExpresionCadena) : ''' Esta clase representa una expresión numérica tratada como cadena. Recibe como parámetro la expresión numérica ''' def __init__(self, exp) : self.exp = exp
Y finalmente, definimos nuestras expresiones lógicas
1 2 3 4 5 6 7 8 9 10
class ExpresionLogica() : ''' Esta clase representa la expresión lógica. Esta clase recibe los operandos y el operador '''
Para construir el AST durante nuestro análisis sintáctico importamos nuestras clases de instrucciones y expresiones. Esto también incluye nuestros enum para las constantes, esto se hará en el archivo gramatica.py.
1 2 3 4
# Definición de la gramática
from expresiones import * from instrucciones import *
Una vez importados podemos hacer uso de ellas en la gramática. Por ejemplo, para la construcción de operaciones aritméticas hacemos uso de nuestras clases de tipo ExpresionNumerica, pasamos como parámetros los operandos y el tipo operación (utilizando nuestras constantes).
La tabla de símbolos es la que permite el almacenamiento y recuperación de los valores de las variables. Para su implementación hacemos uso de una clase, ya que necesitaremos más de una instancia de tabla de símbolos. Cada ámbito tiene acceso únicamente a su propia tabla de símbolos y a la de los niveles superiores, la definición de esta clase puede encontrarse en el archivo ts.py.
Definimos las constantes para los tipos de datos, en este tutorial se hace uso únicamente del tipo de dato numérico.
1 2 3 4
from enum import Enum
class TIPO_DATO(Enum) : NUMERO = 1
Definimos una clase para los Símbolos.
1 2 3 4 5 6 7
class Simbolo() : 'Esta clase representa un simbolo dentro de nuestra tabla de simbolos'
def __init__(self, id, tipo, valor) : self.id = id self.tipo = tipo self.valor = valor
La clase TablaDeSimbolos define la estructura de una tabla de símbolos y sus funciones para agregar, modificar y obtener símbolos.
def agregar(self, simbolo) : self.simbolos[simbolo.id] = simbolo def obtener(self, id) : if not id in self.simbolos : print('Error: variable ', id, ' no definida.')
return self.simbolos[id]
def actualizar(self, simbolo) : if not simbolo.id in self.simbolos : print('Error: variable ', simbolo.id, ' no definida.') else : self.simbolos[simbolo.id] = simbolo
Construcción del Intérprete
La definición del Intérprete se encuentra en el archivo principal.py
Para iniciar con la implementación, primero importamos nuestra gramática, las constantes y clases de nuestro AST y la Tabla de Símbolos.
1 2 3 4
import gramatica as g import ts as TS from expresiones import * from instrucciones import *
Seguidamente, obtenemos el AST a partir del archivo de entrada.
Nótese que el AST está contenido en la variable instrucciones.
La función principal del intérprete es de reconocer cada instrucción y ejecutarla, para esto es necesario recorrer el AST; es por ello que se ha definido la función procesar_instrucciones la cual itera las instrucciones en un ámbito y las ejecuta.
Para iniciar con la ejecución se crea la tabla de símbolos para el ámbito global y se invoca la función procesar_instrucciones con la raíz del AST y la tabla de símbolos del ámbito global.
1 2 3 4 5 6 7 8 9 10
def procesar_instrucciones(instrucciones, ts) : ## lista de instrucciones recolectadas for instr in instrucciones : if isinstance(instr, Imprimir) : procesar_imprimir(instr, ts) elif isinstance(instr, Definicion) : procesar_definicion(instr, ts) elif isinstance(instr, Asignacion) : procesar_asignacion(instr, ts) elif isinstance(instr, Mientras) : procesar_mientras(instr, ts) elif isinstance(instr, If) : procesar_if(instr, ts) elif isinstance(instr, IfElse) : procesar_if_else(instr, ts) else : print('Error: instrucción no válida')
Existe una función para procesar cada instrucción.
Las sentencias Mientras, If e If-Else crean nuevas tablas de símbolos antes de procesar las instrucciones dentro de sus bloques de instrucciones. Estas nuevas tablas de símbolos se inicializan con los valores de la tabla de símbolo actual y al terminar la ejecución de la sentencia los valores son eliminados ya que la instancia se crea localmente en el cuerpo de la función.
def procesar_if(instr, ts) : val = resolver_expreision_logica(instr.expLogica, ts) if val : ts_local = TS.TablaDeSimbolos(ts.simbolos) procesar_instrucciones(instr.instrucciones, ts_local)
def procesar_if_else(instr, ts) : val = resolver_expreision_logica(instr.expLogica, ts) if val : ts_local = TS.TablaDeSimbolos(ts.simbolos) procesar_instrucciones(instr.instrIfVerdadero, ts_local) else : ts_local = TS.TablaDeSimbolos(ts.simbolos) procesar_instrucciones(instr.instrIfFalso, ts_local)
Las sentencias de Declaración y Asignación agregan y modifican valores de la tabla de símbolos. La sentencia Imprimir muestra el valor de una cadena en la consola.
def procesar_definicion(instr, ts) : simbolo = TS.Simbolo(instr.id, TS.TIPO_DATO.NUMERO, 0) # inicializamos con 0 como valor por defecto ts.agregar(simbolo)
Finalmente, todas las sentencias descritas anteriormente hacen uso de las operaciones numéricas, con cadenas y lógicas las cuales hacen uso de la tabla de símbolos para obtener valores de las variables.
Para las expresiones numéricas evaluamos el tipo de operación y con base en ellos resolvemos el valor apropiado
Para las expresiones con cadenas también validamos el tipo de operación para verificar si es necesario una operación de concatenación. En cualquier caso se resuelve la cadena. También es posible concatenar valores numéricos, para esto resolvemos la expresión apoyándonos de la función para procesar expresiones numéricas.
Al igual que las expresiones con cadena, las expresiones lógicas también se apoya en la función que procesa expresiones numéricas para poder evaluar las condiciones booleanas.
Para ejecutar nuestro intérprete y procesar el archivo de entrada ejecutamos el siguiente comando:
1
$ python3 ./principal.py
Y veremos el resultado en consola.
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Rainman Sián, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.
Fuentes consultadas:
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
PLY es una implementación en Python de lex y yacc, herramientas populares para la construcción de compiladores.
La principal tarea de un analizador léxico es leer los caracteres de entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens.
Un token es un par que consiste en un nombre de token y un valor de atributo opcional.
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 este token.
Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.
El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generarse con la gramática para el lenguaje fuente. Una gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación.
En PLY se definen los patrones de los diferentes tokens que se desean reconocer, esto se hace a través de expresiones regulares. Mientras que las producciones y acciones para formar la gramática se definen a través de funciones.
Para hacer uso de PLY en nuestro proyecto no hacemos instalación como tal, lo que necesitamos es descargar el archivo ply-3.11.tar.gz (versión 3.11 al momento de escribir este tutorial) de la página oficial de PLY y lo que hacemos es copiar el fólder “ply” a nuestro proyecto.
Crear nuestro proyecto
Primero crearemos un nuevo fólder, en este caso lo llamaremos PROYECTOPLY. Luego lo abrimos en nuestro editor de texto, en este caso usaremos Visual Studio Code. Finalmente procedemos a crear un nuevo archivo llamado gramatica.py donde escribiremos nuestro compilador.
Los directorios “pycache“, al igual que los archivos “parser.out” y “parsetab.py” son generados por Python los cuales pueden ser excluidos en nuestro controlador de versiones. En este caso, los agregamos a nuestro .gitignore.
1 2 3
parser.out parsetab.py **/__pycache__/**
El directorio “ply” es el que descargamos y utilizaremos para construir nuestro compilador.
Código Fuente para el analizador léxico y sintáctico
En el archivo gramatica.py tenemos la construcción de nuestro compilador.
Explicación del código fuente para el analizador léxico
Lo primero que debemos hacer es definir el listado de tokens que vamos a reconocer ya asignarlo a la variable tokens
Luego escribimos los patrones para los tokens que definimos. Existen dos formas de definir las reglas de nuestros tokens.
La primera, es con expresiones regulares, agregamos el prefijo “t_” al token que queremos definir y luego le especificamos la expresión regular, para esto se hace uso del módulo re de Python.
La otra forma es a través de funciones, esto nos sirve para manipular el valor del token que procesamos. Por ejemplo para los valores numéricos los retornamos con el tipo apropiado, hacer validaciones, etc.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def t_DECIMAL(t): r'\d+\.\d+' try: t.value = float(t.value) except ValueError: print("Floaat value too large %d", t.value) t.value = 0 return t
def t_ENTERO(t): r'\d+' try: t.value = int(t.value) except ValueError: print("Integer value too large %d", t.value) t.value = 0 return t
Es importante definir también los caracteres que se van a ignorar.
1 2
# Caracteres ignorados t_ignore = " \t"
Las funciones también llevan el prefijo “t_” antes del nombre del token que queremos procesar. La función recibe un parámetro, “t” en nuestro ejemplo, este contiene el valor del token. Retornamos el valor ya procesado que deseamos, o no retornar nada si lo que deseamos es ignorar el token (por ejemplo: comentarios, contadores, etc.).
Finalmente construimos el analizador léxico haciendo uso de las librerías de PLY
1 2 3
# Construyendo el analizador léxico import ply.lex as lex lexer = lex.lex()
Explicación del código fuente para el analizador sintáctico
Otra de las ventajas de Python es que en el mismo archivo podemos definir nuestro análisis sintáctico haciendo uso de los tokens previamente definidos en la sección del analizador léxico.
Primeramente definimos la asociatividad y precedencia de los operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto al analizar, en este caso la precedencia es la misma que la de los operadores aritméticos, la precedencia más baja la tienen la suma y la resta, luego están la multiplicación y la división que tienen una precedencia más alta y por último está el signo menos de las expresiones negativas que tendría la precedencia más alta.
1 2 3 4 5 6
# Asociación de operadores y precedencia precedence = ( ('left','MAS','MENOS'), ('left','POR','DIVIDIDO'), ('right','UMENOS'), )
Ahora procedemos a escribir nuestras producciones, aquí vemos otra de las ventajas de Python, las acciones semánticas de nuestras producciones se hacen en forma de funciones. Las características de estas funciones son:
El nombre inicia con el prefijo “_p”. El complemento del nombre queda a nuestra discreción
Tiene un único parámetro “t” el cual es una tupla, en cada posición tiene el valor de los terminales y no terminales de la producción.
Haciendo uso del docstring de las funciones de Python especificamos las producciones que serán procesadas por la función.
En el cuerpo de la función definimos la funcionalidad que deseamos
Para ejecutar este script corremos el siguiente comando:
1
$ python3 .\gramatica.py
Como podemos ver, obtenemos la salida esperada.
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Rainman Sián, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.
Fuentes consultadas:
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
