Homework 11

The goal of this homework is to implement a recursive descent parser for the lambda calculus. You can read about recursive descent parsers here. We will follow the conventions in the example there.

Here is a grammar for the lambda calculus:

term_list := term term_list | term

term := paren_term | lambda_term | variable_term

paren_term := ( term_list )

lambda_term := L variable_list . term_list

variable_list := variable_term variable_list | variable_term

variable_term := a lowercase letter

To get you started, you can download my lambda_calc1.py, which parses this simplified grammar:

variable_list := variable_term variable_list | variable_term

variable_term := a lowercase letter

Put your solution in a file named lambda_calc.py. You can also download lambda_test.py, which is a test suite.

A couple of notes:

• 1. Take a few minutes to make sure you understand accept and expect. They are fairly idiomatic for this kind of parser (accept is sometimes called match).

  2. In general, the translation from a grammar in this form to a recursive descent parser is pretty mechanical, so if you feel like you are inventing something new, you are doing it wrong!

  3. My implementation of variable_list uses a while loop, rather than recursion, to accumulate the list. That's a bit of a cheat, but you can do the same thing to implement term_list if you want.

  4. Your program should work if the input is a legal string in lambda calculus. If it is not, you should raise an exception. See expect for an example. But you don't have to catch every conceivable error.