# EECS 337 Assignment #9 solution

Part 1: Reading Compilers - Principles, Techniques, & Tools, 2nd Edition, Sections 7.1, 7.2, 7.4 Homework Exercises – laboratory assignment and answer the questions at the end of the assignment.
Introduction In this assignment you copy and modify the previous calculator program to support C style if-else statements and add the equality and relational operators (==, !=, <, , <=, =). You design and implement a quad function to support the three-address code highlighted below. An if-else expression without an equality operator assumes the not equal to zero operation. For example, if(a) is the same as if(a != 0) and generates the IFTRUE quad. 1) X = Y op Z 2) X = op Y 3) X = Y 4) GOTO L 5) IFTRUE X GOTO L and IFFALSE X GOTO L 6) IF X relop Y GOTO L 7) CALL P,N or Y = CALL P,N and RETURN or RETURN Y 8) X = Y[i] or X[i] = Y 9) X = &Y or X = *Y or *X = Y
The equality and relational operators are part of an expression and do not have to be the last operation. For example: if((a == 1) ^ (b != 0)) a = 1; else b = 1; This C fragment creates the following sequence of three-address quads: t1 = a t2 = 1 t3 = t1 == t2 t4 = b t5 = 0 t6 = t4 != t5 t7 = t3 ^ t6 IFTRUE t7 GOTO label1 t8 = 1 a = t8 GOTO label2 label1: t9 = 1 b = t9 label2:
Notice the assembler style format with labels in the first column and quads tabbed over. The equality and relational operators are treated as binary operators with a result of zero or one.
Precedence and Associatively of C Operators
OPERATORS ASSOCIATIVITY () {} - . left to right ! ~ ++ -- + - * & (type) sizeof right to left * / % left to right + - left to right << left to right < <= = left to right == != left to right & left to right ^ left to right | left to right && left to right || left to right ?: right to left = += -= *= /= %= &= ^= |= <<= = right to left , left to right The calculator program uses the yacc precedence operators (%left, %right, %prec) where the ansi C compiler uses productions to determine precedence. An ansi C compiler fragment for expressions is shown below. Notice how they implement part of the precedence table. multiplicative_expr : cast_expr | multiplicative_expr '*' cast_expr | multiplicative_expr '/' cast_expr | multiplicative_expr '%' cast_expr ; additive_expr : multiplicative_expr | additive_expr '+' multiplicative_expr | additive_expr '-' multiplicative_expr ; shift_expr : additive_expr | shift_expr LEFT_OP additive_expr | shift_expr RIGHT_OP additive_expr ; relational_expr : shift_expr | relational_expr '<' shift_expr | relational_expr '' shift_expr | relational_expr LE_OP shift_expr | relational_expr GE_OP shift_expr ; equality_expr : relational_expr | equality_expr EQ_OP relational_expr | equality_expr NE_OP relational_expr ; and_expr : equality_expr | and_expr '&' equality_expr ;
Part 2: Laboratory From a console window, make a directory on your computer in your EECS337 directory under your Case ID and call it hw09. mkdir ~/EECS337/caseid/hw09/ ; where caseid is YOUR Case ID, enter all in lower case
Change directory to the hw09 directory. cd ~/EECS337/caseid/hw09/
Download a copy of: hw09_caseid.tar file to the hw09 directory from http://blackboard.case.edu/ in the EECS337 homework assignment area. To untar the tar file type the command: tar xvf hw09_caseid.tar
The following files will be created in the current working directory. hw09_test.sh Makefile math21.txt math22.txt math23.txt // extra credit
Copy the following files from the assignment 08 directory to this directory with the commands: cp ../hw08/lex.l . cp ../hw08/main.c . cp ../hw08/quad.c . cp ../hw08/symbol_table.c . cp ../hw08/yacc.y . cp ../hw08/yystype.h .
You are now ready to solve the laboratory assignment.
Part 3: Laboratory Assignment There are no changes to the main.c and symbol_table.c files for this assignment. You may want to go in and change the comments in the headers to note this is assignment 09.
Edit the yystype.h file and below in the external functions section add the function prototype for the new parser action. /* * new function for IF ELSE productions */ extern QUAD *new_quad5( int operator, QUAD *q1, QUAD *q2, QUAD *q3);
Save the yystype.h file.
Edit the lex.l file and add two regular expressions below "\$" and actions to support the if-else keywords. "if" { return IF; } "else" { return ELSE; } Below the constant expressions and before the white space expression, add the relational operators. Notice the less than and greater than operators (<, ) are already defined. "<=" { return( LE); } "=" { return( GE); } "==" { return( EQ); } "!=" { return( NE); }
Save the lex.l file.
Edit the yacc.y file and add the tokens shown below. The parser grammar uses six new tokens and the next four are used as quad operators. %token IF %token ELSE %token LE %token GE %token EQ %token NE /* quads operators */ %token LABEL %token GOTO %token IFTRUE %token IFFALSE
Insert the new precedence operators. Use the precedence table to determine the correct location. %left EQ NE %left '<' '' GE LE Remove the previous statement productions and insert the code below. These statements are the if-else and assignment statements. Notice the assignment statement now ends with a semi-colon and the if-else productions do not. This allows generating quads from C program fragments.
Build the calc program and fix any errors using the commands: make clean make
To test your version, and print the symbol table type the command line: ./calc +symbol and at prompt enter an expression: if( a3 ^ 0x01) a3 = a3 + b2; else a3 = 0x01; To exit the application type on the command line: \$ To test with the symbol table and with the yydebug statements type: ./calc +symbol +yydebug and enter a math expression as before. Your output for the example above should be: for caseid start time: Fri Oct 25 14:17:20 2013 Enter calculator expression and \$ to exit if( a3 ^ 0x01) a3 = a3 + b2; else a3 = 0x01; t1 = a3 t2 = 0x01 t3 = t1 ^ t2 IFTRUE t3 GOTO label1 t4 = a3 t5 = b2 t6 = t4 + t5 a3 = t6 GOTO label2 label1: t7 = 0x01 a3 = t7 label2: \$ symbol table: index: 1 identifier: a3 length: 3 index: 2 constant: 0x01 length: 5 format: hexadecimal index: 3 identifier: b2 length: 3
Test using the test files using the commands below: ./calc math21.txt ./calc math22.txt Part 4: Output Generation When all your lab assignments have been completed execute the homework script file “./hw09_test.sh” using the command below. ./hw09_test.sh & hw09_test.txt
Print out the hw09_test.txt file and put your name, assignment number and date on it. Turn in the printout and answer the questions at the end of the assignment.
Your final directory structure for the calc compiler should be as below (using your Case ID): EECS337/caseid/hw09/Makefile EECS337/caseid/hw09/calc EECS337/caseid/hw09/hw09_caseid.tar EECS337/caseid/hw09/hw09_test.sh EECS337/caseid/hw09/hw09_test.txt EECS337/caseid/hw09/lex.l EECS337/caseid/hw09/main.c EECS337/caseid/hw09/math21.txt EECS337/caseid/hw09/math22.txt EECS337/caseid/hw09/math23.txt EECS337/caseid/hw09/quad.c EECS337/caseid/hw09/symbol.c EECS337/caseid/hw09/yacc.y EECS337/caseid/hw09/yystype.h
Part 5: Extra Credit (5 points) Save a copy of your code and edit the yacc .y file. Add the not (!) operator to the precedence section. Use the precedence table to determine the correct location. Then add the new not production to the expression productions. This uses the same quad function as the other unary operators. Notice this operator is already defined in the lex.l file. | '!' expr { \$\$.quad = new_quad2( '!', \$2.quad); } Save the yacc.y file.