Advent of Code, día 18

Parsear y evaluar expresiones: Lenguages y Gramáticas

Parte 1

La parte uno no parecía — a priori — muy complicada. Tenemos que parsear y evaluar la expresión con unas reglas de precedencia distintas a las habituales.

El primer paso es tokenizar la cadena de entrada, es decir dividirla en tokens relevantes para el parseo de la expresión. Observando la entrada, parece que hay espacios entre los números y los operadores, pero no alrededor de los paréntesis.

En lugar de complicarme la vida separando bien los tokens (que se suele llamar analizador léxico o scanner), tomé un pequeño atajo: reemplacé todos los paréntesis por paréntesis con espacios alrededor, y luego hice un split por espacios:

tokens = input.replace('(', ' ( ') \
    .replace(')', ' ) ') \
    .replace('  ', ' ') \         # dos espacios → un espacio
    .strip().split(' ')

Resolví la parte de análisis sintáctico y evaluación en un mismo paso, con una función recursiva… voy parseando números y operadores acumulando el resultado y si encuentro un paréntesis izquierdo, llamo a la misma función recursivamente hasta que encuentre un paréntesis derecho.

def expr(tokens):
    total = None
    operator = None
    while tokens:
        token = tokens.pop(0)
        if token == '*' or token == '+':
            operator = token
        elif token == ')':
            return total
        else:
            if token == '(':
                value = expr(tokens)
            else:
                value = int(token)
            if operator == '+':
                total += value
            elif operator == '*':
                total *= value
            else:
                total = value

    return total
def solve(input):
    return sum(
        expr(line.replace('(', ' ( ')
             .replace(')',' ) ')
             .replace('  ', ' ')
             .strip().split(' '))
        for line in input.strip().split('\n')
    )

Parte 2

La parte 2 tiene más miga. Hay que parsear las expresiones “correctamente” aplicando las reglas de precedencia opuestas a las habituales. Al ver el enunciado pensé en implementar una sencilla gramática para parsear las expresiones, pero no quería utilizar ninguna herramienta ni librería externa.

Las reglas son lo suficientemente sencillas como para implementarlas “a pelo”, y es un ejercicio de programación bastante divertido. Hice una búsqueda en Google de “simple expression grammar” y en el primer resultado encontré esta gramática que me parecía prometedora (reformateando un poco para que quepa):

expression ::= term + expression| term - expression | term
term ::= factor * term | factor / term | factor
factor ::= ( expression ) | float | var

Esta sería una gramática para parsear expresiones sencillas con los operadores básicos +,-,*,/ con la precedencia habitual. En nuestro caso, para alterar las reglas de precedencia deberíamos intercambiar factor por term y * por +. Además podemos eliminar los operadores / y - y la reglavar

expression ::= factor * expression | factor
factor ::= term + factor | term
term::= ( expression ) | num

Para parsear cada línea de la gramática (técnicamente se llaman “producciones”) escribimos una función que intenta consumir los tokens que se corresponden con las reglas y llama a las producciones anidadas. Las funciones son recursivas (term puede llamar a expression).

Por ejemplo, la función factor(tokens) sería:

# factor ::= term + factor | term
def factor(tokens):
    v1 = term(tokens)

    if tokens and tokens[0] == '+':
        tokens.pop(0)
        return v1 + factor(tokens)
    else:
        return v1

Un “factor” siempre empieza por un “term” (en las dos ramas). Por lo tanto, siempre llamamos a la función term(tokens) para parsear el primer “term”.

• Si el siguiente token es un + entonces estamos en la primera rama de la regla (term + factor): consumimos el token + y parseamos el factor siguiente llamando a factor(tokens)
• Si el siguiente token NO es un + (o no nos quedan más tokens) entonces estamos en la segunda rama de la regla (term) y ya hemos terminado de parsear el factor.

El resto de funciones expr() y term() son similares.

El código completo es este:

# expression ::= factor * expression | factor
def expr(tokens):
    v1 = factor(tokens)

    if tokens and tokens[0] == '*':
        tokens.pop(0)
        return v1 * expr(tokens)
    else:
        return v1


# factor ::= term + factor | term
def factor(tokens):
    v1 = term(tokens)

    if tokens and tokens[0] == '+':
        tokens.pop(0)
        return v1 + factor(tokens)
    else:
        return v1


# term::= ( expression ) | num
def term(tokens):
    token = tokens.pop(0)
    if token == '(':
        v = expr(tokens)
        if tokens:
            token = tokens.pop(0)
            assert token == ')'
        return v
    else:
        return int(token)


def top_level(line):
    tokens = line.replace('(', ' ( ') \
         .replace(')', ' ) ') \
         .replace('  ', ' ') \
         .strip().split(' ')
    result = expr(tokens)
    assert len(tokens) == 0, line
    return result


def solve(input):
    return sum(
        top_level(line)
        for line in input.strip().split('\n')
    )

La función top_level() tokeniza cada línea de la entrada y llama a expr() para iniciar el parseo, y devuelve el resultado final.

La gran ventaja de parsear la expresión de esta manera es que las reglas de precedencia, paréntesis, etc… se resuelven solas por la propia estructura de las reglas de la gramática.

El código completo aquí: https://github.com/jabadia/adventOfCode2020/tree/main/d18

NOTA: como de costumbre, la versión “final” del código es bastante más clara y legible que la primera versión… ambas están en github.