Intérprete sencillo utilizando PLY con Python 3

Funcionamiento de la aplicació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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
reservadas = {
'numero' : 'NUMERO',
'imprimir' : 'IMPRIMIR',
'mientras' : 'MIENTRAS',
'if' : 'IF',
'else' : 'ELSE'
}

tokens = [
'PTCOMA',
'LLAVIZQ',
'LLAVDER',
'PARIZQ',
'PARDER',
'IGUAL',
'MAS',
'MENOS',
'POR',
'DIVIDIDO',
'CONCAT',
'MENQUE',
'MAYQUE',
'IGUALQUE',
'NIGUALQUE',
'DECIMAL',
'ENTERO',
'CADENA',
'ID'
] + list(reservadas.values())

# Tokens
t_PTCOMA = r';'
t_LLAVIZQ = r'{'
t_LLAVDER = r'}'
t_PARIZQ = r'\('
t_PARDER = r'\)'
t_IGUAL = r'='
t_MAS = r'\+'
t_MENOS = r'-'
t_POR = r'\*'
t_DIVIDIDO = r'/'
t_CONCAT = r'&'
t_MENQUE = r'<'
t_MAYQUE = r'>'
t_IGUALQUE = r'=='
t_NIGUALQUE = r'!='

def t_DECIMAL(t):
r'\d+\.\d+'
try:
t.value = float(t.value)
except ValueError:
print("Float 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

def t_ID(t):
r'[a-zA-Z_][a-zA-Z_0-9]*'
t.type = reservadas.get(t.value.lower(),'ID') # Check for reserved words
return t

def t_CADENA(t):
r'\".*?\"'
t.value = t.value[1:-1] # remuevo las comillas
return t

# Comentario de múltiples líneas /* .. */
def t_COMENTARIO_MULTILINEA(t):
r'/\*(.|\n)*?\*/'
t.lexer.lineno += t.value.count('\n')

# Comentario simple // ...
def t_COMENTARIO_SIMPLE(t):
r'//.*\n'
t.lexer.lineno += 1

# Caracteres ignorados
t_ignore = " \t"

def t_newline(t):
r'\n+'
t.lexer.lineno += t.value.count("\n")

def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)

# 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.
'''

def __init__(self, expLogica, instrucciones = []) :
self.expLogica = expLogica
self.instrucciones = instrucciones

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.
'''

def __init__(self, id, expNumerica) :
self.id = id
self.expNumerica = expNumerica

Finalmente, completamos nuestras instrucciones con If e If-Else

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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.
'''

def __init__(self, expLogica, instrucciones = []) :
self.expLogica = expLogica
self.instrucciones = instrucciones

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.
'''

def __init__(self, expLogica, instrIfVerdadero = [], instrIfFalso = []) :
self.expLogica = expLogica
self.instrIfVerdadero = instrIfVerdadero
self.instrIfFalso = instrIfFalso

Clases para Expresiones

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class ExpresionBinaria(ExpresionNumerica) :
'''
Esta clase representa la Expresión Aritmética Binaria.
Esta clase recibe los operandos y el operador
'''

def __init__(self, exp1, exp2, operador) :
self.exp1 = exp1
self.exp2 = exp2
self.operador = 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
'''

def __init__(self, exp1, exp2) :
self.exp1 = exp1
self.exp2 = exp2

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
'''

def __init__(self, exp1, exp2, operador) :
self.exp1 = exp1
self.exp2 = exp2
self.operador = operador

Construcción del AST

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def p_expresion_binaria(t):
'''expresion_numerica : expresion_numerica MAS expresion_numerica
| expresion_numerica MENOS expresion_numerica
| expresion_numerica POR expresion_numerica
| expresion_numerica DIVIDIDO expresion_numerica'''
if t[2] == '+' : t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.MAS)
elif t[2] == '-': t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.MENOS)
elif t[2] == '*': t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.POR)
elif t[2] == '/': t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.DIVIDIDO)

def p_expresion_unaria(t):
'expresion_numerica : MENOS expresion_numerica %prec UMENOS'
t[0] = ExpresionNegativo(t[2])

def p_expresion_agrupacion(t):
'expresion_numerica : PARIZQ expresion_numerica PARDER'
t[0] = t[2]

def p_expresion_number(t):
'''expresion_numerica : ENTERO
| DECIMAL'''
t[0] = ExpresionNumero(t[1])

def p_expresion_id(t):
'expresion_numerica : ID'
t[0] = ExpresionIdentificador(t[1])

