Accidentally Learning Parser Design

As a programming nerd, I always wanted to make my own language. And during the summer vacation, I had a lot of free time So I said “fuck it I am giving it a shot”.

This is going to be my first “real” programming language ever made. We will have variables, functions, types… the whole shebang. I want to make something that’s ACTUALLY potentially useful. or at least functional as a programming language.

This is probably going to be very difficult but not because writing a language is some sort of magic, I am relatively sure it's “just” a lot of normal code.

My dad actually had to write a basic Lisp interpreter as part of his university education. And I have seen projects by many people who wrote their own language.

I have been actively working on this project for like… 3 weeks. Before that, I did not really know any theory about parsers and I have never written one that’s more complex than a few split statements in Python.

Most of the theory is things I kind of stumbled into when trying to work out how to do things.

So if I can do it you can probably do it too. Probably much better than me since I suck at writing parsers.

Basic Theory

Compilation usually has these 4 steps:

1. lexing the text into simple tokens
2. parsing the tokens into some sort of tree structure
3. checking for errors and warnings
4. move the tree into something like assembly

The reason we split lexing and parsing is that trying to deal with spaces and comments in the parsing stage is kind of annoying. By having the lexer remove comments and white space we guarantee that these won't effect the code.

Sometimes the boundaries between the different stages are not super clear. For instance you could generate some of the errors during lexing or parsing. You could also drop the lexing stage entirely.

Maybe you run the code directly from the tree. Sometimes there are more stages, like optimization passes. Or maybe your language compiles to something like C and then you compile that C code.

But the basic theory is the same:

We take a list of characters, Move them into some sort of tree, then do something useful with it.

There are more advanced mathematical theories, for specific ways to achieve this. We will look into some of them later. But I want you to remember that they are not a requirement… They are a tool and we use them when it helps.

Handwritten

A lot of the best parsers out there are written by hand from scratch. For instance Rust has a handwritten parser and it has arguably the best error messages. However, starting from scratch is a lot of work and usually requires a lot of people.

The first time I wrote a parser it was in pure C99 and it didn’t really fit into any specific formal framework. Mostly because it just overall sucked.

I tried parsing expressions like:

Name1 value1 : value2 direction Name2

After messing around for 3 days and going nowhere I wrote a small parser in Python that just split on “:” then on whitespace. That took me like 20 minutes and moving it to C took me about a day.

So I realized that as much as I love C I really don't want to write a parser in it. But I also don't want to use Python because that's just asking for bad performance.

Changing Gears

Rust has a really good reputation for writing parsers compilers and just other programming languages in general. And I anyway wanted to learn it so this seemed like the perfect opportunity.

I started with a few small projects to get my feet wet. One of those exercises was a small arithmetic expression parser. I used the same procedural style I did in C. which worked but it took me a few days and a small headache trying to figure out the algorithm.

This confirmed to me that writing things from scratch is probably not the way to go here. On the other hand, I didn’t want to have the same feeling I have with Python where my code is just a bunch of dependencies I don’t have control over.

Python dependencies breaking was also 50% of my work in data science and I did not want to go back to that.

So I tried using as few dependencies as I could. Every dependency had to have a purpose and had to be able to build on any machine I own. I am proud to say my project builds with just Cargo without any issues and that I only use 3 libraries, So I think I managed to strike a balance.

Combinators and PEGs

PEGs (I know great name) are a very simple approach for parsing text. The basic premise is that we consume tokens from the text 1 by 1 until the text is empty.

At its core, a PEG looks something like this

def PEG_Parse_func(text,table):
  for rule in table:
    if rule(text):
      remaining_text,token = rule.parse(text)
      return remaining_text,token
  
  return error("failed to match")

What’s nice about this is that they are composable. the rules in table are also PEG parsers. So you have this long PEGing chain of parsers each doing a small part of the input at a time.

A notable example of a language that uses PEGs is Python. They use some fancy optimization named Packrat Parsing That mathematically guarantees linear time (but costs linear memory). And they write the entire thing themselves.

That’s way too fancy for me so I just used nom. It’s a nice rust “parser combinators” library for processing text, which is performant and battle-tested.

The main Idea is that we use higher-order function that allows us to combine our existing parsers into something new, for instance:

fn lext_token<'a>(input: &'a str) -> LexResult<'a>{
    alt((
        lex_word,
        lex_atom,
        lex_operator,
        lex_number, 
        lex_string,
        lex_unknowen,
    ))(input)
}

alt basically tries all the parsers you give it until something works and returns the result of the first one that matched. It's basically PEG_Parse_func from earlier.

Get Neva Krien’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

It's important to note that order does matter. For instance, lex_unknowen will match literally anything. So if we had it in the start all tokens would be treated as unknown.

