CalcParser

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.

• 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.

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

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 commands are as follows:

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.

|	or (lowest prescedence)
[...]	optional
{...}	0,1,2... repetitions
(...)	grouping (to change precedence)
"..."	terminal symbol (from scanner)
text	non-terminal symbol (needs production rule)
.	end of production rule

[...]	if statement
{...}	while statement
"..." (terminal symbol)	test (assert or if statement)
text (non-terminal symbol)	procedure call

Differentiation and Simplification

Differentiation uses the four differentiation rules in the mathematical background section to generate a new syntax tree. Simplify simplifies and evaluates expressions using the following rules:

f + 0 = f

f + f = 2*f

1 + 1 = 2

f - f = 0

2 - 1 = 1

3 / 2 = 1

3 * 2 = 6

1 * f = f

0 * f = 0

2 ^ 2 = 4

f ^ 1 = f

f ^ 0 = 1

The results of some of the calculations performed by CalcParser are shown below

• Accuracy

The success of the project is largely based on accuracy of results in numerical computation and the evaluation of derivatives. We paid close attention to memory optimization in order to accommodate long numerical expressions. Longer expressions required a larger heap and stack size to process. Only long size integer operation is supported and there are no accuracy issues with the exception of overflow.

• Design Safety

CalcParser does not include any mechanical parts or features such as motors or gears. The PC Board was carefully soldered observing all safety guidelines. We did run into initial troubles with the soldering mechanism when the port pins on the microcontroller were shorted out which we solved by desoldering.

• Interference

This project does not create any RF interference.

• Usability

Usability of our project can improve if we add a battery pack, LCD screen, and keypad, instead of using a serial connection.

We are quite happy with the outcome of the project. Due to last minute changes in the project idea, we had little time to implement CalcParser but the final outcome has been rewarding. This project still has scope for much improvement. Support for floating point numbers and mathematical functions such as trigonometric and logarithmic functions can be added to CalcParser. Another exciting addition would be an LCD for plotting.

• Ethical considerations
1. to accept responsibility in making decisions consistent with the safety, health and welfare of the public, and to disclose promptly factors that might endanger the public or the environment;

In keeping with the IEEE Code of Ethics, we strove to maintain the safety standards in the lab and observed the required guidelines during soldering such as wearing eye protection and keeping safe distance from the iron.

2. to avoid real or perceived conflicts of interest whenever possible, and to disclose them to affected parties when they do exist;

Our project posed no conflict with any other projects in the class and we were sincere with the progress of our work as was reported in our progress reports that were due at the end of labs.

3. to be honest and realistic in stating claims or estimates based on available data;

All statements regarding CalcParser in this report are honest and realistic to the best of our knowledge.

4. to reject bribery in all its forms;

There was no situation that raised any concerns regarding bribery or illegal actions during the course of this project.

5. to improve the understanding of technology, its appropriate application, and potential consequences;

As part of the class as well as members of a group, we improved our technical competence as well as group work and project management skills.

6. to maintain and improve our technical competence and to undertake technological tasks for others only if qualified by training or experience, or after full disclosure of pertinent limitations;

This was not an issue with this project.

7. to seek, accept, and offer honest criticism of technical work, to acknowledge and correct errors, and to credit properly the contributions of others;

We also made sure to return the unused parts to the lab and put them in the right place. We also appropriately credited all the people and firms that helped towards the working of our project.

8. to treat fairly all persons regardless of such factors as race, religion, gender, disability, age, or national origin;

Our project did not offend anyone on the basis of race, religion, gender, disability, age, or national origin.

9. to avoid injuring others, their property, reputation, or employment by false or malicious action;

Our project did not result in any injury to property or people. Since it is software based, it involves no physical harm to its surroundings.

10. to assist colleagues and co-workers in their professional development and to support them in following this code of ethics.

While working in the lab, we helped fellow project groups by sharing extra parts and providing assistance when requested.

• Legal considerations

There were no legal considerations for CalcParser.

We would like to thank the staff of ECE 476 for their constant support and encouragement throughout the class. We especially want to thank Prof. Bruce Land and our lab TA, Eric Okawa for their guidance and advise. We would also like to thank all the TAs and consultants who stayed up until late to keep the lab open for use as well as our fellow classmates who have been extremely helpful throughout the semester.

CalcParser code and project file can be obtained here: CalcParser.zip

The budget distribution for the project is as follows

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

A list of the specific tasks in the project carried out by each team member are as follows:

Task	Person Responsible
Idea Formulation	Patrick, Gyanda
Soldering	Patrick, Gyanda
Programming	Patrick, Gyanda
Debugging Code	Patrick
Webpage	Gyanda

Datasheets: ATMEL Mega32

Serial Communication: ECE476 Serial Communication Page