CSE 413 Spring 2011 -- Assignment 7

Context Free Grammars & Calculator Parser/Interpreter

Due: Online via the Catalyst Dropbox no later than 11 pm, Thursday, June 2, 2011.

Part I. Written problems

Answer the following questions about context free grammars.

1. Consider the following grammar:
                   S ::= aAS | a
                   A ::= SbA | SS | ba
1. What are the terminals, nonterminals, and start symbol for this grammar?
2. Draw parse trees for the following sentences:
1. aabbaa
2. aabaaabaa
3. Give leftmost derivations of the sentences in (b).
   
2. Give context free grammars that generate the following languages:
   1. The language consisting of balanced parentheses and square brackets.
      Example: ([[](()[()][])])[] .
   2. The language containing strings with an equal number of a's and b's.
   3. The language containing strings of the form ww^Rcaⁿb²ⁿ, where w is a string of 1 or more a's and b's; w^R denotes the reversal of w, and the superscript n stands for any positive integer, meaning that the end of the string should contain 1 or more a's followed by twice as many b's as a's.
      
3. Write a grammar for English sentences using the following words (only)
                       time, arrow, banana, flies, like, a, an, the, fruit
   and the semicolon.  Be sure to include all the senses (noun, verb, etc.) of each word, and the basic sentence parts like subject, predicate, etc.  Then show that this grammar is ambiguous by exhibiting more than one parse tree for "time flies like an arrow; fruit flies like a banana."
   
   (The wikipedia articles on sentence diagrams and English grammar are a useful place to refresh your knowledge of grammar, but contain far more detail than you should use for this question.)

Part II. Programming - Parser and Interpreter

Complete your calculator program by adding a parser and interpreter for the calculator language to the scanner that you implemented in the previous assignment. You should construct a recursive-descent parser that calls the scanner's next_token method to read the tokens making up the input program and parses and evaluates the calculator statements in the input. The parser/interpreter should contain a separate method for each major calculator language construct such as statement and exp. Each time one of these methods is called it should parse the corresponding part of the grammar and evaluate the result. After each expression statement is evaluated, the resulting value should be printed to standard output. You should, of course, include additional methods and data structures as needed to organize your program cleanly. In particular you will need a hash table (dictionary) to record variables and the values they are bound to as the calculator executes.

Your parser/interpreter need only work on correct input.

You should test your calculator by evaluating a variety of statements, and you should turn in a sample of the tests you performed that show that your calculator works properly. These examples should range from simple expressions consisting of a single number or identifier, to more complex expressions and statements. In particular, your tests should demonstrate that the code to bind names to values, use those names in expressions, and delete names with unset, all work properly.

Your code should be contained in a file calc.rb. You may, if you wish, break your program into more than one source file in the source directory, but it should be possible to run your program by executing the file calc.rb using the appropriate ruby command. Be sure to include your name and other identifying information as comments at the beginning of your file(s). There should also be descriptive comments as needed, in particular to describe classes and important data structures.

Extra Credit

A small amount of extra credit will be awarded for extending your calculator in interesting ways. Here are a few ideas:

• (very easy) Print some meaningful message(s) after assignment and unset statements.
• (fairly easy) Extend the language by allowing empty lines (statements) in the input, allowing multiple statements on an input line separated by semicolons, or allowing unary minus operators (-3 or -(x+4)).
• (more complex) Extend the language to provide a selection of built-in functions in addition to sqrt(exp). These can be implemented by calling the corresponding functions in the Ruby math library.
• Add decent error handling. One possibility: recover from an error by printing a message and skipping to the next input statement. A little more graceful: produce meaningful error messages and/or attempt to resume scanning and parsing after an error in an input statement.

If you add any extensions to the language, you should do it systematically by figuring out how to extend the grammar, then implement the corresponding extensions in the parser/interpreter and, if necessary, scanner. Regardless of any extensions, your final calculator should accept any valid program described by the original grammar and execute it correctly.

What to Hand In

Turn in a file containing your answers to the questions from Part I, your calculator source file(s) for part II, and some examples of test input and output that demonstrate that your calculator works on a variety of test input. You should also include a readme.txt file that describes what works and what doesn't and any extensions you added. If you extended the language, your readme.txt file should describe the changes you made to the grammar as well as give an overall description of the extension(s).

For the problems in part I you can use any common file format including plain text, Word, or pdf. You can also submit a scanned document of a handwritten solution if that is convenient, as long as it is clear and legible.