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.

Intérprete sencillo utilizando JavaCC

De no estar familiarizado con la herramienta JavaCC, se recomienda al lector seguir el siguiente tutorial:

El desarrollo con JavaCC resulta sencillo, pero la legibilidad de la gramática puede llegar a ser un inconveniente si no se trata con la atención debida, sin embargo, el resto de las funcionalidades que nos ofrece JavaCC son un buen aliciente para utilizarlo, por lo tanto en esta ocasión vamos a desarrollar un intérprete, este contendrá la ejecución de sentencias básicas, como declaraciones de variables, asignaciones, sentencias de control, funciones y demás. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Conceptos básicos

  • Intérprete: Es un tipo común de procesador de lenguaje. En vez de producir un programa destino como una traducción, el intérprete ejecuta directamente las operaciones especificadas en el programa de origen (fuente) con las entradas proporcionadas por el usuario.
  • Árbol de sintaxis abstracta (AST): es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.

Lenguaje de entrada

En la raíz del proyecto hay un archivo llamado entrada.txt, este contiene un ejemplo con las instrucciones que el lenguaje soporta.

Listado instrucciones soportadas

  • Declaración de variables
  • Asignación de variables
  • Evaluación de expresiones aritméticas, lógicas y relaciones
  • If…elseif…else
  • While
  • Continue
  • Break
  • Return
  • Declaración de funciones
  • Llamadas a funciones
  • Recursividad
  • Funciones nativas: pie, toUpper. Pie genera una gráfica pie, y toUpper convierte a mayúsculas cierta cadena.
  • Comentarios de una línea y multilínea
  • Control de excepciones semánticas

Estructura del archivo Gramatica.jj de JavaCC

La extensión para los archivos JavaCC es .jj, a continuación vamos a describir la estructura del archivo de JavaCC utilizado para este ejemplo.

Sección de opciones
Aquí vamos a indicar que no haga distinción entre mayúsculas y minúsculas, además de indicar que los métodos de nuestro archivo luego de compilados no sean estáticos.

Sección de parserBegin y parserEnd
Aquí vamos a definir el nombre de nuestro paquete, adicionalmente y muy importante todos los import de archivos que vayamos a utilizar en las acciones para generar nuestro AST. Por último vamos a crear una clase vacía, esta es la que vamos a utilizar para invocar a nuestra gramática.

Sección de análisis léxico
En este punto vamos a definir todos los tokens que vamos a utilizar en el lenguaje:

  • Sección skip
    Contendrá todos los tokens que javacc va a ignorar cuando los reconozca, por ejemplo los comentarios o saltos de línea, espacios en blanco, etc.
1
2
3
4
5
6
7
SKIP : {
" "
| "\t"
| "\r"
| "\n"
| <"//" (~["\n", "\r"])*>
}
  • Sección de token
    En esta sección cada vez que se reconozca un lexema este generará un nuevo objeto de tipo token.
1
2
3
4
5
TOKEN : {
<NUMERO: (["0"-"9"])+>
| <DECIMAL: (["0"-"9"])+"."(["0"-"9"])+>
| <ENTERO: "Numero">
}
  • Sección more
    Sección utilizada para la creación de estados.
1
2
3
4
5
6
7
8
9
MORE :
{
"\"" :STRING_STATE
}

<STRING_STATE> MORE:
{
<~["\""]>
}

Sección de análisis sintáctico
Aquí vamos a definir la gramática y agregar las acciones correspondientes para generar nuestro AST. Ciertas producciones van a generar una clase que tiene cierta funcionalidad donde se indica lo que la ejecución deberá hacer.

Veamos el caso del while

1
2
3
4
5
6
7
/** While -> while(condicion) instrucciones */
AST Mientras() :
{AST e; ArrayList<AST> ins;}
{
<MIENTRAS> <PARENI> e=Expresion() <PAREND> ins=Bloque()
{return new Mientras(e, ins, token.beginLine, token.beginColumn);}
}

