Assignment 15: Random sentences

Due: 8:00am, Thursday, April 22. Value: 30 pts. Submit to Sauron.

A Python program can represent a context-free grammar using a dictionary where each key-value pair represents one of the grammar's rules: The dictionary keys are symbols in the grammar (always enclosed in angle brackets), and their corresponding dictionary values are lists of strings, each string representing an option for how that symbol might be replaced. For example, below is some Python code that creates a dictionary, along with the context-free grammar to which it corresponds. As it happens, the context-free grammar is for the language of all strings of 0's and 1's corresponding to a binary number that is a multiple of 3.

grammar = {     '<S>': ['1 <B>', '0'],     '<A>': ['0 <A>', '1 <B>', ''],     '<B>': ['1 <A>', '0 <C> 0 <B>'],     '<C>': ['1 <C>', ''] }

S → 1 B | 0 A → 0 A | 1 B | λ B → 1 A | 0 C 0 B C → 1 C | λ

I have created rand-sentence.py, which allows the user to type the name of a file describing a grammar and creates a dictionary as described above based on the file's contents. You can choose from any of the following four grammar files. (In fact, all were created at Stanford University in the 1990's.)

haiku.g	Generates Haiku poetry
expr.g	Generates mathematical expressions
insult.g	Generates insults (sometimes crude)
rejection.g	Generates college rejection letters

Your job is to complete the generate function, which takes a parameter string that contains a symbol name (including the angle brackets) and should randomly creates a string of atoms that can be generated from that symbol. You must use a recursive algorithm.

In partiticular, you should look into the dictionary to retrieve the choices of how to expand the symbol, and select a random one of these. You can use split to break your random choice into individual words and step through each of them:

• When you find a word that is an atom (i.e., doesn't start with a less-than sign, which would be the beginning of angle brackets), you simply incorporate that atom into your return value.
• When you find a word that is a symbol (i.e., starts with a less-than sign), you will perform a recursive call, asking your own generate function to determine how that symbol can itself be expanded into a string of atoms. You'll incorporate the string returned by the recursive call into your return value.

To select a random element of a list, you can use the random module's choice function. For example, prime = random.choice([2, 3, 5, 7, 11]) would assign prime to refer to a number randomly chosen from the first five primes.