Пишем лексер на Python

Соберём настоящий лексер, который превращает строку с выражением в список токенов.

Лексер (сканер) — модуль компилятора, который читает исходный текст символ за символом и выдаёт поток токенов.

Теория позади — пора писать код. Наш лексер примет строку вроде "12 + 3 * 4" и вернёт список токенов. Весь код — на стандартном Python, его можно запустить прямо в браузере.

Идея алгоритма

Лексер держит позицию-указатель внутри строки. На каждом шаге он смотрит на текущий символ и решает: пропустить пробел, собрать число (пока идут цифры), распознать оператор или скобку. Когда строка кончилась — выдать EOF.

Распознавание чисел

Число — это последовательность цифр. Встретив первую цифру, лексер «жадно» читает все следующие цифры подряд, пока они не кончатся, и собирает из них одно число.

def tokenize(text):
    tokens = []
    i = 0
    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
        ops = {"+": "PLUS", "-": "MINUS", "*": "STAR",
               "/": "SLASH", "(": "LPAREN", ")": "RPAREN"}
        if ch in ops:
            tokens.append((ops[ch], ch))
            i += 1
            continue
        raise ValueError("Неизвестный символ: " + ch)
    tokens.append(("EOF", None))
    return tokens

for tok in tokenize("12 + 3 * 4"):
    print(tok)

Вывод:

('NUMBER', 12)
('PLUS', '+')
('NUMBER', 3)
('STAR', '*')
('NUMBER', 4)
('EOF', None)

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

Обратите внимание на конструкцию continue после каждого случая. Она возвращает нас в начало цикла, не давая случайно обработать символ дважды. А внутренний цикл для чисел сдвигает указатель i ровно на длину числа — поэтому 12 становится одним токеном, а не двумя цифрами.

Многосимвольные числа и есть причина, по которой лексер сложнее простого перебора. Для одиночных операторов хватило бы и таблицы, но числа, имена и многосимвольные операторы (==, <=) требуют «заглядывания вперёд».

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

Если встретился символ, который лексер не знает (например, @), мы поднимаем ошибку. Это правильно: лучше честно сообщить о непонятном символе на самом раннем этапе, чем тащить мусор дальше по конвейеру.

def tokenize(text):
    tokens = []
    i = 0
    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
        raise ValueError("Неизвестный символ: " + repr(ch))
    return tokens

try:
    tokenize("2 @ 3")
except ValueError as e:
    print("Ошибка:", e)

Вывод:

Ошибка: Неизвестный символ: '@'

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

Самая частая — забыть сдвинуть указатель i, из-за чего цикл зависает на одном символе вечно. Каждая ветка обязана либо увеличить i, либо обработать его внутри (как чтение числа).

Вторая — обрабатывать число посимвольно, выдавая по токену на каждую цифру. Тогда 12 распадётся на 1 и 2, и арифметика сломается.

Итог

Лексер держит указатель и решает, что делать с текущим символом.
Числа читаются «жадно» — все подряд идущие цифры собираются в один токен.
Неизвестные символы лучше отлавливать сразу с понятной ошибкой.
Каждая ветка обязана продвигать указатель, иначе цикл зависнет.