Este post es una traducción del artículo original de Erez, publicado en
su blog Stories For Sad Robots. El original puede consultarse aquí:
http://blog.erezsh.com/how-to-write-a-calculator-in-70-python-lines-by-writing-a-recursive-descent-parser/
Hay referencias a un artículo anterior, si alguien está interesado un que
lo traduzca también que me deje un comentario y se hará lo que se pueda.
Hace tres meses, escribí un post detallando el proceso de implementar una
calculadora usando una librería de parsing. La respuesta popular, sin embargo,
mostró que la mayoría de los lectores estaban más interesados en ver una
calculadora implementada desde cero, usando solo las "pilas incluidas". Y me
dije ¿Por qué no?
Implementar una calculadora es fácil, si usas algunos trucos específicos de
las expresiones aritméticas, pero usar estos trucos siempre produce lo mismo:
La solución pierde elegancia, no se puede extender y se hace difícil de
comprender intuitivamente. Como parecía un desafío interesante, y puede
conducir a un post útil, he decidido escribirlo usando un analizador
descendente recursivo (recursive descent parser en wikipedia) genérico. Con
la mismo filosofía de la vez anterior, quiero mantener el menor número de
líneas que sea razonable, así que el código estará lleno de trucos y hacks,
pero estarán a un nivel superficial y no serán específicos de la tarea que
tenemos entre manos.
Este artículo es una explicación detallada, paso a paso, de la implementación.
Si quieres pasar directamente al código e intentar entenderlo por tu cuenta,
solo tienes que ir a la última parte. Con suerte una vez leído y entendido el
artículo tendrás una mejor comprensión del funcionamiento interno de un
analizador sintáctico. Luego puedes incluso utilizar una librería de análisis
sintáctico de verdad y ahorrarte todos estos enojosos detalles.
Para entender este artículo, hace falta tener un conocimiento más o menos
completo de Python, y es recomendable tener al menos una idea de lo que son
los analizadores sintácticos o parsers y para que sirven. Si no estás seguro,
te recomiendo que leas el artículo anterior How To Write A Calculator in 50
Python Lines (Without Eval), en el que se explica la gramática que
usaremos aquí.
Paso 1: Tokenizar (Tokenize)
Para poder evaluar una expresión, el primer paso será convertirla en una lista
de símbolos individuales, o tokens. Esta es la parte más fácil, y no es el tema central
de interés en este artículo, así que haremos un poco de trampa para facilitar
las cosas.
En primer lugar, definiremos los tokens (Se observará que falta la definición
de números, eso es porque vamos a considerarlos el valor por defecto):
token_map = {'+':'ADD', '-':'ADD',
'*':'MUL', '/':'MUL',
'(':'LPAR', ')':'RPAR'}
Token = namedtuple('Token', ['name', 'value'])
Y este es el código que usaremos para tokenizar una expresión dada, expr:
split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr)
tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]
La primera línea es un truco que divide la expresión en sus componentes básicos, de
forma que:
'1.2 / ( 11+3)' --> ['1.2', '/', '(', '11', '+', '3', ')']
La siguiente línea asigna nombres a los tokens, para que el parser
pueda reconocerlos por categoría:
['1.2', '/', '(', '11', '+', '3', ')']
-->
[Token(name='NUM', value='1.2'), Token(name='MUL', value='/'),
Token(name='LPAR', value='('), Token(name='NUM', value='11'),
Token(name='ADD', value='+'), Token(name='NUM', value='3'),
Token(name='RPAR', value=')')]
Se asume que cualquier token que no esté en el diccionario token_map
corresponderá a un número. Nuestro tokenizador carece de la virtud de
la validación, que evitaría que se aceptaran cosas que no fueran
números, pero por suerte el evaluador realizará más tarde esta tarea por
nosotros.
Ahora que ya tenemos una lista de tokens, nuestro siguiente paso será parsearlo para
obtener un AST.
Paso 2: Definir la gramática
El parser que usaremos en esta implementación es un versión un tanto ingenua
de parser recursivo descendente (recursive descent parser), que es una
versión simplificada del parser LL (LL parser). Este tipo de parser es el
más fácil de implementar, y de hecho solo nos ocupará unas 14 líneas de
código. Es un tipo de parser descendente, lo que significa que primero intenta
emparejar la regla más alta (como expression), y continua de forma
recursiva intentado emparejar subreglas hasta que alcanza las reglas de más
bajo nivel (como por ejemplo, number). Para expresarlo de otra manera,
mientras que un parser ascendente (Como un LR Parser o Analizador sintáctico LR en
español) intenta de forma gradual "plegar" o "comprimir" tokens y reglas dentro de otras
reglas, hasta que solo quede una, un parser descendente irá expandiendo las
reglas, usando cada vez reglas menos abstractas, hasta el punto en que haya
emparejado completamente los tokens de entrada.
Pero antes de entrar en materia con el parser, hablemos un poco de la
gramática. En el post anterior usamos un parser LR, y se definió la gramática
así (las mayúsculas son tokens):
add: add ADD mul | mul;
mul: mul MUL atom | atom;
atom: NUM | '(' add ')' | neg;
neg: '-' atom;
esta vez usaremos un parser LL, así que definiremos la gramática de esta otra forma:
rule_map = {
'add' : ['mul ADD add', 'mul'],
'mul' : ['atom MUL mul', 'atom'],
'atom': ['NUM', 'LPAR add RPAR', 'neg'],
'neg' : ['ADD atom'],
}
Hay un cambio sutil: Las definiciones recursivas de add y mul
están invertidas. Este detalle es muy importante, y necesita su
aclaración.
La versión LR de esta gramática usa lo que se llama recursividad por la izquierda
(left recursion en inglés). Cuando un parser LL se encuentra con una
llamada recursiva, la ejecuta de inmediato, en un intento de emparejar la
regla que está utilizando, por lo que puede entrar en un bucle infinito.
Incluso parsers LL bastante avanzados como ANTLR se enfrentan a esta problema, aunque
probablemente, en vez de dar vueltas indefinidamente, como hace nuestro
parser de juguete, terminarán con un conveniente mensaje de error .
La recursividad por la izquierda se soluciona de forma sencilla cambiándola
por recursividad por la derecha, que es justo lo que acabamos de hacer con
nuestro sutil cambio. Pero como nada en la vida es fácil cuando tratamos con
parsers, se ha creado otro problema: Mientras que la recursividad por la
izquierda analiza 3-2-1 correctamente como (3-2)-1, la recursividad
por la derecha lo analiza, de forma incorrecta, como 3-(2-1). No sé como
solucionar esto de forma fácil, así que para mantener las cosas sencillas he
optado por mantener la forma incorrecta y resolverlo en una etapa posterior
(véase el paso 4).
Paso 3: Obtener un AST (Árbol de Sintaxis Abstracta)
El algoritmo es sencillo. Vamos a definir una función recursiva que acepta dos
parámetros: El primero es el nombre de la regla que estamos intentando
capturar, y el segundo es una lista de los tokens que nos quedan por
comprobar. Empezaremos con add, -que es la regla más alta- y con la lista
de todos los tokens, y haremos que las sucesivas llamadas recursivas sean cada
vez más específicas. La función retorna una tupla: La correspondencia
encontrada y una lista de los tokens que faltan por comprobar. Con el
propósitos de reducir en lo posible el código, este será capaz de encontrar
tokens también (En los dos casos son cadenas de texto: en un caso con todas
las letras en mayúsculas y en el otro con todas las letras en minúsculas).
Este es el código del parser:
RuleMatch = namedtuple('RuleMatch', ['name', 'matched'])
def match(rule_name, tokens):
if tokens and rule_name == tokens[0].name: # Match a token?
return RuleMatch(tokens[0], tokens[1:])
for expansion in rule_map.get(rule_name, ()): # Match a rule?
remaining_tokens = tokens
matched_subrules = []
for subrule in expansion.split():
matched, remaining_tokens = match(subrule, remaining_tokens)
if not matched:
break # no such luck. next expansion!
matched_subrules.append(matched)
else:
return RuleMatch(rule_name, matched_subrules), remaining_tokens
return None, None # match not found
Las líneas 4-5 comprueban si rule_name es realmente un token, y si coincide
con el token actual. Si lo hace, devuelve la coincidencia, junto con el resto
de los tokens que aun faltan por consumir.
La línea 6 itera sobre las subreglas de rule_name, de forma que cada una
pueda ser analizada recursivamente. Si rule_name es un token, la llamada a
get() devolverá una tupla vacía y el código continuará hasta alcanzar el
return final, que devuelve una tupla sin valores.
Las líneas 9-14 iteran sobre cada elemento de la subregla actual, e intenta
hacerlas coincidir de forma secuencial. Cada iteración intenta consumir tantos
tokens como le sea posible. Si un elemento no coincide, se descarta toda la
regla. Si, por el contrario, se consigue casar todos los elementos, alcanzaremos
la cláusula else y devolveremos nuestra coincidencia para rule_name,
junto con el resto de tokens que faltan por casar.
Vamos a ejecutarlo con 1.2 / ( 11+3) como entrada:
>>> tokens = [Token(name='NUM', value='1.2'), Token(name='MUL', value='/'),
Token(name='LPAR', value='('), Token (name='NUM', value='11'),
Token(name='ADD', value='+'), Token(name='NUM', value='3'),
Token(name='RPAR', value=')')]
>>> match('add', tokens)
(RuleMatch(name='add', matched=[RuleMatch(name='mul',
matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='1.2')]),
Token(name='MUL', value='/'), RuleMatch(name='mul',
matched=[RuleMatch(name='atom', matched=[Token(name='LPAR',
value='('), RuleMatch(name='add', matched=[RuleMatch(name='mul',
matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='11')])]),
Token(name='ADD', value='+'), RuleMatch(name='add',
matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom',
matched=[Token(name='NUM', value='3')])])])]), Token(name='RPAR',
value=')')])])])]), [])
El resultado es una tupla, como era de esperar, y podemos ver que no queda
ningún token para analizar. La coincidencia actual no es fácil de leer, vamos
a representarla gráficamente para que se entienda mejor:
add
mul
atom
NUM '1.2'
MUL '/'
mul
atom
LPAR '('
add
mul
atom
NUM '11'
ADD '+'
add
mul
atom
NUM '3'
RPAR ')'
Esta es la pinta que presenta un AST, en concepto. Es una buena práctica
ejecutar mentalmente el parser, o quizá con la ayuda de papel. Me atrevería a
decir que es necesario si realmente quieres entenderlo. Puedes usar este AST
como referencia para asegurarte de que lo estás haciendo bien.
En este punto, henos escrito un parser capaz de analizar correctamente
operaciones binarias, operadores unitarios, paréntesis y precedencia,
Solo hay una cosa que hace mal, y vamos a arreglarla a continuación.
Paso 4: Post Procesado
El parser no es perfecto en muchos aspectos. El más importante ahora es que no
puede manejar la recursividad por la izquierda, lo que obliga a que la
gramática sea recursiva derecha. En consecuencia, analizar la cadena 8/4/2
nos genera el siguiente AST:
add
mul
atom
NUM 8
MUL '/'
mul
atom
NUM 4
MUL '/'
mul
atom
NUM 2
Si intentamos resolver esta expresión con este árbol, tendríamos que calcular
primero 4/2, que es incorrecto. Algunos parsers LL eligen arreglar la
asociatividad en el árbol. Pero esto llevaría demasiadas líneas ;). En vez de
eso, lo que vamos a hacer en "aplanarlo". El método es sencillo: Para cada regla en el AST que:
- necesite ser arreglada,
- sea una operación binaria (tiene tres subreglas), y
- el operando por la derecha resulta ser la misma regla
entonces "aplanaremos" la última en la primera. Por "aplanar" quiero decir
reemplazar un nodo por sus hijos, en el contexto de su padre. Como nuestro
recorrido por el árbol es DFS post-order, esto significa que empieza por los
bordes del árbol y va progresando hacia la raíz, de forma que los efectos son
acumulativos. Este es el código:
fix_assoc_rules = 'add', 'mul'
def _recurse_tree(tree, func):
return map(func, tree.matched) if tree.name in rule_map else tree[1]
def flatten_right_associativity(tree):
new = _recurse_tree(tree, flatten_right_associativity)
if tree.name in fix_assoc_rules
and len(new)==3
and new[2].name==tree.name:
new[-1:] = new[-1].matched
return RuleMatch(tree.name, new)
Este código convertirá cualquier composición secuencial de sumas o
multiplicaciones en una lista plana (sin mezclar unas con otras). Los
paréntesis rompen la secuencia, por supuesta, así que no se ven afectados.
A partir de aquí se podría reconstruir la estructura en forma asociativa
por la izquierda, usando código como:
def build_left_associativity(tree):
new_nodes = _recurse_tree(tree, build_left_associativity)
if tree.name in fix_assoc_rules:
while len(new_nodes)>3:
new_nodes[:3] = [RuleMatch(tree.name, new_nodes[:3])]
return RuleMatch(tree.name, new_nodes)
Pero no lo vamos a hacer. Queremos reducir el número de líneas de
código, y cambiar el código de evaluación para que pueda manejar listas
conlleva menos líneas que reconstruir el árbol.
Nota
DFS post order: DFS significa "búsqueda en profundidad", y significa que
a medida que recorremos el árbol, se visitan primero los nodos que están en los
niveles inferiores (O, dicho de otra manera, los más profundos). Hay dos tipos
de búsquedas en profundidad, en preorden o postorden. La diferencia entra
las dos es el momento en que se añade un nodo a la salida, antes o después de
visitarlo)
Paso 5: Evaluar
Evaluar el árbol es muy sencillo. Lo único que hace falta es navegar por él de
forma similar a como lo hicimos en el código de post-proceso (Es decir, DFS
post-order) y evaluar cada regla que nos encontramos. Como hemos evaluado
primero los nodos más profundos, cada vez que alcanzamos un nodo de tipo regla,
sus hijos no pueden ser otra cosa más que números. Este es el código:
bin_calc_map = {'*':mul, '/':div, '+':add, '-':sub}
def calc_binary(x):
while len(x) > 1:
x[:3] = [ bin_calc_map[x[1]](x[0], x[2]) ]
return x[0]
calc_map = {
'NUM' : float,
'atom': lambda x: x[len(x)!=1],
'neg' : lambda (op,num): (num,-num)[op=='-'],
'mul' : calc_binary,
'add' : calc_binary,
}
def evaluate(tree):
solutions = _recurse_tree(tree, evaluate)
return calc_map.get(tree.name, lambda x:x)(solutions)
Hemos escrito calc_binary para que evalúe tanto la suma como
la multiplicación (y sus contrapartidas). También evalúa listas, dado
el caso, de manera asociativa por la izquierda. De esa forma resolvemos
el problema que teníamos con nuestra pequeña gramática LL.
Paso 6: El REPL (Read–Eval–Print Loop)
La forma más sencilla posible sería:
if __name__ == '__main__':
while True:
print( calc(raw_input('> ')) )
Que no precisa más explicación. Espero :)
Apéndice: Todo el código en uno: una calculadora en 70 líneas
Este es el código final:
'''A Calculator Implemented With A Top-Down, Recursive-Descent Parser'''
# Author: Erez Shinan, Dec 2012
import re, collections
from operator import add,sub,mul,div
Token = collections.namedtuple('Token', ['name', 'value'])
RuleMatch = collections.namedtuple('RuleMatch', ['name', 'matched'])
token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'}
rule_map = {
'add' : ['mul ADD add', 'mul'],
'mul' : ['atom MUL mul', 'atom'],
'atom': ['NUM', 'LPAR add RPAR', 'neg'],
'neg' : ['ADD atom'],
}
fix_assoc_rules = 'add', 'mul'
bin_calc_map = {'*':mul, '/':div, '+':add, '-':sub}
def calc_binary(x):
while len(x) > 1:
x[:3] = [ bin_calc_map[x[1]](x[0], x[2]) ]
return x[0]
calc_map = {
'NUM' : float,
'atom': lambda x: x[len(x)!=1],
'neg' : lambda (op,num): (num,-num)[op=='-'],
'mul' : calc_binary,
'add' : calc_binary,
}
def match(rule_name, tokens):
if tokens and rule_name == tokens[0].name: # Match a token?
return tokens[0], tokens[1:]
for expansion in rule_map.get(rule_name, ()): # Match a rule?
remaining_tokens = tokens
matched_subrules = []
for subrule in expansion.split():
matched, remaining_tokens = match(subrule, remaining_tokens)
if not matched:
break # no such luck. next expansion!
matched_subrules.append(matched)
else:
return RuleMatch(rule_name, matched_subrules), remaining_tokens
return None, None # match not found
def _recurse_tree(tree, func):
return map(func, tree.matched) if tree.name in rule_map else tree[1]
def flatten_right_associativity(tree):
new = _recurse_tree(tree, flatten_right_associativity)
if tree.name in fix_assoc_rules and len(new)==3 and new[2].name==tree.name:
new[-1:] = new[-1].matched
return RuleMatch(tree.name, new)
def evaluate(tree):
solutions = _recurse_tree(tree, evaluate)
return calc_map.get(tree.name, lambda x:x)(solutions)
def calc(expr):
split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr)
tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]
tree = match('add'<div></div>, tokens)[0]
tree = flatten_right_associativity( tree )
return evaluate(tree)
if __name__ == '__main__':
while True:
print( calc(raw_input('&gt; ')) )
Hasta aquí el artículo original. Si quieres que traduzca el artículo anterior al que
se hace referencia en el texto, déjame una nota en los comentarios.
