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

Due: Online via the Catalyst Dropbox by 11 pm, Thursday, December 8, 2016. If you have late days remaining, you may still use up to 2 of them them on this assignment, as usual, 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 of 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, including the empty string.
      Example: ([[](()[()][[]])])[]((())) .
    2. The language containing non-empty 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 one 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 one 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. This is not an exercise in linguistics or natural language processing; it is meant as an example of using grammars to generate sentences and also as an example of the limitations of context-free grammars for describing natural languages. So don't overthink the problem and don't produce an overly elaborate solution.)

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 that they are currently 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 clear, all work properly.

Your parser/evaluator code should be contained in a file calc.rb. Your scanner code should continue to be in the scan.rb file from the previous assignment. You may, if you wish, break your program into additional source files in the same directory, but it should be possible to run your program by executing the file calc.rb using an appropriate ruby command, and by default the program should read input from the keyboard and display output on the screen, i.e., don't make any special provisions in your program for reading or writing specific named files. 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 clear 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 scan.rb, calc.rb, and any other source file(s) for part II, and some examples of test input and output in a file hw8.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 hw8.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 hw8.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 hw8.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 hw8.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 or a few extra characters like backspaces entered to correct typing errors. 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 files, you should also include a readme.txt file that describes what works and what doesn't and any extensions that 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.