Introduction
CalcParser is a command line calculator. Controlled by a serial connection, CalcParser parses and evaluates an arithmetic expression and has the capabilities to perform symbolic polynomial differentiation with respect to a userdefined variable. It can also evaluate the differentiated expression at a given constant value of the userdefined variable.
High Level Design

 Rationale and sources of project idea
The rationale behind building a CalcParser is to have a tool to parse and evaluate basic mathematical expressions that are frequently used in calculators and can be integrated into future projects involving calculators. The expression syntax and order of operations are commonly found on graphing calculators and mathematical software packages.

 Background Mathematics
CalcParser takes expressions in the common operator notation frequently used to express mathematical equations in computing applications. The order of operations is as follows with the top of the table having the highest precedence :
1  Parenthesis 
2  Exponents 
3  Multiplication / Division 
4  Addition / Subtraction 
The way CalcParser evaluates expressions may be different with other implementations. We do not implement floating point expression evaluation so the result is returned as zero. Some cases are listed in the following table:
Expression  Evaluates To 
a^b^c  a^(b*c) 
2^2  (2)^2 
10^(2)  0 
2^0  1 
Symbolic differentiation is implemented by applying differentiation rules to the Abstract Syntax Tree generated by the parser. The following rules of differentiation are applied:

 Constant Rule: if f(x) = constant

 Linearity

 Product Rule

 Chain Rule: if f(x) = h(g(x))

 Logical Structure
The program runs on a state machine with two states. These states correspond to the two functional modes: Evaluate and Differentiate abbreviated on the hyperterm prompt as eval and diff respectively. As the names suggest, these functions are used to distinguish between the two procedures: evaluation of an arithmetic expression and the differentiation of an expression. The user can switch to either of the two modes by using the command ‘diff’ or ‘eval’.
The scanner reads the input provided by the user once the serial read buffer is ready. The parser then parses the expression according to the predetermined syntax. The parsing results in the formation of a tree structure with a root node and a variable number of other nodes. The following functions are used to give a logical structure to our code.
Scanner Functions

 GetC() : Returns the next character in the receive buffer, r_buffer
 SGet() : Calls GetC() and assigns a symbol/type to the character retruned by GetC()
 Variable() : Assigns the character returned by GetC() to var if the character is of type variable
 Number() : Assigns the characters returned by GetC() to a numerical value if the character is an ASCII number
Parser Functions
 Expr() : The main recursive parser function that calls GetC() to grab characters out of the receive buffer r_buffer[RBUF_SIZE] and converts it to a syntax tree. This function recursively builds the syntax tree by recognizing addition and subtraction terms.
 Term() : Returns a pointer to the node that accounts for a multiply or divide term in the expression. The function calls ExpTerm() to assign the left and the right children of this node. It also checks for the Divide by Zero error.
 ExpTerm() : Returns a pointer to the node that accounts for an exponent term in the expression. The function calls Factor() to assign the left and the right children of this node.
 Factor() : Returns a pointer to a new node which can be a number, variable, or in the general case, another expression by calling Expr() specifically doing a parenthesis check. This function also recognizes any syntax errors, for instance if the expression provided by the user does not start with a number/minus sign/variable/left parantheses. It also takes into account the sign of the numbers entered by the user.
Other Functions
 Print() : Prints the tree structure from the specified root node to the specified level.
 PrintLinear() : Prints the tree structure from the specified root node to the specified level in a linear format.
 Diff() : Takes a root node of a syntax tree as an argument and returns a new syntax tree root node which corresponds to the differentiated expression.
 Simplify() : Takes a root node of a syntax tree as an argument and runs algebraic simplifications.
 NodeFree() : Takes a root node of a syntax tree and frees all the nodes below that node.
 NodeCopy() : Takes a root node of a syntax tree and makes a replica of the entire tree in memory.
 NodeCompare() : Takes two tree root nodes and check for identical expressions.

 Hardware/Software Tradeoffs
Since our project requires dynamic memory allocation, memory constrants of the Mega32 is the biggest tradeoff for portability.

 Standards, Patents, Copyrights, and Trademarks
CalcParser utilizes the RS232 standard for serial communication. No patents, copyrights, or trademarks were violated.
Program Design
The project uses a parser designed for the purpose of understanding the user input in a mathematical expression syntax. The usefulness of the project is further enhanced by the usability of the syntax. The scanner scans the input and uses the parser to interpret the expression and create an Abstract Syntax Tree. The program is designed to detect the following errors:
 Divide By Zero
 Program out of Memory
 Can’t differentiate expression
 Syntax Error
MCU Serial Communication
USART controls the serial communication from the PC, sending information to and from the microcontroller. The USART control and status register UCSRB was initialized to 0x18 which sets the receive and transmit enable bits for the USART to 1. UBRRL was initialized to 103 using the following formula:
Interrupts are used to alert the system when a packet is received or transmitted so that no blocking occurs. Global variables r_buffer and t_buffer were declared as 60 and 40 element arrays respectively. When the USART receives a character from the PC, the interrupt is run and the character is stored in the r_buffer. After the carriage return \r is received signifying the end of the string, the receive interrupt, UCSRB.7 is set to zero. At the same time a 1 bit flag, r_ready is set to 1.
User Control Specificaions
User commands are as follows:
Command  Action 
diff  Switch to differentiate mode 
eval  Switch to evaluate mode 
Scanner, Parser, and Syntax Tree
The scanner converts input characters into the following symbols.
Character  Symbol 
NULL or ;  eof 
+  plus 
–  minus 
*  times 
/  divide 
(  lparen 
)  rparen 
^  exponent 
[09]  number 
[az]  variable 
unlisted character  illegal 
The parser is implemented using a pushdown automaton which converts the symbols to an abstract syntax tree by recognizing a contextfree language. We implemented a recursive desent LL(1) parser for this project. The first L stands for read left to right. The second L stands for reduce left to right. The number one (1) in parenthesis stands for one symbol lookahead. EBNF (Extended BackusNaur Form) is the common notation used to express contextfree grammars. Below is an example of the abstract syntax tree generated by the parser and the EBNF notation for the contextfree gammer.
Parts List:
Part  Cost 
Atmel Mega32 Microcontroller  $8.00 (rental from ECE 476 lab) 
Custom Mega32 PC board  $5.00 
RS232 Connector  $1.00 (rental from ECE 476 lab) 
MAX233A, SOIC  Free (Sampled from MaximIC) 
Power Supply  $5.00 
Total Cost:  $19.00 
For more detail: CalcParser Using Atmel Mega32