CS 7400: Machine Problem 2

Abstract Data Types; Working with SLLGEN

Out: Tuesday, 9/22/09

Due: Tuesday, 9/29/09

(5 pts) Do exercise 2.3 in EOPL3. However, instead of using lists to implement diff-trees (as in the book), use define-datatype to implement a data type of diff-trees.
(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.
(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.
Your solution should consist of a module called mp21.ss with your code and your tests (using check-expect). I've given you a starting version of mp21-skeleton.ss.
(5 points) Now extend your solution 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.
For associative operators, the answer for a single argument should be what it would be if the appropriate identity were present:
```
+(3) = +(3,0) = 3
*(3) = *(3,1) = 3
```
What about the others? The specification says that the operators are to be done left to right, so -(n1,n2,n3,n4) = (((n1 - n2) - n3) - n4). This suggests that -(n1) should be n1, and /(n1) should be n1 as well.
```
-(3) = 3
/(3) = 3    
```
Turn in your solution to this problem as a module mp22.ss.
(5 pts) Modify your system so that empty operand lists are allowed. The sum of no operands is zero (the additive identity); the product of no operands is 1 (the multiplicative identity). The difference or quotient of no arguments should cause an error to be reported, since these operations are not associative and therefore do not have a clear identity.
Turn this in as a module mp23.ss.

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: Tue Sep 22 15:50:24 -0400 2009