Una introducción a los intérpretes: un evaluador lógico

Desde que empecé mi camino en la programación, me ha fascinado cómo hemos logrado la «comunicación» entre humanos y ordenadores. La capacidad de escribir programas en lugar de fabricar distintos dispositivos codificados para un único propósito fue uno de los mayores avances a los que la tecnología se ha enfrentado jamás. Si eres una persona curiosa, esto por supuesto te hace preguntarte «¿pero cómo?». Bueno, ese es un tema increíblemente amplio, interesante y complicado. Pero lo que puedo y voy a enseñarte si sigues leyendo son los fundamentos de un tipo concreto de lenguajes de programación: los lenguajes interpretados.

Para este ejemplo/tutorial se asume que tienes conocimientos moderados de al menos Python, que es el lenguaje que usaremos para ayudar a la mayoría de la gente a entender los conceptos en lugar de centrarnos demasiado en el código, aunque por supuesto estará presente a lo largo de todas las explicaciones.

¿Qué es un evaluador lógico?

Es un intérprete bastante sencillo, ya que simplemente toma una expresión matemática que se evalúa como true o false según la condición que representa; por ejemplo, !A | B solo devolverá true si la variable B o lo contrario de A es true. Incluso este ejemplo aparentemente simple implica:

• Dos variables: A y B.
• Dos operadores: OR lógico | y NOT lógico !.

También añadiremos una impresión bonita en forma de tabla de verdad para visualizar mejor nuestro trabajo. Se vería algo así:

Las dos primeras columnas representan respectivamente los valores de A y B, mientras que la tercera columna muestra el valor resultante tras evaluar la expresión para esa combinación específica de valores.

El intérprete

La mayoría de los intérpretes siguen los mismos tres pasos o partes: el lexer/tokenizador, el parser y el evaluator. Para esto tendremos la siguiente estructura de archivos:

1.2├── evaluator.py3├── lexer.py4├── main.py5└── parser.py

El lexer

Puedes ver el código completo de lexer.py

1. Concepto

La forma más simple de describir este paso es que toma el texto sin procesar de la entrada y lo descompone en las partes reales de tu lenguaje. En este caso, serían variables y operadores, pero en un lenguaje de propósito general también tendría que extraer palabras clave (varios caracteres de texto) y entenderlas como un único token, y otras sutilezas como tratar números o símbolos especiales de forma diferente, etc., etc.

2. Tipos de tokens

Como acabamos de mencionar, necesitamos definir los tokens que existen en nuestro lenguaje; simplemente definiremos un Enum con cada uno de ellos (esto se considera una buena práctica en lugar de repetir cadenas por todas partes):

1class TokenType(Enum):2    LParen = "LParen" # (3    RParen = "RParen" # )4    NotOp = "NotOp" # !5    AndOp = "AndOp" # &6    OrOp = "OrOp" # |7    ImpliesOp = "ImpliesOp" # ->8    BiconditionalOp = "BiconditionalOp" # <->9    Variable = "Variable" # A-Z Upper case10    Eof = "Eof" # The endline character (depends on stdin)

Y también deberíamos definir una clase para la forma de cada token que nos ayude más adelante. Contendrá tanto su tipo como su «lexema» (su forma de cadena):

1@dataclass(frozen=True)2class Token:3    type: TokenType4    lexeme: Optional[str] = None

3. Análisis léxico

Ahora sí, la tokenización propiamente dicha. La clase del lexer contendrá tanto la cadena de entrada (la fórmula lógica) como la posición actual a medida que avanzamos por la fórmula tras cada token (ya que, como habrás notado, hay dos operadores que abarcan dos y tres caracteres respectivamente: Implies y Biconditional).

1class Lexer:2    def __init__(self, input: str) -> None:3        self._input = input4        self._position = 056    def _peek(self, offset: int = 0) -> Optional[str]: ...78    def _advance(self, count: int = 1) -> None: ...910    def lex(self) -> list[Token]: ...

Como ya puedes notar, solo necesitamos usar tres métodos. Los dos privados, _peek() y _advance(), son ayudantes para operaciones que se repiten varias veces a lo largo del análisis léxico real que se realiza en lex().

1. Peek: comprueba si existe el carácter en cierto desplazamiento desde la posición actual y, si es así, lo devuelve. Si no, simplemente devuelve None. Se usa en tokens de más de un carácter, de modo que si encontramos el primer carácter, podemos comprobar si los siguientes coinciden con lo esperado para el token esperado y, si no lo hacen, es un carácter inválido, así que simplemente lanzamos un error.

   1def _peek(self, offset: int = 0) -> Optional[str]:2    if self._position + offset < len(self._input):3        return self._input[self._position + offset]4    return None

