README.md

Lingo

Lingo is a C++20 single-header library for building recursive descent parsers. Following a simplicity before performance philosophy, Lingo is intended for parsing small to medium-sized source files or structured text.

Lingo is currently under development. Expect strange things.

Introduction

With Lingo, you can express grammars in a syntax resembling EBNF (Extended Backus–Naur Form) directly in C++ code using operator overloading. There are no external dependencies — just drop include/lingo.h into your project.

Defining a grammar

Here's an example grammar for parsing a list of numbers separated by commas:

<comma>    = ","
<digit>    = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<number>   = <digit>+
<num_list> = <number> (<comma> <number>)*

In Lingo:

lingo::rule comma(',');
lingo::rule digit('0', '9');
lingo::rule number   = lingo::repeat(digit, 1);       // at least one digit
lingo::rule num_list = number + lingo::repeat(comma + number, 0);

Grammars

You build grammars using lingo::rule and lingo::placeholder. Placeholders allow recursive grammars by acting as forward declarations.

Rule constructors

Form	Matches
rule('a')	single character a
rule('a', 'z')	any character in range a–z
rule({'x','y','z'})	any character from the list
rule("hello")	the literal string hello

Operators

Operator	Meaning
a + b	sequence: a followed by b
a | b	alternation: a or b
!a	negation lookahead: succeeds if a does not match (does not consume input)
repeat(r, min)	repeat r at least min times
repeat(r, min, max)	repeat r between min and max times (0 = unlimited)

Example: recursive expression grammar

<expression> = ["+"|"-"] <term> {("+"|"-") <term>}
<term>       = <factor> {("*"|"/") <factor>}
<factor>     = <number> | "(" <expression> ")"

In Lingo:

lingo::rule lparen('('), rparen(')');
lingo::rule sign({'+', '-'});
lingo::rule plus('+'), minus('-'), mul('*'), div('/');
lingo::rule digit('0', '9');
lingo::rule number = lingo::repeat(digit, 1);

lingo::placeholder expression_placeholder;
lingo::rule factor = number | (lparen + expression_placeholder + rparen);
lingo::rule term   = factor + lingo::repeat((mul | div) + factor, 0);
lingo::rule expression =
    lingo::repeat(sign, 0, 1) +
    term +
    lingo::repeat((plus | minus) + term, 0);

expression_placeholder.set(expression);

Named rules

To produce meaningful error messages, assign names to rules using the named constructor variants:

lingo::rule anon_digit('0', '9');               // anonymous
lingo::rule named_digit("digit", '0', '9');     // named
lingo::rule named_number("number", lingo::repeat(digit, 1));

Only some rules need names — diagnostics reference the nearest named ancestor.

Parsing

Source input

Lingo includes a lightweight source class that owns a string and tracks position, line, and column.

// From a string
lingo::source src("1 + 2 * 3");

// From a file
lingo::source src = lingo::source::from_file("data/example.txt");

Parsing is done by constructing a lingo::grammar object from a rule, then calling one of its methods against a lingo::source.

Syntax check only

lingo::source src("1 + 2 * 3");
lingo::grammar g(expression);
if (!g.check(src))
    std::cerr << "parse failed\n";

Check with error message

lingo::source src("1 + * 3");
std::string error;
if (!g.check(src, error))
    std::cerr << error << '\n';
// unexpected '*', expected number at line 1 column 5

Error messages include the unexpected character, the nearest named rule that was expected, and the line and column.

Building a parse tree

lingo::parse_node tree;
std::string error;
if (g.parse(src, tree, error)) {
    // tree contains named nodes with source spans
}

parse_node stores:

• name — the rule name (only named rules appear in the tree)
• start / end — byte offsets into the source
• children — child named nodes

Helper methods on parse_node:

node.text(src);               // matched source text
node.find("name");            // first direct child by name
node.all("name");             // all direct children by name
node.find_deep("name");       // first descendant DFS
node.collect("name");         // all descendants DFS

Evaluation

Lingo does not provide built-in evaluation. You call grammar::parse() to get a named parse tree, then walk it yourself. The samples/ directory contains two complete working examples that illustrate the two main approaches.

Expression evaluator (samples/eval/)

A recursive descent evaluator for arithmetic expressions with operator precedence, unary minus, and parentheses. It demonstrates the direct walk pattern: the parse tree is walked in a single recursive function without building any intermediate representation.

