Лексический анализ: токены, регулярные языки, свой лексер с нуля

Компилятор получает на вход ровно одну вещь: последовательность байтов. Никаких «функций», «переменных» и «операторов» в файле нет — есть 0x6c 0x65 0x74 0x20 0x78. Всё остальное компилятор придумывает сам, и первый шаг этого придумывания называется лексическим анализом.

Аналогия работает точнее, чем кажется: вы читаете эту строку не по буквам — глаз режет текст на слова, мозг собирает из слов фразы. Прочитайте лексическийанализрежеттекстнатокены: вы всё поймёте, но медленнее, потому что придётся одновременно искать границы слов и понимать смысл. Компиляторы разделяют эти работы по той же причине.

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

Что такое токен

Токен — это лексема плюс её классификация плюс её место в исходнике. Все три части обязательны.

• Тип (kind) — IDENT, INT, LET, PLUS. Это буква алфавита, на котором дальше работает парсер: для него x, counter и фиб — один и тот же символ IDENT. Именно эта потеря информации делает грамматику конечной.
• Значение — то, что нужно сверх типа: число 41 для INT, имя для IDENT, раскодированный текст для STRING. Для PLUS значения нет, тип уже всё сказал.
• Спан (span) — полуинтервал [start, end) в исходнике. Единственный мост назад к тексту: из него получаются подчёркивания в ошибках, подсветка в IDE, автоправки, source map, переход к определению.

Всё, что между токенами — пробелы, переводы строк, комментарии — называется тривией. Для парсера её не существует. Для форматтера, линтера и IDE она критична, и это первое место, где надо осознанно решить: выбрасывать или сохранять.

Обратите внимание на последний токен: EOF. Явный токен конца входа убирает из парсера десятки проверок «а не кончился ли вход» — после EOF поток бесконечно возвращает EOF, и любая ветка увидит «не тот токен» вместо выхода за границу массива.

Почему это отдельная фаза, а не часть парсера

Формально ничто не мешает парсеру читать символы напрямую — так работают scannerless-парсеры (PEG, GLL, SGLR). Но почти везде лексер отдельный, и причин четыре.

Сокращение входа. Замер на исходнике Mini размером 989 КБ: 280 001 токен, то есть один токен примерно на 3,5 байта. Парсер — самая тяжёлая часть фронтенда — работает со входом вчетверо короче и с целыми числами вместо строк.

Чистая грамматика. Если пробелы обрабатывает парсер, каждое правило обрастает «здесь может быть пробел или комментарий», и грамматика раздувается в разы.

Разные инструменты для разных задач. «Идентификатор — буква, потом буквы и цифры» распознаётся конечным автоматом за один проход без памяти. «Скобки сбалансированы» так не распознаётся в принципе. Смешивать значит платить за самую дорогую машину всегда.

Переиспользование. Один лексер обслуживает компилятор, подсветку, форматтер, поиск по коду и языковой сервер; подсветке парсер не нужен вовсе.

Где эта граница протекает

Разделение «лексер регулярен, парсер контекстно-свободен» в реальных языках нарушается, и знать эти места полезно — они будут кусаться и в вашем языке.

• Lexer hack в C. (A) * b — умножение или приведение указателя? Зависит от того, объявлен ли A через typedef, поэтому лексер C спрашивает таблицу символов, выдавать IDENTIFIER или TYPEDEF_NAME (описание).
• / в JavaScript — деление или начало регулярки? Спецификация решает через goal symbols: парсер сообщает лексеру, какой набор правил применять (ECMA-262).
• Отступы в Python. Лексер держит стек уровней и выдаёт синтетические INDENT/DEDENT. Стек — уже не конечный автомат (модуль tokenize).
• Точка с запятой в Go вставляется лексером, если строка кончилась подходящим токеном (спецификация) — дешёвое правило на уровне токенов вместо сложного правила в грамматике.
• Вложенные комментарии и raw-строки Rust. /* /* */ */ требует счётчика глубины, r#"..."# — запоминания числа решёток. Оба нерегулярны и оба решаются одним счётчиком.

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

Теория: почему регулярных языков достаточно

