A grammar is a set of rules for generating strings. For this lab, you will write a Python program that generates random strings using the rules of a grammar. For example, when the program was given the strings of a grammar, it generated the following random sentences.

the cat bit the dog. the girl chased the boy. 

the cat chased the boy and the boy kissed the cat. the cat bit the dog and the dog kissed the girl and the dog chased the girl. 

Perhaps such grammars could write childrens books automatically. Seriously, however, more complex grammars have been used to generate random test inputs for programs, as a debugging aid.

1. Theory.

To write this program, you must have a way to generate random integers. You must also know what a grammar is, and how it works.

Random integers. No algorithm can generate truly random integers, but it can generate pseudo-random integers that seem random, even though theyre not. Python has its own random number generators, but for this lab, you must implement your own.

The Park-Miller algorithm (named for its inventors) is a simple way to generate a sequence of pseudo-random integer terms. It works like this. Let N0 be an integer called the seed. The seed is the first term of the sequence, and must be between 1 and 231 2, inclusive. Starting from the seed, later terms N1, N2, ... are produced by the following equation.

5 31 Nk+1 =(7 Nk)%(2 1)

Here 75 is 16807, and 231 is 2147483648. The Python operator % returns the remainder after dividing one integer by another. You always get the same sequence of terms from a given seed. For example, if you start with the seed 101, then you get a pseudo-

random sequence whose first few terms are 1697507, 612712738, 678900201, 695061696, 1738368639, 246698238, 1613847356, and 1214050682.

Terms in the sequence may be large, but you can make them smaller by using the % operator again. If N is a term from the sequence, then N % M gives you an integer between 0 and M 1, inclusive. For example, if you need an integer between 0 and 9, then you write N % 10. You can use this to choose a random element from a Python list or tuple. If S is the list or tuple, then the Python expression S[N % len(S)] returns a randomly chosen element of S.

Grammars. The easiest way to explain a grammar is to show an example. This is the grammar that generated the simple sentences about boys, cats, dogs, and girls that appeared in the introduction.

01 02 03 04 05 06 07 08 09 10 11 

Noun 'cat' Noun 'boy' Noun 'dog' Noun 'girl'

Verb 'bit' Verb 'chased' Verb 'kissed'

Phrase 'the' Noun Verb 'the' Noun Story Phrase Story Phrase 'and' Story

Start Story '.'

Each line is a rule, identified by a number, so this grammar has 11 rules. The names in italics, like Noun, Verb, and Phrase, are called nonterminals. The strings in quotes, like 'girl', 'the'and '.', are called terminals. In each rule, the arrow means may be replaced by. As a result, rule 01 says that the nonterminal Noun may be replaced by the string 'cat'. Similarly, rule 10 says that the nonterminal Story may be replaced by the nonterminal Phrase, followed by the string 'and', followed by the nonterminal Story.

To generate strings from the grammar, you play a little game. The game always begins with the nonterminal Start. The object of the game is to use the rules to get rid of the nonterminals, replacing them by terminals. If you can do that, then the terminals left over at the end are concatenated to produce a string generated by the grammar. For example, you begin with Start and use rule 11 to replace it, like this.

Story '.'

Now you have a new nonterminal, Story, to get rid of. According to rule 10, you can replace Story by Phrase 'and' Story, so you get this.

Phrase 'and' Story '.'

You can then use rule 09 to replace Story by Phrase.

Phrase 'and' Phrase '.'

You use rule 08 to replace the first Phrase, so you get this.

'the' Noun Verb 'the' Noun 'and' Phrase '.'

According to rule 01, you can replace the first Noun by 'cat', and according to rule 02, you can replace the second Noun by 'boy'.

'the' 'cat' Verb 'the' 'boy' 'and' Phrase '.'

And according to rule 06, you can replace Verb by 'chased'.

'the' 'cat' 'chased' 'the' 'boy' 'and' Phrase '.'

Continuing the game, you use rule 08 again to replace Phrase.

'the' 'cat' 'chased' 'the' 'boy' 'and' 'the' Noun Verb 'the' Noun '.'

You use rule 02 to replace the first Noun by 'boy', and use rule 01 to replace the second Noun by 'cat'. Finally, you use rule 07 to replace Verb by 'kissed'.

'the' 'cat' 'chased' 'the' 'boy' 'and' 'the' 'boy' 'kissed' 'the' 'cat' '.' 

