-
Notifications
You must be signed in to change notification settings - Fork 0
Home
Note: this page written and provided by Prof. Hing Leung, PhD, New Mexico State University.
Due: (Friday) Sept 2, 2016 at 11:59pm BEFORE class
Submit all the source codes (including .h files) as a single zip file to CANVAS. Also include a README file that explains how well your program works.
We will learn to write a set of mutually recursive functions
(using the recursive descent parsing method)
to evaluate simple arithmetic expressions.
Following are the programs for solving the problem:
expr.c
expr.h
input_token.c
input_token.h
main.c
error.c
error.h
A simple tokenizer (input_token.h and input_token.c) has been written for you. Your job is to complete the codes given in expr.c
Later, we will solve the problem again using Lex and Yacc programs.
In machine/assembly language, there is no support for the evaluation of complex arithmetic expression involving parentheses and operators of different precedence. Such arithmetic expression needs to be converted into a series of simple arithmetic operations before given to the computer for execution.
How do we human evaluate an arithmetic expression?
For example, consider the expression
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )We read the expression from left to right.
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )So the answer is -511860.( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 306 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 306 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
( 78 + 306 *
( 45 * ( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 * ( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 15 * 4 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 60 ) - 8 ) )( 78 + 306 *
( 45 *
( 23 - 60 ) - 8 ) )( 78 + 306 *
( 45 * -37 - 8 ) )( 78 + 306 *
( -1665 - 8 ) )( 78 + 306 *
( -1665 - 8 ) )( 78 + 306 *
( -1665 - 8 ) )( 78 + 306 *
( -1665 - 8 ) )( 78 + 306 * -1673 )
( 78 + -511938 )
( -511860 )
( -511860 )
-511860
We write a program that simulates the above procedure for evaluating expression. Warning: the above example has not exhausted all the different cases that need to be handled.
We assume that each expression must begin and end with parentheses, which we also called brackets below. That is,
78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 )
is not considered to be a valid expression, but
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )is.
Next, we assume that each operand in an expression is a non-negative integer. That is,
( 56 * -23 )is not a valid expression. it has to be rewritten as
( 56 * (0 - 23) )First, we need to write a library that tokenizes the input expression. the function provided is
int get_token(int *w)See input_token.h for a detailed description of the function get_token.
Also, we assume that the input file holds only ONE expression which may be given over several lines.
Let
( 56 * -23 )
be the given input. get_token returns
OpenBracket Operand: 56 Mult Minus Operand: 23 CloseBracket
as the token sequence.
We need a library that reports the errors. This is given in error.h and error.c. Once an error is reported, we abort the program execution by an exit statement. Currently, the error reporting message is very brief. It can be extended easily to include a corresponding detailed message for every type of error.
The library expr.h and expr.c provides a function
int evaluate_expression()
that evaluates an expression given in the input.
Consider expr.c. How do we write the functions that evaluate an expression? We will be writing a set of mutually recursive functions. After we have read an open parenthesis, we execute eval_expr which assumes that ( has been just read. If we read an operand, then we will call eval_expr_1(opn1) to continue. Next if we read an operator, we will further call eval_expr_2(opn1, opr1) to continue. Altogether, we need five mutually recursive functions:
eval_expr() eval_expr_1(int opn1) eval_expr_2(int opn1,int opr1) eval_expr_3(int opn1,int opr1, int opn2) eval_expr_4(int opn1,int opr1, int opn2, int opr2)The evaluation of the expression should observe the precedence rules:
- * and / are of the same precedence
- + and - are of the same precedence
- * and / are of higher precedence than + and -
data1
data2
data3
data4
data5
data6
The commands to compile and execute the program is as follows:
gcc -c expr.c gcc -c input_token.c gcc -c error.c gcc -c btree.c gcc main.c expr.o input_token.o error.o btree.o -o expression
The executable of the program is placed in expr. To test the program on the test case given in data1, type
./expression data1
In this lab, we want to build an expression tree for a given arithmetic expression.
Modify the C codes expr.c so that the function eval_expr() returns an expression tree which is of the type BTree (instead of returning an integer).
Also, you need to modify the main program main.c so that instead of printing out the integer value for the given arithmetic expression, the program
-
prints out the expression tree by using an in-order traversal
using a recursive function
void in_order_traversal( BTree t )
-
prints out the expression tree by using an post-order traversal,
using a recursive function
void post_order_traversal( BTree t )
-
evaluate the expression tree to return an integer value using a recursive function
int eval( BTree t )
Suppose the expression is
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
the expression tree is
+
/ \
78 *
/ \
* \
/ \ \
34 9 -
/ \
* 8
/ \
45 -
/ \
23 *
/ \
15 4
the in-order traversal would print out
(78 +((34*9)*((45*(23-(15*4)))-8)))
The post-order traversal of the expression tree given in step 1 gives out the same expression in postfix notation which is
78 34 9 * 45 23 15 4 * - * 8 - * +
The integer value evaluated is -511860.
SUPPLEMENTARY NOTES (nothing to turn in for this section)
We can re-write the mutually recursive functions to evaluate arithmetic expressions into a non-recursive program using a stack.
Below is an illustration to evaluate an arithmetic expression using a stack.
For example, consider the expression
( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
INPUT:So the answer is -511860.stack bottom -> ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 306 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 306 * ( 45 * ( 23 - 15 * 4 ) - 8 ) )
stack bottom -> ( 78 + 306 *
stack top -> ( 45 * ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
stack top -> ( 45 * ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 15 * 4 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 60 ) - 8 ) )stack bottom -> ( 78 + 306 *
( 45 *
stack top -> ( 23 - 60 ) - 8 ) )unget_token -37
stack bottom -> ( 78 + 306 *
stack top -> ( 45 * -37 - 8 ) )stack bottom -> ( 78 + 306 *
stack top -> ( 45 * -37 - 8 ) )stack bottom -> ( 78 + 306 *
stack top -> ( -1665 - 8 ) )stack bottom -> ( 78 + 306 *
stack top -> ( -1665 - 8 ) )stack bottom -> ( 78 + 306 *
stack top -> ( -1665 - 8 ) )stack bottom -> ( 78 + 306 *
stack top -> ( -1665 - 8 ) )unget_token -1673
stack bottom -> ( 78 + 306 * -1673 )
stack bottom -> ( 78 + 306 * -1673 )
stack bottom -> ( 78 + -511938 )
stack bottom -> ( -511860 )
stack bottom -> ( -511860 )
unget_token -511860
-511860
SUPPLEMENTARY NOTES (nothing to turn in for this section)
The problem can be solved easily using Lex and Yacc programs
hw1.l and hw1.y.
Commands to run the programs are:
flex hw1.l yacc hw1.y gcc y.tab.c -lfl -ly a.out < data1
Note that + and - are of lower precedence than * and /. Also, +, -, * and / are left associate. Indeed, Yacc provides a facility to handle operators easily so that the user does not have to specify the grammar rules. The Yacc program can be rewritten as hw1a.y to take advantage of the facility. Soon after the specification of the token INTdenotation in the hw1a.y program, the operators are listed with the lower precedence operators (+ and -) presented first, followed by the higher precedence operators (* and /) given in the next line. Within each line, it begins with the word left indicating that the operators are left associative.
We can augment hw1.y to give hw1b.y to print the order for which the grammar rules are applied.
Example: we run hw1b.y on the test data data1 which is the same example input ( 78 + 34 * 9 * ( 45 * ( 23 - 15 * 4 ) - 8 ) ) generated by the C program we developed for evaluating arithmetic expressions.
flex hw1.l yacc hw1b.y gcc y.tab.c -lfl -ly a.out < data1 > data1.out
Click here for the outputs. Next, you should draw the parse tree for the input. Then pay attention to the order that the grammar rules are applied, and compare that to the order in which the expression are processed by the C program. In fact, the order shows that the YACC parser employs the bottom-up parsing technique.