Intro

This post is inspired by the amazing Guido van Rossum series on PEG building and follows my idea of building simple version of B-Minor language.

I have already some experience in building simple recusrive descent parsers, so this is a good time to try to do something more complicated and PEG seems like a good choice. And as I am still in learning mode, I want to implement it in Zig, since I like a lot manual allocations and many other features of this language (but of course there are many things that makes me quite angry).

But enought talks, lets dive in.

Plan

Here is the plan and constraints on how I am going to proceed.

  1. Implement basic arithmetic PEG parser, since rules for it are already provided in this nice Wikipedia page
  2. Add memoizing functionality.
  3. Using this basic PEG parser as a foundation, implement compiler-compiler, which uses PEG rules and generates the same parser.
  4. Add more rules and as a result implement full B-Minor parser.

Basic Arithmetic parser

We have following rules

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Power (('*' / '/') Power)*
Power   ← Value ('^' Power)?
Value   ← NUMBER / '(' Expr ')'

Here NUMBER is a token, which corresponds to the [0-9]+ expression. Of course, it is possible to make tokenization part of the grammar, but I am not completely convinced that it is that useful, so I am ok with extra tokens here and there.

Also, while it is useful to have tokens like ‘+’/’-’ etc in rules, it is more convinient to have them defined as proper tags in tokenizer.

Tokenizer

Tokenizer is straightforward and very similar to what is written in Python tokenizer version. Main difference is that since I do not have pre-ready tokenizer, I split tokenizer in two parts: Scanner which does all the heavy-lifintg, but rather dumb and Lexer which is basically Scanner with buffer and allow me later to utilize infinite backtracking.

pub const Lexer = struct {
    scanner: Scanner,
    tokens: std.ArrayList(Token),
    pos: u32,

    const Self = @This();

    pub fn init(allocator: std.mem.Allocator, scanner: Scanner) Self {
        const tokens = std.ArrayList(Token).init(allocator);

        return .{ .scanner = scanner, .tokens = tokens, .pos = 0 };
    }

    pub fn mark(self: Self) u32 {
        return self.pos;
    }

    pub fn reset(self: *Self, pos: u32) void {
        self.pos = pos;
    }

    pub fn nextToken(self: *Self) !Token {
        const token = try self.peekToken();
        self.pos += 1;
        return token;
    }

    pub fn peekToken(self: *Self) !Token {
        if (self.pos >= self.tokens.items.len) {
            try self.tokens.append(self.scanner.nextToken());
        }

        return self.tokens.items[self.pos];
    }
};

Of course, at some point I should add errors resolution. It is nice to ride on auto inference, but as we know, Zig is not good at resolving error unions from recursive calls and we have plenty of those. Alternative is to panic all the time, since most of the important errors arises from memory manipulation in ArrayList and there is not much I can do about it anyway.

Another thing is that you do not find any deinit in this code, since it is assumed, that Arena Allocator is used. Of course, it is possible to sprinkle everything with destroy, free and deinit just in case, but I do not see it as a reasonable thing. It only adds extra burden of tracking memory leaks, but parsing is a one-time procedure, so all memory should be released anyway. It is faster, it is easier, it is more reliable and it is one the things I love so nuch about Zig.

Memoizing

Needs to figure out, how to do it in Zig.