Токены и лексемы

Прежде чем понять структуру программы, нужно разрезать её на минимальные осмысленные кусочки — токены.

Токен — минимальная осмысленная единица кода с типом и значением: число, имя, оператор, скобка, ключевое слово.

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

Токен против лексемы

Эти понятия легко спутать. Лексема — это конкретная подстрока исходного текста (например, символы 123 или while). Токен — это её классификация: тип плюс, при необходимости, значение. Лексема 123 превращается в токен (NUMBER, 123), а лексема + — в токен (PLUS).

Типы токенов

Для арифметического калькулятора достаточно нескольких типов. Оформим их таблицей.

Зачем отбрасывать пробелы

Для арифметики 2+3 и 2 + 3 — одно и то же. Пробелы и переносы строк (в большинстве языков) не несут смысла для парсера, поэтому лексер их просто пропускает. Комментарии тоже отбрасываются на этом этапе — дальше по конвейеру они не нужны.

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

Простейший способ описать токен — именованный кортеж. Он удобен: у него есть поля, но он неизменяемый и лёгкий.

from collections import namedtuple

Token = namedtuple("Token", ["type", "value"])

# вручную разметим выражение "2 + 3"
tokens = [
    Token("NUMBER", 2),
    Token("PLUS", "+"),
    Token("NUMBER", 3),
    Token("EOF", None),
]

for t in tokens:
    print(t.type, "=", t.value)

Вывод:

NUMBER = 2
PLUS = +
NUMBER = 3
EOF = None

Обратите внимание на токен EOF (end of file). Он не соответствует никакому символу, но крайне полезен: парсеру нужен явный признак, что ввод кончился, иначе придётся постоянно проверять длину списка.

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

Первая ловушка — забыть про EOF. Без него парсер не знает, где остановиться, и легко выходит за границы списка токенов.

Вторая — хранить число как строку. Лексема "42" — это текст, а в токене NUMBER логично хранить уже число 42, чтобы дальше не конвертировать его снова и снова. Преобразование типа — естественная работа лексера.

Итог

• Лексема — подстрока исходника, токен — её тип и значение.
• Типы токенов описывают категории: числа, операторы, скобки.
• Пробелы и комментарии лексер отбрасывает.
• Токен EOF явно отмечает конец ввода и упрощает парсер.