2. Advance: simplemente mueve la posición actual hacia delante una cierta cantidad.

   1def _advance(self, count: int = 1) -> None:2    self._position += count

3. Lex: el método principal que realiza el análisis léxico propiamente dicho. Devolverá la lista de tokens que puede usar el parser.

   1def lex(self) -> list[Token]:2    tokens: list[Token] = []3    while self._position < len(self._input):4        current_char = self._input[self._position]5        match current_char:6            ...

   Lo primero que hacemos es crear una lista vacía de tokens y luego recorremos la cadena de entrada, extrayendo cada token individual a esa lista hasta llegar al final, momento en el que devolvemos la lista. Vamos a desglosarlo un poco:

   • Si el carácter es un espacio, simplemente avanzamos la posición y pasamos al siguiente carácter:

     1case char if char.isspace():2    self._advance()

   • Si el carácter es cualquiera de los siguientes: (, ), !, &, |, se realiza el mismo proceso de crear un token de ese tipo y avanzar la posición. Como son tokens de un solo carácter, no hace falta comprobar nada más:

     1case "(":2    tokens.append(Token(TokenType.LParen, "("))3    self._advance()4# ...5# Same for the other characters6# ...7case "|":8    tokens.append(Token(TokenType.OrOp, "|"))9    self._advance()

   • Ahora los cuatro casos interesantes que quedan: -> y <->, así como el caso por defecto y las variables:

     • Si el carácter es -, indica que estamos a punto de encontrarnos con el operador Implies, ¿verdad? Así que, en lugar de crear ese token de inmediato, usamos el método _peek() que te dije que sería útil para ver si efectivamente el siguiente carácter es >. Si lo es, creamos el token y avanzamos la posición. Si no, lanzamos un error útil, ya que tenemos información disponible como nuestra posición y carácter actuales:

       1case "-":2    if self._peek(1) == ">":3       tokens.append(Token(TokenType.ImpliesOp, "->"))4       self._advance(2)5    else:6        raise Exception(7            f"Lexer error: Unexpected character '{current_char}' at position {self._position}. Expected '->'."8        )

     • Si el carácter es <, indica que estamos a punto de encontrarnos con el Biconditional, pero de nuevo tenemos que hacer las comprobaciones oportunas de forma similar a Implies:

       1case "<":2    if self._peek(1) == "-" and self._peek(2) == ">":3        tokens.append(Token(TokenType.BiconditionalOp, "<->"))4        self._advance(3)5    else:6        raise Exception(7            f"Lexer error: Unexpected character '{current_char}' at position {self._position}. Expected '<->'."8        )

     • Si el carácter es cualquiera de A-Z, creamos un token de tipo Variable y avanzamos la posición:

       1case char if "A" <= char <= "Z":2    tokens.append(Token(TokenType.Variable, char))3    self._advance()

     • Ahora, si algún carácter no ha caído en ninguno de los casos anteriores, significa que es un carácter inválido, así que volvemos a lanzar un error:

       1case _:2    raise Exception(3        f"Lexer error: Unexpected character '{current_char}' at position {self._position}."4    )

   • Lo único que queda es añadir el token EOF correspondiente al final de la lista y devolverla:

     1tokens.append(Token(TokenType.Eof))2return tokens

Eso es todo. Ahora hemos creado la lista de tokens que puede usar el parser. Es importante notar que esta forma de comprobar caracteres puede parecer sencilla cuando se presenta así, pero la importancia del método _peek() es bastante significativa. Puedes imaginar cómo en un lexer más complejo, quizá para un lenguaje de propósito general, por ejemplo, tendrías que comprobar líneas enteras o incluso la línea siguiente.

Fíjate también en cómo almacenar correctamente la posición, además de ayudar en el peek, nos permite dar mensajes de error mucho más precisos, que de nuevo serían mucho más complejos para un lenguaje de propósito general. Y observa cómo, por ejemplo, al lanzar un error en los casos de los operadores Implies y Biconditional, sabíamos que el carácter aparentemente fuera de lugar formaba parte de estos tokens, por lo que sugerimos que podría tratarse del error tipográfico cometido.

El parser

Puedes ver el código completo de parser.py

1. Concepto

Este segundo paso tomará la lista de tokens que acabamos de generar y la convertirá en los nodos correspondientes del árbol de sintaxis abstracta (AST), lo que simplemente significa representar los tokens que forman la expresión analizada anidados unos dentro de otros según corresponda en una lista; esto quedará más claro a medida que avancemos. Es la parte más complicada. Tomando el ejemplo que estamos construyendo, hay diferentes tipos de operadores que determinan cosas como el orden en que deben evaluarse.

