excerpt: If the Advent of Code is mainly about parsing inputs, why not solve it only using parsers? A slightly too detailed introduction to compiler frontends.
For the past years, I've been challenging myself to solve the [Advent of Code](https://adventofcode.com/2022/about) challenges in the most cumbersome ways:
Using a different language each day or by using only C/C++[^php].
But as I left for the christmas holidays, I finally had some time to unwind from thinking about compilers all day.
And then it hit me: Couldn't I just [solve every task by writing a compiler](https://twitter.com/mycoliza/status/824809235632447492)?
[^php]: I faintly remember a PHP-only challenge, though I couldn't find the code for it. On the other hand it's scientifically proven that peoples' subconsciousness erases traumatic memories.
Now hear me out! Of course, strictly speaking a program reading arbitrary text to produce a number or string[^solutions] are hardly a compiler.
On the other hand, the compiler alignment chart (sourced from the [dead bird site](https://twitter.com/SeaRyanC/status/1334233376509763585)) would beg to differ:
[^solutions]: That's how solutions to Advent of Code challenges usually look, you enter a short string produced by your solution.
But it's true, effectively we only need the compiler frontend, i.e. a parser, since most tasks mainly revolve around parsing and processing input.
So my challenge for this year was: **Solve this year's Advent of Code challenges by only writing parsers.**
## The Tools
For a stupid challenge like this, it only made sense to use something arcane for implementing the parser: [`flex`](https://github.com/westes/flex) and [`bison`](https://www.gnu.org/software/bison/).
Both are by now tried and tested tools for writing parsers and lexers, respectively.
And, true to the spirit of the challenge, they generate C or C++ code, even though the latter doesn't compile.
Let me give you an overly long (but still overly simplified -- please don't roast me, dear colleagues) primer on parsing input the _proper_ way (using C and flex+bison).
One of this years' tasks that can most obviously be solved using a parser is [Day 10's CPU instruction interpreter](https://adventofcode.com/2022/day/10).
As part of the story, you have to fix up your broken handheld communication device after falling into a river.
To do that, you have to understand the assembly instructions given off by it.
The CPU has exactly one internal register `X` and features 2 operations:
-`addx val`: modifies the internal register by adding the value to it. This operation takes 2 cycles to complete.
The first task is then to take your [puzzle input](https://code.dummyco.de/feliix42/aoc-2022/src/commit/841b9ec20bdf828f721c12675564e571cc51d9ad/day_10/input.txt) in the form of a bit over 100 lines of instructions and parse it.
You are supposed to take the register contents during the 20th cycle, multiply it with the cycle count and repeat the process every 40 cycles.
All results then have to be summed to form your solution.
### Simplifying the Input
So let's just chuck our input into the parser, right? **Wrong.**
While you could do that, that's not how most parsers are intended to be used. Why?
Because you use a parser only to assign meaning to your input by matching it to certain rules.
To simplify this step, a commonly employed tool is the _lexer_.
It takes an input character stream and maps individual strings (which are called [lexemes](https://en.wikipedia.org/wiki/Lexical_analysis#Lexeme) in this context) to tokens (or syntax errors[^syntaxerror]).
This allows us to write a parser later on that directly operates on the emitted tokens.
Tool of our choice for this step is `flex`, a true jewel from the 80's that nicely integrates with our parser.
[^syntaxerror]: Fun Fact: Replacing the `;` at the end of a line with the identically-looking greek question mark is a commonly referred prank among programmers. However, this will lead to a syntax error as the character can't be processed by the lexer. Take that, pranksters.
Normally, you design the lexer and parser side-by-side, but let's take things step by step.
A piece from our input may look like this:
```text
addx 7
noop
addx 1
addx -33
noop
```
Every input possibly encountered by the lexer must be described using a rule, otherwise we'll run into errors.
First, we define a few shorthands ([full source file here](https://code.dummyco.de/feliix42/aoc-2022/src/commit/841b9ec20bdf828f721c12675564e571cc51d9ad/day_10/lexer.l)) which we can then use in our lexing rules (for small examples like this it's a bit overkill but at least it's good style):
This is, in my opinion, one of the great hurdles when starting out with these tools: They are so deeply intertwined that learning them can result in a lot of headaches as things usually don't work as you expect them to at first.
For example: I originally tried to use C++ this time for at least some Quality of Life improvements over pure C.
But alas, the C++ parser and lexer didn't want to work together and even the official examples didn't compile for me.
So I buried the idea quickly after sinking hours into the debugging process.
The last rules in our lexer declare that we ignore any spaces (we're not in Python after all) and want to match on the end of file as well, to know when lexing is done.
The final rule matches on all remaining lexemes and emits an error message to inform the user of a syntax error occuring.
The full file (containing all set-up instructions and options) can be found [here](https://code.dummyco.de/feliix42/aoc-2022/src/commit/841b9ec20bdf828f721c12675564e571cc51d9ad/day_10/lexer.l).
If it gave you flashbacks to your formal systems lectures, I have bad news.
Job of a parser is to assign semantics to the tokens we produced in the previous step, and these semantics are expressed using a formal _grammar_.
In simple terms, such a grammar is composed of different rules that describe any legal structure of the input.
So, going back to our CPU instruction parser example, the grammar would look like this:
```bnf
<input> ::= <line><input> | END_OF_FILE
<line> ::= <instruction> NEWLINE | NEWLINE
<instruction> ::= NOP | ADDX NUM
```
The syntax you're looking at is called [_"Backus-Naur form"_ (BNF)](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form) and chances are you've learned about that if you ever attended a lecture on formalization of languages.
The left side of each rule is called a _nonterminal_, the symbols in CAPS are _terminals_ or just tokens.
As the name suggests, nonterminals are themselves just placeholders for other grammar rules.
You can think of them as variables or modules that allow you to stick together a grammar.
In our example, we want to parse an arbitrary number of input lines, each containing a single instruction.
This is represented by the rule in line 1, the starting rule for our grammar.
It says that each input instantiation consists either of a line rule followed by another input rule _or_ an end-of-file token (the OR is indicated with a pipe symbol).
This allows us to read as many lines (i.e., instructions) as we want.
The `<line>` rule defines that each line may contain exactly one instruction and is terminated by a newline, allowing for empty lines (I did that because copying the input file adds an empty line to the file at the end).
Our final rule defines different types of instructions, in our case `NOP` or `ADDX NUM`, the only two operations we need to support.
And that's it, that is our grammar.[^actually]
Now we can obviously start writing an absolute unit of an if-else chain matching this grammar in our program and post it to [r/shittyprogramming](https://www.reddit.com/r/shittyprogramming/top/?t=all).
But, as you might have guessed, the problem of "parsing things" has been solved a long time ago and there exist solutions that don't want to make you pull out your hair in agony.
So, we lay our eyes upon the holy grail that has been gifted to us by [Richard M. Stallman](https://rms.sexy) himself[^rms]: `bison`.
[GNU Bison](https://en.wikipedia.org/wiki/GNU_Bison) is a [parser generator](https://en.wikipedia.org/wiki/Compiler-compiler) that allows us to give it a grammar definition written in BNF, from which a parser is generated.
[^actually]: For actual programming languages, these grammars are [quite complex](https://github.com/jorendorff/rust-grammar/blob/master/Rust.g4). In our case however, the individual grammars for each day's tasks are rather simple.
[^rms]: Actually, `bison` was written by Robert Corbett. Richard Stallman just made it compatible to another parser generator named `yacc`.
[^shell]: In case you weren't aware, a parser is indeed used in most shells to disambiguate what part of your input is program invocation and what are meta-operations like I/O-redirections or pipes. `bash` in fact is a whole scripting language and your prompt a mere interpreter.
Numerous parser algorithms exist that all have individual benefits and drawbacks, but discussing them in detail would be a bit much.
It's enough for us to know that Bison generates a [LALR(1)](https://en.wikipedia.org/wiki/LALR_parser)[^lalr] parser.
In case you're not familiar with that, let us just keep the following in mind:
Our parser will work _left-to-right_, meaning it processes our input in the order we feed it into the parser.
The nice thing is, that we don't have to care about what happens under the hood of the parser, except for when our parser fails for dubious reasons.
[^lalr]: A _Look-Ahead Left-to-Right parser_, constructing a _rightmost_ derivation, using 1 lookahead token. I know that's a lot to take in, especially if you're not familiar with it, so let's keep things simple.
### Writing the Parser
Ok, so now that we have digested the core concepts of what a parser does, let's get back to the code.
As I said before, `bison` integrates nicely with `flex`.
It expects a function called [`yylex`](https://www.gnu.org/software/bison/manual/html_node/Lexical.html) that returns the next token for the parser to process.
Normally, you could also implement the function itself, but we have a dedicated lexer for that.
And the neat thing is, that `flex` generates this function already based on our definitions, we can simply import the generated lexer in the parser definition.
For the parser itself, we can now think about how to solve the task we were given.
We don't just have to read the instructions, we must also interpret them, store the register contents and sum them at specific points.
So, it'd be nice if we could invoke specific actions for some grammar rules and keep some sort of internal state.
Luckily, both things are possible.
To keep an internal state for the parser, we just define a corresponding struct (which I just named `parser_state` for convenience) in the header file that will be generated:
```bison
// parser.y
// Code for the header file generated by bison
%code requires {
struct parser_state {
/// Program Counter
size_t cycle;
/// Contents of register X
long reg;
/// For solving task 1
long sum;
/// keeps track of the next CPU cycle.
size_t next_target_cycle;
};
}
```
Additionally, we put a function in the generated C file that takes care of incrementing our program counter and summing the register values:
printf("[info] Register contents at cycle %zu: %ld\n", state->cycle, state->reg);
state->sum += tmp;
if (state->next_target_cycle <220){
state->next_target_cycle += 40;
}
}
}
%}
```
With these functionalities in place, we can now define the real grammar of the parser, similar to the _BNF_ definition we saw above.
For that, we first need to define the tokens we already used in the lexer (and which are imported from the parser, so both files have a symbiotic relationship).
You will see that we can attach values to specific tokens.
This allows us for instance to store the parsed number alongside the `NUM` token.
As a neat bonus, `bison` allows us to define actions (i.e., code) to be executed as part of reading a rule.
We use that to increment the CPU cycles and handle the register value addition:
```bison
// parser.y
%union {
int num;
}
%start input
%token NEWLINE
%token NOP ADDX
%token <num> NUM
%term END_OF_FILE
%%
input
: line input
| END_OF_FILE { return 0; }
;
line
: instruction NEWLINE
| NEWLINE
;
instruction
: NOP { increment_cycle(state); }
| ADDX NUM {
increment_cycle(state);
increment_cycle(state);
state->reg += $2;
}
;
```
As you can see, the rules look similar to the ones we defined before.
And that's it already, there is our grammar to parse the whole task and solve part one automagically while processing the input.
We of course need some more setup code which you'll find in the complete `parser.y` file [here](https://code.dummyco.de/feliix42/aoc-2022/src/commit/841b9ec20bdf828f721c12675564e571cc51d9ad/day_10/parser.y).
The last part we have to take care of is invoking the parser.
But now, that's as easy as pie.
We just write a quick main function at the end of our `bison` file that initializes our state and the lexer and runs the parser to end by invoking `yyparse` with the necessary arguments[^args]:
[^args]: I omitted the definition of parser arguments for the sake of simplicity, but that is not so difficult.
By doing this seemingly stupid challenge, I realized that what I was doing was actually not too different from what you'd normally do in the advent of code.
The parser framework just gives you the right set of tools to reason about the input (in the most cases, for some tasks it felt very forced).
Not all things can be solved during the parse, though.
A notable example for this is the challenge of [day 8](https://adventofcode.com/2022/day/8) which requires you to compute some properties on a square full of trees.
Here, most of the leg work has to be done after the parse as reasoning over the complete data structure is necessary.
