IT-603(C) Embedded Systems - Unit 1: Compiler Design (Based on Past Exam Analysis)

I. Introduction & Compiler Structure

A compiler is a program that translates source code written in a high-level language into an equivalent target language (usually machine code).

Phases of a Compiler (with Role):

Bootstrapping: The process of using a simple, limited version of a compiler (written in another language) to compile a more sophisticated version of itself, eventually leading to a full compiler for its own source language. Purpose: To create a self-hosting compiler without needing an existing compiler for the new language.

II. Lexical Analysis

Reasons for Separating Lexical Analysis from Syntax Analysis:

1. Simplicity: Removes low-level character-level details (whitespace, comments) from syntax analysis.

2. Efficiency: Lexical analyzer can be optimized (e.g., using finite automata) for fast token recognition.

3. Portability: Device-dependent I/O and character encoding handling is isolated.

4. Modularity: Clear interface (token stream) between phases.

Role of Finite Automata (FA):

• Deterministic Finite Automaton (DFA) is constructed from regular expressions (patterns for tokens).

• DFA acts as the recognizer: it reads the input character-by-character and accepts/rejects strings based on whether they match a token pattern.

• The DFA's accepting states correspond to token types.

LEX Tool: Structure and Working

A Lex program has three sections:

%{

    /* C declarations (global vars, functions) */

%}

/* Regular expressions (patterns) */

%%

pattern1    { action1 C code }

pattern2    { action2 C code }

...

%%

/* Additional C code (main, helper functions) */

Working: Lex reads the specifications, generates a lex.yy.c file containing a yylex() function. This function implements a DFA derived from the regex patterns. When yylex() is called, it scans input, matches the longest possible prefix to a pattern, and executes the corresponding action (usually returning a token).

Lexical Analysis Example: Identifiers & Arithmetic Operators

%{
#include "y.tab.h" /* Token definitions from parser */

%}

%%

"+"     { return PLUS; }

"-"     { return MINUS; }

"*"     { return MUL; }

"/"     { return DIV; }

"="     { return ASSIGN; }

[a-zA-Z][a-zA-Z0-9]* { yylval.id = strdup(yytext); return ID; }

[ \t\n] { /* ignore whitespace */ }

.       { return INVALID; } /* any other char */

%%

• For input x = a + b * c, tokens returned: ID('x'), ASSIGN, ID('a'), PLUS, ID('b'), MUL, ID('c').

III. Syntax Analysis (Parsing)

Top-down vs. Bottom-up Parsing (Overview):

Operator Precedence Parsing:

• Concept: Uses precedence relations (<·, =·, ·>) between operators to guide parsing without a full parse tree.

• Algorithm: Constructs a precedence parsing table from grammar (after removing non-operator symbols). Parses by shifting tokens onto a stack and using relations to decide when to reduce.

• Limitation: Only works for operator-precedence grammars (no two non-terminals adjacent in any production).

SLR(1) Parsing:

• Uses LR(0) items to build canonical collection of LR(0) states.

