Проект: интерпретатор арифметики, часть 2

Достроим интерпретатор: добавим вычисление AST и соберём всё в одну функцию, которая считает любое выражение.

Вычислитель (evaluator) — финальная фаза интерпретатора: рекурсивный обход AST, превращающий дерево в число.

В прошлом уроке мы получили AST. Осталось его вычислить — мы это уже умеем из урока про обход дерева. Теперь соберём полный конвейер в одну удобную функцию calc(text).

Полный интерпретатор

Ниже — весь конвейер целиком: лексер, узлы, парсер и вычислитель. Это самодостаточная программа, считающая выражения с приоритетом и скобками.

def tokenize(text):
    tokens, i = [], 0
    ops = {"+": "PLUS", "-": "MINUS", "*": "STAR",
           "/": "SLASH", "(": "LPAREN", ")": "RPAREN"}
    while i < len(text):
        ch = text[i]
        if ch == " ": i += 1; continue
        if ch.isdigit():
            num = ""
            while i < len(text) and text[i].isdigit():
                num += text[i]; i += 1
            tokens.append(("NUMBER", int(num))); continue
        if ch in ops:
            tokens.append((ops[ch], ch)); i += 1; continue
        raise ValueError("Неизвестный символ: " + ch)
    tokens.append(("EOF", None)); return tokens

class Num:
    def __init__(self, v): self.value = v
class BinOp:
    def __init__(self, op, l, r): self.op, self.left, self.right = op, l, r

class Parser:
    def __init__(self, t): self.toks = t; self.pos = 0
    def peek(self): return self.toks[self.pos]
    def eat(self, t):
        tok = self.toks[self.pos]
        if tok[0] != t: raise SyntaxError("Ждал " + t)
        self.pos += 1; return tok
    def expr(self):
        node = self.term()
        while self.peek()[0] in ("PLUS", "MINUS"):
            op = self.eat(self.peek()[0])[1]
            node = BinOp(op, node, self.term())
        return node
    def term(self):
        node = self.factor()
        while self.peek()[0] in ("STAR", "SLASH"):
            op = self.eat(self.peek()[0])[1]
            node = BinOp(op, node, self.factor())
        return node
    def factor(self):
        if self.peek()[0] == "NUMBER":
            return Num(self.eat("NUMBER")[1])
        self.eat("LPAREN"); node = self.expr(); self.eat("RPAREN")
        return node

def evaluate(node):
    if isinstance(node, Num): return node.value
    a, b = evaluate(node.left), evaluate(node.right)
    return {"+": a + b, "-": a - b, "*": a * b, "/": a / b}[node.op]

def calc(text):
    ast = Parser(tokenize(text)).expr()
    return evaluate(ast)

for expr in ["2 + 3 * 4", "(2 + 3) * 4", "10 - 3 - 2", "100 / 5 / 2"]:
    print(expr, "=", calc(expr))

Вывод:

2 + 3 * 4 = 14
(2 + 3) * 4 = 20
10 - 3 - 2 = 5
100 / 5 / 2 = 10.0

Поздравляем — это полноценный интерпретатор. Он правильно обрабатывает приоритет (14, а не 20), скобки (20) и левую ассоциативность (5, а не 9).

Как работает под капотом

Функция calc — это весь конвейер в трёх вызовах: tokenize даёт токены, Parser.expr строит AST, evaluate обходит его и возвращает число. Каждый этап изолирован: можно подменить вычислитель на генератор байткода — и тот же парсер будет компилировать, а не интерпретировать. Это и есть сила разделения на фазы.

Обработка ошибок

Хороший интерпретатор не падает с непонятной трассировкой, а сообщает внятную ошибку. Добавим аккуратную обёртку.

def safe_calc(text, calc_fn):
    try:
        return "= " + str(calc_fn(text))
    except (ValueError, SyntaxError, ZeroDivisionError) as e:
        return "Ошибка: " + str(e)

# имитируем calc через eval только для демонстрации обёртки
def demo(text):
    if "@" in text: raise ValueError("Неизвестный символ: @")
    if text.count("(") != text.count(")"): raise SyntaxError("Ждал RPAREN")
    return 14

print("2 + 3 * 4", safe_calc("2 + 3 * 4", demo))
print("2 @ 3   ", safe_calc("2 @ 3", demo))
print("(2 + 3  ", safe_calc("(2 + 3", demo))

Вывод:

2 + 3 * 4 = 14
2 @ 3    Ошибка: Неизвестный символ: @
(2 + 3   Ошибка: Ждал RPAREN

Частые ошибки

Первая — не проверять, что после разбора достигнут EOF. Выражение 2 + 3) с лишней скобкой наш парсер примет лишь частично; в боевом коде стоит после expr вызвать eat("EOF"), чтобы поймать «хвост».

Вторая — ловить все ошибки голым except:. Лучше перечислять конкретные типы (ValueError, SyntaxError, ZeroDivisionError), иначе можно случайно проглотить баг в самом интерпретаторе.

Итог

• Полный интерпретатор — это tokenize → Parser.expr → evaluate в трёх шагах.
• Разделение на фазы позволяет подменить вычислитель на кодогенератор без правки парсера.
• Корректно обрабатываются приоритет, скобки и левая ассоциативность.
• Понятные ошибки и проверка EOF отличают учебный код от боевого.