milestone: Try out each toolset on a Tiny example

The purpose of this milestone is to make sure that your group functions well together, to get each toolset installed and working on a small example, and to help you compare between toolsets.

For each one of the flex+bison, SableCC 2, and SableCC 3 Tiny expression evaluators, make the following changes:

  1. Extend the Tiny expressions with an exponentiation operator **. Note that this operator is right-associative, i.e. 2**3**4 is to be parsed as 2**(3**4). Also not that this operator has higher precedence than all other numeric operators.
  2. Fix the pretty printer to output the minimal number of parentheses required to preserve the semantics of the expression: not too few and not too many. This should include the exponentiation operator from part 1.
  3. Introduce a unary minus operator -<exp> as syntactic sugar for the expression 0-<exp>. This means that unary minus should be defined in the grammar, but not in the abstract syntax trees. (In particular you do not need to extend the pretty printer etc. to include this operator.) This question is somewhat tricky in SableCC. If using the version 2 syntax, you need to write a CSTtoAST pass that builds an AST and in doing so strips out the unary minus. If using the version 3 syntax, there is no way to create a '0' node. You can either a) create a null node and then use a later pass that replaces it with zero, or b) perform a post pass that fixes up any unary minus nodes directly.
  4. The evaluator currently tries to determine the value of the input expression. Fix it to:
    1. Handle division by constant zero properly. This means that an error message should be printed for evaluating <l_exp> / <r_exp> where <r_exp> evaluates to zero.
    2. Handle partial evaluation of expressions involving identifiers. For instance, a + 3 * 4 should evaluate to a + 12 and no error message should be printed.
    3. Perform basic algebra on identifiers. For instance, 0 * a should evaluate to 0.
Include extra tests in the testcases file that demonstrate your ability to handle good and bad input appropriately. Running make check will create a file called result that will contain the output. We will combine the testcases from all groups and use them to test your improved Tiny expression evaluators.

Finally, based on your experiences, answer the following questions for your milestone report:

  1. Which toolset you will use for the WIG project?
  2. What was frustrating about this milestone? Difficult? Time consuming? Boring? Easy? Interesting? Fun? You can include discussion of things such as using version control, group coordination, and environment setup.
  3. What devious extension to the Tiny expressions should we ask students for next year?
The original Tiny source code is here: tiny. Use svn cp to create a branch group-X/tiny/, check that in, and then start your modifications. The milestone report should be checked as group-X/reports/tiny.txt.

There is no need to email us on completion. Unless you took a late day we will automatically take the version into account that was checked in last before the point of the deadline.

Maintained by Eric Bodden. [HOME]