CompSci 06/101, Fall 2011, RSG

image source and its grammar

In Computer Science a grammar is basically a set of rules. Grammars can be used to recognize and validate text, e.g., a grammar representing a programming language is used to parse, compile, or interpret programs written in the language. Grammars can also be used in a generative mode, to generate texts or images or sounds that conform to the rules of the grammar, with options chosen at random, the results can range from beautiful to humorous.

There are many examples of randomly-generated text, graphics, art, and so on. The ones referenced here all use context free grammars like those you will be using in this assignment. The AD Generator combines slogans with Flickr images to create random ads built on real slogans. The famous SCIgen project generates random computer science papers including those that were actually accepted for publication, albeit in shady conference venues. The site has videos and a complete description of the history of SCIgen. Context Free Art includes information on generating different images using grammars and computerized drawing. Grammars known as L-systems have also successfully modeled plant formation.

For example, here are some Duke CompSci excuses generated by this grammar.

I can't believe I haven't started working on this week's APT assignment. The problems were unbelievably hard and I couldn't find my computer .

I finished working on this week's APT assignment. The problems were like trivial and Eclipse crashed .

I gave up working on this week's APT assignment. The problems were really , really , so impossible and I got h1n1 .

I gave up working on this week's APT assignment. The problems were so , like easy and I had a midterm .

I finished working on this week's APT assignment. The problems were like trivial .

There are three parts to this programming assignment:

• Update the given module, rsgModel, from a program that reads a properly formatted grammar file to one that also generates random sentences/texts based on the grammar by completing the recursive function generate.
• Upload an original grammar file that you create to the grammar website so that it can be used by everyone in the class. Extra points will be awarded for top-placing grammars in several categories. You should submit your grammar online using this online form.
• A-credit/challenge: Update the given module, rsgModel, to format the resulting random text nicely by completing the function pretty_print. For example, it should limit the number of characters printed on each line to a maximum of 50 and not print spaces in front of words that consist solely of punctuation.

You can snarf the starting files for this assignment or view them here. See the HOWTO page for more details on the grammar's format, how to generate random text from it, and how to access the class grammar files from your program.

Grading

Submit your source code: rsgModel.py; as well as a README file and an ANALYSIS file using the submit name assign6-rsg.

In your ANALYSIS file, document any bugs or problems that remain in your program. If you document bugs that you cannot fix, and how you tried to fix them, they will affect your grade far less than bugs we discover in running your program.

You will be graded on how well you implement the module that generates random sentences and whether you have included appropriate README and ANALYSIS files.