#Small parser using std where possible

1 messages · Page 1 of 1 (latest)

timber oyster
#

So I want to write a small little S-expression (Lisp) parser. Few hundred lines of code max type of deal. I want to use the std where possible and I'm a little lost.

Currently I'm doing the tokenizer and I started writing it with the Reader interface, but quickly realized it's not peekable. I had a rummage through std for "peek" and found a few things, but maybe not what I want. I also saw there's a few references to tokens like TokenIterator.

What is the simplest, idiomatic way to write a basic lisp tokenizer, making use of std as much as possible? I don't need you to write my code for me, but just point me at the stuff I need I guess?

flat geyser
#

I don't there's too much you can use in std; there is no Regex module or anything...
you might be able to use std.mem.indexOf and friends to some degree, but not much beyond that...
the design which I always use for a lexer is the classic iterator one:

pub const Lexer = struct {
    src: []const u8,
    pos: usize,

    pub fn next(self: *Lexer) Lexeme {
        // skip comment (comments use `;` here)
        var in_comment = false;
        self.pos = for (self.src[self.pos..], self.pos..) |c, i| switch (c) {
            ' ', '\t' => {},
            ';' => in_comment = true,
            '\n' => in_comment = false,
            else => if (!in_comment) break i,
        } else self.src.len;

        if (self.pos >= self.src.len) return .eof;

        switch (self.src[self.pos]) {
            '(' => {
                defer self.pos += 1;
                return .paren_l;
            },
            ')' => {
                defer self.pos += 1;
                return .paren_r;
            },
            '0'...'9', 'A'...'Z', 'a'...'z', '_' => {
                // lex identifiers and numbers here...
            },
            // maybe some other characters are also accepted...
        }
    }
};
```you can also add extra methods to it if you want to (e.g. `peek`)
timber oyster
#

hmm, I feel like there are definitely methods in, for example, std.ascii that I want to use

#

I don't think I need regex for a lisp parser anyway

dim crow
#

when 0.14 comes out (or if you are on master) you may find labeled switch useful for this kind of stuff

timber oyster
#

I know about labeled switch

#

is there a reason you load the entire source file into memory fri3d?

#

I was thinking the correct way to do it would be with something like Reader or whatever

flat geyser
timber oyster
#

fair enough

flat geyser
# timber oyster is there a reason you load the entire source file into memory fri3d?

we got plenty enough memory in modern computers, so that isn't too much of a concern - there's also the nicety of making the lexer yield only the lexeme type, and its start position - further processing of the tokens (parsing numbers, unescaping string literals, etc) can be done at a later stage, and ad-hoc. having the entire file given in memory means we can refer to it whenever we want, not needing to syscall to read from this or that offset
Zig's lexer only yields the kind and start positions, and as I understand, it helps a bunch with performance (less memory used frequently, cache is happy, you know the drill)

timber oyster
#

hmm, interesting

#

strings do make it easy, because then I can just use slices over strings

flat geyser
timber oyster
#

you're reassuring me a lot lol, I was stuck all day yesterday reading a bunch of source code in std trying to figure out everything, like "oh god, I don't understand any of this deeply enough to make good choices"

#

I think you convinced me to just go strings and slices

dim crow
#

std won't help much here, yeah

timber oyster
#

I was convinced an experienced Zig'er would just pull out a few one-liners and write an effective tokenizer in a few lines of code using existing std stuff

#

and I assumed it would be using like Reader or something

dim crow
timber oyster
#

I mean, in JavaScript I can probably write a Lisp parser in under 25 lines

#

without code golfing, just fairly direct code

#

but I'd probably have to use some regex to get it that small, which is unnecessary

dim crow
timber oyster
#

sure, but Zig is incredibly complex compared to a basic lisp

#

lisp literally has three tokens: left paren, right paren and the rest is symbols

dim crow
#

still you can do the tokenizer in a similar way

#

ig

timber oyster
#

I wonder if I can use the TokenIterator thing

#

does anyone have info on how to use it properly, with some examples?

flat geyser
timber oyster
#

yeah, I read the examples

#

didn't help me with anything

#

cool, I'll try just doing a next token thing with switch

#

I'm going to leave this open a little bit in case someone has another idea

timber oyster
# 
const std = @import("std");

const TokenType = enum {
    open_paren,
    close_paren,
    symbol,
};

const Token = struct {
    type: TokenType,
    value: []const u8,
};

fn isDelimiter(char: u8) bool {
    return char == '(' or char == ')' or std.ascii.isWhitespace(char);
}

const Lexer = struct {
    buffer: []const u8,
    index: usize,

    pub fn next(self: *Lexer) ?Token {
        self.skipWhite();
        if (self.isEOF()) return null;
        switch (self.buffer[self.index]) {
            '(' => {
                self.index += 1;
                return Token{
                    .type = TokenType.open_paren,
                    .value = self.buffer[self.index - 1 .. self.index],
                };
            },
            ')' => {
                self.index += 1;
                return Token{
                    .type = TokenType.close_paren,
                    .value = self.buffer[self.index - 1 .. self.index],
                };
            },
            else => return Token{ .type = TokenType.symbol, .value = self.parseSymbol() },
        }
    }

    fn isEOF(self: *Lexer) bool {
        return self.index >= self.buffer.len;
    }

    fn skipWhite(self: *Lexer) void {
        while (!self.isEOF() and std.ascii.isWhitespace(self.buffer[self.index])) self.index += 1;
    }

    fn parseSymbol(self: *Lexer) []const u8 {
        const start = self.index;
        while (!isDelimiter(self.buffer[self.index])) self.index += 1;
        return self.buffer[start..self.index];
    }
};
#

code review?

flat geyser
#

I see you're just grouping the characters into..?

  • whitespace
  • (
  • )
  • all else
#

oop! parseSymbol might out-of-bounds if the symbol occupies a suffix of the source

timber oyster
flat geyser
#

I'd also suggest having an explicit eof token - makes things much simpler later on

timber oyster
#

okay, cool

flat geyser
#

you can attach location info to it, so you can later point to it in a later parsing error ("expected ) found eof")

timber oyster
#

no need

#

I want the entire parser to fit in like 200 lines of code, that would make it way too complicated

flat geyser
#

ah, valid

timber oyster
#

like, I might add that later, but the MVP needs to be just the basics

#

hence the extremely simple tokenizer lol

#

besides, I'm saving slices, so that info is unnecessary I think?

flat geyser
#

ah, true

timber oyster
#

it might be nicer with location info, we'll see

#

for now BRUTALISM loll

summer rivet
timber oyster
#

I'm actually currently working on packing heh

summer rivet
timber oyster
#

yeah, it looks great

#

I'm currently looking a bit at Ribbit Scheme

#

not sure if I'll go with that, but it's fun

#

this is how they do data cells

#

everything is [3]usize basically

summer rivet
#

I'm actually playing with nan-boxing and have just reached the point in my bytecode interpreter where I need to implement functions next (only arithmetic ops, variables, if, while, for so far)