The grammar produces named nodes number, sign, addop, mulop, unary, factor, term, and expression. Because the grammar is left-recursive by construction, children of expression and term already alternate value/operator/value:

expression
  ├─ term          ← left operand
  ├─ addop ("+")
  └─ term          ← right operand

The entire evaluator is a single eval() function that pattern-matches on the node name:

double eval(const parse_node &n, const source &src)
{
    if (n.name == "number") return std::stod(n.text(src));
    if (n.name == "factor") return eval(n.children[0], src);
    if (n.name == "unary")  return sign * eval(n.children[1], src);
    // expression / term: fold [v, op, v, op, ...]
    double result = eval(n.children[0], src);
    for (size_t i = 1; i + 1 < n.children.size(); i += 2) { ... }
    return result;
}

This approach works well when the parse tree structure maps cleanly onto the computation — no intermediate AST is needed.

BASIC interpreter (samples/basic/)

A tiny BASIC interpreter supporting LET, PRINT, IF/THEN, GOTO, and END. It demonstrates the two-phase pattern: first build an intermediate AST from the parse tree, then execute the AST.

An intermediate AST is necessary here because:

• Variables need to be resolved at runtime, not at parse time.
• GOTO needs a map from line number to program index, which requires all lines to be collected first.

The two phases are:

1. Parse → AST: build_program_ast() walks the parse tree using collect("line"), then for each line uses find("statement") / find("identifier") / all("expression") etc. to build line_ast and statement_ast structs.

2. Execute: A simple interpreter loop with a program counter (pc), a variable map (vars), and a line-number index (index_by_line) for GOTO resolution.

Use the two-phase approach when you need to look ahead, resolve references across the tree, or separate parsing concerns cleanly from execution.

Railroad diagrams

samples/railroad/ generates railroad (syntax) diagrams from a grammar. It is a sample, not part of the library: it is built entirely on the public node_visitor interface, so railroad.h can be copied straight into your own project. Header-only, no dependencies.

#include <lingo.h>
#include "railroad.h"

lingo::placeholder expr;
lingo::rule digit("digit", '0', '9');
lingo::rule number("number", lingo::repeat(digit, 1));
lingo::rule expression("expression",
    number | (lingo::rule('(') + expr + lingo::rule(')')));
expr.set(expression);

std::ofstream("expr.svg") << lingo::railroad_svg(expression);

Or a diagram per rule, cross-referenced by name:

lingo::railroad_document doc;
doc.add("expression", expression);
doc.add("number", number);
doc.add("digit", digit);
doc.svg_file("grammar.svg");

./bin/sample-railroad bin/data writes a set of example diagrams, including notation.svg — every primitive above on one page.

How recursion is handled

Recursion is detected with an active path set of node IDs, not a global visited set. A node already on the current path is a cycle and becomes a reference; a node merely seen before is a shared sub-expression and expands again. So this renders two boxes, not a reference:

lingo::rule digit('0', '9');
lingo::rule pair = digit + digit;    // both occurrences render normally

while A -> B -> A terminates by rendering the repeated node as a reference, labelled with the node's name where it has one and #1, #2, ... where it does not.

Notation

Grammar	Diagram
rule('a')	box a
rule('0','9')	box [0-9]
rule({'x','y','z'})	box [xyz] (a choice of anonymous literals is one class)
rule("hello")	box hello (a run of anonymous characters is one box)
a + b	horizontal sequence
a | b	stacked alternatives, in grammar order
repeat(r, 0, 1)	bypass line over r
repeat(r, 0)	bypass line plus return loop
repeat(r, 1)	return loop
repeat(r, 2, 4)	one loop annotated {2,4}, never four copies
!r	dashed frame labelled NOT

Non-printable characters use readable escapes: \n, \t, \r, \s (space), \x1b.

Output

SVG is canonical: valid viewBox, standard primitives only, no JavaScript, no external CSS or fonts, opaque white background by default (set style.background = "none" for transparency). Output is deterministic — identical grammars produce byte-identical SVG regardless of node IDs — so generated diagrams can be committed without noisy diffs.

railroad-png.h adds an optional raster backend that consumes the same computed layout, so PNG and SVG can never drift apart. It carries its own rasterizer, bitmap font and deflate encoder, and still has no external dependencies. Include it only if you want PNG:

