Computer Science 60
Principles of Computer Science
Fall 2003


Assignment 7: Twenty Questions Revisited and Recursive Descent Parsing!
Due Thursday, October 23 by 11:59 PM.

Please note the unusual (extended) due date for this assignment due to fall break.

This assignment has two parts. In the first part you will be writing the twenty questions game in rex. In the second part you will be writing a recursive descent parser and evaluator for arithmetic expressions with addition and multiplication. You will be submitting these two parts in two separate files: part1.rex and part2.rex.

Throughout this assignment, you can use any built-in rex functions that you like and you can define whatever other helper functions you need.

Please use the standard commenting convention of your name, file name, and date in each file. In addition, please have at least a one-line comment for each function that you implement. Finally, please BE SURE TO NAME YOUR FILES AND FUNCTIONS EXACTLY AS WE'VE SPECIFIED. The grading procedure for this assignment is partially automated and files and functions whose spellings differ at all from those below will cause our scripts to "barf".

Part 1: Twenty Questions (50 Points)


In this part of the assignment you will be implementing twenty questions in rex. Please put this code in a file called part1.rex.

Here's an example of how the game will look when you run it: 

  rex > play();
  Is it bigger than a breadbox? yes
  Is it an elephant? no
  I'm clueless!  What were you thinking of? a computer scientist
  Please give me a question that distinguishes between an elephant and a computer scientist.
  Does it have a long trunk
  And what would the answer be for a computer scientist? no
  Would you like to play again? yes
  Is it bigger than a breadbox? yes
  Does it have a long trunk? no
  Is it a computer scientist? yes
  Would you like to play again? no
  Thanks for playing!
We have provided a file called io.rex in the directory /cs/cs60/assignments/assignment7. You should read through this file carefully! It defines all of the input/output functions that you will need and even defines the initial game tree and a few other things! Your file, part1.rex, must begin (after the comments at the top of the file) with the line 
*i io.rex
This will load in all of the definitions in io.rex so that you may use them in your twenty questions game. As an example of this, take a look at iodemo.rex in that same directory. This file demonstrates how the io.rex file gets used. Please read this file carefully as well. Here's how your program should behave: Here are the things that you'll need to know in order to implement this game in rex: Think about this program carefully before writing it. Take a look at how we wrote the insert function for binary search trees as a reminder of how to operate on trees. For full credit, keep your program as simple and elegant as possible. Your file, part1.rex can be done in roughly 15 lines of rex code. (A bit more or less is OK too, but if you are writing 30 lines of code, this is an indicator that you are doing too much work and your code is unnecessarily complicated.)

Part 2: Recursive Descent Parsing (50 Points)


In this part of the assignment you will be writing a recursive descent parser and an evaluator for arithmetic expressions with addition and multiplication. In particular, we will use the unambiguous context-free grammar that we saw in class except that the variables will now be the digits 0 through 9: 
E -> T + E | T
T -> V * T | V
V -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Your task is to write a recursive descent parser for this grammar. One of the functions in your file should be called parse. This function takes a string to parse and returns a list of two elements: The first element is the parse tree for this string and the second element is the residue. If the parsing was successful, then in the end the residue will, of course, be the empty list. Here's an example of how your parse function will behave. Notice that in the first example, the residue is empty because parsing was successful. The second example did not succeed in parsing because the input was malformed. 
rex > parse("1+2*3");
[[+, 1, [*, 2, 3]], []]

rex > parse("1+2*");
[[+, 1, 2], [*]]
Take a look at (and feel free to use any part of) the file parsing.rex which is in the directory /cs/cs60/assignment7. It shows a recursive descent parser for expressions using only addition. Note the use of explode to convert a string into a list of symbols. Exploding a string results in a list of characters. For example, explode("spam1") returns the list [s, p, a, m, 1]. Although the single quotes don't show up in this list, this is really a list of characters, the first of which is 's', the second is 'p', and the last is '1'. In particular, the character '1' is not the number 1. This is consistent with the fact that the variables in the grammar above are characters and not actual numbers. (More on how to convert from characters to numbers later.) Note also that your input string should have no whitespace, since whitespace will be converted into additional symbols "blank" symbols by explode.

Once you have successfully written your recursive descent parser, implement an Evaluate function and whatever other helper functions you need. Evaluate takes as input an arithmetic expression (with addition and multiplication and one digit numbers) and returns its arithmetic value. For example, here is how your Evaluate function should behave. 

rex > Evaluate("1+2*3");
7

rex > Evaluate("1*2+3");
5

3 rex > Evaluate("1+");
Bad Input
Notice that this function should return the string "Bad Input" if the expression is malformed. The Evaluate function will need to call the parser and some helper functions. You may wish to use the rex built-in function make_number which takes a character as input returns a number corresponding to that character. For example, 
rex > make_number('4');
4

rex > 1 + make_number('2');
3
Last modified October 2003 by Ran Libeskind-Hadas