CSG 111 Machine Problem 2

Abstract Data Types; Working with SLLGEN

Out: Tuesday, 9/25/07

Due: Tuesday, 10/2/07

(5 pts) Do exercise 2.3 in EOPL3.
(5 pts) In this problem, you will use SLLGEN to generate a scanner and parser for arithmetic expressions.
We can write a grammar for arithmetic expressions as follows:
```
AExp ::= Number |  Arith-Op ( AExp , AExp )
Arith-Op ::= + | - | * | /
```
Write a lexical specification and a grammar in SLLGEN that will scan and parse strings according to this grammar. For example, you should get results like:
```
> (scan&parse "22")
#(struct:const-aexp 22)
> (scan&parse "*(22,33)")
#(struct:composite-aexp
  #(struct:times-op)
  #(struct:const-aexp 22)
  #(struct:const-aexp 33))
```
These are the results I got by transcribing the grammar into SLLGEN. Yours should be pretty similar, except maybe for the choice of names. For this problem, you need not use a formal testing framework; a transcript of tests that can be scanned visually is good enough.
(5 pts) Write a set of procedures that will take the syntax tree produced by your parser and evaluate it as an arithmetic expression.
Your solution should include a procedure called value-of-aexp which should take the syntax tree of an AExp and produce its value, and a procedure called value-of-aexp-string, which should be defined by
```
(define value-of-aexp-string
  (lambda (str)
    (value-of-aexp (scan&parse str))))
```
Remember to Follow the Grammar.
Also remember that you must use cases to destructure your trees. If you use any other way to destructure the syntax trees, you will be penalized. You can of course use car and cdr on lists (not trees).
I've provided you with a test module mp2-top.scm in the interps/lecture2 directory. It provides a procedure called run-mp2-tests, which you can call by saying (run-mp2-tests! value-of-aexp-string). Add sufficient additional tests to convince the grader of the correctness of code.
Your solution should consist of two modules: a module called mp2-soln.scm with your code, and your revised version of mp2-top.scm, containing your tests. I've given you a starting version of mp2-soln.scm in the same directory.

(10 points)

This exercise is about translating between grammar notations and using SLLGEN to debug
the given grammar.  It is also about understanding the formal definition of objects
and languages for schemas 
that define both objects and languages. 
Class dictionaries and XML schemas fall into this category.

Consider the following Test language given by the 
Class Dictionary G.

Define the Scheme datatypes (using EOPL define-datatype)  that "correspond" 
to the classes defined in this class dictionary G.
Simulate the class dictionary G as well as you can.
Is there a mismatch between the two datatype definition techniques?

What is wrong with this grammar G? 
Is it non-ambiguous? Prove your answer.

Describe in English the set: Objects(G).
We define the print function for G: Objects(G) -> String by translating the
class dictionary into print functions, taking the follow the grammar approach. 
For each data type defined in the class dictionary we get a print function.
We define Language(G): the set of strings o.print() for all o in Objects(G).
Is print a bijection from Objects(G) to Language(G)?

Is G inductive? Prove that for all classes C there esists a non-circular C-object.

Is G left-recursive?

Here is an input that was actually parsed by the generated parser.
Does the created object represent the intended input?

(
input
and ( or (a !b c) or (!a b !c) or(a)) 0 0
assignment !a
expected output
and ( or (!b c) ) 1 1

input
and ( or ()) 777
assignment !b
expected output
and ( or ()) 777

input
and ( or ()) 
assignment !b
expected output
and ( or ())
)

Here is the object that was created by the parser.

Find the answer by translating the class dictionary to the SLLGEN language.
What is the SLLGEN error message?

Make minimal changes to the grammar so that it is non-ambiguous,
non-left-recursive and inductive.
By a minimal change I mean one which only adds tokens 
to the language without introducing new classes.

A quick introduction to class dictionaries is here:
Class Dictionaries
A detailed description of class dictionaries:
Definition and Design of Class Dictionaries (2 book chapters)

(5 points) Now extend your solution for 3 to handle the following grammar:
```
AExp ::= Number | Arith-Op ( AExp {, AExp}* )
Arith-Op ::= + | - | * | /
```
Notice that the second production for AExp forces the arguments to an arithmetic operator to be a non-empty, comma-separated list of AExp's.
Be sure that your evaluator evaluates the operands from left to right, so "-(5,3,2)" produces (5-3)-2 = 0, not 5-(3-2) = 4.
Turn in your solution to this problem as a pair of modules mp22-soln.scm and mp22-top.scm.

The turn-in procedure and deliverables for this problem will be the same as for Machine Problem #1.

The grading criteria for this problem will also be similar to those used for Machine Problem #1.

Last modified: Mon Feb 5 19:20:24 EST 2007