Con esta gramática observamos lo siguiente, tenemos dos variables:

  • AST e
  • ArrayList ins

AST es nuestra clase abstracta asociada con la variable e que contendrá la condición de nuestro while, y el arraylist contendrá una lista de estas clases, esto con el fin de tener una lista de instrucciones.
Como sabemos un while necesita de una condición y una lista de instrucciones, lo cual se cumple en el diseño planteado, por lo tanto vamos a retornar una instancia de la clase Mientras.

Luego de retornar nuestra clase Mientras, el analizador se encarga de continuar la reducción nuestras producciones, y agregar esta clase a una lista de instrucciones ya que la clase Mientras es una instrucción en sí misma.
Al finalizar el análisis de la entrada se debería generar un árbol, que básicamente contiene una lista de instrucciones, y estas instrucciones pueden ser mientras, imprimir, llamadas, etc.
Esta es la idea general detrás de las acciones del análisis sintáctico, retornar clases que van a formar un AST, que nos servirá para el análisis semántico y para la ejecución de nuestras instrucciones.

Análisis semántico y ejecución de código

Aquí nos vamos a encargar de verificar que lo que ejecutemos tenga sentido, vamos a retomar el ejemplo de la clase Mientras, específicamente la sobre-escritura del método interpretar:

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
@Override
public Object interpretar(Tabla tabla, Arbol tree) {
Object valorCondicion = false;
do {
Tabla t = new Tabla(tabla);
valorCondicion = condicion.interpretar(t, tree);
if (valorCondicion instanceof Excepcion) {
return valorCondicion;
}

if (!(valorCondicion instanceof Boolean)) {
Excepcion ex = new Excepcion("Semantico", "Se esperaba un valor booleano para la condicion", fila, columna);
tree.getExcepciones().add(ex);
return ex;
}
Object result = null;
if ((Boolean) valorCondicion) {
for (AST m : instrucciones) {
result = m.interpretar(t, tree);
if (result instanceof Retorno || result instanceof Excepcion) {
return result;
}
if(result instanceof Detener){
return null;
}
if(result instanceof Continue){
break;
}
}
}
} while ((Boolean) valorCondicion);
return null;
}

Se sobre-escribe la función interpretar que viene desde nuestra clase abstracta AST, cada clase que herede de AST le dará un distinto comportamiento a este método en base a lo que se quiere realizar.

En este caso necesitamos darle el comportamiento de un while, haciendo lo siguiente:

  • Declaramos una variable que almacenara nuestra condición
  • Iniciamos un ciclo doWhile con la condición establecida en la variable creada anteriormente
  • En las instrucciones del do, crearemos un nuevo ámbito para nuestro mientras
  • Obtenemos el valor de la condición y lo asignamos a la variable creada al inicio
  • Si el valor obtenido es una excepción vamos a retornar este valor para que sea reportado.
  • Si continua la ejecución vamos ahora a verificar que el valor obtenido sea de tipo booleano, sino fuera un booleano vamos a generar una nueva excepción y la vamos a retornar para que sea reportada.
  • Si la condición fuera valida vamos a tener un if con esta condición y si el valor fuera true inicia la ejecución de cada instrucción en nuestra lista
  • Si fuera false, simplemente ignora el if y nuestro doWhile termina
  • Dentro del for para recorrer las instrucciones nos encontramos que en cada iteración debemos verificar que lo que obtenemos de valor no sea una excepción ya que si lo fuera la debemos retornar para que sea reportada.
  • Además verificamos si fuera un break, continue o return para saber que hacer en cada caso.
  • Por ejemplo si fuera retorno vamos a devolver el valor como tal, si fuera un continue únicamente tenemos que ir a la siguiente iteración por lo que cortamos la iteración del ciclo interno donde estamos para que no se sigan ejecutando el resto de las instrucciones y si fuera un break debemos terminar la ejecución del mientras por lo tanto terminamos la ejecución de nuestro doWhile.
    Esta sería la lógica para un ciclo while, y así lo haremos con todas las instrucciones, cada una tendrá una implementación distinta.

