Simplifying Expressions

Expression Language

1) Develop a syntax definition Exp.sdf for a language of arithmetic and boolean expressions using at least the following operators:

  + - * / ** % 
  > < <= >= != == 
  ! & |

Use the standard rules for priority and associativity. Furthermore, the language should have identifiers (variables), integer constants, and boolean constants.

2) Write a number of files with example expressions.

3) Derive a signature for the abstract syntax of the language from the syntax definition. (The makefile in the skeleton package should already take care of this.

4) Derive a default pretty-printer from the syntax definition and annotate it with box expressions to produce pretty output.

Simplification of Expressions

5) Write a simplifier for expressions using rewrite rules and innermost rewriting in module simplify.

6) Write tests for simplification and evaluate the results using the 'make check' target.

Concrete Syntax

7) Write another version of the simplifier implemented using concrete syntax instead of abstract syntax.

Assesment

The assignment will be judged by feeding the simplifier a couple of complex expressions according to the following criteria:

• the expression should be parsed correctly
• its should be transformed to an expression that has the same meaning, i.e., for any assignment of values to variables the original and the result should retain the same value
• the result should be pretty-printed correctly
• it should be as simple as possible, i.e., any computations that can be done, have been done, and expensive operations have been replaced with less expensive operations, e.g., multiplication by addition; this is a flexible criterion