El diseño de compiladores/intérpretes es un campo lleno de retos - con espacio para exploración teórica y también para poner las manos a codificar. Siendo un fanático de Python, trate de implementar algunas ideas que he aprendido sobre compiladores/intérpretes en este bello lenguaje. Como no soy ni un Gurú de Python, ni un experto en compiladores, la implementación puede ser imperfecta. Pero fue ciertamente divertida!.
No se desilusione cuando le digo que no vamos a discutir la implementación de un lenguaje orientado a objetos con recolección automática de basura, que funciona! El lenguaje del que hablo aquí es el único cuando niños, el lenguaje de las expresiones aritméticas. Por ejemplo,
1+2*3-4 1/2+3-4/5 ......
Comenzamos con un programa que leerá una expresión de esta forma y la evaluara directamente. Luego modificaremos este programa para generar una estructura de datos llamada árbol de análisis, la cual entonces será evaluada por algoritmos recursivos. El siguiente paso es generar instrucciones para una maquina virtual usando este árbol de análisis. El ultimo paso es almacenar estas instrucciones de maquina virtual en disco y ejecutarlo con un interpretador cuando sea requerido.
Los lenguajes de programación son a menudo descritos usando un notación compacta y poderosa llamada Gramática libre de contexto. La gramática describe un conjunto de substituciones. Esta es un gramática para expresiones aritméticas:
E ::= T { ADDOP T }
T ::= F { MULOP F }
F ::= 0 | 1 | 2 | 3 | .....
ADDOP ::= + | -
MULOP ::= * | /
Asumimos que E es usado para expresión, T para termino y F para factor. las llaves {} representan 'cero o mas repeticiones'. Al leer la primera producción, deberíamos decir que "Una expresión es un termino, seguido de cero o mas repeticiones de una combinación de un operador de suma y un termino." La tercera producción dice que un factor es cualquiera entre 0 o 1 o 2 o 3 o 4 y así sucesivamente, es decir el conjunto completo de enteros positivos. Toma algún tiempo acostumbrarse a definiciones esotéricas como estas, pero si tenemos un entendimiento básico de las estructuras recursivas, no es muy difícil.
Aquí esta el fuente para un evaluador simple de expresiones en Python. (versión texto)
#----------------Un evaluador simple de expresiones--------------#
import re, string
Inputbuf = []
# Un elemento es o un numero o un símbolo de operador.
# El programa principal lee una linea de la entrada y la almacena
# en un arreglo llamado Inputbuf. La funciones gettoken() regresa
# elementos individuales sacados de este arreglo.
def gettoken():
global Inputbuf
p = re.search('^\W*[\+\-\*/]|^\W*[0-9]+', Inputbuf)
token = p.string[p.regs[0][0]:p.regs[0][1]]
token = string.strip(token)
if token not in ['+', '-', '*', '/']:
token = int(token)
Inputbuf = Inputbuf[p.regs[0][1]:]
return token
# lookahead() busca en la secuencia de entrada y le dice cual
# es el siguiente elemento de entrada.
def lookahead():
global Inputbuf
try:
p = re.search('^\W*[\+\-\*/]|^\W*[0-9]+', Inputbuf)
token = p.string[p.regs[0][0]:p.regs[0][1]]
token = string.strip(token)
if token not in ['+', '-', '*', '/']:
token = int(token)
return token
except:
return None
def factor():
return gettoken()
def term():
e1 = factor()
tmp = lookahead()
while (tmp in ['*', '/']):
gettoken()
if (tmp == '*'):
e1 = e1 * factor()
else:
e1 = e1 / factor()
tmp = lookahead()
return e1
def expression():
e1 = term()
tmp = lookahead()
while (tmp in ['+', '-']):
gettoken()
if (tmp == '+'):
e1 = e1 + term()
else:
e1 = e1 - term()
tmp = lookahead()
return e1
def main():
global Inputbuf
Inputbuf = raw_input()
print expression()
if __name__=='__main__':
main()
Seria bueno rastrear la ejecución del código anterior, para algunas expresiones simples.
El programa anterior simplemente evalúa la expresión dada en aritmética infija. Ahora vamos a modificarlo para producir un árbol de análisis en su lugar. Un árbol de análisis para la expresión 1+2*3 debería verse como esto:
+
/ \
/ \
1 *
/ \
/ \
2 3 Cada nodo del árbol consiste en los siguientes campos:
'op' o 'numero' dependiendo si el nodo es un nodo interno o un nodo hoja.
Un enlace a 'hijo izquierdo' llamado 'left'
Un enlace a 'hijo derecho' llamado 'right'
El árbol es construido desde abajo hacia arriba. La función 'factor()' simplemente crea un nuevo nodo del árbol con un numero en el, inicializa los apuntadores 'left' y 'right' a NULL (nulo), y devuelve el nodo. La función 'expression()' crea un nuevo nodo con un operador '+' o '-' como el valor del campo 'op' y asigna a los apuntadores 'left' y 'right' los valores obtenidos de llamar 'term()'. La función 'term()' trabaja en forma similar.
(versión texto)
#------------------Produce un árbol de análisis---------------#
# gettoken() y lookahead() son iguales que el primer listado.
NULL = 0
import re, string
Inputbuf = []
class Tree:
pass
def factor():
newnode = Tree()
newnode.number = gettoken()
newnode.left = newnode.right = 0
return newnode
def term():
left = factor()
tmp = lookahead()
while (tmp in ['*', '/']):
gettoken()
right = factor()
newnode = Tree()
newnode.op = tmp
newnode.left = left
newnode.right = right
left = newnode
tmp = lookahead()
return left
def expression():
left = term()
tmp = lookahead()
while (tmp in ['+', '-']):
gettoken()
right = term()
newnode = Tree()
newnode.op = tmp
newnode.left = left
newnode.right = right
left = newnode
tmp = lookahead()
return left
def treeprint(ptree):
if (ptree):
try:
print ptree.op
except:
print ptree.number
treeprint(ptree.left)
treeprint(ptree.right)
def main():
global Inputbuf
Inputbuf = raw_input()
ptree = expression()
return ptree
if __name__=='__main__':
ptree = main()
treeprint(ptree)El árbol de análisis el cual hemos creado puede ser fácilmente evaluado escribiendo una función recursiva. Pero nosotros adoptaremos un método diferente. Vamos a generar código para evaluar la expresión en un sencilla maquina hipotética llamada 'maquina con pila de datos'. Las instrucciones que esta maquina tiene son muy simples - 'push' inserte un numero en la pila, 'add' sume dos números, 'mul' multiplique dos números, etc. Así la evaluación de la expresión 1+2*3 termina en el siguiente código:
push 1 push 2 push 3 mul add
Estas instrucciones son almacenadas en un arreglo. 'push', 'mul', 'add', etc. son funciones. Las instrucciones pueden ser directamente ejecutadas pasando a través del arreglo y ejecutando las funciones guardadas en cada elemento del arreglo o pueden ser almacenadas en un archivo del disco (una forma fácil es usar el modulo 'pickle' de Python, aunque es una perdida de espacio). Otro programa puede leer este código en un arreglo y ejecutarlo. El código que he escrito trabaja de esta forma: Si usted corre el programa sin ningún nombre de archivo como argumento, el lee la expresión del teclado, genera código para la maquina virtual en un arreglo y lo ejecuta pasando a través del arreglo. El código es también almacenada en un archivo llamado 'code.out'. Ahora si usted con un argumento como el nombre de archivo 'code-out', el lee las instrucciones desde el archivo y las ejecuta, sin leerlas del teclado.
(versión texto)
import re, string, sys, pickle
# Las funciones no incluidas aquí deberían ser copiadas
# de los listados previos.
NULL = 0
Inputbuf = []
NCODE = 100
NSTACK = 100
Code = []
Stack = [0] * NSTACK
Pc = 0
Stackp = 0
class Tree:
pass
class CodeItem:
pass
def initcode():
global Code
for i in range(0, NCODE):
t = CodeItem()
Code.append(t)
def pushop():
global Stack, Stackp, Code, Pc
Stack[Stackp] = Code[Pc].number
Stackp = Stackp + 1
Pc = Pc + 1
def addop():
global Stack, Stackp, Code, Pc
Stackp = Stackp - 1
right = Stack[Stackp]
Stackp = Stackp - 1
left = Stack[Stackp]
Stack[Stackp] = left + right
Stackp = Stackp + 1
# Defina 'subop', 'mulop' y 'divop' aquí.
def generate(codep, ptree):
try:
# si el campo 'number' no esta presente,
# la siguiente linea genera la excepcion.
n = ptree.number
Code[codep].op = pushop
codep = codep + 1
Code[codep].number = n
codep = codep + 1
return codep
except:
if (ptree.op == '+'):
codep = generate(codep, ptree.left)
codep = generate(codep, ptree.right)
Code[codep].op = addop
codep = codep + 1
return codep
# elif (ptree.op == '-'): Intentaremos escribir aquí el
# código para generar las acciones para '-', '*', '/'.
def eval(ptree): # Genera las instrucciones, luego las ejecuta.
global Pc, Stackp, Code, Stack
Pc = generate(0, ptree)
Code[Pc].op = NULL
Stackp = 0
Pc = 0
while Code[Pc].op != NULL:
tmp = Pc
Pc = Pc + 1
Code[tmp].op()
return Stack[0]
def eval2(): # Directamente ejecuta el código cargado.
global Pc, Stackp, Code, Stack
Stackp = 0
Pc = 0
while Code[Pc].op != NULL:
tmp = Pc
Pc = Pc + 1
Code[tmp].op()
return Stack[0]
def main():
global Inputbuf, Code
try:
f = open(sys.argv[1])
Code = pickle.load(f)
f.close()
result = eval2()
print 'El resultado es:', result
return result
except:
print 'Ningun archivo de código abierto, leyendo desde el teclado.'
initcode()
Inputbuf = raw_input()
ptree = expression()
result = eval(ptree)
f = open('code.out', 'w')
pickle.dump(Code, f)
print 'Codigo escrito en un archivo llamado code.out'
print 'El resultado es:', result
return result
if __name__=='__main__':
result = main()
'generate()' y 'eval()' son las funciones criticas. 'generate()' pasa a través del árbol de la expresión creando el código de la maquina virtual y lo almacena en el arreglo 'Code'. 'eval()' pasa a través del arreglo 'Code' ejecutando las instrucciones, usando el arreglo 'Stack' para mantener los resultados parciales.
Es posible extender el programa anterior para manejar variables e instrucciones de asignación, construcciones de control de flujo como el 'goto' y sentencias 'if', etc. Pronto, usted debería estar construyendo un lenguaje simple similar a Basic.
Viniendo de C, la carencia de Python de ciertas construcciones como el operador ++ es una irritación menor. La falta de declaraciones de tipo en tiempo de compilación también parece tener efectos detrimentos en la legibilidad del código. También pagara por los errores de escritura. Si tiene una variable 'f' de tipo 'struct foo' y 'foo' no tiene un un campo llamado 'next', una asignación a 'f.next' genera en C un error al momento de la compilación, mientras el interpretador de Python con gusto permitirá que la asignación pase derecho.
El libro estándar sobre diseño de compiladores es 'Principios de Diseño de Compiladores' por Aho A.V. y Ullman J.D. La inspiración para este articulo vino de 'La Practica de la Programación, otro excelente libro de Brian Kernighan y Rob Pike. Las funciones 'generate' y 'eval' son versiones en Python del código de este libro. 'Un segundo curso en Ciencias de la Computación con Pascal' por Daniel D. McCracken presenta varios algoritmos, incluyendo un evaluador de expresiones con un estilo muy cautivante.