Skip to content
CampusPrep
AD-604 (C) · Compiler Design/Quick Revision Short Notes

Compiler Design (AD-604 (C)) - Unit 3 Short Notes

How unit 3 is examined

This unit covers type systems and type checking, polymorphism, and run-time storage management; the marks sit in polymorphic functions (8 marks) and dynamic allocation strategies (6 marks), both from May 2024.

Type checking: type system, simple type checker, type equivalence

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A type system is a collection of rules that assigns a type to every language construct, and a type checker is the compiler component that verifies these rules so that operators are applied only to operands of compatible types.</mark>

Key points.

  1. A type expression describes the type of a construct: a basic type (integer, real, char, boolean, type_error), a type name, or one built with constructors such as array, product, record, pointer and function ($s \to t$).
  2. A simple type checker is a syntax-directed definition in which each expression production computes a type attribute and each statement production checks it, for example $E \to E_1 + E_2$ has E.type = if E1.type = integer and E2.type = integer then integer else type_error.
  3. For a statement such as if E then S, the checker requires E.type = boolean, and for an array access $E_1[E_2]$ it requires $E_2$ to be integer and $E_1$ to be an array, giving the element type.
  4. For a function call $E_1(E_2)$, the checker requires $E_1$ to have type $s \to t$ and $E_2$ to have type $s$, and the result type is $t$.
  5. Static checking is done at compile time and catches errors early, while dynamic checking is done at run time (array bounds, null pointers) and costs execution time.
  6. Structural equivalence treats two types as the same if they are built from the same constructors over equivalent types, whereas name equivalence treats them as the same only if they carry the same type name.
  7. A sound type system is called strongly typed when the compiler guarantees that no type error can occur at run time.

Example. For int a; float b; a = b + 1; the checker types b + 1 as real, and assigning real to integer is reported as a type error unless a conversion is allowed.

Answer frame. Open with the definition of type system and type checker; then develop type expressions, the syntax-directed rules with one rule written out, static versus dynamic checking, and the two kinds of equivalence; close with the point that the checker also inserts conversions.

Type conversion, overloading and polymorphic functions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Polymorphism is the ability of a function, operator or type to work on values of more than one type; a polymorphic function is one whose argument types are not fixed to a single type.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 462 194" width="462" height="194" role="img" aria-label="Kinds of polymorphism"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="195.1" y1="37" x2="63" y2="101"/><line class="e" x1="195.1" y1="37" x2="165.5" y2="101"/><line class="e" x1="195.1" y1="37" x2="327.3" y2="101"/><line class="e" x1="327.3" y1="101" x2="272" y2="165"/><line class="e" x1="327.3" y1="101" x2="382.5" y2="165"/><rect class="n" x="138.1" y="22" width="114" height="30" rx="8"/><text class="t" x="195.1" y="37" dy=".35em" text-anchor="middle">Polymorphism</text><rect class="n" x="14" y="86" width="98" height="30" rx="8"/><text class="t" x="63" y="101" dy=".35em" text-anchor="middle">Parametric</text><rect class="n" x="128" y="86" width="75" height="30" rx="8"/><text class="t" x="165.5" y="101" dy=".35em" text-anchor="middle">Subtype</text><rect class="n" x="293.8" y="86" width="67" height="30" rx="8"/><text class="t" x="327.3" y="101" dy=".35em" text-anchor="middle">Ad-hoc</text><rect class="n" x="219" y="150" width="106" height="30" rx="8"/><text class="t" x="272" y="165" dy=".35em" text-anchor="middle">Overloading</text><rect class="n" x="341" y="150" width="83" height="30" rx="8"/><text class="t" x="382.5" y="165" dy=".35em" text-anchor="middle">Coercion</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Kinds of polymorphism</figcaption></figure>

Key points.

  1. Parametric polymorphism uses a type variable, so one definition works uniformly for every type, as in $length : list(\alpha) \to integer$, which counts the elements of a list of any type, or C++ template<class T> T max(T a, T b).
  2. In a polymorphic function the type checker treats $\alpha$ as a placeholder, and at each call it unifies $\alpha$ with the actual argument type, so max(3, 5) instantiates $T$ as int and max(2.5, 1.0) as double.
  3. Subtype (inclusion) polymorphism lets an object of a subclass be used wherever its base class is expected, so a Circle or Square can be passed to a function taking a Shape, and the overridden method is chosen at run time.
  4. Ad-hoc polymorphism means overloading, where one name denotes different code for different argument types, for example + adds integers and concatenates strings, and area(int r) and area(int l, int b) coexist.
  5. The compiler resolves an overloaded name by looking at the argument types, so the set of possible types of the identifier is narrowed to one during type checking.
  6. Type conversion changes a value from one type to another and is either implicit (coercion, the compiler widens int to real in 2 + 3.5) or explicit (a cast, (int) x).
  7. Widening (int to float) is safe, while narrowing (float to int) can lose information, so the checker inserts an inttoreal node only for widening.

Example.

int   add(int a, int b)       { return a + b; }
float add(float a, float b)   { return a + b; }
// add(2, 3) -> first version; add(2.5f, 1.5f) -> second version (overloading)

Answer frame. Open by defining polymorphism as one name with many types; draw the classification tree; then develop parametric, subtype and ad-hoc polymorphism each with one example; add coercion and the use in type checking; close with the line that type checking resolves overloads and unifies type variables.

