Ispa parser generator

---

Introduction

This post is written for people deep in compiler or DSL development, who require parsing often, and 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 into two stages, although they may be merged sometimes. The lexer stage processes raw text and produces tokens, so-called independent text chunks. These chunks are then processed by the parser because their order affects 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 a parser's rule are accessible. AST reduces this representation to only meaningful tokens (e.g. an expression group's quotes vs. group value). In other words, an AST removes all syntax context from the representation, so, theoretically, two ASTs can be equivalent with different syntax if the semantics are the same — but that cannot apply to a CST.

For the lexer, an NFA or DFA is used. Shortly, these are tables where a character maps a state, that state has one more character mapping another state... until end of input. An NFA may have several next states on one character, while a DFA is deterministic and maps one character to exactly one state. NFA is easier to construct from regex, and often serves as an intermediate representation in static generation. Decidedly, DFAs only matched text and had no ability for captures. While walking a DFA, we could not execute arbitrary semantic code — semantics could only be executed at the end. To build an AST, people often had to parse some chunks again and extract data. Recently (around 2000), TNFA + TDFA was invented, and has progressed until now (2026). Shortly, it allows capturing while walking the table, so both CST and AST construction can happen fully automatically. No reparsing is needed either.

Parsing is a 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 a function-per-rule approach, where rules can call each other recursively — the approach applied to hand-written parsers, since production LR parsers are impractical to hand-write. For decades, parser generators could not emit good error diagnostics and recovery strategies, include well-established automatic AST construction techniques, or provide semantic actions without grammar bloat in a language-agnostic way — so they were considered a toy by the community, and, for example, all major compilers use hand-written LL parsers.

Why another parser generator

Almost 3 years ago I needed a parser. Most parser generators' output is only half usable out of the box. You must build the AST, error messages and recovery, all yourself (ANTLR), or write legacy grammars mixed with code (Flex + Bison). Or use generators that produce one-target parsers, or don't generate parsers at all but instead use language features to process text (Boost::spirit is painful to look at). If you want something actually production-ready, you'll eventually rewrite it as a hand-written parser. And if your grammar changes, you'll have to maintain all the changes yourself.

People have raised this question recently, because a topic considered solved for decades is not actually solved in terms of software: Dreaming of a parser generator.

This parser generator's ideal state mostly follows the requirements from the link above:

1. Composable grammars
2. Incrementability
3. Error messages and recovery
4. Token value generation
5. Automatic AST
6. Compiler error recovery

Those are the highest-impact points, but I'd add:

1. Static generation — no generation at runtime
2. No dependencies — the generated parser should be easy to set up
3. Multi-language output
4. Semantic actions and error handling alongside the grammar, without bloating it
5. Flexibility to use in both trivial and very large projects
6. An easy-to-use API

Core design and usage

The lexer is generated as a 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's marked @, and the resulting token is AST-like. Nested token capture is also implemented, but small generator edits are needed to make it work. The architecture supports parser-level rules, but that's not yet implemented.

The parser is LL(k) in this implementation but can be extended to LL(*) in the future. Its 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);

Grammar:

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 above 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 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 like ID, STRING, or QUANTIFIER, 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 a name field (from the ID capture) and a v field (from the repeated #value captures)." 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, #capture, etc. exist only within rule; #pattern, #STRING, and 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. \s is 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 the parser being any 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 the generated parser looks

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();
}

Currently working on

I'm bootstrapping the grammar parser. Releases are available on GitHub, can be downloaded and run. They're stable enough to generate a C++ parser, compile it, and parse an input.

Future features

1. Modules
2. Semantic actions with advanced rules (a Python-like language), with fail blocks for error messages and recovery strategies
3. Modifiers
4. Templates (inheritance is unlikely to be added with this design)

Project

github.com/Sinfolke/ispa-parser-generator

Comments

[Sinfolke]

Update: a python subset has just successfully parsed

even_more_complex = factory(1, enabled=True).items[compute(a + b * 2)].method(x if flag else y, mode='fast')[0]

the test, grammar and tree output:
github.com/Sinfolke/ispa-parser-ge...