Your task is to construct a parser for the Python programming language.
Unusually among programming languages, Python is straightforward to parse. In fact, it is one of the few popular programming languages with an LL(1) grammar, making it amenable to hand-written recursive descent parser.
Of course, it is also possible to use a parsing tool.
Guidelines
You can use any language you want for this project, but you must be able to run your program under Linux or Mac OS X.
If the TA or I can't get your code to run, we'll ask you to help us get it running.
Requirements
You must parse the simplified Python grammar.
You should assume that Python source is coming in -- not pre-lexed input.
If you need to use a working lexer, you can assume that the programpylex is in the current PATH, and that it matches the behavior of the web app by consuming a file on STDIN and printing its tokens as S-Expressions line-by-line on STDOUT.
The output S-Expression should fit within grammar for the concrete AST.
Include a README.txt file that contains:
your name;
a list of software dependencies necessary to run your assignment;
a description of what you got working, what's partially working and what's completely broken; and
a manifest briefly describing each file you've turned.
Every source code file you turn in needs to have your name and student number at the top and the bottom in comments.
The program should use a Makefile:
make should compile the program (if compilation is necessary).
make run should accept input on STDIN and send output to STDOUT.
make lex should run the lexer on STDIN.
make parse should run the parser on STDIN.
make test should run any test cases you used.
The program should output one s-expression containing the concrete parse tree on success or #f on failure.
Simplifications
Use the simplified grammar provided.
Hints and tips
Do not write the parser by hand, unless you have a lot of time.
I recommend that you use yacc, Racket's parser generator a derivative-based parsing tool.
If you want write your lexer and parser in a different language, you can tie them together with a Unix pipe, like so:
$ pylex | pyparse
Code
A reference web app is available.
You may find the sample parsers useful.
If you take the Racket route, stub code is available for parsing with derivatives.