This assignment is due on April 28th.

Please read appendix A in EOPL and ``Syntax: Scanning and Parsing'' from Mitchell Wand.

Downloads: sllgen.scm and define-datatype.scm. Both are from Mitchell Wand and are documented within EOPL. Please note that a R5RS-conformant Scheme implementation is required for this assignment. It does not work with guile or our old installation of MIT Scheme for this reason. Chez Scheme is recommended.

Question 1

Consider following grammar of a little calculator:

<expression> ---> '(' <operation> ')' | <natural-number>
<operation> ---> <binary-operation> | <if-then-else>
<binary-operation> ---> <binaryop> <expression> <expression>
<if-then-else> ---> 'ifpos' <expression> 'then' <expression> 'else' <expression>
<binaryop> ---> '+' | '-' | '*' | '/'

Specify for SLLGEN in Scheme the corresponding scanner and grammar. Whitespace and comments can be defined as in the example language in the lecture. <natural-number> is non-empty sequence of digits 0-9 that is to be recognized by the scanner.

You can test that immediately and you should get similar results like here (perhaps with different names):

holly$ petite
Petite Chez Scheme Version 6.0a
Copyright (c) 1998 Cadence Research Systems

> (load "sllgen.scm")
sllgen.scm version 2.6.4 99/11/16
> (load "lcalc.scm")
> (define scan&parse (sllgen:make-string-parser
   scanner-lcalc grammar-lcalc))
> (scan&parse "1")
(handle-number 1)
> (scan&parse "(+ 1 2)")
(handle-expression
  (handle-op-binary
    (handle-binary
      (handle-plus)
      (handle-number 1)
      (handle-number 2))))
> (scan&parse "(+ 1 (ifpos (- 10 2) then 3 else 20))")
(handle-expression
  (handle-op-binary
    (handle-binary
      (handle-plus)
      (handle-number 1)
      (handle-expression
        (handle-op-if
          (handle-if
            (handle-expression
              (handle-op-binary
                (handle-binary
                  (handle-minus)
                  (handle-number 10)
                  (handle-number 2))))
            (handle-number 3)
            (handle-number 20)))))))
> ^D
holly$

Question 2

The semantic equations for this little language are simple as there are just arithmetic expressions of constant numbers with no variables. Hence, the semantic function for E is of type Exp --> N where N is the domain of numbers. Write the semantic equations for E[[ (+ E1 E2) ]] and E[[ (ifpos E1 then E2 else E3) ]]. Note that ifpos should return the value of E2 if E1 is positive, otherwise E3.

Question 3

Write a Scheme procedure that computes the resulting value from a given expression tree returned by scan&parse. Note that you have to generate the data types for the tree with:

(sllgen:make-define-datatypes scanner-lcalc grammar-lcalc)

Afterwards it is possible to analyze the syntax tree using cases constructs.

Alternatively, it is also possible to define the data types or the constructors which were given in the action part of the grammar yourself. This might even work on pre-R5RS implementations.

Please submit everything in one email that includes all your answers in attachments. Multiple submission emails are permitted but then only the last one is considered.