ISPA Parser Generator

ISPA turns an .isc grammar into a lexer and parser that build a typed AST. Everything is generated ahead of time — lexer tables, parser logic, AST shape — as C++17, Python or Rust source you ship. The generated parser never depends on ISPA at runtime.

Usage demo

usage.mp4

Why ISPA

• Typed ASTs, no boilerplate. @ marks what to capture and {@} (or @{field, ...}) shapes the result. The tree is built while parsing, so you don't need a visitor or listener pass.
• Static generation. Grammars compile to tables and target code once. Nothing is interpreted at runtime.
• One grammar, several languages. C++17, Python and Rust targets share the same .isc source.
• LL and LR. LL is the full-featured default. LR0/LALR (deterministic and generalized) is available when you want it.
• Built for real grammars. Imports, external parsers and incremental generation let you split and reuse grammars.
• Good tooling. Language server, JetBrains plugin, a parser debugger (ispadbg) and a browser playground.

Install

# Linux / macOS (Apple Silicon)
curl -fsSL https://raw.githubusercontent.com/Sinfolke/ispa-parser-generator/main/scripts/install.sh | sh

# Windows PowerShell
irm https://raw.githubusercontent.com/Sinfolke/ispa-parser-generator/main/scripts/install.ps1 | iex

Then install the standard library and the runtime for each language you generate:

ispa-pkg install std
ispa-pkg install target-cpp     # C++ output
ispa-pkg install python-target  # Python output
ispa-pkg install rust-target    # Rust output
ispa-pkg --export-permanent

• std holds the .isc grammar modules and their Python helpers. See standard library.
• target-cpp builds libispa-core.a and the C++ headers. Run ispa-pkg --build target-cpp to rebuild it, and eval "$(ispa --export)" to export include and library paths into your shell.
• python-target and rust-target provide the runtimes for those languages.

ispa --help lists generation options. ispa-pkg --help covers package management.

Quick start

Save as grammar.isc:

module main -> main;

NUMBER: @ [0-9]+ {@};
main: @ NUMBER {@};

Generate a parser:

ispa -l cpp    -a LL grammar.isc -o build/Parser   # C++
ispa -l python -a LL grammar.isc -o build/Parser   # Python
ispa -l rust   -a LL grammar.isc -o build/Parser   # Rust

Use it from C++:

#include <Parser.h>

Parser::Parser parser;
auto tree = parser.parse("123");

Switch -a LL to -a LALR (or LR(0)) to generate an LR parser from the same grammar.

CMake setup, linking and the Python and Rust paths are covered in Getting Started and Your First Grammar.

Features

Area	What you get
Targets	C++17, Python (ispa_std runtime), Rust
Algorithms	LL (most complete), LR0/LALR with generalized parsing
Lexing	Tagged-DFA lexer, captures, nested token data, dynamic patterns, negative matching
Error recovery	Fail blocks (ctx.error, skip, insert, replace, retry, abort) and synchronization
Actions	Embedded Python-like actions and match statements in advanced rules
Native bindings	Declare functions in plain Python and implement them in the host language (guide)
External parsers	A grammar can call another generated parser and keep its node type
Modules	Grammar imports and incremental generation
Debugging	ispadbg with breakpoints and trace replay
Browser	WASM build and a playground

Dynamic patterns

Match a string that depends on something captured earlier, such as a closing quote that must equal the opening one:

module main -> main;

QUOTE: '"' | '\'';

STRING<QUOTE>:
    &q ${QUOTE} @ !($q | [\n\r])* $q
    {@}
;

main: @ STRING<QUOTE> {@};

• &q captures the matched text into a variable.
• ${QUOTE} matches a compile-time template argument.
• !($q | [\n\r])* matches anything except the captured quote or a line break.
• $q matches the closing quote.

Coming from other tools

ANTLR, Flex or Bison? Converters migrate existing grammars and report what needs manual work:

ispa-pkg tool antlr-to-ispa
ispa-pkg tool flex-to-ispa
ispa-pkg tool bison-to-ispa

See ANTLR conversion and Flex/Bison conversion.

Key differences from ANTLR:

• Captures are explicit. Only tokens and subrules marked with @ end up in the AST.
• Output is ahead of time. The generated parser is plain source, not a runtime that interprets your grammar.
• Left recursion is preserved by the converter.

Performance

ISPA builds a typed AST while parsing and keeps error-recovery bookkeeping, so it trades some raw speed for that. All numbers below were measured on a Core i5-12450H (plugged in, Linux, Clang -O3, Rust --release with codegen-units=1), as the median of several runs. A browser was open during the runs, so expect a few percent of noise. Lower is faster.

