Hacker News Reader

Comment by sigil | Hacker News Reader

If you're looking for a modern compilers class -- including the theory of why this stuff works -- I highly recommend Matt Might's [0]. All of the notes, slides, and code are online.

I audited Might's "Compilers" this spring. He live-coded a parser that parsed with derivatives, returning all possible parse trees whenever there were ambiguities in the grammar. [1] (Try getting that from yacc, or basically any other tool in existence right now.)

All of his coding was done in Racket scheme. At the beginning he told us we could use whatever for the projects, but doing certain things in C++ / Java / Python / some imperative language was "like bringing a knife to a gun-fight."

The final project was a working Python -> C translator.

Really badass class.

[0] http://matt.might.net/teaching/compilers/spring-2013/

[1] http://matt.might.net/articles/parsing-with-derivatives/

View on HN

> returning all possible parse trees whenever there were ambiguities in the grammar. [1] (Try getting that from yacc, or basically any other tool in existence right now.)

Any GLR-based tool can do that trivially, including recent versions of Bison (derived from yacc): http://www.gnu.org/software/bison/manual/html_node/GLR-Parse...

Ultimately I don't think this is the best way to develop parsers, particularly when you are designing the language itself (as opposed to writing a grammar for an existing language), because it gives you no hint that ambiguity exists until you actually encounter an ambiguous string (since the question of whether a grammar is ambiguous is undecidable).

I wrote more about this on my blog: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...

Again, this parsing is trivial if you use parser combinators of (almost) any kind.

http://en.wikipedia.org/wiki/Parser_combinator

http://www.cs.nott.ac.uk/~gmh/monparsing.pdf

Actually, when using such approach you have to fight the power of resulting parser. You have to restrict it or your parser will retain data for too long.

CMU's got a fairly nice one. It guides students as they build a series of compilers for increasingly large subsets of C, effectively from scratch. Course materials are public, I believe.

http://www.cs.cmu.edu/afs/cs/project/fox/mosaic/people/fp/co...

> a working Python -> C translator

Including generator functions? That would be impressive. Well, one could solve it by putting all locals into an heap allocated object and use the "switch over the whole function body"-trick to continue execution at the correct position.

only a small portion of a full compiler involves translators, though.

Reply on news.ycombinator.com