UofT ECE 467 (2022 Fall) - Exercises for Midterm 2

• Home
• Lab 0
• Lab 1
• Lab 2
• Lab 3
• Lab 4
• Continuing Your Compiler
• Quick References
• C++ Primer
• Local Setup
• A Bit About Types
• Undefined Behaviour

The website and starter code is being pre-emptively updated!

I don't know if I'll be teaching the course again, but if I wait until next year I'll forget feedback I've received. Note that more test cases have been added (if you pull the new starter code); those are for the (potential) future!

LR(1) and LALR(1) Parsing

This website can generate (among others) LR(1) and LALR(1) parsers. Note that you need to include the augmented start rule as the first rule yourself. Try the following grammars:

A -> C x A
A -> ''
B -> x C y
B -> x C
C -> x B x
C -> z

S -> L = R
S -> R
L -> * R
L -> id
R -> L

bexpr -> bexpr OR bterm
bexpr -> bterm
bterm -> bterm AND bfactor
bterm -> bfactor
bfactor -> NOT bfactor
bfactor -> LPAREN bexpr RPAREN
bfactor -> TRUE
bfactor -> FALSE

Data-Flow Analyses

There are some existing examples on the web:

• https://pages.cs.wisc.edu/~horwitz/CS704-NOTES/2.DATAFLOW.html (search for “Test Yourself”).
• https://groups.seas.harvard.edu/courses/cs153/2019fa/lectures/Lec20-Dataflow-analysis.pdf (pages 21 - 26, 31).
  • Note: for live variables, “def” = kill, “use” = gen.
• https://cmu-program-analysis.github.io/2022/lecture-slides/05-dataflow-examples.pdf (pages 11 - 14, 22 - 24, 29 - 31).

Exercises from the textbook:

• 9.2.1 - 9.2.6 (pages 615 - 616). Note:
  • for available expressions, “e_gen” and “e_kill” are gen and kill.
  • for live variables, “def” = kill, “use” = gen.

Lattices, Partial Orders, and Monotonicity

Exercises from the textbook:

• 9.3.2 - 9.3.3 (pages 631 - 632).

SSA Form

Convert the following code to SSA form.

int x = input();
int n = 0;
while (x != 1) {
	if (x % 2 == 0) {
		x = x / 2;
	} else {
		x = 3 * x + 1;
	}
	n = n + 1;
}
return n;

What does the following code print given an input of n = 5?

a0 = 0;
b0 = 1;
i0 = 0;
while (a1 = phi(a0, a2); b1 = phi(b0, b2); i1 = phi(i0, i2); i1 < n) {
	c = a1 + b1;
	a2 = b1;
	b2 = c;
	i2 = i1 + 1;
}
print(a1);

Solutions

x0 = input();
n0 = 0;
while (x1 = phi(x0, x4); n1 = phi(n0, n2); x1 != 1) {
	if (x1 % 2) == 0 {
		x2 = x1 / 2;
	} else {
		t = 3 * x1;
		x3 = t + 1;
	}
	x4 = phi(x2, x3);
	n2 = n1 + 1;
}
return n1;

5