Токенизация и парсинг
Предпосылки
Каждый раз, когда вы запускаете Ruby-скрипт, ваш код проходит три превращения, прежде чем хоть что-то выполнится. Ruby берёт текст, разбирает его на части и трижды собирает в другом формате:
текст → токенизация → токены → парсинг → AST → [компиляция](compilation.md) → [байткод](compilation.md) [YARV](../../ruby.md)
Токенизация превращает текст в «слова» — токены. Парсинг группирует токены в «предложения» — узлы абстрактного синтаксического дерева (AST). Компиляция переводит дерево в инструкции виртуальной машины YARV (Yet Another Ruby VM). Разберём первые два шага — токенизацию и парсинг.
Важный момент: токенизатор и парсер не работают по очереди. Парсер управляет процессом — каждый раз, когда ему нужно следующее «слово», он вызывает токенизатор. Токенизатор возвращает один токен, парсер решает, что с ним делать, и просит следующий. Два процесса переплетены, но концептуально делают разное: один находит слова, другой строит из них структуру.
Токенизация: текст → слова
Возьмём простую программу:
10.times do |n|
puts n
endДля нас это осмысленный код. Для Ruby в первый момент — просто последовательность символов: 1, 0, ., t, i, m, e, s, , d, o… Токенизатор проходит по ним слева направо и группирует в токены.
Встретив 1, токенизатор понимает, что начинается число, и продолжает читать, пока символы «числовые». Следующий символ — 0, всё ещё число. Дальше — точка. Точка может быть частью числа с плавающей точкой (как в 10.5), поэтому токенизатор заглядывает ещё на один символ вперёд. Видит t — значит, точка не часть числа. Токенизатор делает шаг назад и фиксирует первый токен: целое число 10.
Дальше точка становится отдельным токеном — оператором вызова метода. Буквы t-i-m-e-s группируются в идентификатор times. Пробел отбрасывается — он не несёт смысла. Слово do — не обычный идентификатор, а ключевое слово: Ruby хранит таблицу из 41 зарезервированного слова (do, end, if, class, def и другие) и проверяет каждый идентификатор по ней.
Результат токенизации всей программы — плоский поток:
INTEGER("10") DOT(".") IDENTIFIER("times") KEYWORD_DO("do")
PIPE("|") IDENTIFIER("n") PIPE("|")
IDENTIFIER("puts") IDENTIFIER("n")
KEYWORD_END("end")
Пробелы и переводы строк исчезли — они нужны были только чтобы отделить токены друг от друга. Комментарии тоже отбрасываются (хотя Ruby запоминает magic comments вроде # frozen_string_literal: true). Каждый токен — это тип и фрагмент исходного текста.
Контекстная зависимость
Токенизация кажется простой, пока не встречается неоднозначность. Рассмотрим:
array << n if n < 5Здесь << — оператор добавления в массив (один токен LESS_LESS), а < — оператор сравнения (другой токен LESS). Когда токенизатор встречает первый символ <, он заглядывает вперёд: если следующий тоже < — это <<, если нет — это <.
Но есть ситуация сложнее. Слово if в array << n if n < 5 — модификатор (как в return if done), а не начало условного блока (if ... then ... end). Ruby различает их: это разные токены (KEYWORD_IF_MODIFIER и KEYWORD_IF). Токенизатор знает, что if здесь — модификатор, потому что он помнит, что было до этого. После идентификатора n (который стоит в позиции аргумента) if может быть только модификатором.
Для этого токенизатор хранит состояние (lex state): был ли предыдущий токен началом выражения, концом выражения, аргументом, оператором. Одни и те же символы порождают разные токены в зависимости от контекста. Это одна из причин, почему токенизатор Ruby написан вручную, а не сгенерирован автоматическим инструментом — контекстные правила слишком сложны.
Парсинг: слова → предложения
Токены — это слова. Но слова сами по себе не говорят, что делать. Возьмём выражение:
2 + 2 * 3Токенизатор выдаст: INTEGER(2), PLUS(+), INTEGER(2), STAR(*), INTEGER(3). Плоский поток — в нём нет информации о том, что умножение выполняется раньше сложения. Парсер берёт этот поток и строит дерево, в котором структура фиксирует смысл:
(+)
/ \
(2) (*)
/ \
(2) (3)
Узел * вложен внутрь узла + — значит, сначала вычисляется 2 * 3, потом результат складывается с 2. Это абстрактное синтаксическое дерево (AST) — дерево узлов, где каждый узел представляет конструкцию языка: операцию, вызов метода, присваивание, блок.
Для нашей исходной программы 10.times do |n| puts n end дерево выглядит так:
program
└── method_add_block
├── call
│ ├── integer: 10
│ ├── dot: .
│ └── identifier: times
└── do_block
├── block_var
│ └── param: n
└── body
└── command
├── identifier: puts
└── var_ref: n
В дереве видно то, чего в потоке токенов не было: 10.times — это вызов метода, do |n| ... end — это блок, переданный этому вызову, puts n — команда внутри блока, а n — ссылка на переменную из параметров блока. AST фиксирует смысл кода — всю информацию, которая потом понадобится для выполнения.
Как парсер строит дерево
Парсер работает по правилам грамматики — набору шаблонов, описывающих, какие комбинации токенов допустимы. Для 10.times do |n| puts n end цепочка правил выглядит так:
program → statement → method_call + block
method_call → primary_value "." identifier
└── 10 times
block → "do" block_params body "end"
└── |n| └── puts n
Каждое правило описывает один тип конструкции. method_call — это «значение, точка, имя метода». block — это do, параметры, тело, end. Правила ссылаются друг на друга: program содержит statement, statement может быть method_call с block.
Правила грамматики описывают что допустимо. Остаётся вопрос — как парсер применяет эти правила к потоку токенов. В Ruby существуют два парсера, использующих разные подходы.
Recursive descent: сверху вниз
Prism — парсер Ruby по умолчанию начиная с Ruby 3.4 — работает методом рекурсивного спуска (recursive descent). Идея: каждое правило грамматики превращается в функцию. Функция читает токены, которые ожидает по правилу, и вызывает другие функции для вложенных конструкций. Парсер «спускается» от целой программы к конкретным конструкциям.
Для 10.times do |n| puts n end цепочка выглядит так:
parse_program()— «разбери программу» → вызываетparse_statement()parse_statement()→ вызываетparse_expression()parse_expression()→ видит число10, за ним точку — это вызов метода. Вызываетparse_method_call()parse_method_call()→ берёт10как получателя,.как оператор вызова,timesкак имя метода. Видитdo— за вызовом идёт блок. Вызываетparse_block()parse_block()→ берётdo, разбирает параметры|n|, вызываетparse_statements()для тела блока, ожидаетend- Внутри тела:
parse_statement()→parse_expression()→ видитputs n, разбирает как вызов метода с аргументом
Каждая функция собирает свою часть дерева и возвращает узел AST. Дерево растёт сверху вниз — сначала корень, потом ветви:
Шаг 1 Шаг 2 Шаг 3
parse_program() видит 10.times видит do...end
program program program
└── ? └── call └── method_add_block
├── 10 ├── call(10.times)
├── . └── do_block
└── times ├── param: n
└── body: ?
Шаг 4
разбирает puts n
program
└── method_add_block
├── call(10.times)
└── do_block
├── param: n
└── command(puts, n) ← дерево готово
На каждом шаге парсер углубляется: сначала создаёт корень program, потом спускается к call, обнаруживает блок, ныряет внутрь блока, разбирает его тело. Каждая функция возвращает свой узел «наверх» вызвавшей функции.
Название «рекурсивный» — потому что функции вызывают друг друга рекурсивно. parse_expression() может вызвать parse_block(), который внутри вызовет parse_expression() для тела блока, а та — снова parse_block() для вложенного блока. Глубина вложенности кода превращается в глубину рекурсии парсера.
Prism написан вручную на C — каждая функция закодирована программистами, а не сгенерирована автоматически.
LALR: снизу вверх
Исторический парсер Ruby — parse.y — использует другой подход: LALR (Look-Ahead Left-to-Right). Здесь правила грамматики записаны в файле parse.y в формате генератора парсеров Bison. На этапе сборки Ruby Bison читает эти правила и генерирует C-код парсера. Bison не запускается при каждом выполнении ruby — только при компиляции интерпретатора из исходников.
LALR-парсер работает снизу вверх — в обратном направлении по сравнению с recursive descent. Вместо того чтобы начать с «разбери программу» и спускаться к деталям, он начинает с отдельных токенов и собирает из них всё более крупные конструкции. Его механизм — shift/reduce:
Shift — парсер кладёт очередной токен на стек. Reduce — когда верхушка стека совпадает с правой частью правила грамматики, парсер сворачивает эти токены в один узел.
Разберём на примере — переводчике с испанского. Задача: распознать фразу «Me gusta el Ruby» и перевести как «I like Ruby». Нужны правила: «если видишь me и gusta подряд — это “I like”», «если перед el ruby стоит “I like” — это полная фраза». Запишем формально — слева имя правила, стрелка, справа из чего оно состоит:
SpanishPhrase → VerbAndObject "el" "ruby"
VerbAndObject → ILike | SheLikes
ILike → "me" "gusta"
SheLikes → "le" "gusta"
| означает «или»: VerbAndObject — это либо ILike, либо SheLikes. Слова в кавычках — конкретные токены, которые парсер ожидает увидеть.
Входной поток: me, gusta, el, ruby. Парсер:
- Shift
me→ стек:[me] - Shift
gusta→ стек:[me, gusta] - Reduce по правилу
ILike→ стек:[ILike] - Reduce по правилу
VerbAndObject→ стек:[VerbAndObject] - Shift
el→ стек:[VerbAndObject, el] - Shift
ruby→ стек:[VerbAndObject, el, ruby] - Reduce по правилу
SpanishPhrase→ стек:[SpanishPhrase]✓
На шаге 3 выбор очевиден: me gusta на стеке полностью совпадает с правилом ILike — парсер сворачивает. Но в более сложных грамматиках бывает неоднозначность: допустим, существовало бы ещё правило ILikeALot → "me" "gusta" "mucho". Тогда после me gusta парсер не знает — сворачивать в ILike или подождать ещё один токен в надежде на mucho? Для этого он заглядывает вперёд (look-ahead) на следующий токен. Видит el — значит, mucho не будет, можно сворачивать.
Тот же алгоритм работает для Ruby. Вот как LALR-парсер строит дерево для 10.times do |n| puts n end — снизу вверх, от отдельных токенов к целой программе:
Шаг 1 Шаг 2
shift токены, reduce листья reduce → call
10 . times call
╱ │ ╲
10 . times
Шаг 3 Шаг 4
reduce → block reduce → program
do_block program
╱ ╲ └── method_add_block
param: n command ├── call(10.times)
╱ ╲ └── do_block
puts n ├── param: n
└── command(puts, n)
В отличие от recursive descent, дерево собирается от листьев к корню: сначала 10, ., times сворачиваются в call; отдельно puts, n сворачиваются в command, затем do, параметры и тело — в do_block; и только в конце call + do_block сворачиваются в корневой узел.
Грамматика Ruby — сотни правил вместо четырёх, и неоднозначности возникают постоянно, — но алгоритм тот же. parse.y — огромный файл (более 10 000 строк), который исторически был «сердцем» Ruby: местом, где фактически определён синтаксис языка.
Если в какой-то момент ни одно правило не подходит — парсер сообщает синтаксическую ошибку:
syntax error, unexpected end-of-input, expecting keyword_end
Почему два парсера
Зачем менять рабочий LALR-парсер? Сгенерированный Bison’ом код сложно модифицировать, сложно переиспользовать и сложно получить от него понятные сообщения об ошибках. Prism написан вручную — это даёт контроль над качеством ошибок, скоростью и возможностью использовать парсер как библиотеку из IDE, линтеров и Ruby-кода. С Ruby 3.4 Prism — парсер по умолчанию. Старый доступен через --parser=parse.y.
Инструмент Ripper (стандартная библиотека для анализа Ruby-кода) по-прежнему работает через parse.y. Для совместимости существует Prism::Translation::Ripper, генерирующий вывод в формате Ripper через Prism.
Инструменты анализа
Ruby предоставляет инструменты, чтобы наблюдать за токенизацией и парсингом. Ripper.lex показывает токены:
require 'ripper'
pp Ripper.lex('10.times do |n| puts n end')[[1, 0], :on_int, "10", END]
[[1, 2], :on_period, ".", DOT]
[[1, 3], :on_ident, "times", ARG]
[[1, 9], :on_kw, "do", BEG]
[[1, 12], :on_op, "|", BEG|LABEL]
[[1, 13], :on_ident, "n", ARG]
[[1, 14], :on_op, "|", BEG|LABEL]
[[1, 16], :on_ident, "puts", CMDARG]
[[1, 21], :on_ident, "n", END|LABEL]
[[1, 23], :on_kw, "end", END]
Каждая строка — токен: позиция в исходнике, тип (:on_int, :on_kw, :on_ident), текст, и состояние лексера (END, BEG, ARG). Состояние — тот самый lex state, который определяет контекст.
Ripper.sexp показывает AST:
pp Ripper.sexp('2 + 2 * 3')[:program,
[[:binary,
[:@int, "2", [1, 0]],
:+,
[:binary, [:@int, "2", [1, 4]], :*, [:@int, "3", [1, 8]]]]]]Видно, что * вложен внутрь + — парсер понял приоритеты. Каждый массив — узел AST. Ripper выводит S-expression (символьное представление дерева), а не само дерево, но структура та же.
Prism предоставляет свой API:
require 'prism'
Prism.lex('10.times do |n| puts n end') # токены
Prism.parse('10.times do |n| puts n end') # ASTДля отладки можно запустить Ruby с флагом --dump=parsetree, чтобы увидеть AST в формате внутренних узлов:
ruby --dump=parsetree -e '10.times do |n| puts n end'Токенизатор не проверяет синтаксис. Если передать ему код с ошибкой (например, забыть | после параметра блока), он спокойно разобьёт текст на токены — синтаксическая ошибка обнаружится только на этапе парсинга, когда токены не совпадут ни с одним правилом грамматики.
Sources
- Pat Shaughnessy, 2013, Ruby Under a Microscope — главы 1–2: токенизация, парсинг, LALR.
- Kevin Newton, 2024, The Prism Parser — доклад о дизайне Prism.
- Ruby 3.4.0 Release Notes — Prism как парсер по умолчанию: https://www.ruby-lang.org/en/news/2024/12/25/ruby-3-4-0-released/