Clases importantes del proyecto
Estas clases son clave para el desarrollo de nuestro intérprete y se explicarán a continuación

  • Clase abstracta AST
    Contiene los atributos y métodos que tendrán las instrucciones en común, además el método interpretar que será sobre-escrito en cada implementación, la finalidad de esta clase es poder modelar clases de distintos tipos que comparten un comportamiento cómun que en este caso sería que se pueden interpretar.
  • Clase símbolo
    Esta clase nos sirve como nodo para crear nuestras variables, vemos que contiene tipo, identificador y valor, aunque esto puede variar dependiendo del tipo de interprete que estemos construyendo.
  • Clase tabla
    Esta a tener la función de tabla de símbolos, aquí vamos a almacenar nuestras variables y funciones, nuestras variables las vamos a almacenar en un hashmap y las funciones en un arraylist. Contamos con métodos que nos ayudaran a obtener, guardar variables, obtener y guardar funciones.
  • Clase árbol
    Es la clase que nos devuelve el análisis sintáctico contiene las instrucciones que deberán ser ejecutadas, la lista de excepción que vamos a reportar y la tabla global para cuando ejecutemos las llamadas a funciones.
  • Clase tipo
    Aquí es donde vamos a definir los tipos que contendrá nuestro interprete.
  • Clase función
    Como cualquier otra instrucción, extiende de la clase AST, y recibe una lista de parámetros y el nombre de la función y una lista de instrucciones.
    Y para la ejecución únicamente necesitamos recorrer la lista de instrucciones ejecutando el método interpretar asociado a cada una de estas.

Creación de funciones nativas

Para funciones nativas es muy sencillo, únicamente debemos extender de la clase función y modificar el comportamiento por cualquier otro que deseemos. Tomamos de ejemplo la función nativa aMayuscula, esta recibe en su constructor los mismos datos que la funciones y únicamente se va a diferenciar en el método interpretar donde le daremos una lógica distinta.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public Object interpretar(Tabla tabla, Arbol tree) {
Simbolo simbolo = tabla.getVariable("toUpper%%parametro1");
if (simbolo == null) {
Excepcion ex = new Excepcion("Semantico", "No se ha encontrado la variable " + this.nombre + ".", fila, columna);
tree.getExcepciones().add(ex);
return ex;
}
if (!simbolo.getTipo().equals(new Tipo(Tipo.Tipos.CADENA))) {
Excepcion ex = new Excepcion("Semantico", "El tipo de los parametros no coinciden.", fila, columna);
tree.getExcepciones().add(ex);
return ex;
}
return (simbolo.getValor() + "").toUpperCase();
}

Ejecución de la entrada
Para ejecutar la entrada debemos instanciar nuestra gramática, esto sucede en la clase UIController, específicamente dentro del método Ejecutar:

1
2
3
Gramatica parser = new Gramatica(new BufferedReader(new StringReader(entrada.getText())));
Arbol arbol = parser.Analizar();
EjecutarInstrucciones(arbol);

