Tag: context free grammar

CS107 – Assignment 1 – Context Free Grammar – Random Sentence Generator

This is assignment 1 from a older CS107 course, because the latest course work is held on a UNIX server which in turn you need access to!!.. kinder does not help when you do not have access too!!.. Here is where I got the files from cs107 link, there is a zip file at the bottom of that page which has all of the assignments and handouts etc.

The basics of a context free grammar is (as taken from the PDF file attached which is the assignment 1 in more details), the tokens as such are the <..> parts of the block, so that you start at <start> and then you print out “The ” and then goto the <object> block to then print out a randomly picked object to then print out the <verb> if there is any blocks within the object/verb then do them before heading back to the last word on the <start> block which is “tonight”. That is it, it generates random text :).

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 ;
}

So the assignment is mainly to get used to compiling up programs within a Linux/Unix environment, I was using qt-creator IDE (which has placed some files within the zip file attached, but it does not effect the directory structure as such). To compile on Linux/Unix as long as there is a Makefile you can just

make

So, the assignment 1 base code reads in the textual files and all is required is to output the text within a random sentence and repeat 3 times, so the start of the code does the looping and calls the doRandomText function which requires as parameters the mapped (map) grammar and where to start ()

  for (int i =1;i <= 3; i++)
  {
      cout << "Version #" << i << endl << endl;
      doRandomText(grammar, "<start>");
      cout << endl << endl;
  }
  return 0;
}
 
// recursive loop in the text and produce randomly generated text
void doRandomText(map<string, Definition> theGrammar, string terminal)
{
    Definition def = theGrammar[terminal];
    assert(def.getNonterminal().size() !=0);
    Production prod = def.getRandomProduction();
    for (Production::iterator prodIter = prod.begin(); prodIter != prod.end(); prodIter++)
    {
        string theText = *prodIter;
        if (theText.at(0)=='<' && theText.at(theText.size()-1)== '>')
            doRandomText(theGrammar, theText);
        else
        {
            if (theText == "," || theText == ".")
                cout << theText;
            else
                cout << " " << theText;
        }
    }
}

The recursive function above basically tries to find the terminal within the grammar definitions and if there is not one, exit the code (assert), else print out the textual data whilst iterating over them, if there is any more terminals within the sentence then goto that terminal by calling this same function.

Here is the output of a run from the program.

./rsg assn-1-rsg-data/excuse.g 
The grammar file called "assn-1-rsg-data/excuse.g" contains 7 definitions.
Version #1
 
 I need an extension because my disk got erased, and I'm sure you've heard this before, but I had to make up a lot of documentation for the Navy in a big hurry, and I'm sure you've heard this before, but my printout was enshrowded in a mysterious fog for three days and then vanished, and I'm sure you've heard this before, but all my pencils broke, and just then I had 7 programs in like, a billion different langauges, and if you can believe it, I just didn't feel like working, and and then if I recall correctly I had to worry about the Winter Olympics, and and then if I recall correctly my disk got erased, and as if that wasn't enough I forgot how to write.
 
Version #2
 
 I need an extension because I got stuck in a blizzard at Tahoe, and then get this, my Mac was enshrowded in a mysterious fog for three days and then vanished.
 
Version #3
 
 I need an extension because I didn't know I was in this class, and then I just didn't feel like working, and I'm sure you've heard this before, but I thought I already graduated, and then, just when my mojo was getting back on its feet, the bookstore was out of erasers, and if you can believe it, I didn't know I was in this class, and and then if I recall correctly my dorm burned down.