P-I · VI. Compiler Construction

CSS Computer Science (Optional) — Paper-I, Section-B, Topic VI. Index for Compiler Construction — each subtopic has its own page below.

---

✅ Self-Test Questions (with Answers)

Q1. List the six phases of a compiler in correct order.

Ans: (1) Lexical analysis — source characters → tokens; (2) Syntax analysis (parsing) — tokens → parse/syntax tree, checks grammar; (3) Semantic analysis — type checking, scope and declaration checks, builds the annotated tree; (4) Intermediate code generation — machine-independent form (e.g., three-address code); (5) Code optimization — improve speed/space without changing meaning; (6) Code generation — target machine/assembly code with register allocation. The symbol table and error handler interact with every phase. Phases 1–3 form the analysis (front end), 4–6 the synthesis (back end).

Q2. Distinguish LL(k) and LR(k) parsers by their parsing direction/strategy.

Ans: LL(k) — scans input Left to right, produces a Leftmost derivation, with k lookahead tokens; it is top-down (predictive), building the tree from the root down, and needs grammars free of left recursion and ambiguity (usually after left factoring). LR(k) — scans Left to right, produces a Rightmost derivation in reverse, with k lookahead; it is bottom-up (shift-reduce), building from the leaves up, and accepts a strictly larger class of grammars, including left-recursive ones. Every LL(k) grammar is LR(k), but not the reverse.

Q3. What is the difference between synthesized and inherited attributes?

Ans: A synthesized attribute at a node is computed from its children (information flows bottom-up) — e.g., the value of an expression node from its operands; a grammar using only these is S-attributed and can be evaluated during bottom-up parsing. An inherited attribute is computed from the node's parent and/or siblings (information flows top-down/left-to-right) — e.g., passing a declared type down a list of identifiers; grammars combining both in a left-to-right evaluable way are L-attributed.

Q4. Why is intermediate code generation useful for building compilers that target multiple machines?

Ans: Intermediate code is machine-independent, so the compiler splits into a front end (language-specific) and a back end (machine-specific). For m languages and n machines you then need only m + n components instead of m × n separate compilers. It also allows machine-independent optimization to be done once, makes retargeting to a new processor cheap (write one new back end), and simplifies the compiler's design (as with the UNCOL idea, LLVM IR or Java bytecode).

Q5. Give one example each of a loop optimization and a peephole optimization.

Ans: Loop optimization — loop-invariant code motion: moving a computation whose operands never change inside the loop (e.g., x = a * b;) out to just before the loop; other examples are strength reduction (replacing i * 8 with repeated addition), loop unrolling and induction-variable elimination. Peephole optimization — examining a small window of target instructions and replacing it with a cheaper equivalent: e.g., deleting a redundant STORE R1, x immediately followed by LOAD x, R1; others are constant folding, algebraic simplification (x * 1 → x), eliminating jumps to jumps, and using machine idioms (INC instead of ADD 1).