2. Tipos de nodos del AST

Distintos operadores tienen distintos niveles de precedencia, lo que significa que deben evaluarse primero y, como acabamos de tokenizar la expresión sin procesar, ahora debemos convertirla en la lista ordenada de nodos que puede usarse para evaluar la expresión correctamente. En nuestro ejemplo concreto, la precedencia sería la siguiente:

1. Not: !
2. And: &
3. Or: |
4. Implies: ->
5. Biconditional: <->

Así que, en una expresión como !A & B | C -> D <-> E, el parser debe analizar !A primero, luego &, luego |, y así sucesivamente para construir el AST correctamente. Esto nos lleva al concepto de asociatividad, que determina cómo se agrupan los operadores de la misma precedencia (lo que en este caso solo puede ocurrir si es el mismo operador):

• Asociativo por la izquierda: el operador se evalúa antes que los operandos, agrupados de izquierda a derecha. En la implementación, esto se representa con un bucle while.
  • Ejemplo: A & B & C -> And(left=And(left=Var(name='A'), right=Var(name='B')), right=Var(name='C'))
• Asociativo por la derecha: el operador se evalúa después de los operandos, agrupados de derecha a izquierda. En la implementación, esto se representa con un condicional en su lugar.
  • Ejemplo: A -> B -> C -> Implies(left=Var(name='A'), right=Implies(left=Var(name='B'), right=Var(name='C')))

Los operadores asociativos por la derecha son Not e Implies, mientras que los asociativos por la izquierda son And, Or y Biconditional.

Además, como habrás notado, todos los operadores excepto Not tienen una rama izquierda y otra derecha en el árbol de nodos, así que también deberíamos definir una clase para la forma de cada nodo (todas heredando de Expression para que puedan tratarse como tal) que nos ayude más adelante. Contendrán ambas ramas o, en el caso de Variables y Not, simplemente el nombre y la expresión interna respectivamente:

1class Expression:2    pass34@dataclass(frozen=True)5class Var(Expression):6    name: str78@dataclass(frozen=True)9class Not(Expression):10    expression: Expression1112@dataclass(frozen=True)13class And(Expression):14    left: Expression15    right: Expression1617@dataclass(frozen=True)18class Or(Expression):19    left: Expression20    right: Expression2122@dataclass(frozen=True)23class Implies(Expression):24    left: Expression25    right: Expression2627@dataclass(frozen=True)28class Biconditional(Expression):29    left: Expression30    right: Expression

3. Análisis sintáctico

Igual que hicimos con el lexer, vamos a echar un vistazo a cada uno de los métodos auxiliares de la clase Parser, aunque es bastante más complejo debido a la recursividad mutua entre los distintos métodos _parse_*(). Veamos primero los auxiliares:

1. Consume: como ahora tenemos tokens individuales, nos moveremos linealmente por la lista. Este método consumirá el siguiente token y lo devolverá, lanzando un error si no es del tipo esperado:

   1def _consume(self, expected_type: TokenType) -> None:2    if self._peek().type == expected_type:3        self._position += 14    else:5        raise Exception(6            f"Parser error: Expected {expected_type} but found {self._peek().type}"7        )

2. Peek: similar al método _peek() del lexer, aunque este método solo comprobará la posición actual y no la siguiente. Devolverá el token en la posición actual si existe, y EOF en caso contrario:

   1def _peek(self) -> Optional[Token]:2    if self._position < len(self._tokens):3        return self._tokens[self._position]4    return Token(TokenType.Eof)

