CSE 413 14au Assignment 8 - Context Free Grammars & Calculator Parser/Interpreter

Due: Online via the Catalyst Dropbox by 11 pm, Thursday, December 4, 2014. (If you have late days remaining you may still use them on this assignment if you wish.)

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). (i.e., show the steps in the derivation in order starting with S => ... .)
  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 wwRcanb2n, where w is a string of 1 or more a's and b's; wR 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 syntactically 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 an 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 PDF file named hw8.pdf containing your answers to the questions from Part I, your calc.rb and any other source file(s) for part II, and some examples of test input and output in a file test.txt that demonstrate that your calculator works on a variety of test input containing input that is syntactically correct, but has a mix of correct and incorrect input (e.g., using undefined variables, etc.). The test.txt file should be a transcript of a terminal session showing operation of your calculator.

On Linux and OS X systems you can create a transcript file by running the command script test.txt to start a new shell and capture all of the input and output while it is running. Run your ruby command there, then, when you're done, terminate ruby and type exit in the shell window. That will leave you back in the original window where you ran script, and there will be a test.txt file containing your work in the current directory. Turn in that file.

Windows does not have a script command. If no better tool is available, you can create a transcript file as follows. Run ruby or irb in a command window. When you're done, right-click the window title bar and pick edit>select all from the popup menu, then pick edit>copy. Open a plain text editor like notepad++, paste the copied terminal session into a new window, and save that file as test.txt.

Regardless of how you create the transcript file, you can do some light editing to delete major typos or false starts, but don't worry about minor problems. We're interested in your overall demonstration, not in every small detail (as long as it's clear which things are false starts that should be ignored).

In addition to the code and transcript file, 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). The PDF file for part I can be a scanned document of a handwritten solution if that is convenient, as long as it is clear and legible and does not exceed a few MB in size.