Compiler Design

Define a compiler.

A compiler is a program that translates an entire source program written in a high-level language into an equivalent target program (machine code/object code) before execution.

Define an interpreter.

An interpreter is a program that translates and executes a source program line by line without producing a separate object file.

What is a cross-compiler? [2023]

A cross-compiler runs on one machine (host) but generates machine code for a different machine (target).

What is a symbol table?

A symbol table is a data structure used by the compiler to store information about identifiers (names, types, scope, memory locations) encountered during compilation.

What is a preprocessor?

A preprocessor is a program that processes directives (macros, #include, #define) in the source code before passing it to the compiler.

What is a pass in a compiler?

A pass is one complete scan of the source program. A single-pass compiler processes the source in one scan; a multi-pass compiler uses multiple scans with intermediate files.

Compare compiler and interpreter with at least five points. [2023]

Explain the phases of a compiler with a neat diagram. [2023]

A compiler consists of two main parts: Analysis Phase and Synthesis Phase.

Analysis Phases:

• Lexical Analysis: Reads source characters, groups them into tokens (identifiers, keywords, operators). Output: token stream.
• Syntax Analysis (Parsing): Checks token stream against grammar rules, builds a parse tree (CST). Output: parse tree.
• Semantic Analysis: Checks semantic correctness (type checking, scope rules). Output: annotated parse tree.

Synthesis Phases:

• Intermediate Code Generation: Produces a platform-independent representation (Three-Address Code).
• Code Optimization: Improves intermediate code for speed/size (constant folding, loop optimization).
• Code Generation: Translates optimized IR into target machine code, handles register allocation.

Supporting Components: Symbol Table Management (stores identifier info) and Error Handler (reports errors from each phase).

What is a bootstrapper? Explain single-pass vs multi-pass compilers. [2022]

A bootstrapper (or bootstrap compiler) is a compiler written in its own source language. Initially, a compiler is written in another language; once it can compile itself, it is called self-hosting.

Single-pass compiler: Reads the source once and performs all phases. Advantages: fast, uses less memory. Disadvantage: limited optimization, cannot handle forward references easily.

Multi-pass compiler: Makes multiple passes over the source or intermediate representations. Advantages: better optimization, handles forward declarations. Disadvantage: slower, requires intermediate storage.

Explain the role of error handling in a compiler. [2021]

Error handling detects, reports, and recovers from errors in each phase:

• Lexical phase: Reports invalid characters (e.g., $ in a C identifier).
• Syntax phase: Reports syntax errors (missing semicolon, mismatched braces). Recovery strategies: panic-mode (skip tokens until synchronizing token), phrase-level (correct token), error production.
• Semantic phase: Reports type mismatches, undeclared variables, wrong number of arguments.
• Intermediate/Code generation: Reports overflow, unreachable code.

A good error handler: (1) detects each error accurately, (2) reports with location and nature, (3) recovers to continue compilation, (4) does not cascade errors.

Draw and explain the complete structure of a compiler. Discuss the role and function of each phase. [2023]

  SOURCE PROGRAM (.c, .java, .py)
       │
       ▼
  ┌─────────────┐
  │  PREPROCESS │  ← Handles #include, #define, macros
  └──────┬──────┘
         │ Preprocessed source
         ▼
  ┌─────────────┐
  │   LEXICAL   │  ← Tokenization (scanner/lexer)
  │  ANALYZER   │  ← Removes whitespace/comments, produces tokens
  └──────┬──────┘
         │ Token stream
         ▼
  ┌─────────────┐
  │   SYNTAX    │  ← Parsing (checks grammar rules)
  │  ANALYZER   │  ← Builds Parse Tree / CST
  └──────┬──────┘
         │ Parse Tree
         ▼
  ┌─────────────┐
  │   SEMANTIC  │  ← Type checking, scope validation
  │  ANALYZER   │  ← Annotated Parse Tree (AST)
  └──────┬──────┘
         │ AST
         ▼
  ┌─────────────┐
  │INTERMEDIATE │  ← Three-Address Code (TAC)
  │CODE GENER.  │  ← Platform-independent representation
  └──────┬──────┘
         │ IR
         ▼
  ┌─────────────┐
  │   CODE      │  ← Constant folding, DAG, loop unrolling
  │  OPTIMIZER  │  ← Improves speed/size
  └──────┬──────┘
         │ Optimized IR
         ▼
  ┌─────────────┐
  │   CODE      │  ← Register allocation, instruction selection
  │ GENERATOR   │  ← Target machine code
  └──────┬──────┘
         │
         ▼
  TARGET PROGRAM (.o, .exe, .class)
          

Symbol Table Management and Error Handling run alongside all phases.

Detailed explanation:

• Lexical Analyzer: Reads characters from source, forms the longest possible lexemes matching token patterns, outputs tokens of the form <type, value>. Example: "int" → <KEYWORD, "int">.
• Syntax Analyzer: Groups tokens into grammatical phrases. Uses a grammar (CFG). Builds a Concrete Syntax Tree (CST) or Abstract Syntax Tree (AST). Detects syntax errors.
• Semantic Analyzer: Ensures the program makes sense. Performs type checking, verifies all identifiers are declared, checks function argument counts/types.
• Intermediate Code Generator: Produces an intermediate representation like Three-Address Code (TAC). E.g., t1 = a + b.
• Optimizer: Applies transformations to improve the IR — constant propagation, dead code elimination, loop optimization.
• Code Generator: Maps optimized IR to target machine instructions, assigns registers, generates relocatable machine code.

Distinguish between compiler, interpreter and assembler. Explain why we need compilation at all. [2022]

Compiler, Interpreter, and Assembler — Detailed Comparison:

Why we need compilation: Computers only understand machine code (binary 0s and 1s). Writing programs directly in machine code is nearly impossible for complex software. High-level languages (C, Java, Python) are human-readable. The compiler bridges this gap by translating human-readable code into machine-executable instructions, performing critical checks (syntax, semantics), optimizing for performance, and enabling portability across platforms.

Advantages of using compilers: (1) Efficiency — compiled code runs faster. (2) Error detection — catches many errors before execution. (3) Optimization — improves code quality. (4) Portability — same source compiles on different machines.

What is a token? Give examples.

A token is a pair <token-name, attribute-value> representing a logical unit. Examples: <ID, pointer>, <NUM, 42>, <IF, –>, <PLUS, +>.

Differentiate lexeme and pattern.

A pattern is the rule that describes a set of lexemes (e.g., "identifier" pattern). A lexeme is a specific character sequence that matches a pattern (e.g., "count" is a lexeme matching the identifier pattern).

What is input buffering in a lexical analyzer? [2023]

Input buffering reads source characters in large blocks (buffers) to reduce I/O operations. Uses two halves with a sentinel character at the end of each half to avoid boundary checks.

What is a sentinel in input buffering?

A sentinel is a special character (e.g., NUL or EOF) placed at the end of each buffer half. It signals the end of the buffer without requiring an explicit boundary check on every character read.

What is lexeme specification?

Lexeme specification defines the rules for what constitutes a valid token. It is described using regular expressions. Lexeme recognition is the process of matching the input against these specifications.

Give one example of a regular expression for an identifier.

letter (letter | digit)* — starts with a letter, followed by any number of letters or digits.

What is the Lex tool? [2022]

Lex (or Flex) is a lexical analyzer generator that takes regular expression specifications and produces C code for a lexical analyzer function (yylex).

What is a DFA?

A DFA (Deterministic Finite Automaton) is a finite state machine where for every state and input symbol, there is exactly one next state. No ε-transitions allowed.

Explain the role of a lexical analyzer. What are token, pattern, and lexeme? [2023]

Role of Lexical Analyzer: The lexical analyzer (scanner) is the first phase of compilation. It reads source characters, groups them into tokens, removes whitespace and comments, and reports lexical errors (invalid characters). It acts as an interface between the source program and the parser.

Token: A pair <token-name, attribute-value> representing a class of lexemes. Token names are used by the parser.

Pattern: A rule describing the form of lexemes for a token, described by a regular expression. E.g., pattern for keyword "if".

Lexeme: A specific character sequence (instance) matching a token's pattern. E.g., "while" is a lexeme for the WHILE token.

Example: For the statement pos = init + rate * 60:

• <ID, "pos"> — lexeme "pos" matches pattern for identifier
• <ASSIGN, "=">
• <ID, "init">
• <PLUS, "+">
• <ID, "rate">
• <MUL, "*">
• <NUM, 60>

Explain input buffering technique with sentinels. [2021]

Input buffering reads source code in large blocks to reduce I/O overhead. The buffer is divided into two N-sized halves. Two pointers are maintained:

• lexemeBegin: Marks the start of the current lexeme.
• forward: Scans ahead to find the end of the lexeme.

A sentinel (special character like NUL, ASCII 0) is placed at the end of each half. When forward reaches the sentinel, a new block is loaded instead of checking boundary on every character.

  ┌─────── Buffer Half 1 ───────┐  ┌─────── Buffer Half 2 ───────┐
  │ c  h  a  r  1  ...  N/2-1   │  │ c  h  a  r  N/2  ...  N-1  │
  │                            │  │                            │
  ↑                            │  ↑                            │
  lexemeBegin                  │  sentinel                    sentinel
                               ↑  │                            │
                               forward                          │
  └────────────────────────────┘  └────────────────────────────┘
          

What are regular expressions? List the RE operators with precedence. [2022]

Regular Expressions (RE) are algebraic notations used to describe patterns of strings (languages). They are built from:

• Union (|): r | s means strings matching r or s. Lowest precedence.
• Concatenation: rs means r followed by s. Medium precedence.
• Kleene Closure (*): r* means zero or more occurrences of r. Highest precedence.
• Positive Closure (+): r+ means one or more occurrences of r.
• Optional (?): r? means zero or one occurrence of r.

Precedence: * > concatenation > |

Example: RE for unsigned integer: digit+ where digit = (0|1|2|3|4|5|6|7|8|9)

RE for real number: digit+ (. digit+)? which matches: 42, 3.14, 0.5

Differentiate NFA and DFA with a comparison table. [2021]

What is a Context-Free Grammar (CFG)?

A CFG is a 4-tuple G = (V, T, P, S) where V is the set of variables/non-terminals, T is the set of terminals, P is the set of productions, and S ∈ V is the start symbol.

What is an ambiguous grammar? [2023]

A grammar is ambiguous if there exists at least one string that has two or more distinct parse trees (or leftmost derivations).

What is left recursion? Why is it a problem? [2022]

Left recursion occurs when a non-terminal A derives itself as the first symbol: A → A α. It causes infinite loops in top-down parsers because the parser keeps expanding A without consuming input.

What is left factoring?

Left factoring removes common prefixes from productions. E.g., A → αβ₁ | αβ₂ becomes A → αA' ; A' → β₁ | β₂. Used to make grammar suitable for predictive parsing.

Define FIRST and FOLLOW sets.

FIRST(X) = set of terminals that can begin strings derived from X. FOLLOW(A) = set of terminals that can immediately follow A in some derivation. $ ∈ FOLLOW(start symbol).

What is a shift-reduce parser?

A bottom-up parser that repeatedly shifts input symbols onto a stack and reduces handle substrings (matching RHS of a production) back to the LHS non-terminal.

What is an LR parser?

An LR parser is a shift-reduce parser that uses LR(k) items (productions with a dot and k lookahead tokens) to construct parsing tables and decides when to shift/reduce based on those tables.

What is recursive descent parsing? Explain with an example. [2023]

Recursive Descent Parsing is a top-down parsing technique where each non-terminal in the grammar has a corresponding recursive procedure. The parser tries to match the input by calling these procedures recursively.

Grammar: E → T E' ; E' → + T E' | ε ; T → int

Procedures:

void E()  { T(); E_prime(); }
void E_prime() {
  if (lookahead == '+') { match('+'); T(); E_prime(); }
  // else ε-production — return
}
void T() { match(INT); }  // INT is a terminal token
          

For input "int + int": E() calls T() which matches "int", then E_prime() sees '+' so it matches '+' and calls T() again matching "int". Parsing succeeds.

Limitation: Fails on left-recursive grammars and requires left-factored grammar for predictive parsing.

Construct an LL(1) parsing table for the grammar: E → T E', E' → + T E' | ε, T → int. Show FIRST and FOLLOW sets. [2023]

Grammar:

E  → T E'
E' → + T E' | ε
T  → int
          

FIRST sets:

• FIRST(E) = {int}
• FIRST(E') = {+, ε}
• FIRST(T) = {int}

FOLLOW sets:

• FOLLOW(E) = {$}
• FOLLOW(E') = {+, $}
• FOLLOW(T) = {+, $}

LL(1) Parsing Table:

No conflicts → Grammar is LL(1).

Eliminate left recursion and left factor the grammar: S → S a | b S b | b. [2022]

Step 1: Eliminate Left Recursion

Original: S → S a | b S b | b

S → b S b | b | S a

Group: S → α₁ | α₂ | β (where α = Sa, β = bSb | b)

S → β S' ; S' → α S' | ε

S → b S b | b | S' (where S' handles recursion)

S → b S b S' | b S'

S' → a S' | ε

Step 2: Left Factoring

The grammar S → b S b S' | b S' already has common prefix 'b'. Factor:

S → b S'' ; S'' → S b S' | S' ; S' → a S' | ε

This grammar is now suitable for LL(1) parsing.

Explain shift-reduce parsing with an example. [2021]

Shift-reduce parsing is a bottom-up technique that uses a stack and an input buffer. Two actions:

• Shift: Move the next input token onto the stack.
• Reduce: When the RHS of a production appears on top of the stack, replace it with the LHS non-terminal.

Example — Grammar: E → E + T | T ; T → int

Input: int + int $

Differentiate SLR, LR(1), and LALR parsers. [2023]

What is Syntax Directed Translation (SDT)?

SDT is a method of translating a grammar by attaching semantic actions/rules to its productions. It combines parsing with translation.

What is a synthesized attribute?

A synthesized attribute is an attribute whose value is computed from the children (descendants) of a node in the parse tree. It flows bottom-up.

What is an inherited attribute?

An inherited attribute is an attribute whose value is passed from the parent or siblings of a node in the parse tree. It flows top-down.

What is an activation record?

An activation record (stack frame) is a contiguous block of storage containing all information needed for one procedure invocation: parameters, return address, local variables, temporaries, control links.

What is a quadruple?

A quadruple is a four-field intermediate code representation: (operator, operand1, operand2, result). E.g., (+, a, b, t1) for t1 = a + b.

What is a triple in intermediate code?

A triple is a three-field intermediate code: (operator, operand1, operand2). The result is referenced by its position number. E.g., (+, a, b) at position (0).

What is an indirect triple?

An indirect triple is a list of pointers to triples. It allows easy reordering of instructions without changing the triple list.

Explain SDD and SDT. Differentiate between synthesized and inherited attributes with examples. [2023]

SDD (Syntax Directed Definition): A CFG with semantic rules. Each production has associated semantic rules that compute attribute values.

SDT (Syntax Directed Translation scheme): A CFG with semantic actions embedded within productions (between symbols). Actions can appear anywhere in the production body.

Synthesized Attribute: Computed from children. Example: E → E₁ + T { E.val = E₁.val + T.val } — E.val is synthesized from E₁ and T.

Inherited Attribute: Received from parent/siblings. Example: T → { T.type = E.type } int — T.type is inherited from parent E.

L-attributed definitions allow inherited attributes to be passed from left to right only, making them suitable for both top-down and bottom-up evaluation.

Generate Three-Address Code for: a = b + c * d - e / f. Show quadruples and triples. [2023]

Three-Address Code (TAC):

t1 = c * d
t2 = e / f
t3 = b + t1
t4 = t3 - t2
a  = t4
          

Quadruples:

Triples:

Explain parameter passing methods: call by value, call by reference, call by value-result, and call by name. [2022]

Call by Value: The value of the actual parameter is copied into the formal parameter. Changes to formal do NOT affect actual. E.g., C language default.

void swap(int a, int b) { int t=a; a=b; b=t; }
// Calling: x=10, y=20; swap(x,y);
// After call: x=10, y=20 (unchanged!)
          

Call by Reference: The address of the actual parameter is passed. The formal parameter becomes an alias (another name) for the actual. Changes to formal DO affect actual. E.g., C++ with &.

void swap(int &a, int &b) { int t=a; a=b; b=t; }
// After call: x=20, y=10 (SWAPPED!)
          

Call by Value-Return: Copy values in at call time, copy back at return. May cause issues with overlapping actuals.

Call by Name: The formal parameter is textually replaced by the actual parameter everywhere in the procedure body (implemented via thunks). Very expensive.

What is type checking? Explain type conversion and type equivalence. [2021]

Type Checking verifies that the operands of an operator are of compatible types. Performed during semantic analysis.

Type Conversion: Converting a value from one type to another.

• Implicit (coercion): Automatically done by compiler. E.g., int + float → int converted to float.
• Explicit (casting): Done by programmer. E.g., (int)3.14 → 3.

Type Equivalence:

• Name equivalence: Two types are equivalent if they have the same name. Strict.
• Structural equivalence: Two types are equivalent if they have the same structure (same type components).

What is code optimization? [2023]

Code optimization is the phase that transforms intermediate or target code to improve execution speed and/or reduce code size, without changing the program's output.

What is a basic block?

A basic block is a sequence of consecutive statements with exactly one entry point (first statement) and one exit point (last statement). Control enters at the first statement and leaves at the end.

What is a leader in basic block identification?

A leader is the first statement of a basic block. Statements that are leaders: (1) first statement, (2) target of a goto/branch, (3) statement immediately following a goto/branch.

What is a DAG in compiler optimization?

A DAG (Directed Acyclic Graph) represents a basic block where nodes are operators/operands and edges show data flow. It helps identify and eliminate common subexpressions.

What is peephole optimization? [2022]

Peephole optimization examines a small "window" (peephole) of adjacent instructions and replaces them with a shorter or faster equivalent sequence.

What is reaching definitions?

A definition d reaches a point p if there exists a path from the definition of d to p where d is not redefined along the path.

What is a live variable?

A variable is live at a point if its current value may be used along some path from that point to the program's exit (before being redefined).

Construct the DAG for the basic block: a = b + c; b = a - d; c = b + c; d = a - d. [2023]

Step 1: Identify leaders and basic block (all statements form one block here).

Step 2: Build DAG:

            (+) ←── b ──┐
            │          │
         c ─┘          │
                        │
             ┌──────────┘  → a (stored)
             │
             │
          (-) ←── a ──┐
          │           │
         d ─┘         │
                      │
                  ┌───┘  → b (stored)
                  │
                  │
               (+) ←── b (from above)
               │
               c (original, not the redefined b)
               │
            ┌──┘  → c (stored)
            │
            │
         (-) ←── a (from first computation)
         │
         d
         │
      ┌────┘  → d (stored)

  Shared nodes:
  • (+) for "b+c" used in a = b+c and c = b+c
  • (-) for "a-d" used in b = a-d and d = a-d
          

Optimized code: t1 = b + c; a = t1; b = t1 - d; c = b + c_original; d = t1 - d

Construct basic blocks and draw the flow graph for the given code. [2022]

Code:

1:  a = b + c
2:  b = a - d
3:  if b < c goto 8
4:  d = a * e
5:  e = d + 1
6:  goto 9
7:  x = d - e
8:  y = a * c
9:  z = x + y
         

Step 1: Find Leaders

• Statement 1 (first statement) → Leader
• Statement 3 (target of goto? No, but let's check: statement 8 is target of goto from 6) → Leader
• Statement 4 (after goto/branch at 3) → Leader
• Statement 7 (target of goto from 3) → Leader
• Statement 8 (target of goto from 6) → Leader
• Statement 9 (after goto from 6) → Leader

Step 2: Basic Blocks

• B1: {1: a=b+c; 2: b=a-d; 3: if b<c goto 8}
• B2: {4: d=a*e; 5: e=d+1; 6: goto 9}
• B3: {7: x=d-e}
• B4: {8: y=a*c}
• B5: {9: z=x+y}

Step 3: Flow Graph

          ┌───┐
          │ B1 │
          └─┬─┘
            │ (b≥c)
            ▼
          ┌───┐
          │ B2 │
          └─┬─┘
            │ (goto)
            ▼
          ┌───┐
          │ B5 │
          └───┘
            │
      (b<c) │
            ▼
          ┌───┐
          │ B3 │──┐
          └───┘  │
                  │
                  ▼
                ┌───┐
                │ B4 │
                └─┬─┘
                  │
                  ▼
                ┌───┐
                │ B5 │
                └───┘
          

Explain reaching definitions and live variable analysis. [2021]

Reaching Definitions: A definition d reaches point p if there exists a path from the point of d's definition to p where d is NOT redefined. Used for:

• Constant propagation
• Common subexpression elimination
• Detecting uninitialized variables

Data Flow Equations (Reaching Definitions):

• IN[n] = UNION of OUT[p] for all predecessors p of n
• OUT[n] = GEN[n] ∪ (IN[n] − KILL[n])
• GEN[n] = definitions generated in block n
• KILL[n] = definitions killed (overwritten) in block n

Live Variable Analysis: A variable v is live at point p if its value at p may be read along some path from p to the exit. Used for:

• Register allocation (only allocate registers to live variables)
• Dead code elimination
• Copy propagation

Data Flow Equations (Live Variables):

• OUT[n] = UNION of IN[s] for all successors s of n
• IN[n] = USE[n] ∪ (OUT[n] − DEF[n])
• USE[n] = variables used before defined in n
• DEF[n] = variables defined in n