CalcParser Using Atmel Mega32

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 user-defined variable. It can also evaluate the differentiated expression at a given constant value of the user-defined 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 pre-determined 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
[0-9]	number
[a-z]	variable
unlisted character	illegal

The parser is implemented using a push-down automaton which converts the symbols to an abstract syntax tree by recognizing a context-free 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 Backus-Naur Form) is the common notation used to express context-free grammars. Below is an example of the abstract syntax tree generated by the parser and the EBNF notation for the context-free gammer.

Parts List:

Part	Cost
Atmel Mega32 Microcontroller	$8.00 (rental from ECE 476 lab)
Custom Mega32 PC board	$5.00
RS-232 Connector	$1.00 (rental from ECE 476 lab)
MAX233A, SOIC	Free (Sampled from Maxim-IC)
Power Supply	$5.00
Total Cost:	$19.00

For more detail: CalcParser Using Atmel Mega32