TL;DR – Copy-paste Matcheroni.hpp into your C++20 project and you can build simple parsers without needing a parser generator or a regex library.

Matcheroni is a minimal, zero-dependency (not even stdlib), single-file header library for building pattern-matchers, lexers, and parsers out of trees of C++20 templates.

Matcheroni is a generalization of Parsing Expression Grammars and can be used in place of regular expressions in many cases.

Matcheroni generates tiny code – 100s of bytes for moderately-sized patterns versus 100k+ if you have to include the std::regex library.

Matcheroni generates fast code – often 10x faster than std::regex.

Matcheroni matchers are more readable and more modular than regexes – you can build large matchers out of small simple matchers without affecting performance.

Matcheroni allows you to freely intermingle C++ code with your matcher templates so that you can build parse trees, log stats, or do whatever else you need to do while processing your data.

Matcheroni doesn’t have to match text – you can customize it to match patterns in arrays of any type as long as you define appropriate comparison functions for your types.

Matchers are roughly equivalent to regular expressions. A regular expression using the std::regex C++ library

std::regex my_pattern("[abc]+def");

would be expressed in Matcheroni as

using my_pattern = Seq'a','b','c'>>, Lit<"def">>;

In the above line of code, we are defining the matcher “my_pattern” by nesting the Seq<>, Some<>, Atom<>, and Lit<> matcher templates. The resuling type (not instance) defines a static “match()” function that behaves similarly to the regex.

Unlike std::regex, we don’t need to link in any additional libraries or instantiate anything to use it:

const std::string text = "aaabbaaccdefxyz";

// The first argument to match() is a user-defined context pointer.
// The second two arguments are the range of text to match against.
// The match function returns the _end_ of the match, or nullptr if there was no match.
const char* result = my_pattern::match(nullptr, text.data(), text.data() + text.size());

// Since we matched "aabbaaccdef", this prints "xyz".
printf("%sn", result);

Matchers are also modular – you could write the above as

using abc = Atom<'a','b','c'>;
using def = Lit<"def">;
using my_pattern = Seq, def>;

and it would perform identically to the one-line version.

Unlike regexes, matchers can be recursive. Note that you can’t nest a pattern inside itself directly, as “using pattern” doesn’t count as a declaration. Forward-declaring a matcher function and using that in a pattern works though:

Install Ninja if you haven’t already, then run ninja in the repo root.

See build.ninja for configuration options.

If you’re familiar with C++ templates, you are probably concerned that this library will cause your binary size to explode and your compiler to grind to a halt.

I can assure you that that’s not the case – binary sizes and compile times for even pretty large matchers are fine, though the resulting debug symbols are so enormous as to be useless.

Matcheroni is based on two fundamental primitives –

• A “matching function” is a function of the form atom* match(void* ctx, atom* a, atom* b), where atom can be any data type you can store in an array, ctx is an opaque pointer to whatever bookkeeping data structure your app requires, and a and b are the endpoints of the range of atoms in the array to match against.

• A “matcher” is any class or struct that defines a static matching function named match().

Matching functions should return a pointer in the range [a, b] to indicate success or failure – returning a means the match succeded but did not consume any input, returning b means the match consumed all the input, returning nullptr means the match failed, and any other pointer in the range indicates that the match succeeded and consumed some amount of the input.

Matcheroni includes built-in matchers for most regex-like tasks, but writing your own is straightforward. Matchers can be templated and can do basically whatever they like inside match(). For example, if we wanted to print a message whenever some pattern matches, we could do this:

and we could use it like this:

Since Matcheroni is based on Parsing Expression Grammars, it includes all the basic rules you’d expect:

• Atom matches any single “atom” of your input that is equal to one of the template parameters. Atoms can be characters, objects, or whatever as long as you implement atom_cmp(...) for them. Atoms “consume” input and advance the read cursor when they match.
• Seq matches sequences of other matchers.
• Oneof returns the result of the first successful sub-matcher. Like parsing expression grammars, there is no backtracking – if x matches, we will never back up and try y.
• Any is equivalent to x* in regex – it matches zero or more instances of x.
• Some is equivalent to x+ in regex – it matches one or more instances of x.
• Opt is equivalent to x? in regex – it matches exactly 0 or 1 instances of x.
• And matches x but does not advance the read cursor.
• Not matches if x does not match and does not advance the read cursor.

While writing the C lexer and parser demos, I found myself needing some additional pieces:

• Rep matches x N times.
• NotAtom is equivalent to [^abc] in regex, and is faster than Seq>, AnyAtom>
• Range is equivalent to [x-y] in regex.
• Until matches anything until X matches, but does not consume X. Equivalent to Any,AnyAtom>>
• Ref allows you to plug arbitrary code into a tree