PT Course
Home
Education Page
Description
Schedule
Slides
Assignments
Center for ST
Home
Master Program
Center
Home
Courses
People
Projects
Page
Edit Page
Rename Page
Attach File
Printable
Wiki Source
More ...
Web
Recent Changes
Notify Service
News
Page Index
Search
More ...
Wiki
About TWiki
Text Formatting
Registration
Change Password
Reset Password
Users
Groups
Log In
or
Register
Simplifying Expressions
Pt04
----+++ Expression Language 1) Develop a syntax definition Exp.sdf for a language of arithmetic and boolean expressions using at least the following operators: <verbatim> + - * / ** % > < <= >= != == ! & | </verbatim> 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