COS 126: Fall 1996 Exercise Set 8

Answers

These exercises are intended help review the material on compilers. Do not turn in solutions.

1. There's a bug in compile.c! Try the expression q+z and look at the generated code. Fix the bug.
2. Polish prefix is the opposite of Polish suffixthe operators precede their operands; for example, the Polish prefix for ((a*(b + 2)) - (c + 9) is - * a + b 2 + c 9. Write a function that, given an abstract syntax tree, prints the expression in Polish prefix.
3. compile.c generates code using the registers as a stack. Revise the codegen function so that it uses the stack pointed to by R7; that is, it pushes results onto the stack and pops operands from the stack, and thus needs only 2 registers.

Answers

As always, try to solve the problems before looking at the suggested solutions.

1. Change the first case in codegen to

   if (isalpha(t->op)) {
   		int addr = t->op - 'a';
   		if (addr > 15) {
   			printf("%02X: B%X%02X\tR%d <- %02X\n", loc++,
   				dst, addr, dst, addr);
   			printf("%02X: 9%X%X%X\tR%d <- M[R%d+%d]\n", loc++,
   				dst, dst, 0, dst, dst, 0);
   		} else
   			printf("%02X: 9%X%X%X\tR%d <- M[R%d+%d]\n", loc++,
   				dst, 0, addr, dst, 0, addr);
   	} 

2. void preorder(Tree *t) {
   	if (t != NULL) {
   		fprintf(stderr, "%c", t->op);
   		preorder(t->left);
   		preorder(t->right);
   
   	}
   }

3. int codegen(Tree *t, int loc) {
   	if (isalpha(t->op)) {
   		int addr = t->op - 'a';
   		if (addr > 15) {
   			printf("%02X: B1%02X\tR1 <- %02X\n", loc++, addr, addr);
   			printf("%02X: 9110\tR1 <- M[R1+0]\n", loc++);
   		} else
   			printf("%02X: 910%X\tR1 <- M[R0+%d]\n", loc++, addr, addr);
   	} else if (isdigit(t->op))
   		printf("%02X: B1%02X\tR1 <- %d\n", loc++, t->op - '0', t->op - '0');
   	else {
   		loc = codegen(t->left, loc);
   		loc = codegen(t->right, loc);
   		printf("%02X: 9171\tR1 <- M[R7+1]\n", loc++);
   		printf("%02X: 9270\tR2 <- M[R7+0]\n", loc++);
   		printf("%02X: %X112\tR1 <- R1 %c R2\n", loc++,
   			strchr("+1-2*3", t->op)[1] - '0', t->op);
   		printf("%02X: B202\tR2 <- 2\n", loc++);
   		printf("%02X: 1772\tR7 <- R7 + R2 = R7 + 2\n", loc++);
   	}
   	printf("%02X: B201\tR2 <- 1\n", loc++);
   	printf("%02X: 2772\tR7 <- R7 - R2 = R7 - 1\n", loc++);
   	printf("%02X: A170\tM[R7+0] <- R1\n", loc++);
   	return loc;
   }