Регулярные языки — нижняя ступень иерархии Хомского, подробно разобранной в статье «Автоматы и формальные языки». Их распознаёт детерминированный конечный автомат (ДКА): конечное множество состояний, переход по каждому символу, никакой дополнительной памяти. Отсюда три следствия.

1. O(n) по времени, O(1) по памяти. Один проход, один переход на символ, отката нет — быстрее, чем просто прочитать вход, нельзя.
2. Класс замкнут относительно объединения и конкатенации, поэтому правила для чисел и для идентификаторов объединяются в один автомат — это и делает генератор лексеров.
3. Считать автомат не умеет. Нет памяти — нет глубины вложенности: регулярным выражением не распознать сбалансированные скобки, HTML или вложенные комментарии. Следствие леммы о накачке, а не недоработка движков.

Путь от регулярки к сканеру — цепочка регулярка → НКА (построение Томпсона) → ДКА (построение подмножеств) → минимальный ДКА. Построение Томпсона (CACM 1968, статья) даёт НКА размера O(m); детерминизация в худшем случае даёт 2^m состояний, но для языков программирования это сотни состояний, а не миллионы; минимизация Хопкрофта — O(k log k). Разбор всей цепочки — у Расса Кокса, «Regular Expression Matching Can Be Simple And Fast».

Предупреждение. Регулярки в PCRE, Python re, JS и Java — не автоматы, а бэктрекинг-движки с экспоненциальным временем на патологическом входе (ReDoS). Для лексера это не смертельно, но вложенных квантификаторов вида (a+)+ в нём быть не должно.

Вот автомат нашего лексера — не абстрактный, а тот, который мы сейчас запишем кодом. Из состояния Minus выход зависит от следующего символа: это и есть ядро разрешения неоднозначностей.

Максимальное поглощение и разрешение конфликтов

Два правила разрешают почти все неоднозначности лексики; они встроены в flex, re2c, ANTLR и в любой рукописный лексер.

Правило 1: максимальное поглощение (maximal munch). Из всех подходящих правил выигрывает то, что съедает больше символов. == — это EQ, а не два ASSIGN; -> — ARROW, а не MINUS и GT; 1234 — одно число, а не четыре.

Правило 2: при равной длине выигрывает правило, объявленное раньше. Так ключевые слова побеждают идентификаторы. На практике ключевые слова обычно не делают правилами вовсе: читают идентификатор целиком, потом ищут в хеш-таблице — быстрее и невозможно забыть новое слово.

Максимальное поглощение требует запоминания последнего принимающего состояния: автомат идёт вперёд, пока может, и при застревании откатывается к последней позиции, где вход был допустимым токеном. В худшем случае это даёт O(n·m); flex умеет предупреждать о таких правилах, но в языках программирования отката почти нет — токены короткие.

Алгоритм одного шага лексера целиком:

Из состояния ошибки лексер не выходит: записывает диагностику и двигается дальше.

Модель данных: что возвращает лексер

Три решения здесь стоит проговорить.

Храним смещения, а не строку и колонку. Пара (line, col) — два лишних поля, которые надо поддерживать при каждом символе. Смещение получается из курсора само, а строка и колонка восстанавливаются за O(log n) бинарным поиском по таблице начал строк — так устроены SourceLocation в Clang и Span в rustc.

Не копируем текст лексемы: token.text(src) — срез исходника. На миллионе токенов разница между срезом и копией — десятки мегабайт и столько же аллокаций.

ERROR — тип токена, а не исключение. Ошибочный фрагмент остаётся в потоке со своим спаном, и парсер с IDE видят дырку ровно там, где она есть.

Свой лексер с нуля: язык Mini

Пишем на Python — читаемо и запускается везде. Цель — вот этот вход:

fn fib(n: Int) -> Int {
  if n <= 1 { return n; }
  return fib(n - 1) + fib(n - 2);
}

Каркас и главный цикл

from dataclasses import dataclass
from enum import Enum, auto