3. Parse: este es el método principal que realiza el análisis sintáctico propiamente dicho. Devolverá la expresión del AST que puede usar el evaluador. Funciona usando un montón de ayudantes privados de análisis para cada tipo de token que son mutuamente recursivos uno tras otro. Lo que esto significa es que, siguiendo el orden de precedencia, cada operación de análisis llamará a la siguiente hasta el final de la expresión:

   1parse()2└── _parse_biconditional()3    └── _parse_implies()4        └── _parse_or()5            └── _parse_and()6                └── _parse_not()7                    └── _parse_primary()

   Esto es un poco contraintuitivo, ya que puede parecer «al revés», pero es el orden correcto. El proceso de análisis comienza con el operador de menor precedencia (_parse_biconditional), que llama a la función del operador de precedencia inmediatamente superior (_parse_implies), y así sucesivamente hasta llegar a los operadores de mayor precedencia (_parse_primary y _parse_not). Este enfoque de descenso recursivo maneja naturalmente el orden de las operaciones delegando en funciones para expresiones de mayor precedencia.

   1def _parse_primary(self) -> Expression:2     token = self._peek()3     if token.type == TokenType.Variable:4         self._consume(TokenType.Variable)5         if token.lexeme is None:6             raise Exception("Parser error: Variable name is missing.")7         return Var(token.lexeme)8     elif token.type == TokenType.LParen:9         self._consume(TokenType.LParen)10         expr = self._parse_biconditional()11         self._consume(TokenType.RParen)12         return expr13     else:14         raise Exception(15             f"Parser error: Expected variable or '(' but found {token.type}"16         )1718 def _parse_not(self) -> Expression:19     if self._peek().type == TokenType.NotOp:20         self._consume(TokenType.NotOp)21         return Not(self._parse_not())22     return self._parse_primary()2324 def _parse_and(self) -> Expression:25     left = self._parse_not()26     while self._peek().type == TokenType.AndOp:27         self._consume(TokenType.AndOp)28         right = self._parse_not()29         left = And(left, right)30     return left3132 def _parse_or(self) -> Expression:33     left = self._parse_and()34     while self._peek().type == TokenType.OrOp:35         self._consume(TokenType.OrOp)36         right = self._parse_and()37         left = Or(left, right)38     return left3940 def _parse_implies(self) -> Expression:41     left = self._parse_or()42     if self._peek().type == TokenType.ImpliesOp:43         self._consume(TokenType.ImpliesOp)44         right = self._parse_implies()45         left = Implies(left, right)46     return left4748 def _parse_biconditional(self) -> Expression:49     left = self._parse_implies()50     while self._peek().type == TokenType.BiconditionalOp:51         self._consume(TokenType.BiconditionalOp)52         right = self._parse_implies()53         left = Biconditional(left, right)54     return left5556 def parse(self) -> Expression:57     expr = self._parse_biconditional()58     if self._peek().type != TokenType.Eof:59         raise Exception("Parser error: Unexpected tokens remaining.")60     return expr

El evaluador

Puedes ver el código completo de parser.py

1. Concepto

¡Enhorabuena! Ya hemos repasado básicamente toda la implementación. Ahora solo tenemos que evaluar la expresión ya analizada e imprimir el resultado. No entraremos en los detalles de la impresión, pero evaluar es bastante fácil, ya que tenemos el AST. Dado que ya habremos creado las distintas asignaciones, es decir, las diferentes combinaciones posibles de las variables dadas, al generar la tabla (si tienes curiosidad, mira el código fuente), podemos simplemente crear un método evaluate() general que tome la expresión y las variables y devuelva el resultado de cada cálculo lógico.

2. Evaluar el AST

Para lograrlo, es tan simple como hacer coincidencia de patrones con las distintas ramas del árbol y aplicar cada operación de forma recursiva.

1class Evaluator:2    def __init__(self, assignments: dict[str, bool]) -> None:3        self._assignments = assignments45    def evaluate(self, expr: Expression) -> bool:6        match expr:7            case Var(name):8                return self._assignments[name]9            case Not(expression):10                return not self.evaluate(expression)11            case And(left, right):12                return self.evaluate(left) and self.evaluate(right)13            case Or(left, right):14                return self.evaluate(left) or self.evaluate(right)15            case Implies(left, right):16                return not self.evaluate(left) or self.evaluate(right)17            case Biconditional(left, right):18                return self.evaluate(left) == self.evaluate(right)19            case _:20                raise Exception("Evaluation error: Unknown expression type.")

En el improbable caso de que un error haya llegado hasta este punto del proceso, simplemente lo lanzaremos con un mensaje adecuado, como siempre. Habrás notado que este es un patrón que se repite constantemente en todo el código: comprobaciones por todas partes y mensajes de error lo más informativos posible, aunque ningún error debería poder llegar hasta aquí.

Puedes ver el archivo principal para la interacción real con el usuario y el acoplamiento de las tres partes juntas main.py solo por curiosidad, pero ya hemos cubierto toda la implementación del intérprete.

Conclusión

¡Hemos llegado al final del tutorial! Y aunque no es el ejemplo más complejo, sigue mostrando el poder del intérprete y cómo puede usarse para evaluar cualquier tipo de cálculo.

Como siempre, gracias por leer y, si tienes alguna pregunta o comentario, no dudes en contactarme en cualquiera de mis redes sociales; están en mi Link Tree. Siempre estoy abierto a las críticas, tal como espero que hayas hecho al leer esto; siempre intento aprender y mejorar.

Patrocinar

Si te ha gustado esta entrada y te ha resultado útil, considera apoyarme a través de cualquiera de los canales que aparecen en mi página de patrocinadores (enlazada con el botón justo debajo).