Compiler Design

Here you can find links and info regarding Dr. Ligatti’s Fall 2011 Compiler Design course. I highly recommend taking the course!

As I was learning about compilers and parsers, I waited as patiently as I could until I could implement a parser for some meaningful (read: Turing-complete) language. One evening I took that first step and derived the LR(1) parse table for this lambda calculus grammar (the ‘a’ denotes abstraction, and ‘x’ are variables):

S -> E$
E -> x | ax.E | (E)(E)

You can find the parse table here (OpenDocument format). I successfully ran a full-page-long test trace of the parser with that table on the following program:

as.az.(s)((s)(z))

You receive bonus points if you recognize the above function. So this is what bison (and similar software like jison) does behind the scenes? Cool!