Теория языков программирования
Лексический анализ
Каждый раз при запуске TypeScript или Python, первые 10 миллисекунд работы - лексер. Он читает тысячи строк кода и выдаёт структурированный поток токенов. Без этого этапа парсер получил бы хаос символов.
- **Clang**: ручной лексер с буферизацией и SIMD сравнением читает ~1 GB/s исходного кода - поэтому lldb быстро открывает большие проекты
- **TypeScript compiler**: лексер написан вручную на TypeScript (src/compiler/scanner.ts, ~2500 строк) - самый критичный для производительности компонент
- **Python tokenize module**: используется в IDE, линтерах, форматтерах (black, autopep8) - стандартная библиотека предоставляет лексер для метапрограммирования
Токены и лексемы
Лексер (scanner/tokenizer) - первый проход компилятора. Он читает поток символов и выдаёт поток токенов. Токен - это пара (тип, значение). Лексема - это конкретная строка из исходного кода, которую представляет токен.
Лексер добавляет позиционную информацию (line:col) к каждому токену. Rust компилятор хранит spans - диапазоны байт в файле. Это основа для точных сообщений об ошибках.
Что выдаёт лексер как результат своей работы?
Регулярные выражения и лексер
Каждый тип токена описывается регулярным выражением. Лексер - это набор regex с приоритетами. При конфликте (keyword 'if' vs identifier): правило longest match (берём длиннейшее совпадение) и priority (keyword перед identifier).
Как лексер различает ключевое слово 'if' и идентификатор 'ifcount'?
Конечные автоматы
Каждое регулярное выражение компилируется в NFA (недетерминированный конечный автомат), затем через subset construction в DFA (детерминированный). DFA читает строку за один проход O(n) - поэтому лексеры быстрые.
Thompson construction (1968) строит NFA из regex за O(n). Subset construction конвертирует NFA->DFA. В worst case DFA может иметь 2^n состояний, но на практике языковые токены дают компактные DFA. GCC lexer - ручной DFA, Clang использует re2c.
Почему лексеры используют DFA, а не NFA напрямую?
Генераторы лексеров
Генераторы лексеров (lex, flex, re2c, logos) принимают спецификацию токенов (regex + действия) и генерируют эффективный лексер. re2c генерирует C код с прямыми jump таблицами. Logos (Rust) генерирует match-based DFA в compile time.
Производительность: re2c - ~800 MB/s. Logos - ~500 MT/s. Ручной рукописный лексер Clang - ~1 GB/s (с буферизацией и SIMD). Лексер обычно не является узким местом компилятора - парсер медленнее.
Лексер - это просто split() по пробелам и специальным символам
Лексер - конечный автомат, обрабатывающий все граничные случаи: строки с пробелами, вложенные комментарии, юникод, числа с экспонентой
split(' ', '(', ')') сломается на строке 'hello world', многострочном комментарии, 1.5e-10. DFA-based лексер обрабатывает всё корректно за O(n)
Какое главное преимущество генераторов лексеров (logos, flex) перед ручным написанием?
Ключевые идеи
- **Лексер** преобразует поток символов в поток токенов. Убирает пробелы, комментарии, добавляет позиционную информацию
- **Токены** описываются regex. Конфликты решаются через longest match + priority (keyword > identifier)
- **DFA** - детерминированный конечный автомат, обеспечивает O(n) лексический анализ. NFA->DFA через subset construction
- **Генераторы лексеров** (Logos, re2c, flex): декларативная спецификация -> эффективный DFA. ~500 MT/s
Связанные темы
Лексер - первый этап компилятора:
- Парсер — Парсер получает поток токенов от лексера и строит AST
- AST и семантический анализ — AST строится парсером и используется для type checking и codegen
Вопросы для размышления
- Python чувствителен к отступам - блоки определяются индентацией. Как лексер Python обрабатывает это? Что такое токены INDENT и DEDENT?
- Строковая интерполяция (f'hello {name}') создаёт проблему для лексера: внутри строки вдруг снова нужен полный лексер для выражения. Как это решается?
- re2c генерирует C-код с прямыми jump таблицами. Почему такой подход быстрее, чем интерпретация DFA в runtime?