At this point, youve eliminated all the nonterminals, so youve won the game. If you concatenate all the strings together, separated by blanks, then you get a string generated by the grammar, like this:

'the cat chased the boy and the boy kissed the cat .' 

By the way, there are many different kinds of grammars, each with different kinds of rules. The grammars used for this lab are called context-free grammars, in which each rule has a single nonterminal on the left side of the arrow .

2. Implementation.

The grammar game described in the previous section is so simple that a short Python program can play it. You must implement such a program for this lab. Your program must have two Python classes, Random and Grammar. Neither class extends the other.

The class Random. The first class must be called Random, and it must implement the Park-Miller algorithm. It must have the following methods. They must have the same parameters as described here, and they must also work as described here.

__init__(self, seed) 

(5 points.) Initialize an instance of Random so it generates the sequence of pseudo-random integers that begin with seed. You may assume that seed is an integer in the proper range for the Park-Miller algorithm to work.

next(self)

(5 points.) Generate the next random integer in the sequence, and return it.

choose(self, objects) 

(5 points.) Choose an element from the tuple objects at random, using an index obtained by calling next. Return that element. You may assume that objects is a tuple with at least one element.

Your Random class must not compute big numbers like 75 and 231 over and over again. Either compute them only once, and store them in variables, or else write them as constants, so you dont have to compute them at all.

The methods in Random are very short, just one or two lines each. If your methods are much longer than that, then you do not understand what you are doing, and you should ask for help.

The class Grammar. The second class must be called Grammar, and it must implement a grammar with rules like those described in the previous section. The class Grammar must have the following methods. They must have the same parameters as described here, and they must also work as described here.

__init__(self, seed) 

(5 points.) Initialize an instance of Grammar. It must have an instance of the random number generator Random that uses seed. It must also have a dictionary that stores rules.

rule(self, left, right) 

(5 points.) Add a new rule to the grammar. Here left is a string. It represents the nonterminal on the left side of the rule. Also, right is a tuple whose elements are strings. They represent the terminals and nonterminals on the right side of the rule.

Find the value of left in the dictionary. If there is no such value, then let the value of left in the dictionary be a list whose only element is right. However, if there is such a value, then it will be a list. Add right to the end of that list.

generate(self) 

(5 points.) Generate a string. If there is a rule with the left side 'Start' in the dictionary, then call generating with the tuple ('Start',) as its argument, and return the result. If there is no such rule, then raise an exception, because you cant generate strings without a rule for 'Start'.

generating(self, strings) 

(10 points.) This method does all the work for the program. The parameter strings is a tuple whose elements are strings. The strings represent terminals and nonterminals.

Initialize a local variable to '', the empty string. It will hold the result to be returned by this method. Now visit each string in strings, using a loop.

If the visited string is not a key in the dictionary, then it is a terminal. Simply concatenate it to the end of the result string, followed by a blank ' '.

If the visited string is a key in the dictionary, then it is a nonterminal. That means its value in the dictionary is a list, created by the method rule. Get that list from the dictionary. Choose one of its elements at random. The chosen element will be a tuple of strings. Call generating recursively with the chosen tuple as its argument. The call will return a string. Concatenate that string to the end of the result string, but without a blank at the end.

Continue in this way until all elements of the tuple have been visited. Then return the result string.

For example, the following Python code creates an instance G of the class Grammar. It has the rules of the example grammar that was described earlier.

G = Grammar(101) G.rule('Noun', ('cat',)) #01 G.rule('Noun', ('boy',)) #02 G.rule('Noun', ('dog',)) #03 G.rule('Noun', ('girl',)) #04 G.rule('Verb', ('bit',)) #05 G.rule('Verb', ('chased',)) #06 G.rule('Verb', ('kissed',)) #07 G.rule('Phrase', ('the', 'Noun', 'Verb', 'the', 'Noun')) # 08

G.rule('Story', ('Phrase',)) 

G.rule('Story', ('Phrase', 'and', 'Story')) G.rule('Start', ('Story', '.')) 

# 09

# 10 # 11

Remember that a tuple with exactly one element e must be written as (e,) with an extra comma at the end. If you leave off the extra comma, then you get (e) which is the same as e. Leaving off that comma may make your program do crazy thingsthis can be a very hard mistake to find.

In the example, Gs random number generator is initialized with the seed 101. If you continue the example by calling G.generate() four times, then you should get the same four sentences that appear in the introduction.

I got most of them but how can I do else function for generating method ??