class T(Enum):
    INT = auto(); IDENT = auto(); STRING = auto(); LET = auto(); FN = auto()
    IF = auto(); ELSE = auto(); RETURN = auto(); TRUE = auto(); FALSE = auto()
    PLUS = auto(); MINUS = auto(); STAR = auto(); SLASH = auto(); ASSIGN = auto()
    EQ = auto(); NE = auto(); LT = auto(); LE = auto(); GT = auto(); GE = auto()
    ARROW = auto(); COLON = auto(); SEMI = auto(); COMMA = auto(); LPAREN = auto()
    RPAREN = auto(); LBRACE = auto(); RBRACE = auto(); EOF = auto(); ERROR = auto()

# Ключевые слова — таблица, а не отдельные правила лексера (правило 2).
KEYWORDS = {"let": T.LET, "fn": T.FN, "if": T.IF, "else": T.ELSE,
            "return": T.RETURN, "true": T.TRUE, "false": T.FALSE}
SIMPLE = {"+": T.PLUS, "*": T.STAR, "/": T.SLASH, ":": T.COLON, ";": T.SEMI,
          ",": T.COMMA, "(": T.LPAREN, ")": T.RPAREN, "{": T.LBRACE, "}": T.RBRACE}

@dataclass(frozen=True)
class Token:
    kind: T
    start: int              # смещение первого символа лексемы
    end: int                # смещение за последним: полуинтервал [start, end)
    value: object = None

    def text(self, src: str) -> str:
        return src[self.start:self.end]        # срез, а не копия

@dataclass
class LexError:
    message: str
    start: int
    end: int

class Lexer:
    def __init__(self, src: str) -> None:
        self.src, self.pos, self.start = src, 0, 0
        self.errors: list[LexError] = []

    def _at_end(self) -> bool:
        return self.pos >= len(self.src)

    def _peek(self, offset: int = 0) -> str:
        # "\0" вместо конца входа — тот же приём, что и токен EOF:
        # избавляет от проверки границы в каждом условии
        i = self.pos + offset
        return self.src[i] if i < len(self.src) else "\0"

    def _advance(self) -> str:
        self.pos += 1
        return self.src[self.pos - 1]

    def _match(self, expected: str) -> bool:
        """Условное поглощение — ядро maximal munch для двухсимвольных операторов."""
        if self._peek() == expected:
            self.pos += 1
            return True
        return False

    def _tok(self, kind: T, value: object = None) -> Token:
        return Token(kind, self.start, self.pos, value)

    def _error(self, message: str) -> Token:
        self.errors.append(LexError(message, self.start, self.pos))
        return self._tok(T.ERROR, self.src[self.start:self.pos])

    def tokens(self):
        """Ленивый поток; последним всегда идёт EOF."""
        while True:
            tok = self.next_token()
            yield tok
            if tok.kind is T.EOF:
                return

    def next_token(self) -> Token:
        self._skip_trivia()
        self.start = self.pos
        if self._at_end():
            return self._tok(T.EOF)
        ch = self._advance()
        if ch.isdigit():                       # порядок ветвей — по частоте
            return self._number()
        if ch.isalpha() or ch == "_":
            return self._ident()
        if ch == '"':
            return self._string()
        if ch in SIMPLE:
            return self._tok(SIMPLE[ch])
        # Максимальное поглощение: сначала пробуем двухсимвольный вариант.
        if ch == "=":
            return self._tok(T.EQ if self._match("=") else T.ASSIGN)
        if ch == "<":
            return self._tok(T.LE if self._match("=") else T.LT)
        if ch == ">":
            return self._tok(T.GE if self._match("=") else T.GT)
        if ch == "-":
            return self._tok(T.ARROW if self._match(">") else T.MINUS)
        if ch == "!":
            if self._match("="):
                return self._tok(T.NE)
            return self._error("одиночный '!' в Mini не определён")

        return self._error(f"недопустимый символ {ch!r}")

Порядок ветвлений — не стиль, а частотность: цифры и буквы встречаются чаще всего. В компиляторах на C и Rust ту же роль играет таблица классов символов на 256 элементов: один индексированный доступ вместо цепочки сравнений.