El proceso es el mismo para las Instrucciones, cada producción de tipo Instrucción construye una instancia concreta de la instrucción apropiada.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def p_instruccion_imprimir(t) :
'imprimir_instr : IMPRIMIR PARIZQ expresion_cadena PARDER PTCOMA'
t[0] =Imprimir(t[3])

def p_instruccion_definicion(t) :
'definicion_instr : NUMERO ID PTCOMA'
t[0] =Definicion(t[2])

def p_asignacion_instr(t) :
'asignacion_instr : ID IGUAL expresion_numerica PTCOMA'
t[0] =Asignacion(t[1], t[3])

def p_mientras_instr(t) :
'mientras_instr : MIENTRAS PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER'
t[0] =Mientras(t[3], t[6])

def p_if_instr(t) :
'if_instr : IF PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER'
t[0] =If(t[3], t[6])

def p_if_else_instr(t) :
'if_else_instr : IF PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER ELSE LLAVIZQ instrucciones LLAVDER'
t[0] =IfElse(t[3], t[6], t[10])

Finalmente, una vez que hayamos reconocido toda la entrada, construimos un arreglo con cada uno de los nodos. Este será nuestro AST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def p_init(t) :
'init : instrucciones'
t[0] = t[1]

def p_instrucciones_lista(t) :
'instrucciones : instrucciones instruccion'
t[1].append(t[2])
t[0] = t[1]


def p_instrucciones_instruccion(t) :
'instrucciones : instruccion '
t[0] = [t[1]]

def p_instruccion(t) :
'''instruccion : imprimir_instr
| definicion_instr
| asignacion_instr
| mientras_instr
| if_instr
| if_else_instr'''
t[0] = t[1]

La tabla de símbolos

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TablaDeSimbolos() :
'Esta clase representa la tabla de simbolos'

def __init__(self, simbolos = {}) :
self.simbolos = simbolos

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.

1
2
3
4
5
6
7
f = open("./entrada.txt", "r")
input = f.read()

instrucciones = g.parse(input)
ts_global = TS.TablaDeSimbolos()

procesar_instrucciones(instrucciones, ts_global)

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def procesar_mientras(instr, ts) :
while resolver_expreision_logica(instr.expLogica, ts) :
ts_local = TS.TablaDeSimbolos(ts.simbolos)
procesar_instrucciones(instr.instrucciones, ts_local)

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.

1
2
3
4
5
6
7
8
9
10
11
def procesar_imprimir(instr, ts) :
print('> ', resolver_cadena(instr.cad, ts))

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)

