Programming Assignment 1

Due on Thursday February 24 before midnight


This assignment must be done individually. No copying is permitted.

Use your favorite programming language (C, Java, C++, etc) to implement a recursive descent parser for the following grammar that parses lists:

E → ( L )
  | ( )
  | id
  | int
L → L , E
  | E
Note that tokens are strings. We have 5 tokens (terminals) in this grammar: "(", ")", ",", id, and int. The id token matches any alphanumerical sequence of characters (ie, from a-z, A-Z, and 0-9) starting with a lowercase letter from a-z. The int token matches any sequence of digits 0-9.

For example, your parser should be able to parse the file a.txt.

You should not use any scanner or parser generator tools. All code must be put in one file.

Hints: See page 48 of the lecture slides. You need to implement read_next_token() (which skips whitespaces and reads the next token as a string) and current_token (which returns the string of the current token, such as "b3" and "(").

What to Submit

Use the form below to submit your programming assignment. We do not accept email or hardcopy submissions. The only acceptable file format for your submitted file is plain text (you source file). You may submit your file as many times as you like, but only the most recently submitted file will be retained and evaluated.

Submit Project #1:

Last modified: 02/16/11 by Leonidas Fegaras