Tree application: A rudimentary parser

In this section we present a not-too-complicated grammar and a random sentence generator for that grammar. Then we reverse this process  and "parse" the sentences according to that grammar. Strictly speaking there is no issue of computational complexity in this section. Nonetheless it is shown because it is a cute example of tree construction, it is generally relevant to computer science (where parsing theory is a common theme), and because more complicated parsers will frequently work in similar manner but require, say, stacks as intermediate data structures. Indeed, more complicated grammars generally require preprocessing that is itself computationally intensive and in need of useful data structures. A good reference for all this is
(1977) Principles of Complier Design, Aho, Alfred, and Ullman, Jeffrey. Addison Wesley.
(aka "The Dragon Book"). In particular see chapter 5.

First we give our grammar. It is quite capable of producing a variety of nonsense sentences, as we will soon see. With minor modifications one could probably use it to turn out scripts for bad movies. We use Hold to prevent infinite recursion. We also weight the probabilities of "empty" productions in adjective and adverb clauses so that they will not be terribly long.


Now generate random sentences from that grammar. We also provide a means to format the results.


Here is a set of random sentences. Note that our random generator is rigged to go slightly beyond strict syntax, in that adjectives and adverbs are never reused within the same clause.

A red shark grated a sheep above this crazy sheep.
That wet hideous mad red hatter gnashed the delectable village in that cow.
Fix that shark in this red big ball!
Launch the village!
Could the repugnant ball salivate that cow from this wet delectable buffalo?
Did the librarian grate the slimy hatter?
Break a slimy village from that repugnant village!
The hideous librarian jumped a programmer at a ball.
Squeeze the programmer in that city!
Could the mad librarian with the silly city salivate the ball?
Did the attorney jump that ball?
A attorney at this attorney milked a village.
Will the wet lazy hideous mild-mannered mad red attorney near a lazy programmer eat a dog?
This city threw that librarian from a delectable slimy village.
Squeeze the attorney!
Fix the crazy programmer under the red crazy repugnant wet silly cow!
Will a red librarian milk that big moon?
A city with the hideous wet big city ate a sheep.
Fix this mad librarian in a programmer!
Should that shark under that red crazy skyscraper salivate this city near that lazy silly hatter?

Now for the parser. We will break down each sentence part and indicate this by encapsulating it in a special head. When we encounter empty subexpressions e.g. adjective lists with no adjectives, we do not return them; for many purposes this is acceptable and of course one could easily modify the parsing code below to indicate where these lists would be. Note that this parser assumes the input is valid, and makes no attempt to detect errors.