Тривия, включая вложенные комментарии

    def _skip_trivia(self) -> None:
        while not self._at_end():
            ch = self._peek()
            if ch in " \t\r\n":
                self.pos += 1
            elif ch == "/" and self._peek(1) == "/":
                while not self._at_end() and self._peek() != "\n":
                    self.pos += 1
            elif ch == "/" and self._peek(1) == "*":
                self._block_comment()
            else:
                return

    def _block_comment(self) -> None:
        """Один счётчик — и мы вышли за пределы регулярного языка."""
        opened_at, depth = self.pos, 0
        while not self._at_end():
            if self._peek() == "/" and self._peek(1) == "*":
                self.pos += 2; depth += 1
            elif self._peek() == "*" and self._peek(1) == "/":
                self.pos += 2; depth -= 1
                if depth == 0:
                    return
            else:
                self.pos += 1
        self.errors.append(LexError("незакрытый блочный комментарий", opened_at, self.pos))

depth — та самая память, которой у конечного автомата нет. Восемь строк вместо стека парсера: ровно тот прагматичный компромисс, о котором шла речь выше.

Числа, идентификаторы, строки

    ESCAPES = {"n": "\n", "t": "\t", '"': '"', "\\": "\\"}

    def _number(self) -> Token:
        while self._peek().isdigit() or self._peek() == "_":
            self.pos += 1
        raw = self.src[self.start:self.pos]
        if self._peek().isalpha():
            # 12abc — почти наверняка опечатка. Съедаем всю склейку целиком,
            # чтобы не породить лавину из ERROR + IDENT.
            while self._peek().isalnum() or self._peek() == "_":
                self.pos += 1
            return self._error("цифра не может переходить в букву")
        if raw.endswith("_"):
            return self._error("число не может заканчиваться на '_'")
        return self._tok(T.INT, int(raw.replace("_", "")))

    def _ident(self) -> Token:
        while self._peek().isalnum() or self._peek() == "_":
            self.pos += 1
        word = self.src[self.start:self.pos]
        kind = KEYWORDS.get(word, T.IDENT)     # ключевое слово побеждает идентификатор
        return self._tok(kind, word if kind is T.IDENT else None)

    def _string(self) -> Token:
        chunks: list[str] = []
        while self._peek() not in ('"', "\n", "\0"):
            ch = self._advance()
            if ch != "\\":
                chunks.append(ch)
                continue
            if self._peek() in ("\n", "\0"):
                break
            esc = self._advance()
            if esc in self.ESCAPES:
                chunks.append(self.ESCAPES[esc])
            else:                              # сообщаем и продолжаем разбор
                self.errors.append(LexError(
                    f"неизвестная escape-последовательность '\\{esc}'", self.pos - 2, self.pos))
                chunks.append(esc)
        if self._peek() != '"':
            return self._error("незакрытая строка: нет закрывающей кавычки до конца строки")
        self.pos += 1                          # закрывающая кавычка
        return self._tok(T.STRING, "".join(chunks))

Запрет на перенос строкового литерала — не техническое ограничение, а дизайн: незакрытая кавычка иначе съедает половину файла и порождает каскад бессмысленных ошибок. Для многострочных литералов все современные языки заводят отдельный синтаксис.

Запуск

src = ('fn fib(n: Int) -> Int {\n'
       '  if n <= 1 { return n; }\n'
       '  return fib(n - 1) + fib(n - 2);\n'
       '}\n')
for t in list(Lexer(src).tokens())[:10]:
    print(t.kind.name, repr(t.text(src)), (t.start, t.end))

FN     'fn'   (0, 2)      COLON  ':'   (8, 9)
IDENT  'fib'  (3, 6)      IDENT  'Int' (10, 13)
LPAREN '('    (6, 7)      RPAREN ')'   (13, 14)
IDENT  'n'    (7, 8)      ARROW  '->'  (15, 17)

36 токенов вместе с EOF, ноль ошибок. -> не распалось на - и >, <= — на < и =, а fn, if, return стали ключевыми словами. Int остался обычным идентификатором: имена типов разберёт семантический анализ, лексеру о них знать незачем.

Сложность. Время — O(n) от числа символов: каждый символ читается один раз, _peek не двигает курсор, отката нет. Память — O(1) на токен сверх выхода (лексемы это срезы) и O(t) на весь поток, где t ≈ n/3,5.

Ошибки: лексер, которым не больно пользоваться

