Parsers don’t have to be complicated | Branimir Karadžić's Home Page

Table of Contents

Introduction

Years ago I started writing a proper shader front-end parser for bgfx and used the Lemon parser generator. It was small, it worked, but I never liked the code it produced. The generated output felt hard to read, and the code that generated the parser also felt alien to me. Every time the grammar changed I had to re-learn the shape of the resulting code. It solved the problem, but eventually I abandoned it.

On the other side of the spectrum I kept writing ad-hoc parsers for smaller things where using something like Lemon was overkill. Pointer arithmetic, manual loops over characters, a handful of strchr/strncmp style calls, some state variables, and a hope that I hadn’t missed an edge case. These were fast and had no dependencies, but they always ended up repeating the same patterns: skipping whitespace, collecting identifiers, tracking line numbers for error messages, handling the inevitable off-by-one when the input wasn’t perfectly formed. Each new parser became its own little minefield of one-off bugs, and every new thing that needed parsing got its own private copy of them.

Most of this ad-hoc parsing code looked roughly like this:

1const char* pos = input.getPtr();<br>2const char* end = input.getTerm();<br>4while (pos end<br>5 && bx::isSpace(*pos) )<br>6{<br>7 ++pos;<br>8}<br>10const char* start = pos;<br>11while (pos end<br>12 && (bx::isAlphaNum(*pos) || *pos == '_') )<br>13{<br>14 ++pos;<br>15}<br>16<br>17bx::StringView ident(start, pos);

Multiply that pattern by every token type, add manual line counting, add handling for \r\n versus \n, and you have the classic ad-hoc scanner. It works and it is fast. I’ll leave it to the reader’s imagination how the same logic would look after someone decided it needed to be &ldquo;modern&rdquo; and rewrote it with Boost.Spirit.

What I wanted was something in between: a small set of reusable primitives that took care of the repetitive parts of scanning without dragging in a generator or a dependency graph. Zero-copy, allocation-free, and readable in a debugger. That is what bx::Scanner is. It is not a parser generator and not a Parsing Expression Grammars (PEG) library, and it is not trying to become either.

Design

bx::Scanner is built around a small set of deliberate constraints:

Zero-copy and non-owning.<br>The scanner never allocates and never copies text. Every result is a StringView that points directly into the original input, including the empty ones, which point at the cursor rather than at nothing.

One cursor, and it never moves on its own.<br>A single current position. accept / acceptWhile / acceptUntil move it forward. peek runs the same test without moving. seek and reset exist, but nothing backtracks implicitly.

Built-in line and column tracking.<br>Any movement across a newline updates the line number, including a backwards seek. getLine and getColumn are always available and both are one-based, which makes decent error messages nearly free.

Character classes instead of a mini-language.<br>A handful of classes (Class::Space, Class::NonSpace, Class::Identifier, Class::EndOfLine, Class::NewLine) cover most everyday scanning. Anything more specific is an ordinary bool(*)(char) predicate handed to accept / acceptWhile. There is no pattern language to learn, and nothing to debug except your own function.

Tiny surface area.<br>The whole public interface fits in one small header.

The workflow is always the same: construct a Scanner over a StringView, then peek and accept until you are done.

1bx::Scanner scanner(input);<br>3// Skip leading whitespace.<br>4scanner.accept(bx::Scanner::Class::Space);<br>6// Read an identifier.<br>7const bx::StringView ident = scanner.accept(bx::Scanner::Class::Identifier);

accept consumes matching text and returns it as a StringView. If the expected token is not there it returns an empty view and leaves the cursor alone, so you can go try the next alternative. peek runs the same test without moving.

StringView has no operator bool, so a successful match reads as !scanner.accept('=').isEmpty(). Noisier than returning a bool, but the matched text comes back with the answer instead of requiring a second call to go get it.

Here is how it is actually used in bx today.

LineReader, the simplest helper

LineReader splits input into lines, handles \n and \r\n, and trims the stray trailing \r that malformed input likes to leave behind:

1for (bx::LineReader lr(fileContents); !lr.isDone(); )<br>2{<br>3 const bx::StringView line = lr.next();<br>5 // `line` excludes the terminator, and lr.getLine() is its line number.<br>6}

Note the loop condition. The obvious-looking while (!lr.next().isEmpty() ) is wrong. A file can contain a blank line, and that blank line is a valid result. Empty means &ldquo;this line has no characters&rdquo;, not &ldquo;there are no more lines&rdquo;, so the exhaustion test has to be isDone.

INI parsing, and sub-scanners

This one replaced a third-party INI library outright....