Decisions, Ambiguity, and Generating Code for Two Machines

Read alongside this

Compilers: Principles, Techniques and Tools — Ch. 4 §4.3.2 (ambiguity and the dangling else), §4.8 (using ambiguous grammars); Ch. 6 §6.6 (boolean expressions and control flow), §6.7 (backpatching), §6.8 (switch-statements); Ch. 7 review; Ch. 8 §8.6 (a simple code generator), §8.8 (register allocation and assignment); Ch. 9 §9.1 review.
§6.6 and §6.7 together are the theoretical core of this topic — read them before you write any lowering code.
§6.8 is three pages and gives all three switch implementations with their costs.

0Where this topic sits

This topic completes the language. Everything in it is a variation on machinery you already have: if is a loop without the back edge, switch is a chain of ifs, and break uses the same label stack. What is genuinely new is one famous grammar ambiguity, one real code-generation choice, and one question — what would it cost to target a different machine — that the whole architecture has been building toward.

1The dangling else

This is the best-known ambiguity in programming languages, and your grammar has it the moment you write the two obvious rules (Dragon §4.3.2):

stmt -> 'if' '(' expr ')' stmt
      | 'if' '(' expr ')' stmt 'else' stmt
      | other

The dangling-else ambiguity (Dragon §4.3.2, Fig. 4.9). if (a) if (b) X else Y has two parse trees. With a true and b false, the first runs Y and the second runs nothing. Every mainstream language chooses the first — else matches the nearest unmatched if — and a compiler must declare that choice rather than inherit it by accident.

Both trees are legal derivations. The universal resolution is match each else with the closest unmatched if, and every mainstream language adopts it — partly because it is what indentation suggests, partly because the alternative makes it impossible to write an if without an else inside one that has one.

Removing the ambiguity from the grammar

Dragon §4.3.2 gives the unambiguous grammar. The idea is to distinguish a matched statement — one in which every if already has its else — from an unmatched one, and forbid an unmatched statement between an if and its else:

stmt            -> matched_stmt | unmatched_stmt

matched_stmt    -> 'if' '(' expr ')' matched_stmt 'else' matched_stmt
                 | other

unmatched_stmt  -> 'if' '(' expr ')' stmt
                 | 'if' '(' expr ')' matched_stmt 'else' unmatched_stmt

This works, needs no parser-generator features, and is what you would use with a hand-written recursive-descent parser. It also doubles the number of statement nonterminals, and the doubling propagates into every rule that mentions stmt.

Or resolving it with precedence

The ambiguity, as the parser sees it (Dragon §4.8.1). Sitting on a complete if with else as lookahead, the parser can reduce or shift, and one token of lookahead does not separate them — a shift/reduce conflict. Bison always prefers shift, which happens to be correct here. Leaving it as a warning means relying on a default; declaring the precedence means choosing.

Dragon §4.8 argues for the other route: keep the short ambiguous grammar and disambiguate with precedence. The two declarations say that the rule without else has lower precedence than the ELSE token, so when they compete the token wins and the parser shifts:

%nonassoc LOWER_THAN_ELSE     /* declared first  → lower precedence */
%nonassoc ELSE                /* declared later  → higher          */

if_stmt : 'if' '(' expr ')' stmt %prec LOWER_THAN_ELSE
        | 'if' '(' expr ')' stmt 'else' stmt
        ;

The order of those two lines is the entire answer

Precedence in bison is positional: each successive declaration binds tighter than the one above it. Swap the two lines and ELSE becomes the weaker one, the parser reduces instead of shifting, and every else attaches to the outer if. The program still compiles; it simply means something different. This is worth doing once, deliberately, to see it happen.

Bison would have shifted anyway — shift is its default for a shift/reduce conflict. The value of declaring it is not that it changes the outcome; it is that the conflict disappears from the warnings, so the next conflict is visible. A grammar with unexplained conflicts is a grammar nobody is reading.

Bison reports one shift/reduce conflict on your if-statement rules and produces a working parser. What should you do?

2Lowering conditionals

Lowering a conditional (Dragon §6.6.3). If you built loops in Topic 4 you have already written every mechanism this needs. The one instruction worth staring at is goto after at the end of the then-branch: without it, control falls out of the then-branch straight into the else-branch and both run — a bug invisible to any test whose condition is false.

Dragon §6.6.3 gives these schemes as syntax-directed definitions with inherited attributes for the true and false targets. If you built loops in Topic 4 you have already written every mechanism this needs — which is the payoff for having done that carefully.

Nesting needs no special handling, provided the label generator never repeats a name. Each nested if simply generates its own pair, and the recursion in the generator does the rest.