#include "railroad-png.h"
lingo::railroad_png_file(expression, "expr.png");

Configuration

railroad_options controls behaviour, railroad_style controls appearance; no visual value is hard-coded in the renderer.

lingo::railroad_options opt;
opt.style = lingo::railroad_style::dark();   // or minimal(), publication()
opt.style.line_color = "#334155";
opt.name_mode = lingo::railroad_name_mode::references_for_named_nodes;
opt.show_rule_names = true;
opt.scale = 2.0;

Option	Default	Description
name_mode	references_for_recursive_only	expand_all, or references_for_named_nodes for documentation
show_repeat_counts	true	Annotate bounded loops with {n,m}
flatten_sequences / flatten_choices	true	Splice nested unnamed sequences and choices
merge_char_sequences / merge_char_classes	true	Collapse literal runs and literal choices into one box
show_rule_names	false	Frame named sub-diagrams with their rule name
show_node_ids	false	Debugging aid; breaks determinism
scale / png_dpi	1.0 / 96	Output size

Project structure

lingo
├── README.md              ← This file
├── LICENSE                ← MIT license
├── CMakeLists.txt         ← Build configuration
├── include/
│   └── lingo.h            ← Single header (drop this into your project)
├── samples/
│   ├── eval/              ← Arithmetic expression parser/evaluator
│   ├── basic/             ← Tiny BASIC interpreter
│   └── railroad/          ← Railroad diagram generator (header-only)
├── tests/
│   ├── parse-tests.cpp    ← Core parse tests
│   ├── basic-tests.cpp    ← BASIC grammar tests
│   ├── railroad-tests.cpp ← Railroad diagram tests
│   └── data/              ← Input files for tests
└── build/                 ← CMake build output

Architecture

Lingo is organized in four layers, each with a single responsibility:

┌─────────────────────────────────────────────────────────┐
│  rule / placeholder          (grammar layer)            │
│  User-facing combinators. Build a shared_ptr<node>      │
│  tree via operator+, operator|, operator!, repeat().    │
│  rule describes structure — it never parses anything.   │
├─────────────────────────────────────────────────────────┤
│  node hierarchy              (grammar representation)   │
│  literal, or_node, and_node, not_node, repeat_node,     │
│  placeholder_node. Each node implements accept() for    │
│  the visitor pattern and carries a stable id() for      │
│  graph identity. Nodes are ref-counted and shared       │
│  across rules to avoid copying.                         │
├─────────────────────────────────────────────────────────┤
│  detail::parser              (parsing engine)           │
│  Implements node_visitor. Walks the grammar node tree   │
│  against a source, tracks the furthest failure for      │
│  error messages, and — when a root parse_node is        │
│  supplied — incrementally builds the named parse tree   │
│  with checkpoint/rollback on backtrack.                 │
├─────────────────────────────────────────────────────────┤
│  grammar                     (user-facing facade)       │
│  Owns the root node (shared_ptr). Exposes check() and   │
│  parse() which construct a detail::parser internally    │
│  and run it. Users never touch detail::parser directly. │
└─────────────────────────────────────────────────────────┘

Key design decisions:

• rule is immutable after construction — combinators return new rules, never modify existing ones.
• Only named nodes (rule("name", ...)) appear in the parse tree. Unnamed nodes are transparent glue — they match input but produce no tree output.
• detail::parser is stateless between calls; grammar::check() / grammar::parse() construct one per invocation.
• placeholder breaks recursive grammar cycles: it holds a shared_ptr<node> that is filled in after the recursive rule is defined.
• node::id() and node::name() have separate jobs. id() is unique for the node's lifetime and answers which node is this — that is what graph tooling uses to detect recursion. name() is for humans and need not be unique.
• rule::accept() is public and const, so external visitors can walk a grammar without the library knowing about them. The railroad diagram generator in samples/railroad/ is written entirely against that interface.

Building

No dependencies — GoogleTest is fetched automatically by CMake.

cmake -B build
cmake --build build

Run tests:

./bin/test-lingo

Build options

Option	Default	Description
BUILD_TESTS	ON	Build the test executable
BUILD_SAMPLES	ON	Build the sample executables

Running samples

./bin/sample-evaluator "1 + 2 * (3 + 4)"
./bin/sample-basic path/to/program.bas
./bin/sample-railroad bin/data      # writes example diagrams