def procesar_asignacion(instr, ts) :
val = resolver_expresion_aritmetica(instr.expNumerica, ts)
simbolo = TS.Simbolo(instr.id, TS.TIPO_DATO.NUMERO, val)
ts.actualizar(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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def resolver_expresion_aritmetica(expNum, ts) :
if isinstance(expNum, ExpresionBinaria) :
exp1 = resolver_expresion_aritmetica(expNum.exp1, ts)
exp2 = resolver_expresion_aritmetica(expNum.exp2, ts)
if expNum.operador == OPERACION_ARITMETICA.MAS : return exp1 + exp2
if expNum.operador == OPERACION_ARITMETICA.MENOS : return exp1 - exp2
if expNum.operador == OPERACION_ARITMETICA.POR : return exp1 * exp2
if expNum.operador == OPERACION_ARITMETICA.DIVIDIDO : return exp1 / exp2
elif isinstance(expNum, ExpresionNegativo) :
exp = resolver_expresion_aritmetica(expNum.exp, ts)
return exp * -1
elif isinstance(expNum, ExpresionNumero) :
return expNum.val
elif isinstance(expNum, ExpresionIdentificador) :
return ts.obtener(expNum.id).valor

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.

1
2
3
4
5
6
7
8
9
10
11
def resolver_cadena(expCad, ts) :
if isinstance(expCad, ExpresionConcatenar) :
exp1 = resolver_cadena(expCad.exp1, ts)
exp2 = resolver_cadena(expCad.exp2, ts)
return exp1 + exp2
elif isinstance(expCad, ExpresionDobleComilla) :
return expCad.val
elif isinstance(expCad, ExpresionCadenaNumerico) :
return str(resolver_expresion_aritmetica(expCad.exp, ts))
else :
print('Error: Expresión cadena no válida')

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.

1
2
3
4
5
6
7
def resolver_expreision_logica(expLog, ts) :
exp1 = resolver_expresion_aritmetica(expLog.exp1, ts)
exp2 = resolver_expresion_aritmetica(expLog.exp2, ts)
if expLog.operador == OPERACION_LOGICA.MAYOR_QUE : return exp1 > exp2
if expLog.operador == OPERACION_LOGICA.MENOR_QUE : return exp1 < exp2
if expLog.operador == OPERACION_LOGICA.IGUAL : return exp1 == exp2
if expLog.operador == OPERACION_LOGICA.DIFERENTE : return exp1 != exp2

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.

Mi primer proyecto utilizando PLY con Python 3

Se desarrollará un intérprete que recibe como entrada varias expresiones aritméticas y presentando como salida el resultado de dichas expresiones.

Las tecnologías a utilizar son:

  • PLY: Generador de analizadores léxicos y sintácticos.
  • Python 3: Es un lenguaje de programación interpretado de alto nivel.
  • Visual Studio Code: Es un editor de código ligero pero poderoso. Existen complementos para trabajar con este lenguaje.

El proyecto completo lo pueden descargar del siguiente enlace

PLY

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.

Pre-requisitos

Instalamos PLY

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tokens  = (
'REVALUAR',
'PARIZQ',
'PARDER',
'CORIZQ',
'CORDER',
'MAS',
'MENOS',
'POR',
'DIVIDIDO',
'DECIMAL',
'ENTERO',
'PTCOMA'
)

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.

1
2
3
4
5
6
7
8
9
10
11
# Tokens
t_REVALUAR = r'Evaluar'
t_PARIZQ = r'\('
t_PARDER = r'\)'
t_CORIZQ = r'\['
t_CORDER = r'\]'
t_MAS = r'\+'
t_MENOS = r'-'
t_POR = r'\*'
t_DIVIDIDO = r'/'
t_PTCOMA = r';'

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.).

1
2
3
4
5
6
7
def t_newline(t):
r'\n+'
t.lexer.lineno += t.value.count("\n")

def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)

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

Por ejemplo:

1
2
3
4
5
6
def p_expresion_evaluar(t):
'expresion : expresion MAS expresion'
# ^ ^ ^ ^
# t[0] t[1] t[2] t[3]

t[0] = t[1] + t[3]

Sintetizamos en p[0] (expresion) el valor del resultado de sumar loo valores de p[1] (expresion) y p[3].

A continuación el código completo de nuestras producciones:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definición de la gramática
def p_instrucciones_lista(t):
'''instrucciones : instruccion instrucciones
| instruccion '''

def p_instrucciones_evaluar(t):
'instruccion : REVALUAR CORIZQ expresion CORDER PTCOMA'
print('El valor de la expresión es: ' + str(t[3]))

def p_expresion_binaria(t):
'''expresion : expresion MAS expresion
| expresion MENOS expresion
| expresion POR expresion
| expresion DIVIDIDO expresion'''
if t[2] == '+' : t[0] = t[1] + t[3]
elif t[2] == '-': t[0] = t[1] - t[3]
elif t[2] == '*': t[0] = t[1] * t[3]
elif t[2] == '/': t[0] = t[1] / t[3]

def p_expresion_unaria(t):
'expresion : MENOS expresion %prec UMENOS'
t[0] = -t[2]

def p_expresion_agrupacion(t):
'expresion : PARIZQ expresion PARDER'
t[0] = t[2]

def p_expresion_number(t):
'''expresion : ENTERO
| DECIMAL'''
t[0] = t[1]

def p_error(t):
print("Error sintáctico en '%s'" % t.value)

Por último, podemos manejar también las producciones de error para el manejo de errores sintácticos.

Ahora construimos el analizador sintáctico,la funcionalidad para leer el archivo y enviarle su contenido a nuestro compilador.

1
2
3
4
5
6
7
import ply.yacc as yacc
parser = yacc.yacc()

f = open("./entrada.txt", "r")
input = f.read()
print(input)
parser.parse(input)

Creando un archivo de entrada para nuestro analizador

Creamos un nuevo archivo de texto utilizando nuestro editor llamado entrada.txt. El contenido de este archivo es el siguiente:

1
2
3
4
5
Evaluar[1+1];
Evaluar[1+1*2];
Evaluar[-(1+1*6/3-5+7)];
Evaluar[-(1+1*6/3-5+1*-2)];
Evaluar[-(1.6+1.45)];

Ejecución

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.

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×