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
6) Write tests for simplification and evaluate the results using the 'make check' target.
7) Write another version of the simplifier implemented using concrete syntax instead of abstract syntax.
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