CSE 413 23sp Assignment 8 - Context-Free Grammars & Calculator Parser/Interpreter

Due: Thursday, June 1 by 11 pm. You should use Gradescope to submit your assignment in two parts, corresponding to the written and programming parts below. Details are given in the "What to hand in" section at the bottom of the assignment. If you have late days remaining, you may still use up to 2 of them them on this assignment, as usual, if you wish.

Added Sunday, May 28: we want to allow a bit of extra time for this assignment because of the end of the quarter crunch. So, for this assignment, everyone can use two late days, meaning the final deadline for everyone to turn in this assignment is 11 pm, Saturday, June 3, even if you have already used all or most of your late days previously. No further extensions or late days allowed after that deadline except, of course, for serious emergencies beyond your control (in which case you must send email to cse413-staff as soon as you can to notify the staff of the situation).

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


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 ww^Rcaⁿb²ⁿ, where w is a string of one 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 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."
   Your solution should use the English words in some essential way to show the ambiguity, not just something involving punctuation. (Hint: do not go overboard. This is not an exercise in computational linguistics or Natural Language Processing. If you've done "sentence diagrams" in grade school, that's the right level of complexity for the grammar here. If you are not familiar with sentence diagrams, wikipedia has an article that shows what we've got in mind - look at the later half of the article for example trees. Don't try to reproduce diagrams with exactly the same details, but that's the general idea. The idea is to have a bit of fun with grammars and explore ambiguities in the English language. 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.

Hint: one useful way to calculate the value of an expression is to have each of the parser methods return the value of the expression or sub-expression they parse.

Your parser/interpreter need only work on syntactically correct input. But note that a syntactically correct program can contain an unbound variable, which should be handled as specified in the calculator language description.

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

Use Gradescope to submit your solutions to this assignment in two parts.

For the problems in Part I please turn in a pdf file named hw8.pdf with your answers. This can be a scanned handwritten document if that is convenient, as long as it is clear and legible. Gradescope's web site has several instructional videos and help pages to outline the process, and this guide has specific information about scanning and uploading pdf files containing assignments.

• Unreadable solutions cannot be graded--no blurry photos, poor contrast, or illegible handwriting, please.
• Type-written solutions are encouraged but not required.
• If possible, don't split the solution to a problem across a page break.

For Part II, turn in scan.rb, calc.rb and any other source file(s) containing your Ruby code. Also submit a text file named hw8.txt containing some examples of input and output 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.

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

On Linux and OS X systems you can create a transcript file using 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.

Historically, Windows has not had 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).