Python grammar (real-world input)

The input is a corpus of top-level statements taken from the Python standard library, normalized with ast.unparse and filtered to the statements the bundled ISPA Python grammar accepts (4068 of 5402). Times are parse time in ms; lexing is reported separately.

Target	Algorithm	8 KB	32 KB	262 KB
C++	LL	21.9	63.5	454
C++	LALR (generalized)	796.5	7788	n/a
Rust	LL	21.8	74.7	535
Rust	LALR (generalized)	395.5	3316	n/a
Python	LL	424.6	1642	12483
Python	LALR (generalized)	855.7	n/a	n/a
ANTLR 4 (C++), no tree		9.9	28.4	74.7
ANTLR 4 (C++), parse tree		10.0	29.1	83.6

Lexing time at 8 KB / 32 KB / 262 KB: C++ 1.3 / 8.0 / 295 ms, Rust 1.2 / 2.7 / 19 ms, Python 85 / 324 / 3231 ms, ANTLR 98 / 363 / 2799 ms.

The C++ LL and Rust LL rows were re-measured after the parser-speed work (failure signalled by a flag instead of a C++ exception, shared recovery claim sets, terminal and rule fast paths, no per-character allocations in the Rust lexer). The LALR, Python-target and ANTLR rows are carried over from the earlier run and were not re-measured, so compare them with the LL rows only roughly (the machine was about 15% slower in the later session, judging by ANTLR on JSON).

Caveats:

• ANTLR parses faster than ISPA here, and its lexer is slower. ISPA's figures include building the typed AST and recovery bookkeeping; the ANTLR figures use the full Python 3 grammar from grammars-v4, ISPA's is a subset.
• The Python grammar has LALR conflicts, so LALR uses the generalized parser (runtime branching). It hits its resource limit above ~32 KB ("n/a"). Use LL for this grammar.
• The Python target and Rust LALR are not optimized yet. The Rust LL build used codegen-units=8 for this grammar (a single unit ran out of memory while compiling it).
• Backtracking no longer throws. Failed alternatives used to cost a C++ exception each (about 60% of the C++ LL time on the 262 KB input). The core now signals an absent rule by a flag that the generated rules check and return on, which is what made C++ LL about 3.9x faster on this grammar.
• No bison grammar for Python exists that we could use, so bison is compared on JSON below.

Reproduce: python3 tools/core-parity/benchmark_python.py --targets cpp rust python --algorithms LL LALR.

JSON, 10 MB (bison comparison)

Configuration	Lex	Parse
flex + bison, recognition only		60 ms
ANTLR 4 (C++), no tree (lex + parse)		1130 ms
ANTLR 4 (C++), parse tree (lex + parse)		1394 ms
ISPA C++ LL	892 ms	1154 ms
ISPA C++ LALR	881 ms	2255 ms
ISPA Rust LL	998 ms	1671 ms
ISPA Rust LALR	1084 ms	4021 ms
ISPA C LL	861 ms	981 ms

Medians of 5 interleaved runs on a 10 MB compact JSON file. The C LL row was measured separately (median of 5, -O2, python3 tools/core-parity/benchmark_c.py) after the other rows; only LL exists for the C target so far. For reference, the Rust LL target took 2064 ms to lex and 5892 ms to parse before the Rust speed-up work (3.5x faster parse, 2.1x faster lex now).

flex + bison is far faster, about 19x the C++ LL parse, but it only recognizes the input and builds no AST. ISPA's C++ LL parse builds a full typed AST. On this grammar LR is about 2x slower than LL in C++ and about 2.4x slower in Rust, whose LR driver has not been optimized yet. Sources: parser/ispa/bench and tools/core-parity/benchmark_json.py.

Limitations

• Prefer LL for applications. LR modes support fewer grammar features, and some LL actions and recovery have no LR equivalent.
• External parser calls need LL and lazy tokenization. An eager lexer is rejected if the grammar uses them.
• Rust and Python do not yet match every C++ backend option.
• Generated C++ requires C++17. Building ISPA itself needs Clang + libc++ on Linux or MSVC on Windows (GCC is not supported yet).
• Release artifacts cover Linux x86_64, Windows x64 and macOS Apple Silicon. See Releases.
• Editors: the JetBrains plugin is the tested integration (highlighting, completion, diagnostics, fail-block support). VS Code, Neovim and Emacs extensions exist but are not tested by this project.

Learn more

• Wiki: grammar syntax, CLI reference, generated code and runtime API, error recovery, modules, package manager, debugging, building from source.
• Changelog
• Library versioning and ispa-pkg doctor
• Discussions and Issues for questions and bug reports.

License

Apache-2.0