3Boolean expressions, and a decision you may be making by accident

Dragon §6.6 distinguishes two ways of translating boolean expressions, and the distinction is not stylistic.

Numerically, a boolean expression computes a value — 1 or 0 — which is then tested. By flow of control, it is translated into a position in the code: there is no value at all, only a jump to the true target or the false target. The second is what makes short-circuiting natural.

Two ways to compile A && B (Dragon §6.6.1–6.6.4). Short-circuiting produces more instructions in the listing and fewer executed whenever A is false. It stops being an optimization and becomes part of the language's meaning the moment an operand can have a side effect — n != 0 && divide(x, n) is correct under one rule and a division by zero under the other.

Ours is numeric and therefore eager: both operands are always evaluated. That is a defensible choice for a language whose expressions have no side effects, and ours very nearly qualifies — there is no assignment operator and no ++. But expressions can contain function calls, and a function call can print, so the difference is observable and should be documented rather than discovered.

MIPS and and or are bitwise

2 & 1 is 0, but in C 2 && 1 is 1. Emitting the bitwise instruction directly gives the wrong answer for every value that is truthy but not exactly 1. Each operand must first be normalized to 0 or 1 — sne $t, $x, $zero — and only then combined. !x is simply seq $d, $x, $zero. This is the single most common bug in this milestone, and print(2 && 1); is the test that catches it.

4Backpatching

Dragon §6.7 addresses a problem we have arranged not to have, and it is worth understanding why we do not have it.

Backpatching (Dragon §6.7). A one-pass compiler must emit a jump before it knows where the jump goes. The fix is to leave the target blank, remember the instruction on a list carried as a synthesized attribute, and fill it in later. We do not need this — our multi-pass design lets us generate labels first and place them afterward — but it is the classic technique, and knowing why we can avoid it is a good answer to 'why is your compiler multi-pass?'

A one-pass compiler generating code as it parses must emit a conditional jump before it knows the address of the target — the target is further along in the input. Backpatching leaves the field blank, carries a list of such instructions as a synthesized attribute, and fills them all in when the label is finally placed. makelist, merge and backpatch are the three operations, and they are elegant.

Our compiler generates symbolic labels into a TAC list and resolves them later, so the problem never arises. That is a direct consequence of being multi-pass, and it is a good concrete answer to 'what does multi-pass buy you?'

5Switch statements

Dragon §6.8 treats switch as a code-generation problem rather than a parsing one, because the interesting decision is how to dispatch.

Three ways to compile a switch (Dragon §6.8). Which is best depends entirely on the case values: dense and few favors the table, sparse and many favors binary search, and a handful of cases makes the linear chain unbeatable for simplicity. Production compilers choose per switch, and often build a hybrid. We implement the chain — correct for every distribution, and twenty lines.

Case values	Best implementation	Why
1, 2, 3	either — but the chain is simpler	three comparisons is nothing
1, 1000, 50000	binary search, or a chain	a jump table would need 50,000 words for three cases
1 … 200, dense	jump table	one indexed jump instead of up to 200 comparisons
200 values over 0 … 2,000,000	binary search	O(log n) comparisons, O(n) space

A production compiler chooses per switch, and frequently builds a hybrid: a jump table for a dense cluster and comparisons for the outliers. Being able to explain the trade-off is worth more here than implementing the table, which is why the assignment asks for the analysis and makes the table optional.

Fall-through, and why it costs nothing

Why fall-through is free. The case bodies are laid out consecutively with no jump between them, so running off the end of one body simply enters the next. Fall-through is not a mechanism the compiler implements — it is what happens when break is absent. That is also why break in a switch is the same GOTO-to-the-exit-label that it is in a loop, taken from the same stack.

Laying out the dispatch and the bodies as two separate sections is what makes fall-through free. It also explains why break inside a switch leaves the switch rather than an enclosing loop: the switch pushed its exit label more recently, and the label stack is last-in-first-out.

Two checks a switch makes possible

Duplicate case values, and more than one default. Neither can be a grammar rule — the grammar for a case clause is satisfied however many times it appears with whatever value — so both belong in the semantic analyzer. They are cheap to implement and genuinely useful, which makes them a good demonstration of what phase 3 is for.

6Code generation, revisited

With the language complete, the back end is worth looking at as a whole. Dragon §8.1 named three problems in Topic 2; here is what a compiler actually does about the hardest of them.

Register allocation

