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

Соберём весь пройденный конвейер в один работающий интерпретатор — начнём с лексера и парсера, строящего AST.

Интерпретатор выражений — программа, которая принимает строку вроде 2 + 3 * 4 и возвращает её числовое значение, проходя все фазы: лексер → парсер → AST → вычисление.

Все детали мы уже разобрали по отдельности. Теперь склеим их. В этом уроке доведём конвейер до построения AST, а вычисление добавим в следующем. Весь код запускается в браузере.

Шаг 1: лексер

Берём знакомый лексер: пропускает пробелы, читает числа, распознаёт операторы и скобки, добавляет EOF.

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

print(tokenize("2 + 3 * 4"))

Вывод:

[('NUMBER', 2), ('PLUS', '+'), ('NUMBER', 3), ('STAR', '*'), ('NUMBER', 4), ('EOF', None)]

Шаг 2: узлы AST

Два класса узлов — число и бинарная операция, как в разделе про AST.

class Num:
    def __init__(self, v): self.value = v
    def __repr__(self): return str(self.value)

class BinOp:
    def __init__(self, op, l, r): self.op, self.left, self.right = op, l, r
    def __repr__(self):
        return "(" + repr(self.left) + self.op + repr(self.right) + ")"

print(BinOp("+", Num(2), BinOp("*", Num(3), Num(4))))

Вывод:

(2+(3*4))

Шаг 3: парсер, строящий AST

Главное отличие от прошлого парсера: функции теперь не просто проверяют синтаксис, а возвращают узлы AST. Грамматика та же: expr → term → factor.

class Num:
    def __init__(self, v): self.value = v
    def __repr__(self): return str(self.value)
class BinOp:
    def __init__(self, op, l, r): self.op, self.left, self.right = op, l, r
    def __repr__(self): return "(" + repr(self.left) + self.op + repr(self.right) + ")"

class Parser:
    def __init__(self, tokens): self.toks = tokens; 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 + ", получил " + tok[0])
        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

toks = [("NUMBER",2),("PLUS","+"),("NUMBER",3),("STAR","*"),("NUMBER",4),("EOF",None)]
print(Parser(toks).expr())

Вывод:

(2+(3*4))

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

Ключевая строка — node = BinOp(op, node, self.term()) в цикле. Она «накапливает» дерево слева направо: для 10 - 3 - 2 сначала получится (10-3), затем ((10-3)-2). Так реализуется левая ассоциативность из урока про приоритет. А приоритет умножения обеспечен тем, что * и / живут в более глубокой функции term.

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

Первая — в цикле перезаписывать node неправильно, теряя уже накопленное дерево. Левый операнд каждой новой операции — это предыдущий результат, а не свежий term.

Вторая — забыть вернуть узел из factor при скобках. После self.eat("RPAREN") нужно вернуть именно внутренний node, а не None.

Итог

• Конвейер собирается из готовых частей: лексер → узлы AST → парсер.
• Парсер рекурсивного спуска теперь возвращает узлы, а не только проверяет синтаксис.
• Накопление node = BinOp(op, node, ...) даёт левую ассоциативность.
• Уровни expr/term/factor обеспечивают приоритет умножения над сложением.