Hacker News Reader

Comment by cabaalis | Hacker News Reader

I have been following this for the past few weeks in my off-time and would recommend it to everyone. It is also geared towards teaching C. I wrote in C many years ago but with the past 8 or so years writing exclusively C# it feels like a homecoming.

It does make use of the author's grammar parser, which is my only minor complaint. Does anyone know a good resource in which the author handcrafts a parser? I'm aware of the various parser generators that exist. I also read the dragon book in my college's compiler design course ~12 years ago. But we also used a parser generator in that class.

View on HN

http://www.lispworks.com/documentation/HyperSpec/Body/02_b.h...

That's the algorithm for the common lisp reader. Writing a recursive descent parser based on that spec is fairly straightforward.

And once you hand write your own recursive descent parser you'll probably not want to give up the control that gives you to a parser generator. Yuck.

I was playing with a parser generator last summer, and it was immensely frustrating to bump into bugs it had & features it lacked. In the end, it was much easier easier to write the entire parser myself. So if I understand the point you're making, I agree that giving up control can suck!

You should check out parser combinators. I've also used parser generators in the past and experienced similar frustrations. Parser combinators are just so much easier to use.

Hey, I saw your comment on ketamine but couldn't reply. Are you still taking it?

And then you will write a parser generator with Parsec and you will not want to give up the ease compared to writing your own recursive descent parser :)

Yeah, parser combinators are basically magic, and not in an “overly clever code that you’ll regret later” sense.

And, while a Haskell-style type system makes them nicer, they work really well in dynamically typed languages too. (e.g. https://github.com/drewc/smug )

I'd love a good parser generator to save me writing recursive descent ones roughly annually in my career, but the ones I've encountered are awful.

The "Let's Build A Simple Interpreter" series of posts (starting at https://ruslanspivak.com/lsbasi-part1/) is excellent, geared towards building an interpreter for a Pascal-like language in Python. It does not use a parser generator, and builds up everything incrementally. Unfortunately it's incomplete...

I read through parts of this book a few months back. I also did not like using that parser because I wanted to keep external dependencies to a minimum. Writing a parser for s-expressions turned out to be relatively simple. You can check out my implementation here: https://github.com/00vareladavid/scheme/blob/master/src/pars... . I believe the technique is called "recursive descent parsing".

> Does anyone know a good resource in which the author handcrafts a parser?

http://craftinginterpreters.com/contents.html the book implements the Lox language in Java and C.

I found LLVM’s Kaleidoscope tutorial to be great for learning how to write a parser from scratch.

https://llvm.org/docs/tutorial/LangImpl02.html

Hand-crafted parser:

Building LISP: http://www.lwh.jp/lisp/index.html

- Parser: http://www.lwh.jp/lisp/parser.html

Full source: https://github.com/kimtg/ToyLisp

Honestly, if I were you I would try to write it blind. It's one of the more rewarding things to write, because when you do it correctly, it collapses down to a bunch of macro calls. You'll start off writing it long hand, and eventually you'll start to see some patterns. Then you'll see the need for certain combinators, and then finally you'll see how everything collapses down. It's one of the more rewarding things to write if you're a fan of DRY, and the fuzzy feeling you get when you properly abstract something.

minischeme[0] has a pretty good parser built into the SECD machine.

I've been hacking on it here and there and almost have it r4rs compliant -- replaced the lexer with re2c and was going to do the parser in lemon but the design they already have is just too simple to mess with.

[0]https://github.com/catseye/minischeme --note: the bog stock original is floating around on the internets if you google hard enough.

Hand crafted lisp parser: https://github.com/sctb/lumen/blob/master/reader.l

Equivalent JavaScript: https://github.com/sctb/lumen/blob/master/bin/reader.js

It’s 158 lines of lisp, fully bootstrapped, and zero fanciness.

Reply on news.ycombinator.com