• Parsing Table Construction:

  1. Build LR(0) automaton (states as sets of items).

  2. ACTION Table:

     • shift on [A → α·aβ] for terminal a.

     • reduce A → α on [A → α·] if · is at end, only if FOLLOW(A) does not contain any terminal that also causes a shift-reduce conflict.

     • accept on [S' → S·].

     • error otherwise.

  3. GOTO Table: goto[state, non-terminal] = next_state.

• Checking SLR(1) Correctness: Grammar is SLR(1) if no reduce-shift or reduce-reduce conflicts exist in the ACTION table after applying the FOLLOW set condition.

LALR Parsers:

• Comparison with SLR:

  | Feature | SLR | LALR | | :--- | :--- | :--- | | State Construction | Uses FOLLOW sets of LHS non-terminal for reductions in all states. | Merges LR(0) states with identical cores (items without lookahead). Uses lookaheads propagated during merge. | | Power | Less powerful (more likely to have conflicts). | More powerful than SLR, but less than full LR(1). | | Table Size | Smaller. | Larger than SLR, smaller than LR(1). |

CLR(1)/LR(1) Parsing:

• Uses LR(1) items: [A → α·β, a] where a is lookahead.

• Construction:

  1. Build canonical collection of LR(1) items (closure and goto operations consider lookaheads).

  2. ACTION Table: reduce A → α only on [A → α·, a] for lookahead a.

  3. GOTO Table: Same as SLR but on LR(1) states.

• Result: Largest class of grammars parsable by deterministic shift-reduce parser (all deterministic CFLs).

Parse Tree Construction for Ambiguous Grammars:

• Ambiguous grammar (e.g., E → E+E | E*E | id) allows multiple parse trees for a+b*c.

• Elimination: Use precedence and associativity rules to rewrite grammar unambiguously.

  
  E → E + T | T
  
  T → T * F | F
  
  F → (E) | id
  
  

  Now, a+b*c has a unique parse tree reflecting * higher precedence than +.

Context-Free Grammars (CFG):

• Capabilities: Describe nested, hierarchical structures (matching parentheses, if-then-else, loops). Express recursion.

• Limitations: Cannot express context-sensitive constraints (e.g., variable must be declared before use, type compatibility). Cannot count (e.g., equal number of a's and b's).

FIRST and FOLLOW Sets:

• FIRST(α) for string α: Set of terminals that can begin any string derived from α. If α ⇒* ε, include ε.

• FOLLOW(A) for non-terminal A: Set of terminals that can appear immediately to the right of A in some sentential form. If A is at end, include $ (end-of-input).

• Step-by-Step Computation:

  1. FIRST:

     • If X is terminal, FIRST(X) = {X}.

     • If X → ε is production, add ε to FIRST(X).

     • For X → Y1 Y2 ... Yk:

       • Add FIRST(Y1) \ {ε} to FIRST(X).

       • If ε ∈ FIRST(Y1), add FIRST(Y2) \ {ε}, and so on.

       • If ε in all FIRST(Yi), add ε to FIRST(X).

  2. FOLLOW:

     • Add $ to FOLLOW(S) where S is start symbol.

     • For production A → α B β:

       • Add FIRST(β) \ {ε} to FOLLOW(B).

     • For production A → α B or A → α B β where ε ∈ FIRST(β):

       • Add FOLLOW(A) to FOLLOW(B).

IV. Syntax-Directed Translation & Semantic Analysis

Attribute Grammars:

• Annotate grammar with attributes (values associated with grammar symbols).

• S-attributed Definitions:

  • Attributes are synthesized only (computed from children's attributes).

  • Bottom-up evaluation: Attributes computed during reductions in a bottom-up parser.

  • Example: Evaluating arithmetic expressions:

    
    E → E1 + T   { E.val = E1.val + T.val }
    
    E → T        { E.val = T.val }
    
    T → int      { T.val = int.lexval }
    
    

• L-attributed Definitions:

  • Attributes can be synthesized or inherited.

  • Inherited attributes are computed from parent and left siblings (not right siblings).

  • Allows top-down flow of information (e.g., symbol table scope).

  • Conversion to Translation Scheme: Embed semantic actions within productions at positions respecting L-attributed constraints (actions before/after symbols).

    
    S → { push new scope } A { pop scope }
    
    A → D L
    
    L → ; D L | ε
    
    

• Differentiation:

  | Feature | S-attributed | L-attributed | | :--- | :--- | :--- | | Attribute Types | Only synthesized. | Synthesized + Inherited (from left siblings/parent). | | Evaluation Order | Pure bottom-up (post-order). | Can be evaluated in both top-down and bottom-up passes. | | Use Case | Simple expression evaluation. | Context-sensitive info (e.g., scope, type checking). |

Translation Schemes:

• Grammar with embedded semantic actions (in { }).

• For Case Statements:

  
  stmt → case expr { gen('t1', '=', expr.place) }
  
          of case_list end
  
  case_list → case_list ; case_item
  
             | case_item
  
  case_item → const_list : stmt { gen('goto', '-') }
  
  

  Actions generate code for expression evaluation and conditional jumps.

Dependency Graphs:

• Directed graph representing dependencies between attribute values.

• Nodes: Attribute instances.

• Edges: X.i → Y.j if value of Y.j depends on X.i.

• Construction: For each semantic rule X.a = f(Y1.b1, ..., Yk.bk), add edges Y1.b1 → X.a, ..., Yk.bk → X.a.

• Evaluation: Topological sort of graph gives order for attribute evaluation. Cycles indicate circular definitions (semantic error).

Backpatching:

• Concept: Technique to handle forward jumps (unresolved addresses) in code generation for boolean expressions and control flow.

• Use: Generate code with temporary labels (placeholders). Maintain lists of incomplete jumps (list of instruction addresses needing a target). When target label is known, backpatch the list with the actual address.

• Example: For if (a < b) goto L1; ... L1: ..., generate if a < b goto - and add this instruction's address to a list. When L1's address is known, fill in all addresses in the list.

V. Intermediate Code Generation

Forms of Intermediate Code:

Generation Example: d = (a-b) + (a-c) + (a-c)

1. Quadruples:

   
   1: (-, a, b, t1)
   
   2: (-, a, c, t2)
   
   3: (+, t1, t2, t3)
   
   4: (-, a, c, t4)   // Common subexpression reused?
   
   5: (+, t3, t4, t5)
   
   6: (=, t5, -, d)
   
   

2. Triples:

   
   1: (-, a, b)
   
   2: (-, a, c)
   
   3: (+, 1, 2)
   
   4: (-, a, c)     // Same as 2, but new triple
   
   5: (+, 3, 4)
   
   6: (=, 5, d)
   
   

3. Indirect Triples:

   
   Triple Table:
   
   1: (-, a, b)
   
   2: (-, a, c)
   
   3: (+, 1, 2)
   
   4: (-, a, c)   // Duplicate
   
   5: (+, 3, 4)
   
   6: (=, 5, d)
   
   Pointer List: [1, 2, 3, 4, 5, 6]  // Can reorder for optimization
   
   

VI. Symbol Tables

Purpose:

• Store information about identifiers (variables, functions, constants).

• Support insertion, lookup, and scope management.

• Used by all phases (lexical, syntax, semantic, code generation).

Data Structures for Implementation:

Common Choice: Hash Table with separate chaining is most common due to average constant-time performance.

VII. Runtime Environment & Storage Management

Static vs. Dynamic Storage Allocation:

Heap Storage Allocation Strategy:

• Manages dynamic memory (e.g., malloc in C, new in C++).

• Algorithms:

  1. First-fit: Allocate first block of sufficient size.

  2. Best-fit: Allocate smallest sufficient block (reduces fragmentation).

  3. Worst-fit: Allocate largest block (tries to leave large free blocks).

• Fragmentation:

  • External: Free memory exists but is non-contiguous.

  • Internal: Allocated block is larger than requested (wasted space inside).

• Compaction: Moving allocated blocks to create larger free space (costly, requires updating pointers).

Activation Record (AR) / Stack Frame:

Structure pushed onto call stack for each function call:

|------------------------|  ↑ Higher Addresses

|   Actual Parameters    |  (if any, pushed by caller)

|------------------------|
|   Return Address       |  (saved PC)

|------------------------|
|   Dynamic Link (FP)    |  (pointer to caller's AR)

|------------------------|  ← Frame Pointer (FP)

|   Local Variables      |  (including temporaries)

|------------------------|
|   Saved Registers      |  (if needed)

|------------------------|
|   ...                  |
|------------------------|  ↓ Lower Addresses (Stack Pointer SP)

VIII. Code Optimization

Basic Blocks:

• Definition: A sequence of statements with:

  1. Single entry (first statement executed only if control enters here).

  2. Single exit (last statement causes all control to leave).

• Construction:

  1. Identify leaders (first statement, target of jump, statement after jump).

  2. Each leader starts a new basic block.

  3. Block includes all statements up to (but not including) next leader.

• Example: if (a<b) x=0; else x=1; y=x+1;

  • Leaders: 1 (if), 2 (x=0), 4 (x=1), 5 (y=x+1).

  • Blocks: B1: 1, B2: 2, B3: 4, B4: 5.

Optimization of Basic Blocks:

1. Constant Folding: Evaluate constant expressions at compile time.

2. Constant Propagation: Replace variables with known constant values.

3. Common Subexpression Elimination (CSE): Reuse computed value if same expression reappears.

4. Dead Code Elimination: Remove statements whose results are never used.

5. Algebraic Simplifications: x*1 → x, x+0 → x.

Flow Graphs:

• Nodes = Basic Blocks.

• Edges = Possible control flow between blocks (fall-through and jumps).

• Entry node = block containing first statement.

Reducible vs. Non-Reducible Flow Graphs:

Optimization Techniques (with Example):

Exam Tip: For basic block optimization, always draw the block, apply transformations step-by-step, and show the final optimized block.