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
5+4*(3-2)/1
% caculator exp_file
9
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.
<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.
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.)