It does take a bit of getting used to so I am not expecting you to understand it right away. For me, it took about 3 days until it finally clicked. But once you get used to it you can lean much more into this combinator pattern. for instance, this is how I wrote the string parsing:

fn lex_string<'a>(input: &'a str) -> LexResult<'a> {
    // Match the string delimiters (either ' or ")
    let (input, d) = recognize(one_of("'\""))(input)?;
    
    // Process the content inside the delimiters
    let (input, last) = preceded(
        // Handle either escaped delimiters (like \' or \") or any character except the delimiter
        many0_count(alt((
            recognize(preceded(tag("\\"), one_of(d))), // Handles escaped delimiters
            is_not(d),                     // Everything else that's not the delimiter
        ))),
        opt(one_of(d))  // Expect to match the closing delimiter
    )(input)?;

    match last {
        None => Ok((input,LexTag::PoisonString)),
        Some(_) => Ok((input,LexTag::String)),
    }
}

Hooray, we can write code that’s as cursed as Python list comprehensions! In all honesty, I do love list comprehensions so this is a huge step forward. I used nom in the lexer and it was great. For the parser I ran into issues with the type system, I also want good error messages and I just could not get something working with nom.

Pivoting

I could probably use nom to write the happy path if I really tried. But adding performant error handling later without breaking the happy path seems like it would be difficult.

So I tried writing the error handling from the start. But I got bogged down trying to catch every possible bad input. Worse I didn’t know yet which syntax errors are important to catch. Or for that manner how my language even looks like.

Instead what I want is something where we could just write the happy path, and integrate errors later, in a way that won't feel like an afterthought, and won't break the happy path.

So we need something where we can just declare a new type of error we want to report and have that integrate efficiently with my existing code, without requiring that we change anything.

we need a parser generator…

Parser Generators

So I decided to pivot into something more managed. There is this whole paradigm of parser generators. They are something between just a giant macro and an entirely new programming language.

The basic idea is to try and take some fancy mathematical framework and implement a compiler for it.

PHP to this day still uses YACC for its parsing. Which is a great sign for us. Because if you can make a language that runs most of the internet with an approach then it's probably not a terrible idea.

That being said Parser Generators do have a reputation for making bad error messages. Most languages eventually move away from them. For instance, C++ was originally implemented in YACC. But later moved to use a custom-made solution.

There are PEG parser generators, but I couldn’t find one I like for this project. Pest looked nice but it was missing some features. So instead I went with lalrpop since it has guaranteed linear time and it integrates very well with my existing lexer and Rust code in general.

Which meant I needed to learn a new language and a new mathematical framework… Yippe more math.

LALR

LALR(1) is part of the CFG (context-free grammars) family of parsers. This is a very popular mathematical framework for parsing text. Many languages use a parser from this family :

1. Python prior to 3.9 used LL(1)
2. PHP uses YACC which is LALR(1)
3. Old C++ (again YACC)
4. and Lalrpop uses LALR(1) as well

The basic premise of a CFG is similar to PEGs. But they have 1 key difference. They are order-independent. With PEGs, if 2 rules apply we take the first match. But a CFG would simply fail to build in the first place.

This can be a bit of a pain but it does help making sure your code does what you think it does. For instance, when implementing the pipe operator I wanted to just say:

Pipe: FunctionCall = {
    <v:Value> "|>" <f:FuncCall>=> {
        //return f(v,fargs)
        }
    },

Which seems like it should work, a PEG would just accept this as is. And it does work for simple inputs like:

a()|>b()

But for this case

a|>b()()

a PEG would read it as b(a)() But that’s not really the intent. Most languages actually mean b()(a). With a CFG we are forced to specify which of the 2 we mean from the start, so there are less surprises. I ended up doing it like so:

Pipe: FunctionCall = {
    <v:PipableValue> "|>" <f:NoPipeFuncCall>=> {
        //return f(v,fargs)
        }
    },

This does not mean CFGs are slow to write, far from it. Almost all of my tests worked first try. Which coming from writing things by hand in C was a huge change. And it only took me a week to get a basic parser working.

I still need to add more advanced pattern matching. But I want to first try writing some programs before I design that. So for now the parser is complete.

Conclusion

Wow, that was much more theory than I thought it would be. Both for writing the actual parser and for the article. In reality, Theory was not the main thing on my mind when writing code.

For instance, I realized nom was PEG only AFTER writing my lexer… I only read about PEGs because of Pest. And I also wanted to explain LL vs LR parsers but honestly, it's not relevant so I just cut it.

I hope that you enjoyed the article maybe even learned something new.

I also hope that despite all the complicated theories and frameworks, I got across that writing a parser is definitely something you can do. It won't take 1 afternoon, but if you give it a month you can probably make that work.

Next time we start working on the interpreter.

See you there.

Neva.