Żbik – LR(k) grammar analysis and parser construction in C++20

What it does

LR parsing with more lookahead

Canonical LR(k), LALR(k) built directly or by merging, SLR(1), conflict diagnostics for the grammar itself, and a stack-based parser runtime that never backtracks.

Grammar analysis

NULLABLE, FIRST(k) and FOLLOW(k), productivity and reachability, recursion and cycle detection, and the minimum and maximum lengths a symbol can yield.

Sequences and ambiguity

Enumerate terminal sequences with their derivation trees up to a length bound, and search for a sequence with two different trees. A bounded search finds ambiguity; not finding it proves nothing.

EBNF

A restricted programmatic EBNF model converts to BNF, and the helper productions remember where they came from, so that diagnostics point at what you wrote.

Compact tables

ACTION and GOTO tables compressed for storage, and exported as a DSL or as JSON.

Lexers

Regular expressions to NFA and DFA, byte and UTF-8 lexers, and lexer classes that the parser switches by context.

Use it

Żbik needs CMake 4.0, a C++20 compiler and ICU (uc); GoogleTest for its tests.

git clone https://github.com/parstools/zbik.git
cmake -S zbik -B zbik/build -DCMAKE_BUILD_TYPE=Release -DBUILD_TESTING=ON
cmake --build zbik/build -j4
ctest --test-dir zbik/build --output-on-failure

The zbik_core library embeds in another CMake project:

add_subdirectory(path/to/zbik)
target_link_libraries(my_parser PRIVATE zbik_core)

The zbik command-line tool analyzes and classifies a corpus of BNF grammars; it does not generate parser source code. For a grammar language, ASTs, semantic analysis and code generation on top of Żbik, see Borsuk.

build/zbik res/grammars.dat /tmp/grammars-result.dat --max-lr=3

Documentation

Each document also has a Polish version, with the .pl.md suffix.