Первое правило: лексер не имеет права падать на первой ошибке. IDE вызывает его на каждое нажатие клавиши, и половину времени код в редакторе синтаксически неверен; лексер с исключением делает автодополнение невозможным. Второе: ошибка — это спан плюс сообщение, а строка и колонка восстанавливаются индексом.

from bisect import bisect_right

class LineIndex:
    """Смещение -> (строка, колонка) за O(log n), память O(числа строк)."""

    def __init__(self, src: str) -> None:
        self.starts = [0] + [i + 1 for i, ch in enumerate(src) if ch == "\n"]

    def locate(self, offset: int) -> tuple[int, int]:
        line = bisect_right(self.starts, offset) - 1
        return line + 1, offset - self.starts[line] + 1

def render_error(src: str, err: LexError) -> str:
    idx = LineIndex(src)
    line, col = idx.locate(err.start)
    start = idx.starts[line - 1]
    end = src.find("\n", start)
    end = len(src) if end == -1 else end
    width = max(1, min(err.end, end) - err.start)     # не подчёркиваем перевод строки
    gutter = " " * len(str(line))
    return (f"ошибка [{line}:{col}]: {err.message}\n"
            f" {line} | {src[start:end]}\n"
            f" {gutter} | {' ' * (col - 1)}{'^' * width}")

На входе let n = 12abc; и let s = "не закрыта;:

ошибка [1:9]: цифра не может переходить в букву
 1 | let n = 12abc;
   |         ^^^^^
ошибка [2:9]: незакрытая строка: нет закрывающей кавычки до конца строки
 2 | let s = "не закрыта;
   |         ^^^^^^^^^^^^

Обе ошибки найдены за один проход, поток токенов не оборвался, SEMI после 12abc на месте. Отдельный приём — склейка: наивный лексер выдал бы на 12abc пару INT(12), IDENT(abc) без всякой ошибки, а слишком осторожный — ERROR на каждый символ. Правильно поглотить весь слипшийся фрагмент и выдать одну диагностику. Доводить сообщения до ума будем в статье про проектирование языков.

Регулярки вместо ручного цикла: когда это правильный выбор

Тот же лексер, собранный из одной регулярки с именованными группами:

import re

TOKEN_RE = re.compile(r"""
      (?P<WS>    [ \t\r\n]+ | //[^\n]* )       # тривия
    | (?P<INT>   \d+ )
    | (?P<IDENT> [A-Za-z_][A-Za-z_0-9]* )
    | (?P<ARROW> -> ) | (?P<EQ> == ) | (?P<NE> != )
    | (?P<LE>    <= ) | (?P<GE> >= )
    | (?P<OP>    [-+*/=<>:;,(){}] )
    | (?P<BAD>   . )
""", re.VERBOSE | re.DOTALL)

KEYWORDS = {"let", "fn", "if", "else", "return", "true", "false"}

def tokenize(src: str):
    for m in TOKEN_RE.finditer(src):
        kind, text = m.lastgroup, m.group()
        if kind == "WS":
            continue
        if kind == "IDENT" and text in KEYWORDS:
            kind = text.upper()                # правило 2 таблицей
        if kind == "BAD":
            raise SyntaxError(f"недопустимый символ {text!r} на позиции {m.start()}")
        yield kind, text, m.start()

Порядок альтернатив здесь — правило 2 в чистом виде: -> объявлен раньше OP, иначе - съело бы дефис в одиночку. BAD в конце ловит мусор и гарантирует, что finditer не промолчит.

Регулярка в 2,4 раза быстрее — контринтуитивный, но объяснимый результат: цикл while исполняет байткод, а re крутится в C. В компилируемом языке отношение переворачивается: рукописный сканер на Rust или C даёт сотни МБ/с и обгоняет универсальный движок. Правило: на Python и JS для DSL и конфигов берите регулярку, на C/Rust/Go пишите руками. И помните, что регулярочный вариант не масштабируется на сложную лексику — интерполяция строк, вложенные комментарии и отступы в регулярку не помещаются вовсе.

Генераторы лексеров

Между «одна регулярка» и «всё руками» лежат генераторы: по описанию правил они строят ДКА и выдают исходник сканера — метапрограммирование в чистом виде.

