This assignment has three 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 a language of arithmetic expressions. In the very short third part, you will get a small taste of Prolog. You will be submitting these parts in three separate files: 20q.rex, parsing.rex, and prologstuff.pl. You can submit these files by typing cs60submitall in the directory which contains your files or you can submit them separately using cs60submit.
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! ALL of your code will be in the file 20q.rex. This file already includes io.rex which has the provided input-output functions. You should not modify io.rex.
After you have examined io.rex to see what it provides, take a look 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:
For full credit, keep your program as simple and elegant as possible. The file, 20q.rex can be done in roughly 12 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.)
S -> P + S | P P -> E * P | E E -> U ^ E | U U -> ( S ) | - V | 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 the residue list. If the parsing was successful, the residue will be the empty list.
From our experience, a good way to approach this problem is to first build a parser for a simplified version of this grammar. For example, you might begin with the grammar:
S -> P + S | P P -> E * P | E E -> V V -> '0' | ... | '9'Once you get the parser working for this grammar, you can extend it to the full grammar for this problem. Here's an example of how your parse function will behave once you have implemented the full grammar. 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)^3+-4");
[[+, [^, [+, 1, 2], 3], [-, 4]], []]
rex > parse("1+2*+3");
[[+, 1, [*, 2, Error]], [BADTOKEN, 3]]
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
This last part of the assignment will give you an opportunity to play with Prolog a bit. This is based on material which we'll see on the Thursday after fall break.
Recall that to enter Prolog, you can simply type prolog at the prompt on turing. Once you are in Prolog, you can enter the contents of a file which you've defined (presumably using an editor such as vim or emacs) by typing: [prologstuff]. at the Prolog prompt. Note that although the filename should end in the suffix pl, you should not use that suffix when loading in the file. Moreover, like everything in Prolog, you must end the command with a period. (Who invented this funny syntax?!)
You can exit Prolog by typing halt. (You need to include the period after the word halt!)In the directory /cs/cs60/assignments/assignment8 you will find a file called prologstuff.pl. This file contains an expanded database of the Simpsons family with many additional facts. Begin by taking a close look at the kinds of facts provided in that file.
You should make a copy of this file and add the following rules. You may add any additional helper rules that you wish, including anything that we looked at in class.