Using the map for sentence generation


  1. Our grammar is defined as:


<X> :: = <a> | <a><a>

<a> ::= <b><d> | <b><d><c>

<b> ::= the | a

<d> :: = TA | dog | student

<c> ::= runs | goes crazy | doesn’t read requirements


All objects of type Definitions are marked with def. The key to each Definitions object is the term for which the Definitions object holds SingleDefinitions for.


  1. If I call generate(<X>), I will then enter the method as follows:
    1. Is <X> a terminal?

                                                              i.      Yes – add the string to a List<String> and return

                                                            ii.      No – get the Definitions object for <X> from the map using <X> as key via getDefinitions(<X>):

                                                          iii.      So the Definitions object is actually a container for SingleDefinition objects, like so:

                                                          iv.      The red boxes are elements of the Definitions object.

The blue boxes are elements of the SingleDefinition object.

I need to randomly select one of the SingleDefinition objects,

Which in turn contain strings. By random, let’s say I pick the object containing   one strings of the form “<a>”. (the definition <a>)

                                                            v.      Now, I need to generate terminals for every element in the SingleDefinition, since <a> is not a terminal. So I will have to get the Definitions object corresponding to the definition of <a>. This is done by passing <a> into the getDefinitions method of the Grammar class:

                                                          vi.      Now I once more need to pick out of two definitions, this time let’s say I randomly choose <b><d><c>, which is really a SingleDefinition list containing the three elements like so:

   [<b>, <c>, <d>]

                                                        vii.      Now I need to loop through these strings, calling generate(term) for each of them. For each call, I will get their Definitions objects.

                                                      viii.      Note that each of the SingleDefinition objects for these Definition objects are terminals. Thus when we pick one of these randomly and pass them into generate, we can return a one element list containing the terms.

                                                          ix.      Since each step was random, I could end up with the following lists, or possibly others:

[a, TA, runs]

[the, boy, goes crazy]

As this is just a List<String>, it will need to be processed in a method to get a proper sentence printed out.