CS107 Handout 04Spring 2008 April 4, 2008Assignment 1: Random Sentence GeneratorBased on an old CS107 assignment written by Julie Zelenski. First three pagesare taken verbatim from someone else’s handout.The InspirationIn the past decade or so, computers have revolutionized student life. In addition toproviding no end of entertainment and distractions, computers also have also facilitatedall sorts of student work from English papers to calculus. One important area of studentlabor that has been painfully neglected is the task of filling up space in papers, Ph.D.dissertations, extension requests, etc. with important sounding and somewhatgrammatically correct random sequences. An area that’s been neglected, that is, untilnow.Due: Sunday, April 13th at 11:59 p.m.The Random Sentence Generator is a handy and marvelous piece of technology to createrandom sentences from a structure known as a context-free grammar. A grammar is atemplate that describes the various combinations of words that can be used to formvalid sentences. There are profoundly useful grammars available to generate extensionrequests, generic Star Trek plots, your average James Bond movie, "Dear John" letters,and more. You can even create your own grammar! Fun for the whole family! Let’sshow you the value of this practical and wonderful tool:• Tactic #1: Wear down the TA's patience.I need an extension because I had to go to an alligator wrestling meet, and then, just whenmy mojo was getting back on its feet, I just didn't feel like working, and, well I'm a littleembarrassed about this, but I had to practice for the Winter Olympics, and on top of thatmy roommate ate my disk, and right about then well, it's all a haze, and then my dormburned down, and just then I had tons of midterms and tons of papers, and right about then Ilost a lot of money on the four-square semi-finals, oh, and then I had recurring dreamsabout my notes, and just then I forgot how to write, and right about then my dog ate mydreams, and just then I had to practice for an intramural monster truck meet, oh, and thenthe bookstore was out of erasers, and on top of that my roommate ate my sense of purpose,and then get this, the programming language was inadequately abstract.• Tactic #2: Plead innocence.I need an extension because I forgot it would require work and then I didn’t know I was inthis class.• Tactic #3: Honesty.I need an extension because I just didn't feel like working.Please note that some of the resources used in this assignment require a Stanford Network Account and therefore may not be accessible.2What is a grammar?A grammar is a set of rules for some language, be it English, C++, Scheme, or somethingyou just invent for fun.  If you continue to study computer science, you will learnmuch more about languages and grammars in a formal sense. For now, we willintroduce to you a particular kind of grammar called a context-free grammar (CFG).Here is an example of a simple CFG:The Poem grammar{<start>The <object> <verb> tonight. ;}{<object>waves ;big yellow flowers ;slugs ;}{<verb>sigh <adverb> ;portend like <object> ;die <adverb> ;}{<adverb>warily ;grumpily ;}According to this grammar, two possible poems are "The big yellow flowers sigh warilytonight." and "The slugs portend like waves tonight." Essentially, the strings in brackets(<>) are variables which expand according to the rules in the grammar.More precisely, each string in brackets is known as a non-terminal. A non-terminal is aplaceholder that will expand to another sequence of words when generating a poem. Incontrast, a terminal is a normal word that is not changed to anything else whenexpanding the grammar. The name terminal is supposed to conjure up the image thatit’s something of a dead end, that no further expansion is possible.A definition consists of a non-terminal and its set of productions (or expansions), eachof which is terminated by a semi-colon (';'). There will always be at least one andpotentially several productions for each non-terminal. A production is just a sequence ofwords, some of which themselves may be non-terminals. A production can be empty(i.e. just consist of the terminating semi-colon) which makes it possible for a non-3terminal to evaporate into nothingness. The entire definition is enclosed in curly braces'{' '}'. The following definition of <verb> has three productions:{<verb>sigh <adverb> ;portend like <object> ;die <adverb> ;}Comments and other irrelevant text may be outside the curly braces and should beignored. All the components of the input file—braces, words, and semi-colons—will beseparated from each other by some sort of white space (spaces, tabs, newlines), so thatwe’re able to treat them as delimiters when parsing the grammar.Once you have read in the grammar (and that part’s easy, because I’m already providinga readGrammar function for you), you will be able to produce random expansions. Youalways begin with the single non-terminal <start>. For a non-terminal, consider itsdefinition, which will contain a set of productions. Choose one of the productions atrandom. Take the words from the chosen production in sequence, (recursively)expanding any that are themselves non-terminals as you go. For example:<start>The <object> <verb> tonight. // expand <start>The big yellow flowers <verb> tonight. // expand <object>The big yellow flowers sigh <adverb> tonight. // expand <verb>The big yellow flowers sigh warily tonight. // expand <adverb>Since we are choosing productions at random, a second generation would probablyproduce a different sentence.What To Do, What To DoWithout a doubt, the most difficult and time-consuming portion of Assignment 1 hasvery little to do with C++ coding. We expect you to spend a majority of your timegetting used UNIX, emacs, and Makefiles. In past quarters, the first assignment hasbeen a little more intense that this one, but this time I’m giving a smaller problem wheremuch of the code has already been written for you. I’ve taken care of the not-so-sexytask of parsing the command line and reading in the specified grammar file to build agrammar object in the form of an STL map (which is similar to the CS106 Map, but justdifferent enough that you’ll need to read Handout 03 before you can make use of it.)Here’s a high-level outline of how I’d approach the problem over the next seven days.• Read the Unix Basics handout, which is being distributed today