Ирония в том, что почти все крупные компиляторы пишут лексер руками: GCC, Clang, rustc, Go (go/scanner), V8, TypeScript, Roslyn. Причины одни и те же: понятные сообщения, восстановление после ошибок, инкрементальность для IDE, контроль над производительностью и нерегулярные углы вроде интерполяции. Генераторы остаются там, где язык маленький и стабильный: конфиги, протоколы, запросные языки, DSL.

Доклад Роба Пайка «Lexical Scanning in Go» показывает третий стиль — лексер как отдельная горутина, шлющая токены в канал. Это прямое применение CSP: состояние автомата хранится в точке исполнения, а не в переменной. Красиво и читаемо, но в самом Go стандартный сканер в итоге сделали синхронным — за каналы приходится платить.

Ту же модель на TypeScript пишут через размеченное объединение (type TokenKind = "INT" | "IDENT" | ... и interface Token { kind; start; end }), а таблицу операторов держат отсортированной по убыванию длины — линейный поиск по ней и есть maximal munch для бедных. Инвариант «отсортировано по длине» легко нарушить, добавив оператор, поэтому в настоящем лексере операторы кладут в префиксное дерево: спуск по нему даёт максимальное поглощение автоматически и за длину оператора, а не за размер таблицы.

Юникод, кодировки и безопасность

В чём измеряются смещения. Байты UTF-8, кодовые точки или кодовые единицы UTF-16 — три разные системы координат (как устроены кодировки). Rust и Go считают в байтах, Python — в кодовых точках, а протокол LSP по умолчанию требует UTF-16 (наследство JavaScript). Несовпадение проявится только на строке с эмодзи или кириллицей: подчёркивание уедет на пару символов. Решение — одна система внутри компилятора и конвертация ровно на границе с протоколом.

Что считать буквой. isalpha() в Python пропустит переменная и 变量. Rust следует UAX #31, Go разрешает любые Unicode-буквы, C++ — список диапазонов. Пускаете юникод — нормализуйте идентификаторы (NFC), иначе визуально одинаковые имена окажутся разными.

Безопасность. Атака Trojan Source (CVE-2021-42574) использует управляющие символы двунаправленного текста: в редакторе код выглядит одним образом, а лексер видит другой порядок — и return оказывается внутри комментария. Защита реализуется именно в лексере: запрет непарных bidi-символов и предупреждение о визуально неотличимых идентификаторах. Rust, Go и GCC добавили такие проверки за полгода после публикации.

Мелочи, которые ломают всё: BOM в начале файла (снять до лексинга), \r\n против \n (нормализовать или честно учитывать в индексе строк), табы против пробелов при вычислении колонки (Clang считает таб за одну колонку, некоторые IDE — за восемь).

Производительность и раскладка в памяти

Лексер — единственная фаза, которая касается каждого байта входа, поэтому его константа заметна на больших проектах. Рычаг здесь не алгоритмический (O(n) уже оптимально), а связанный с иерархией памяти.

• Никаких объектов на токен. Плоский массив записей (kind, start, len) вместо объектов со строками — порядок по памяти и разы по скорости обхода.
• Структура массивов (SoA). Компилятор Zig держит токены в MultiArrayList: отдельно типы, отдельно смещения. Парсер в горячем цикле читает почти только тип — плотность в кэше вырастает примерно в 12 раз.
• Интернирование идентификаторов. Имя кладётся в хеш-таблицу один раз и дальше живёт как целочисленный SymbolId; сравнение имён становится сравнением чисел. Окупится в таблице символов.
• Классификация символов таблицей на 256 элементов вместо цепочки if — один доступ вместо десятка ветвлений и промахов предсказателя переходов.
• SIMD. simdjson сканирует по 32–64 байта за такт, находя границы битовыми масками. Для языков программирования применяют реже, но идея та же: быстрый проход по классам символов, потом медленный по найденным границам.

Инкрементальность и lossless-деревья

В IDE лексер запускается на каждое нажатие клавиши, но перелексировать мегабайт ради одной буквы не нужно: правка меняет токены только локально. Если после изменённого места лексер пришёл в то же состояние на той же границе токена, весь хвост берётся из прошлого разбора — так работают Roslyn и tree-sitter.

