PA1 - Expression Calc
Goal
To gain experience writing a simple lexer, an LL(1) parser, and several syntax tree traversals by hand.
Description
The program should read infix mathematical expressions from standard input, one expression per line. For each expression, the program should output a line in the following format:
[postfix-expr] = [result]
Where [postfix-expr] is the translated postfix form of the
expression, and [result] is the answer obtained by mathematically
evaluating the expression.
For simplicity, arithmetic should be right-associative, and should support the following operators: "+", "-", "*", "/", and "~". The "~" operation represents unary negation.
Your program MUST build at least two internal representations:
- a list or array of scanned tokens
- a tree of parsed syntax nodes
In other words, you should not produce all of the output in a single pass.
You should include verbose output that is toggled by a "-V" command-line switch, but the default invocation should not produce this output. The verbose output should match the formatting below.
If an input or calculation is invalid, your program should produce an appropriate error message instead of the regular output for that input. Possible errors include syntax or formatting errors as well as semantic problems such as dividing by zero. Your program should not terminate after an error, but should continue processing other lines of input after the erroneous input.
You may use the language of your choice, but the program must be compilable and executable using the software installed on wraith. You should include a Makefile or other appropriate build framework to generate an executable, preferably titled simply "calc".
In accordance with the assignment goal, you may not use any compiler tools infrastucture or generation tools, such as LLVM, ANTLR, lex/flec, or yacc/bison.
Language (BNF/Regex)
<expr> := <term> '+' <expr>
| <term> '-' <expr>
| <term>
<term> := <fact> '*' <term>
| <fact> '/' <term>
| <fact>
<fact> := '(' <expr> ')'
| '~' <fact>
| [int_literal]
[int_literal] := /[0-9]+/
Required Functions
lexer() : string -> list/array of tokens
parser() : list/array of tokens -> expression tree
format() : expression tree -> graphical representation
postfix() : expression tree -> postfix string
eval() : expression tree -> int
Sample Input
2+3*4
Sample Output
Regular:
2 3 4 * + = 14
Verbose: (w/ "-V" option)
Expression: 2+3*4
Tokens: [Num 2,Sym "+",Num 3,Sym "*",Num 4]
Formatted:
2
+
3
*
4
Postfix: 2 3 4 * +
Result: 14
Submission
DUE: Friday, Jan 30, 2015, at 23:59 (11:59PM) EST
Submit a zip or tarball with your complete solution on Canvas. Your code must compile and work on the class server. Part of your grade will be based on automated testing and part will be based on style considerations. Please make sure that your project adheres to the specification exactly to avoid difficulties with the automated testing framework, and make sure that your code is clean and documented.