Q4Compiler Design
Question
(a) Explain Type Checking. (b) Discuss Backpatching with an example. (c) Explain how boolean expressions are translated.
Answer
Type Checking enforces type safety rules; Backpatching resolves forward references in jump instructions during code generation; Boolean expression translation generates conditional jump code for if-then-else and loops.
Type checking is the process of verifying that each operation in the program receives operands of the correct type, either at compile time (static type checking) or at runtime (dynamic type checking). The type checker traverses the annotated parse tree and assigns types to expressions based on the types of their operands.
- Type Expressions: Types are represented as type expressions. Basic types: int, float, char, bool. Constructed types: arrays (array(10, int)), functions (int→float), pointers (pointer(int)), records.
- Type Equivalence: Structural equivalence — two types are equivalent if they have the same structure. Name equivalence — two types are equivalent only if they are the same named type.
- Coercions: Implicit type conversions. E.g., int + float → the int is coerced to float. Explicit coercions are type casts.
- Overloading: Same operator/function with different type signatures — type checking resolves which version to use.
- Example: For E1 + E2, if type(E1) = type(E2) = int, then type(E1+E2) = int. If one is float, coerce int to float and result is float.
Backpatching is a technique to handle forward references in jump instructions during one-pass intermediate code generation. When a jump instruction is generated, the target label (jump destination) may not yet be known. Backpatching keeps a list of incomplete jump instructions and fills in (patches) the target addresses when they become known.
- makelist(i): Creates a new list containing the single instruction number i (where i has an unfilled jump target).
- merge(p1, p2): Returns a new list containing instructions in both p1 and p2.
- backpatch(p, i): Fills in instruction number i as the target of all jump instructions in list p.
- 100: if a < b goto _ [makelist(100)] → truelist = {100}
- 101: goto _ [makelist(101)] → falselist = {101}
- Backpatch(truelist, 102): 100: if a < b goto 102
- 102: x = 1
- 103: goto _ [list to patch later with S.nextlist]
- Backpatch(falselist, 104): 101: goto 104
- 104: x = 2
Boolean expressions in control structures (if, while, for) are translated using the 'jumping code' method: instead of computing a boolean value, the compiler generates code that jumps to different targets based on the truth value.
- For E → E1 || E2: If E1 is true, the whole expression is true (short-circuit). Backpatch(E1.falselist, E2.firstinstr). E.truelist = merge(E1.truelist, E2.truelist). E.falselist = E2.falselist.
- For E → E1 && E2: If E1 is false, the whole expression is false. Backpatch(E1.truelist, E2.firstinstr). E.truelist = E2.truelist. E.falselist = merge(E1.falselist, E2.falselist).
- For E → !E1: E.truelist = E1.falselist; E.falselist = E1.truelist.
- For E → a relop b: Generate: if a relop b goto _; goto _. E.truelist = makelist(first goto); E.falselist = makelist(second goto).