Для этого лексер должен быть lossless: сохранять тривию и уметь восстановить исходный текст побайтово. Roslyn привязывает комментарии и пробелы к соседним токенам как leading/trailing trivia, rust-analyzer использует rowan с той же идеей. Правило: если из ваших токенов нельзя собрать исходник обратно — форматтер и автоправки написать не получится. Отсюда лучший тест лексера: склейка лексем и тривии посимвольно равна исходнику, проверяется property-based тестами на случайных входах.

Типичные ошибки

1. Бросать исключение на первой ошибке — убивает IDE и показывает одну проблему за проход.
2. Хранить строку и колонку в каждом токене — дублирование состояния и рассинхронизация при правках; храните смещение.
3. Копировать текст каждой лексемы — аллокация на токен, худший способ ничего не сделать.
4. Ключевые слова как отдельные правила — работает, пока их пять, и ломается на letx.
5. Забыть про максимальное поглощение — x<=1 станет x < = 1, а ругаться парсер будет совсем в другом месте.
6. Молча выбрасывать комментарии — потом понадобится форматтер или doc-комментарии, и переписывать придётся всё.
7. Отсутствие токена EOF — каждая ветка парсера обрастает проверкой границы массива.
8. Смешивать байтовые и символьные смещения — проявится на первом эмодзи, и у пользователя.
9. Бэктрекинг-регулярки с вложенными квантификаторами — ReDoS прямо в компиляторе.
10. Не тестировать лексер отдельно — вход и выход плоские, тесты пишутся тривиально.

Что запомнить

• Лексер превращает поток символов в поток токенов (тип, значение, спан) за один проход: O(n) по времени, O(1) дополнительной памяти на токен.
• Тип токена — алфавит для парсера, спан — единственный мост назад к тексту, а судьбу тривии выбирают сознательно.
• Лексика — регулярный язык, поэтому её распознаёт конечный автомат без памяти; всё, что требует счёта, — не к лексеру, кроме пары прагматичных исключений.
• Неоднозначности разрешают максимальное поглощение и приоритет по порядку объявления; ключевые слова — таблица, а не правила.
• В Python быстрее одна большая регулярка, в C/Rust/Go — рукописный цикл; крупные компиляторы пишут лексер руками ради диагностик, восстановления и инкрементальности.
• Лексер не имеет права падать: ошибка — это токен ERROR со спаном плюс запись в диагностиках.

Упражнения

1. Добавьте числа с плавающей точкой (3.14) и разберитесь, что делать с 1..2: правило максимального поглощения здесь работает против вас.
2. Реализуйте литералы 0xFF и 0b1010 с разделителями _.
3. Сделайте лексер lossless и напишите тест «склейка лексем и тривии равна исходнику».
4. Замените цепочку if в next_token таблицей классов символов на 256 элементов, измерьте.
5. Реализуйте INDENT/DEDENT со стеком уровней и убедитесь, что это уже не автомат.
6. Напишите fuzz-тест: случайные строки не должны давать исключений, зависаний или спанов за границами текста.

Источники

• Aho, Lam, Sethi, Ullman. Compilers: Principles, Techniques, and Tools, глава 3 — канонический разбор (страница книги).
• Robert Nystrom. Crafting Interpreters, глава Scanning — лучший текст про рукописный сканер.
• Ken Thompson. Regular Expression Search Algorithm, CACM 1968: ACM DL.
• Russ Cox. Regular Expression Matching Can Be Simple And Fast — НКА, ДКА и почему бэктрекинг взрывается.
• Сканер Go и rustc dev guide — рукописные лексеры в проде.
• Документация flex и re2c — два подхода к генерации сканеров.
• PEP 701 — как менялся токенизатор Python ради f-строк.
• Trojan Source и UAX #31 — юникод, безопасность и идентификаторы.

Что дальше

У нас есть плоский поток токенов — и на нём по-прежнему нельзя ответить, что означает 2 + 3 * 4. Плоскость надо превратить в дерево, а для этого нужен инструмент мощнее конечного автомата: грамматика и автомат со стеком.

Синтаксический анализ: грамматики, рекурсивный спуск, приоритеты операторов