CSC254 Calculator Assignment

Due by 11:59pm 09/22/2010


In this assignment, you are required to write a calculator that takes an expression of integer constants and outputs the result of the expression. Following is an example (each line is input/out in a shell):
       % cat exp_file
       % caculator exp_file

The semantics of arithmetic operations is the same as integer operations in C (so 5/3 = 1). Your calculator needs to evaluate the expression in the left-associative order. For example, the steps to evaluate 3+4+5 are 3+4+5 => 7+5 => 12.

To complete this assignment you need to write a parser for an expression grammar and write an evaluator.  The parser requires grammar design and parsing, especially LL(1) parsing.  The evaluator uses a technique called attribute grammar or syntax-directed translation, which we will discuss in detail starting in the lecture on September 21.

Note: do NOT use lex or yacc to generate code automatically.

Syntax of an input expression

<expression> --> <term> | <expression> <addop> <term>
<addop> --> plus_sign | minus_sign
<term> --> <factor> | <term> <mulop> <factor>
<mulop> --> star_sign | forward_slash
<factor> --> NUMBER | minus_sign NUMBER | left_parenthesis <expression> right_parenthesis

We recommend you to implement a top-down parser.  You may use the LL(1) grammar given by the slides in lecture_slides/parsing.pdf.  You may choose to implementent a bottom-up parser, for which you may use the LALR grammar from the 9/14 lecture.

What/When to Submit

Turn in your code with a report of your design including passed expressions and instructions to run your calculator. Submit these files in project_code/calculator/user_id before 11:59pm Wednesday 09/22/2010. You MUST submit your calculator by using hg reporsitory. (TA will give a free poke on Thursday morning if he doesn't see your directory there.)