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

The generator emits a Parser.h / Parser.cpp pair: enums for Tokens and Rules, a FlatTypes namespace with one struct per AST node (each carrying write_to_output, print, and to_string helpers), a Lexer built around static DFA/action tables plus a semantic_action_exec dispatcher, and a Parser with one templated method per grammar rule (e.g. rule_value_pattern, rule_value_group) that walks the token stream, matches alternatives, and assembles the typed AST node via assign_compatible. The .cpp file fills in the static tables and the stream-printing boilerplate for every generated type, plus parseFromTokens/lazyParse entry points that kick the whole thing off from a Lexer iterator.

It's generated code, so it isn't meant to be hand-edited — but it's plain, dependency-light C++ (aside from a small ispastdlib.hpp runtime support header), which keeps it easy to drop into a build and step through in a debugger when something needs diagnosing.

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