Introduction
This post is written for people, deep in compiler or dsl development, require parsing often, build complex configurations or engines from scratch. This tool is designed to parse most context-free languages with little effort. It does not pretend to generate something you can’t beat in performance, although it would be harder to achieve higher performance in hand-written parsers.
Related theory (free to skip)
Parsers are tools designed to perform transformation of text patterns to more machine friendly representation. Parser generators therefore generate parsers. They are often divided onto two stages, although they may be merged sometimes. Lexer stage process raw text and produce tokens, such called independent text chunks. These chunks are then processed by parser because their order affect the resulting representation. The representation can be output as CST or AST. CST (Concrete Syntax Tree) is prior to AST representation, where all tokens of parser’s rule are accessible. AST reduce this representation by only meangful tokens (e.g an expression group quotes vs group value). Other words an AST remove all Syntax context out of representation, so, theoritically, two AST can be equivalent with different syntax if semantics are the same, but it cannot apply to CST.
For lexer NFA or DFA is used. Shortly, these are tables where character map state, that state has one more character map another state … until end of input. NFA may have several next states on one character, while DFA is deterministic and maps one character -> exactly one state. NFA is easier to construct from regex, and often serve as intermediate representation in static generation. Decides DFAs only matched text and had no ability for captures. While walking DFA we could not execute arbitary semantic code. Semantics could be executed at the end only. To build an AST, people often had to parse again some chunks and extract data. Recently (around 2000), TNFA + TDFA was invented, and progressed until now (2026). Shortly it allows to capture WHILE walking table, so both CST and AST construction can be constructed fully automaticcally. No reparsing is needed too.
Parser is more developed topic. There are LL (Top-down) and LR(bottom-up) construction algorithms. This generator implements both, but Top-down is what has been implemented and highly tested. Shortly, this is function-per-rule, where they can call each other recursively. This is approach applied to hand written parsers, as production LR parsers are impractical to hand-write. For decides parser generators could not emit good error diagnostics and recovery strategies, include well established automatic AST construction techniques, provide semantic actions without grammar bloat in langauge-agnostic way, so they were considered toy by community and, for example, all major compilers are using hand written LL parsers.
Why another parser generator
almost 3 years ago I needed parser. Most of parser generators output is half usable out of the box. You must build AST, Error messages and recovery, all yourself (ANTRL), or write legacy grammars with code (Flex + Bison). Or use some generators that generate one-target parsers, or do not generate them at all but use language features to process text (Boost::spirit is pain to look at). If you want actually something production ready, eventually you’ll re-write this to hand-written parser. And if your grammar change you’ll have to maintain all changes yourself.
People raised this question recently, because for decides considered solved topic is not solved in terms of software. https://blog.adamant-lang.org/2019/dreaming-of-a-parser-generator/
This parser generator ideal state mostly follows the requirements by link above:
-
Composable grammars
-
Incrementability
-
Error messages and recovery
-
Token value generation
-
Automatic AST
-
Compiler error recovery
This is most impact points, but i can add also:
-
Static generation. No generate in runtime
-
No dependecies, generated parser should be easy to setup
-
Multi-language output
-
Semantic actions and error handling alongside grammar without bloating it
-
Flexibility to use in trivial and very large projects
-
Easy to use API
Core design and usage
Lexer is generated as TDFA, supporting grammar patterns + nested tokens (without losing AST structure) + parser-level rules inside tokens + Semantic actions while traversing.
TEMPLATED_TYPE: 'template' __WS 'type' __WS @ '==' | '!=' __WS @ 'int' | 'str' | 'bool' @{op, type};main: TEMPLATED_TYPE;
TEMPLATED_TYPE ├── op: == └── type: str
here it captured what marked @ and result token is AST-like. Nested tokens capture is also implemented, but small generator edits are needed to make it working. Architecture supports parser level rules, but it it not yet implemented.
Parser is LL(k) in this implementation but can be extended to LL(*) in future. It’s ast is fully constructed automatically, automatically supports recursive nodes and is ready to use out of the box.
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>
The snippet isn’t an example grammar — it’s ISPA’s own rule syntax, written in ISPA. The generator is self-hosted: the same DSL used to describe C or JSON. It is expressive enough to describe itself.
A few primitives to read it by:
-
@marks a capture point — the span starting there becomes available to the semantic action. This is the TDFA tagging mechanism surfacing directly in the grammar syntax, not bolted on afterward. -
{...}is a semantic action.{@}is shorthand for “return the single capture as-is” — used on leaf rules likeID,STRING, orQUANTIFIER, which just yield the text they matched. -
@{field1, field2}builds an AST node directly from named captures — no separate tree-construction code.rule’s action@{name, v}means “the node this rule produces has anamefield (from theIDcapture) and avfield (from the repeated#valuecaptures).” This is what “automatic AST” means in practice: the shape of the action is the shape of the node. -
#name:declares a nested, locally-scoped rule — visible only inside the rule that contains it.#value,#pattern,#captureetc. exist only withinrule;#pattern,#STRINGand friends exist only within#value. This keeps grammar-internal helper rules out of the global namespace instead of forcing every generator-wide rule to live at the top level. -
Standard regex-like operators carry over:
+(one or more),*(zero or more),?(optional),|(alternation), and quoted literals for exact text.\sis a built-in whitespace-skip token.
Walking it top to bottom: ID matches an identifier (letter, then letters/digits/underscore). A rule is a name, a colon, one or more #values, and a terminator — each #value being a #pattern (an ID reference, string, whitespace, or parenthesized #group) optionally followed by alternatives and a quantifier. main is just the entry point: a grammar file is one or more rules.
I can’t imagine user code to interact with parser simpler:
#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";}
How generated parser looks like
// 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 alternativesuccess_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 valuesuccess_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 developersstd::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 ()F
Currently working on
I’m bootstrapping grammar parser. releases are available on github, can be downloaded and run. They are stable enough to generate C++ parser, compile and parse an input.
Future features
-
Semantic actions with advanced rules (python-like language), Fail blocks with error message and recovery strategies.
-
Templates. Inheritance is unlikely to be added with this design
Project
ссылка на оригинал статьи https://habr.com/ru/articles/1092934/