Asked: [8 marks] (May 2024) Explain different polymorphic functions with example.

Run time environment: storage organization, allocation strategies, parameter passing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>The run-time environment is the arrangement of memory and the mechanisms, such as activation records and calling sequences, by which the target program manages procedures, storage and parameters while it runs.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 80 338" width="80" height="338" role="img" aria-label="Run-time memory from low to high address: C = Code, S = Static data, H = Heap (grows down), K = Stack (grows up)"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M40,59 L40,105" marker-end="url(#ah6)"/><path class="e" d="M40,145 L40,191" marker-end="url(#ah6)"/><path class="e" d="M40,231 L40,277" marker-end="url(#ah6)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">H</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">K</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Run-time memory from low to high address: C = Code, S = Static data, H = Heap (grows down), K = Stack (grows up)</figcaption></figure>

Key points.

  1. The code area holds the fixed-size executable target code, and static data holds global and static variables whose size is known at compile time.
  2. The stack holds activation records of procedure calls and grows and shrinks with calls and returns, while the heap holds dynamically allocated data, and the two grow towards each other.
  3. An activation record holds the return value, actual parameters, control link, access link, saved machine status, local data and temporaries.
  4. Static allocation fixes all addresses at compile time and cannot support recursion; stack allocation creates a record per call and supports recursion; heap allocation gives memory on request with lifetime outliving the call.
  5. In call by value the actual value is copied to the formal parameter, so changes do not affect the caller.
  6. In call by reference the address is passed, so changes to the formal parameter change the caller's variable.
  7. In copy-restore the value is copied in and the final value is copied back on return, and in call by name the argument is textually substituted for the parameter at each use.

Answer frame. Open with the definition and draw the memory layout; then develop the storage areas, activation record fields, the three allocation strategies and the four parameter passing methods; close with the point that stack allocation makes recursion possible.

Dynamic storage allocation, symbol table, error detection and recovery

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Dynamic storage allocation is the assignment of memory at run time, using the stack for procedure activations and the heap for data whose size or lifetime is unknown at compile time.</mark>

Key points.

  1. Stack allocation pushes an activation record when a procedure is called and pops it on return, so local variables exist only during the call and recursion works because each call has its own record.
  2. The activation record contains return address, parameters, locals, temporaries, control link (caller's record) and access link (non-local data), and the stack pointer marks its top.
  3. Heap allocation gives a block on request (malloc, new) and the block stays until it is freed, so data can outlive the procedure that created it, but requests are slower and free memory can fragment.
  4. Garbage collection automatically finds heap blocks that are no longer reachable and reclaims them, using methods such as reference counting, mark-and-sweep and copying collection; explicit freeing risks dangling pointers and leaks.
  5. Static allocation is fixed at compile time with no recursion and no run-time cost, stack allocation is automatic and fast with last-in first-out lifetime, and heap allocation is the most flexible but slowest.
  6. The symbol table is a data structure that stores each identifier's name, type, scope and address, and is searched and updated by all phases, typically as a hash table.
  7. Error detection finds lexical, syntactic, semantic and logical errors, and recovery strategies are panic mode (skip to a synchronising token), phrase-level (local correction), error productions and global correction.
Feature Static Stack Heap
When allocated Compile time On procedure call On explicit request
Recursion Not supported Supported Not applicable
Lifetime Whole program Until return Until freed or collected
Speed Fastest Fast Slower
Fragmentation None None Possible

Answer frame. Open by defining dynamic storage allocation and activation record; draw the activation record and memory layout; then develop stack allocation, heap allocation with garbage collection, and close with the static, stack and heap comparison table.

Asked: [6 marks] (May 2024) Explain different dynamic allocation strategies.

Last-minute revision

  • A type system assigns a type to every expression; the type checker enforces the rules.
  • Function type is written $s \to t$; the call $E_1(E_2)$ needs $E_2$ of type $s$.
  • Structural equivalence compares structure; name equivalence compares names.
  • Static checking is at compile time; dynamic checking is at run time.
  • Polymorphism has three kinds: parametric, subtype and ad-hoc (overloading).
  • Coercion is implicit conversion (widening int to real); a cast is explicit.
  • Run-time memory has code, static data, heap and stack; heap and stack grow towards each other.
  • An activation record holds return address, parameters, locals, temporaries and links.
  • Parameter passing methods are value, reference, copy-restore and name.
  • Garbage collection reclaims unreachable heap blocks (reference counting, mark-and-sweep).
  • Error recovery: panic mode, phrase-level, error productions, global correction.

Memory hooks

  • Polymorphism kinds: "PSA" = Parametric, Subtype, Ad-hoc.
  • Memory layout: "Code, Static, Heap, Stack", the last two grow towards each other.
  • Parameters: "VRCN" = Value, Reference, Copy-restore, Name.
  • Static is fixed, Stack is scoped, Heap is asked for.

Coverage checklist

  • Type checking: type system, specification of simple type checker, equivalence of expression, types: no past questions.
  • type conversion, overloading of functions and operations, polymorphic functions: May 2024 polymorphic functions (8 marks).
  • Run time Environment: storage organization, Storage allocation strategies, parameter passing: no past questions.
  • dynamic storage allocation, Symbol table, Error Detection & Recovery, Ad-Hoc and Systematic Methods: May 2024 dynamic allocation strategies (6 marks).
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in