Como mencionamos el resultado de ejecutar nuestra gramática nos devolverá un objeto de tipo Arbol, lo enviamos a un método para tratarlo.
En este método pasamos la consola de la interfaz a nuestro árbol para imprimir cosas, crear la tabla global y asignarla a nuestro árbol, crear las funciones nativas.
Luego recorremos por primera vez nuestras instrucciones en búsqueda de funciones para declararlas, pero solamente funciones no otra instrucción.
Luego recorremos por segunda vez nuestras instrucciones y las ejecutamos utilizando el siempre confiable método interpretar obtenido gracias a nuestra clase abstracta AST. Específicamente con el método EjecutarInstrucciones, de la clase UIController:

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
private void EjecutarInstrucciones(Arbol tree) {
tree.setConsola(consola);
tree.setGrupo(groupChart);
Tabla tabla = new Tabla(null);
tree.setGlobal(tabla);
crearNativas(tabla);
// Recorrido 1 para insertar funciones
tree.getInstrucciones().forEach(m -> {
if (m instanceof Funcion) {
tabla.setFuncion((Funcion) m);
}
});
tree.getInstrucciones().forEach(m -> {
if (!(m instanceof Funcion)) {
Object result = m.interpretar(tabla, tree);

if (result instanceof Excepcion) {
((Excepcion) result).imprimir(tree.getConsola());
}
if (result instanceof Detener) {
Excepcion ex = new Excepcion("Semantico", "Sentencia break fuera de ciclo.", m.fila, m.columna);
tree.getExcepciones().add(ex);
ex.imprimir(tree.getConsola());
} else if (result instanceof Retorno) {
Excepcion ex = new Excepcion("Semantico", "Sentencia retorno fuera de funcion.", m.fila, m.columna);
tree.getExcepciones().add(ex);
ex.imprimir(tree.getConsola());
}
}
});

tree.getExcepciones().forEach(m -> {
System.out.println("" + m.toString());
});
}

Iniciando funciones nativas
Para las funciones nativas recordemos deben ser creadas antes de iniciar la ejecución de nuestro interprete. Esta creación de las funciones nativas se encuentra en clase UIController, específicamente en el método crearNativas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void crearNativas(Tabla t){
Tipo tipo = new Tipo(Tipo.Tipos.CADENA);
String nombre = "toUpper";
ArrayList<AST> parametros = new ArrayList<>();
parametros.add(new Declaracion(tipo, "toUpper%%parametro1", null, -1, -1));
ArrayList<AST> instrucciones = new ArrayList<>();
aMayuscula am = new aMayuscula(tipo, nombre, parametros, instrucciones, -1, -1);
t.setFuncion(am);

tipo = new Tipo(Tipo.Tipos.CADENA);
nombre = "pie";
parametros = new ArrayList<>();
parametros.add(new Declaracion(new Tipo(Tipos.LISTA), "pie%%parametro1", null, -1, -1));
parametros.add(new Declaracion(new Tipo(Tipos.LISTA), "pie%%parametro2", null, -1, -1));
parametros.add(new Declaracion(new Tipo(Tipos.CADENA), "pie%%parametro3", null, -1, -1));
instrucciones = new ArrayList<>();
pieChart pc = new pieChart(tipo, nombre, parametros, instrucciones, -1, -1);
t.setFuncion(pc);
}

Como observamos aquí creamos las funciones nativas de toUpper y pie que mencionamos al inicio. Además los parámetros tienen un nombre especial para que no se confundan con otras variables, al terminar de crearlas las agregamos a nuestra lista de funciones.

Una vez explicado esto procedemos a ejecutar nuestro programa, vemos que contamos con un boton para ejecutar y 2 pestañas, 1 de consola y la otra donde se muestran nuestras graficas:

Agregamos y ejecutamos la entrada proporcionada que produce lo siguiente en la sección de la consola:

Y en la sección de grafica:

Con esto damos por finalizado la explicación de este pequeño proyecto.

Conclusiones

  • Como pudimos observar el desarrollo de un interprete es largo, pero a su vez es ordenado.
  • Las gramáticas en javaCC pueden ser poco legibles pero altamente sencillas de crear.
  • Dry, don’t repeat yourself: si usamos esta filosofía podemos reducir la cantidad de código hecho, por ejemplo en nuestra clase abstracta agregamos código común para todas las clases que la heredan, o con las funciones nativas únicamente heredamos de algo que ya existía, hay que tratar en la manera de lo posible reutilizar el código existente.
  • Algo que no se explico porque no era parte del tutorial, pero que es muy útil fue que la interfaz esta hecha en JavaFX, esta nos proporciona una manera más sencilla de utilizar los componentes de la interfaz con nuestra lógica utilizando el modelo MVC.
  • La utilización de estados en JavaCC nos puede ayudar en casos donde necesitemos crear tokens más complejos.

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Pavel Vásquez, 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

×