Connect the blocks into a graph and find code that can never run.
What to build
A program that builds the control-flow graph of three-address code and lists its unreachable blocks.
Requirements
- Blocks as in the previous exercise. A block ending in
goto Lgoes to L's block; one ending inif … goto LorifFalse … goto Lgoes to L's block and to the next block; any other block goes to the next block, or toexitif it is the last. - Print
Bk (lines a-b) -> S1 S2 …for each block, successors in order withexitlast, thenunreachable:and the blocks not reachable from B1, ornone.
Input
Line 1: n. Then n lines of three-address code.
Output
One line per block, then the unreachable line.
Constraints
n ≤ 100; every jump's label exists.
Example
Input:
8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:
Output:
B1 (lines 1-1) -> B2
B2 (lines 2-4) -> B3 B4
B3 (lines 5-7) -> B2
B4 (lines 8-8) -> exit
unreachable: none
Why it works
The last instruction of a block decides where control can go next, and any block no path reaches can never run.
Examples
Example 1 · Input
8 i = 0 L1: t1 = i < 3 ifFalse t1 goto L2 print i i = i + 1 goto L1 L2:
Expected output
B1 (lines 1-1) -> B2 B2 (lines 2-4) -> B3 B4 B3 (lines 5-7) -> B2 B4 (lines 8-8) -> exit unreachable: none
Example 2 · Input
5 x = 1 goto L1 x = 2 L1: print x
Expected output
B1 (lines 1-2) -> B3 B2 (lines 3-3) -> B3 B3 (lines 4-5) -> exit unreachable: B2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Find the blocks as in the previous exercise, and record which block holds each label.
Hint 2
Then search from B1 along the edges to find the reachable blocks.
Solution
Show one correct solution (try it yourself first)
lines = [input().strip() for _ in range(int(input()))]
leaders = {0}
for i, line in enumerate(lines):
if line.endswith(":"):
leaders.add(i)
if line.split()[0] in ("goto", "if", "ifFalse") and i + 1 < len(lines):
leaders.add(i + 1)
starts = sorted(leaders) + [len(lines)]
count = len(starts) - 1
block_of = {}
for k in range(count):
for line in lines[starts[k]:starts[k + 1]]:
if line.endswith(":"):
block_of[line[:-1]] = k
succ = []
for k in range(count):
words = lines[starts[k + 1] - 1].split()
if words[0] == "goto":
succ.append({block_of[words[1]]})
elif words[0] in ("if", "ifFalse"):
succ.append({block_of[words[3]], k + 1})
else:
succ.append({k + 1})
seen, todo = {0}, [0]
while todo:
for s in succ[todo.pop()]:
if s < count and s not in seen:
seen.add(s)
todo.append(s)
def name(k):
return "exit" if k == count else f"B{k + 1}"
for k in range(count):
print(f"B{k + 1} (lines {starts[k] + 1}-{starts[k + 1]}) -> " + " ".join(name(s) for s in sorted(succ[k])))
missing = [name(k) for k in range(count) if k not in seen]
print("unreachable:", " ".join(missing) if missing else "none")