CalcParser


Yunjiu Patrick Li (yl365), Gyanda Sachdeva (gs256)

ECE 476 Final Project
[ Introduction | High Level Design | Program/Hardware Design | Design Results | Conclusions | Acknowledgments ]
[ Code | Cost | Task | References ]

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.

[Back to Top]

High Level Design

[Back to Top]

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:

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.

Below are the meanings of the symbols used in the EBNF notation.

|

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

Below is how EBNF notation converts to code.

[...]

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

[Back to Top]

Design Results

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

[Back to Top]

Conclusions

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.

[Back to Top]

Acknowledgments

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.

[Back to Top]

Code

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

[Back to Top]

Cost

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

[Back to Top]

Task

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

[Back to Top]

References

Datasheets: ATMEL Mega32

Serial Communication: ECE476 Serial Communication Page

[Back to Top]