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:

1. necesite ser arreglada,
2. sea una operación binaria (tiene tres subreglas), y
3. 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.

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

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.