Dragon §8.8 is blunt: optimal register allocation is NP-complete, even under simplifying assumptions. Every compiler therefore uses a heuristic, and the standard family of heuristics is graph coloring. Build an interference graph with one node per value and an edge between values simultaneously live; coloring it with k colors is exactly assigning k registers without two live values sharing one. Values that cannot be colored are spilled to memory.

Ours does something much simpler: registers are a write-back cache over memory homes, with least-recently-used eviction. It needs no liveness information, which is why it works without a flow graph — and it is also why it flushes everything at every branch. The upgrade path is the same one Topic 4 pointed at: build the flow graph, compute liveness, and a real allocator becomes possible.

The cost of not having liveness

Look at your generated assembly around a loop. Every branch is preceded by stores and followed by loads, because the allocator does not know which values are still needed. A liveness analysis would eliminate most of them. That is a concrete, measurable improvement you can quantify with the tools from Topic 4, and it makes an excellent Project 6 extension.

7Retargeting: MIPS and ARM

The Topic 5 objective asks you to compare code generation for the two architectures. The comparison worth making is not a table of mnemonics.

MIPS versus ARM. A mnemonic table is the least interesting part of the comparison. What matters for a compiler is the model: comparison into a register versus comparison into flags changes how conditions are lowered, and predication changes whether a branch is needed at all.

Two architectural differences actually matter to a compiler writer:

Comparison result versus condition flags. MIPS slt puts 0 or 1 in a register, which a later beq tests. ARM cmp sets flags that a following conditional branch reads. Our IR produces a value, which suits MIPS directly; an ARM back end would prefer the flow-of-control translation of booleans from §3, because it never materializes the value at all.
Predication. On A32 most instructions can carry a condition, so if (a > 0) x = 1; compiles to cmp plus movgt with no branch. Exploiting that is not a transliteration — it needs an if-conversion pass deciding when a branch is worth replacing. That is a genuine architectural difference, not a naming one.

What retargeting to ARM would actually cost. This list is the honest answer to the objective 'compare code generation for MIPS versus ARM'. Only the back end changes, and within it mostly the mnemonic table, the branch cases and the prologue/epilogue. The reason is the IR boundary from Topic 1 §3, and this is the return on that investment.

This is the return on the decision made in Topic 1 §3. The front end, the semantic analyzer, the IR and the optimizer are all target-independent because the intermediate representation was placed between them and the machine. Being able to produce this file-by-file list — and explain why it looks the way it does — is the best single answer you can give about your compiler's architecture.

Which part of your compiler would need the most change to target ARM instead of MIPS?

8The approach for this milestone

Build the conflict before you fix it

Write the two if rules with no precedence declarations, run bison -v, and read the conflicted state in parser.output. Fifteen minutes, and the dangling else stops being a story and becomes something you have seen the parser do.

Write the discriminating test first

if (a) if (b) X else Y with all four combinations of a and b. It is the only test that distinguishes the two readings, and it is the test that proves your resolution rather than assuming it.

Test `2 && 1` the moment logical operators compile

It must print 1. If it prints 0 you have emitted a bitwise instruction on unnormalized operands, and every truthy-but-not-1 value in your language is wrong.

Lower switch on paper before coding it

The dispatch-then-bodies layout is what makes fall-through free. Draw it once and the implementation follows; start coding without it and you will find yourself trying to make fall-through happen, which is the wrong problem.

Do the retargeting analysis as an exercise, not a survey

Take one real function from your own compiler, hand-translate it, and mark every file as unchanged, edited or rewritten. The file-by-file list is the deliverable; the mnemonic table is the least interesting part.

9Self-check

Why must %nonassoc LOWER_THAN_ELSE come BEFORE %nonassoc ELSE?

Why does laying out case bodies consecutively make fall-through free?

print(2 && 1); prints 0. What went wrong?

Your compiler does not need backpatching. Why not?

A switch has cases 1, 5000 and 90000. Which dispatch strategy, and why?

10References

Aho, Lam, Sethi & Ullman, 2nd ed. — §4.3.2 (ambiguity; the dangling else, Fig. 4.9, and the matched/unmatched grammar), §4.8 (using ambiguous grammars, and why precedence declarations are preferable); §6.6 (boolean expressions, numerical versus flow-of-control translation, short-circuit code, flow-of-control statements), §6.7 (backpatching: makelist, merge, backpatch), §6.8 (switch-statements and the three dispatch strategies); §8.6 (a simple code generator), §8.8 (register allocation and assignment, interference graphs, spilling).
Patterson & Hennessy, Computer Organization and Design — the MIPS instruction set; the ARM edition covers the same material for A32.
ARM Architecture Reference Manual, on conditional execution and the condition flags.