Введение
Этот пост написан для тех, кто глубоко погружён в разработку компиляторов или DSL, часто сталкивается с задачами парсинга, строит сложные конфигурации или движки с нуля. Этот инструмент предназначен для разбора большинства контекстно-свободных языков с минимальными усилиями. Он не претендует на то, чтобы генерировать код, который невозможно превзойти по производительности, — добиться более высокой производительности в написанном вручную парсере всё же сложнее.
Немного теории (можно пропустить)
Парсеры — это инструменты, преобразующие текстовые шаблоны в более машинно-дружественное представление. Генераторы парсеров, соответственно, генерируют парсеры. Процесс часто делится на два этапа, хотя иногда они объединяются. Лексер обрабатывает исходный текст и производит токены — так называемые независимые фрагменты текста. Затем эти фрагменты обрабатываются парсером, поскольку их порядок влияет на итоговое представление. Результат может быть выведен как CST или AST. CST (Concrete Syntax Tree, конкретное синтаксическое дерево) — представление, предшествующее AST, где доступны все токены правила парсера. AST сокращает это представление, оставляя только значимые токены (например, группирующие кавычки против значения внутри группы). Другими словами, AST убирает из представления весь синтаксический контекст, поэтому теоретически два AST могут быть эквивалентны при разном синтаксисе, если совпадает семантика, — но для CST это неприменимо.
Для лексера используется NFA или DFA. Коротко говоря, это таблицы, где символ сопоставляется состоянию, у которого следующий символ сопоставляется другому состоянию — и так до конца ввода. У NFA на одном символе может быть несколько следующих состояний, в то время как DFA детерминирован и сопоставляет один символ ровно одному состоянию. NFA проще строить из регулярного выражения и часто служит промежуточным представлением при статической генерации. Классические DFA только сопоставляли текст и не имели возможности захвата (capture). При обходе DFA нельзя было выполнять произвольный семантический код — семантика выполнялась только в конце. Чтобы построить AST, приходилось повторно разбирать некоторые фрагменты и извлекать данные. Относительно недавно (около 2000 года) были изобретены TNFA и TDFA, развитие которых продолжается и по сей день (2026). Коротко — это позволяет захватывать данные прямо во время обхода таблицы, так что построение и CST, и AST может быть полностью автоматизировано. Повторный разбор тоже не требуется.
Парсеры — более развитая тема. Есть алгоритмы построения LL (нисходящий разбор) и LR (восходящий разбор). Этот генератор реализует оба, но именно нисходящий разбор реализован и хорошо протестирован. Коротко, это подход “функция на правило”, где функции могут рекурсивно вызывать друг друга — тот же подход, что применяется в написанных вручную парсерах, поскольку промышленные LR-парсеры писать вручную непрактично. Десятилетиями генераторы парсеров не умели выдавать хорошую диагностику ошибок и стратегии восстановления, не имели устоявшихся техник автоматического построения AST, не позволяли добавлять семантические действия без раздувания грамматики в языконезависимом виде — поэтому сообщество считало их игрушкой, и, например, все крупные компиляторы используют написанные вручную LL-парсеры.
Зачем ещё один генератор парсеров
Почти 3 года назад мне понадобился парсер. Результат работы большинства генераторов парсеров наполовину пригоден к использованию “из коробки”. AST, сообщения об ошибках и восстановление после них приходится строить самостоятельно (ANTLR), либо писать устаревшие грамматики прямо с кодом (Flex + Bison). Либо использовать генераторы, выдающие парсер только под одну целевую платформу, либо вообще не генерирующие парсер, а использующие возможности языка для обработки текста (на Boost::Spirit больно смотреть). Если вам действительно нужно что-то production-ready, рано или поздно вы перепишете это в написанный вручную парсер. А если ваша грамматика меняется — все изменения придётся поддерживать самостоятельно.
Недавно этот вопрос снова подняли, потому что тема, которая десятилетиями считалась решённой, на деле не решена в плане программного обеспечения. https://blog.adamant-lang.org/2019/dreaming-of-a-parser-generator/
Желаемое состояние этого генератора парсеров в основном следует требованиям из статьи по ссылке выше:
Композируемые грамматики
Инкрементальность
Сообщения об ошибках и восстановление после них
Генерация значений токенов
Автоматическое построение AST
Восстановление компилятора после ошибок
Это наиболее значимые пункты, но я бы добавил ещё:
Статическая генерация. Никакой генерации в рантайме
Отсутствие зависимостей — сгенерированный парсер должен легко настраиваться
Вывод на несколько языков
Семантические действия и обработка ошибок прямо в грамматике, без её раздувания
Гибкость использования как в тривиальных, так и в очень крупных проектах
Простой в использовании API
Архитектура и использование
Лексер генерируется как TDFA с поддержкой: шаблонов (patterns) в грамматике + вложенных токенов (без потери структуры AST) + правил уровня парсера внутри токенов + семантических действий во время обхода.
TEMPLATED_TYPE: 'template' __WS 'type' __WS @ '==' | '!=' __WS @ 'int' | 'str' | 'bool' @{op, type} ; main: TEMPLATED_TYPE;
TEMPLATED_TYPE ├── op: == └── type: str
Здесь захвачено то, что помечено как @, а итоговый токен выглядит как AST. Захват для вложенных токенов тоже реализован, но нужны небольшие доработки генератора, чтобы он заработал. Архитектура поддерживает правила уровня парсера, но они пока не реализованы.
Парсер в этой реализации — LL(k), но в будущем может быть расширен до LL(*). Его AST строится полностью автоматически, с автоматической поддержкой рекурсивных узлов, и готов к использованию сразу же.
Самоописывающая грамматика
input: "a: (INT ID '=' '0') | (ID | INT);" ID: @ ([a-zA-Z] [a-zA-Z0-9_]*) {@} ; rule: @ ID ':' @ #value+ ';' @{name, v} #capture: '@' (\s0 @ ID)? {@} ; #value: @ #pattern @ #alternative* @ #QUANTIFIER? @{v, alts, quantifier} #pattern: @ ID | #STRING | #SPACE | group {@} ; #STRING: '\'' @ [^']* '\'' {@} ; #SPACE: '\\s' {@} ; #group: '(' @ #value+ ')' {@} ; #alternative: '|' @ pattern {@} ; #QUANTIFIER: @ '?' | '+' | '*' {@} ; ; ; main: @ rule {@} ;
main └── value ├── rule ├── name ├── ID │ └── value: a └── v └── item ├── rule_value ├── v ├── rule_value_pattern │ └── value │ ├── rule_value_group │ └── value │ ├── item │ ├── rule_value │ │ ├── v │ │ ├── rule_value_pattern │ │ │ └── value │ │ │ ├── ID │ │ │ └── value: INT │ │ ├── alts │ │ └── quantifier │ │ ├── <empty> │ ├── item │ ├── rule_value │ │ ├── v │ │ ├── rule_value_pattern │ │ │ └── value │ │ │ ├── ID │ │ │ └── value: ID │ │ ├── alts │ │ └── quantifier │ │ ├── <empty> │ ├── item │ ├── rule_value │ │ ├── v │ │ ├── rule_value_pattern │ │ │ └── value │ │ │ ├── rule_value_STRING │ │ │ └── value: = │ │ ├── alts │ │ └── quantifier │ │ ├── <empty> │ └── item │ ├── rule_value │ ├── v │ ├── rule_value_pattern │ │ └── value │ │ ├── rule_value_STRING │ │ └── value: 0 │ ├── alts │ └── quantifier │ ├── <empty> ├── alts └── item │ ├── rule_value_alternative │ └── value │ ├── rule_value_pattern │ └── value │ ├── rule_value_group │ └── value │ └── item │ ├── rule_value │ ├── v │ ├── rule_value_pattern │ │ └── value │ │ ├── ID │ │ └── value: ID │ ├── alts │ └── item │ │ ├── rule_value_alternative │ │ └── value │ │ ├── rule_value_pattern │ │ └── value │ │ ├── ID │ │ └── value: INT │ └── quantifier │ ├── <empty> └── quantifier ├── <empty>
Этот фрагмент — не пример грамматики, а собственный синтаксис правил ISPA, записанный на ISPA. Генератор самоприменим (self-hosted): тот же DSL, которым описывают C или JSON, достаточно выразителен, чтобы описать самого себя.
Несколько примитивов, чтобы читать его:
@помечает точку захвата (capture point) — начинающийся там фрагмент становится доступен семантическому действию. Это механизм тегирования TDFA, проявляющийся прямо в синтаксисе грамматики, а не прикрученный сверху.{...}— семантическое действие.{@}— это сокращение для “вернуть единственный захват как есть”; используется в листовых правилах вродеID,STRINGилиQUANTIFIER, которые просто возвращают совпавший текст.@{field1, field2}строит узел AST прямо из именованных захватов — без отдельного кода построения дерева. Действие@{name, v}в правилеruleозначает: “узел, который порождает это правило, имеет полеname(из захватаID) и полеv(из повторяющихся захватов#value)”. Именно это на практике означает “автоматический AST”: форма действия — это и есть форма узла.#name:объявляет вложенное, локально-ограниченное правило — видимое только внутри содержащего его правила.#value,#pattern,#captureи подобные существуют только внутриrule;#pattern,#STRINGи аналогичные — только внутри#value. Это не даёт служебным внутриграмматическим правилам засорять глобальное пространство имён, вместо того чтобы заставлять каждое правило генератора жить на верхнем уровне.Стандартные regex-подобные операторы работают как обычно:
+(один или более),*(ноль или более),?(опционально),|(альтернатива), и строковые литералы в кавычках для точного текста.\s— встроенный токен пропуска пробелов.
Читая сверху вниз: ID совпадает с идентификатором (буква, затем буквы/цифры/подчёркивание). rule — это имя, двоеточие, одно или более #value, и терминатор — где каждый #value представляет собой #pattern (ссылку на ID, строку, пробел, или заключённую в скобки #group), за которым опционально следуют альтернативы и квантификатор. main — это просто точка входа: файл грамматики — это одно или более правил.
Проще код для взаимодействия с парсером я представить не могу:
#include <Parser.h> #include <iostream> #include <fstream> #include <variant> int main(int argc, const char** argv) { if (argc < 2) { std::cout << "Usage: " << argv[0] << " \"<input>\"\n"; return 1; } Parser::Lexer lexer; lexer.makeTokens(argv[1]); Parser::Parser parser; Parser::Types::main &node = parser.parse(lexer); std::ofstream of("tree.txt"); of << node << "\n\n"; }
Как выглядит сгенерированный парсер
// Parser.h #ifndef PARSER_H #define PARSER_H #include <string> #include <vector> #include <unordered_map> #include <array> #include <string> #include <variant> #include <optional> #include <memory> #include <ispastdlib.hpp> namespace Parser { enum class Tokens { NONE, AUTO_5, AUTO_4, AUTO_2, AUTO_1, AUTO_3, rule_value_STRING, __WS, rule_value_SPACE, NUMBER, AUTO_0, rule_value_QUANTIFIER, ID, }; enum class Rules { NONE, main, rule_value_alternative, rule_value_pattern, rule_value_group, rule_value, rule_capture, rule, }; namespace FlatTypes { struct AUTO_5; struct AUTO_4; struct AUTO_2; struct AUTO_1; struct AUTO_3; struct rule_value_STRING; struct rule; struct rule_value; struct __WS; struct rule_value_SPACE; struct NUMBER; struct AUTO_0; struct rule_value_QUANTIFIER; struct ID; struct main; struct rule_value_alternative; struct rule_value_pattern; struct rule_value_group; struct rule_capture; } namespace FlatTypes { struct AUTO_5 { auto write_to_output(::ISPA_STD::ASTPrinter<std::ostream>& printer) const -> void; auto print(std::ostream& os) const -> void; auto to_string() const -> std::string; }; auto operator<<(std::ostream &os, const AUTO_5 &value) -> std::ostream&; } namespace FlatTypes { struct AUTO_4 { auto write_to_output(::ISPA_STD::ASTPrinter<std::ostream>& printer) const -> void; auto print(std::ostream& os) const -> void; auto to_string() const -> std::string; }; auto operator<<(std::ostream &os, const AUTO_4 &value) -> std::ostream&; } // ... using Token = std::variant<std::monostate, ::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_5>, ::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_4> ...>; class Lexer : public ::ISPA_STD::Lexer_base<::Parser::Tokens, Token> { static ::ISPA_STD::DFA::API::CharToClass char_class_table; static ::ISPA_STD::DFA::API::Table<21, 129> dfa_table; static ::ISPA_STD::DFA::API::Table<211, 4> action_table; static auto semantic_action_exec(long long state, const ::ISPA_STD::DFA::API::Captures& captures, long long start_pos, const char* start, long long length, long long line) -> std::pair<long long, Token>; bool init_done; auto init() -> void override; ::ISPA_STD::DFA::API::TdfaLayout<14, 14> tdfa_registers; static std::array<::ISPA_STD::DFA::API::DFADebug, 226> debug_array; static std::unordered_map<long long, std::unordered_map<long long, long long>> debug_index; public: auto makeToken(const char*& pos) -> Token override; }; class Parser : public ::ISPA_STD::LLParser_base<::Parser::Tokens, ::Parser::Rules, Types::main, Token> { // ... template<typename IT> auto rule_value_pattern(IT pos) -> ::ISPA_STD::MatchResult<Rules, Types::rule::value::pattern, IT>{ std::variant<std::monostate, ::ISPA_STD::Node<::Parser::Rules, Types::rule::value::group>, ::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::SPACE>, ::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::STRING>, ::ISPA_STD::Node<::Parser::Tokens, Types::ID>> _0; bool success_1; success_1 = false; // grammar `@ ( ID | rule::value::STRING | rule::value::SPACE | rule::value::group)`: choice; reset match status before selecting an alternative success_1 = false; switch (static_cast<Tokens>((*pos).index())) { case Tokens::AUTO_1: { ::ISPA_STD::MatchResult<Rules, Types::rule::value::group, IT> rule_value_group_2; bool success_3 = false; rule_value_group_2 = rule_value_group(pos); if (!(rule_value_group_2.status)) { return {}; } success_3 = true; pos = rule_value_group_2.it; if (!success_3) { return {}; } _0 = rule_value_group_2.node; success_1 = true; break; } case Tokens::ID: { ::ISPA_STD::Node<::Parser::Tokens, Types::ID> ID_4; bool success_5 = false; if (!(std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::ID>>((*pos)))) { return {}; } ID_4 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::ID>>((*pos)); success_5 = true; pos++; if (!success_5) { return {}; } _0 = ID_4; success_1 = true; break; } case Tokens::rule_value_SPACE: { ::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::SPACE> rule_value_SPACE_6; bool success_7 = false; if (!(std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::SPACE>>((*pos)))) { return {}; } rule_value_SPACE_6 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::SPACE>>((*pos)); success_7 = true; pos++; if (!success_7) { return {}; } _0 = rule_value_SPACE_6; success_1 = true; break; } case Tokens::rule_value_STRING: { ::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::STRING> rule_value_STRING_8; bool success_9 = false; if (!(std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::STRING>>((*pos)))) { return {}; } rule_value_STRING_8 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::STRING>>((*pos)); success_9 = true; pos++; if (!success_9) { return {}; } _0 = rule_value_STRING_8; success_1 = true; break; } } if (!success_1) { return {}; } Types::rule::value::pattern result; ::ISPA_STD::assign_compatible(result.value, _0); ::ISPA_STD::MatchResult<Rules, Types::rule::value::pattern, IT> match_result; match_result.status = true; match_result.node.set_data(result); match_result.it = pos; return match_result; } template<typename IT> auto rule_value_group(IT pos) -> ::ISPA_STD::MatchResult<Rules, Types::rule::value::group, IT>{ ::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_1> AUTO_1_0; bool success_1; ::ISPA_STD::Node<::Parser::Tokens, Types::__WS> __WS_2; bool success_3; ::ISPA_STD::MatchResult<Rules, Types::rule::value, IT> rule_value_5; bool success_6; ::ISPA_STD::Node<::Parser::Rules, Types::rule::value> element_7; std::vector<::ISPA_STD::Node<::Parser::Rules, Types::rule::value>> shadow_8; std::vector<::ISPA_STD::Node<::Parser::Rules, Types::rule::value>> uvar_4; bool success_9; ::ISPA_STD::Node<::Parser::Tokens, Types::__WS> __WS_10; bool success_11; ::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_2> AUTO_2_12; bool success_13; success_1 = false; if (!(std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_1>>((*pos)))) { return {}; } AUTO_1_0 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_1>>((*pos)); success_1 = true; pos++; success_3 = false; if (std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::__WS>>((*pos))) { __WS_2 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::__WS>>((*pos)); success_3 = true; pos++; } success_6 = false; // grammar `@ rule::value+;`: repeat named rule; collect every matched value success_9 = false; while (true) { rule_value_5 = rule_value(pos); if (!(rule_value_5.status)) { break; } success_6 = true; pos = rule_value_5.it; element_7 = rule_value_5.node; shadow_8.push_back(element_7); success_9 = true; } if (!success_9) { return {}; } ::ISPA_STD::assign_compatible(uvar_4, shadow_8); success_11 = false; if (std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::__WS>>((*pos))) { __WS_10 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::__WS>>((*pos)); success_11 = true; pos++; } success_13 = false; if (!(std::holds_alternative<::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_2>>((*pos)))) { return {}; } AUTO_2_12 = std::get<::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_2>>((*pos)); success_13 = true; pos++; Types::rule::value::group result; ::ISPA_STD::assign_compatible(result.value, uvar_4); ::ISPA_STD::MatchResult<Rules, Types::rule::value::group, IT> match_result; match_result.status = true; match_result.node.set_data(result); match_result.it = pos; return match_result; } // ... public: auto parseFromTokens() -> void override; auto lazyParse() -> void override;
// Parser.cpp #include "Parser.h" auto ::Parser::FlatTypes::AUTO_5::write_to_output (::ISPA_STD::ASTPrinter<std::ostream>& printer) const -> void{ printer.node("AUTO_5", true); } auto ::Parser::FlatTypes::AUTO_5::print (std::ostream& os) const -> void{ ::ISPA_STD::ASTPrinter<std::ostream> printer = ::ISPA_STD::ASTPrinter<std::ostream>{os}; write_to_output(printer); } auto ::Parser::FlatTypes::AUTO_5::to_string () const -> std::string{ return ::ISPA_STD::concat("AUTO_5 {", "}"); } auto Parser::FlatTypes::operator<<(std::ostream &os, const AUTO_5 &value) -> std::ostream&{ value.print(os); return os; } // ... ::ISPA_STD::DFA::API::CharToClass Parser::Lexer::char_class_table = {...}; ::ISPA_STD::DFA::API::Table<21, 129> Parser::Lexer::dfa_table = {...} ::ISPA_STD::DFA::API::Table<211, 4> Parser::Lexer::action_table = {...} auto ::Parser::Lexer::semantic_action_exec (long long state, const ::ISPA_STD::DFA::API::Captures& captures, long long start_pos, const char* start, long long length, long long line) -> std::pair<long long, Token>{ switch (state) { case 0: { return std::make_pair(::ISPA_STD::DFA::API::null_state, ::ISPA_STD::Node<::Parser::Tokens, Types::__WS>::create(start_pos, start, length, line, Tokens::__WS, Types::__WS{})); break; } case 1: { return std::make_pair(::ISPA_STD::DFA::API::null_state, ::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_1>::create(start_pos, start, length, line, Tokens::AUTO_1, Types::AUTO_1{})); break; } case 2: { return std::make_pair(::ISPA_STD::DFA::API::null_state, ::ISPA_STD::Node<::Parser::Tokens, Types::AUTO_2>::create(start_pos, start, length, line, Tokens::AUTO_2, Types::AUTO_2{})); break; } case 3: { char value; if (captures.is_set(1)) { value = captures.character(1); } else { if (captures.is_set(3)) { value = captures.character(3); } else { if (captures.is_set(2)) { value = captures.character(2); } } } return std::make_pair(::ISPA_STD::DFA::API::null_state, ::ISPA_STD::Node<::Parser::Tokens, Types::rule::value::QUANTIFIER>::create(start_pos, start, length, line, Tokens::rule_value_QUANTIFIER, Types::rule::value::QUANTIFIER{value})); break; } // ... }auto ::Parser::Lexer::init () -> void{ return ; } // the debug information for DFA table. Useful for developers std::array<::ISPA_STD::DFA::API::DFADebug, 226> Parser::Lexer::debug_array = {...}; std::unordered_map<long long, std::unordered_map<long long, long long>> Parser::Lexer::debug_index = {...}; auto ::Parser::Lexer::makeToken (const char*& pos) -> Token{ return lookup(dfa_table, char_class_table, action_table, tdfa_registers, semantic_action_exec, debug_array, debug_index, pos); } auto ::Parser::Parser::parseFromTokens () -> void{ tree = main(Lexer::iterator( * lexer)).node.data(); } auto ::Parser::Parser::lazyParse () -> void{ tree = main(Lexer::lazy_iterator( * lexer, text)).node.data(); }
Текущая работа
Сейчас я занимаюсь бутстрапингом парсера грамматики. Релизы доступны на GitHub, их можно скачать и запустить. Они достаточно стабильны, чтобы сгенерировать C+±парсер, скомпилировать его и разобрать ввод.
Планы на будущее
Модули
Семантические действия с продвинутыми правилами (python-подобный язык), блоки Fail с сообщениями об ошибках и стратегиями восстановления
Модификаторы
Шаблоны. Наследование в этой архитектуре вряд ли будет добавлено