[Modules] [Syllabus] [Project] [Lab Index]

Compiler Lab #4 - Code generation

Created by Todd Cooper & Karen Lemone

This lab will prepare you to do Project, Part 4 which uses the abstract syntax tree created in Project, part 3 to generate code.

As in the other labs, the yacc (bison) program is in the left box and input to that program is in the right box. The lex code is below.

When you press the button Edit the text and click me, the following will happen.

Like the other labs, the yacc code will be submitted to bison (yacc), flex (lex), the cc compiler, and the resultant program will be run on the input.
The results will be displayed on the bottom of the page.
You might have to scroll down in your browser to see them.

Step 0 Run the input and look at the output. Note that pseudocode for a stack machine is produced.

Step 1 Change the yacc/bison grammar so that it recognizes division and will divide an expression and add that node to the AST tree.
Add an expression to the input and show that the division works.
(You should have this from the last lab.) Make the divide operation print the correct pseudo-assembler in the generate function.

Step 2 Now add code to generate pseudo assembly for the pow() funtion (^) to get the power of two numbers, adding the pow node to the ast tree (as done in the last lab).

Run an expression as input to show that power works.
Add the pseudo code to run the power function.
For simplicity you can assume the machine has an opcode that does power, or you can loop the multiplication.

Step 3 On to Project, part 4! Now you are a compiler designer!

Edit the text above, and click on the button to see the result.

Yacc/Bison Parsing Program	Yacc/Bison Parsing Input
%{ #include <stdio.h> typedef struct node { struct node left; struct node right; int tokcode; char token; } node; node mknode(node left, node right, int tokcode, char token); void printtree(node tree); void generate(node tree); #define YYSTYPE struct node %} %start lines %token NUMBER %token PLUS MINUS TIMES DIVIDE POWER %token LEFT_PARENTHESIS RIGHT_PARENTHESIS %token END %left PLUS MINUS %left TIMES DIVIDE %right POWER %% lines: /* empty / \| lines line / do nothing / line: exp END { printtree($1); printf("\n\n"); generate($1); printf("\n"); } ; exp : term {$$ = $1;} \| exp PLUS term {$$ = mknode($1, $3, PLUS, "+");} \| exp MINUS term {$$ = mknode($1, $3, MINUS, "-");} ; term : factor {$$ = $1;} \| term TIMES factor {$$ = mknode($1, $3, TIMES, "");} ; factor : NUMBER {$$ = mknode(0,0, NUMBER, (char )yylval);} \| LEFT_PARENTHESIS exp RIGHT_PARENTHESIS {$$ = $2;} ; %% int main (void) {return yyparse ( );} node mknode(node left, node right, int tokcode, char token) { / malloc the node / node newnode = (node )malloc(sizeof(node)); char newstr = (char )malloc(strlen(token)+1); strcpy(newstr, token); newnode->left = left; newnode->right = right; newnode->token = newstr; newnode->tokcode = tokcode; return(newnode); } void printtree(node tree) { int i; if (tree->left \|\| tree->right) printf("("); printf(" %s ", tree->token); if (tree->left) printtree(tree->left); if (tree->right) printtree(tree->right); if (tree->left \|\| tree->right) printf(")"); } void generate(node tree) { int i; / generate the code for the left side / if (tree->left) generate(tree->left); / generate the code for the right side / if (tree->right) generate(tree->right); / generate code for this node / switch(tree->tokcode) { case 0: / we need no code for this node / break; case NUMBER: / push the number onto the stack / printf("PUSH %s\n", tree->token); break; case PLUS: printf("POP A\n"); printf("POP B\n"); printf("ADD A= A+B\n"); printf("PUSH A\n"); break; case MINUS: printf("POP A\n"); printf("POP B\n"); printf("SUB A= A-B\n"); printf("PUSH A\n"); break; case TIMES: printf("POP A\n"); printf("POP B\n"); printf("MULT A= AB\n"); printf("PUSH A\n"); break; default: printf("error unkown AST code %d\n", tree->tokcode); } } int yyerror (char *s) {fprintf (stderr, "%s\n", s);}	1+1; 1+23; 23+(56); 2(3+5)*6;
Lex Scanner Program
%{ #include "parsing_lab.h" %} %% [0-9]+ {yylval = (int)yytext; return NUMBER;} /* cast pointer to int for compiler warning / [ \t\n] ; "+" return(PLUS); "-" return(MINUS); "" return(TIMES); "/" return(DIVIDE); "^" return(POWER); "(" return(LEFT_PARENTHESIS); ")" return(RIGHT_PARENTHESIS); ";" return(END); %% int yywrap (void) {return 1;}