CSE 413 Autumn 2008 -- Assignment 7

Context Free Grammars & Calculator Parser/Interpreter

Due: Electronically: 11 pm, Thursday, Dec. 4, 2008. Written problems and printed copy of the code and test output at the beginning of class on Friday, Dec. 5, 2008.

No late assignments will be accepted, even if you have late days remaining, because it is the end of the quarter.

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.)

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.

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 like 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.

Project Turnin

Electronic: Turn in your program electronically using the link on the assignments page. You should include your Ruby code and 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).

Paper: Turn in answers to the written problems, a copy of your code and readme.txt file, and examples of test input and output that demonstrate the operation of your program.