Please note the unusual (shortened) due date for this assignment due to spring break. This assignment is also shorter than previous assignments, and is worth 80 points (instead of 100). Have a great spring 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: 20q.rex and parsing.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 from those below will cause our scripts to "barf".
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 files called 20q.rex and io.rex in the directory /cs/cs60/assignments/assignment8. You should read through these files, especially io.rex 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, 20q.rex, must begin (after the comments at the top of the file) with the line
*i io.rexThis 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:
S -> P + S | P P -> E * P | E E -> V ^ E | V V -> '0' | ... | '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 things:
Note that the first element in each case will be a parse tree, and the second element will be a list of remaining unparsed tokens. If the parsing was successful, as in the first case below, then in the end the residue will be the empty list. Here's an example of how your parse function will behave. Notice that in the first two examples, the residue is empty because parsing was successful. The third 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/assignments/assignment8. It shows a recursive descent parser
for expressions using only addition. Note the use of explode
to tokenize the original string, i.e., to break it into individual
meaningful units, which in this case are single characters.
Note that your input
string should have no whitespace, since whitespace will be converted into
additional "space" characters 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^4");
17
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
For extra and completely optional bonus credit of up to 10 points, augment your parser to handle the following grammar:
S -> P + S | P
P -> E * P | E
E -> U ^ E | U
U -> '(' S ')' | '-' V | V
V -> '0' | ... | '9' | 'a' | ... | 'z' | 'A' | ... | 'Z'
This allows you to parse single-character variables,
negated values, and arbitrarily
parenthesized expressions. The parentheses should not
show up at all in the parse tree, but should allow
for a change in the default order of operations. The
'-' is a unary operator: it has only one
operand in its parse tree. Here's an example:
rex > parse("(1+a)^-x");
[ [^, [+, 1, a], [- x]], [] ]
For a second extra credit possibility (up to 5 points, available if you have completed the above extended parser), write a second Evaluate function that takes in a string to evaluate and a list of [ variable, value ] pairs, where each variable will be a single-letter character and each value will be an integer. It then evaluates the string (after parsing it), and uses the list of variable bindings to assign values to variables that appear in the expression. You may assume that every variable will be bound (and you may want to use assoc). Here is an example:
rex > Evaluate("(1+a)^-x", [ ['a',2], ['x',-5] ]);
243
With this, you've implemented some of the core features of
rex (in rex!).