Compiler Design Basics: Phases, Roles, and Real-World Impact

Core Concepts: Compiler vs. Interpreter

1. Definitions

A compiler is a program that translates entire source code into machine code (or intermediate code) before execution. It produces an executable file (e.g., .exe, .out). An interpreter translates and executes source code line-by-line without generating a separate executable.

2. Why Compilers Matter in Nepal?

In the Real World

• eSewa (Nepal Government): Uses compiled languages (C++, Java) for high-performance backend services (e.g., processing thousands of online payments per second). The compiler optimizes code to handle load balancing and low-latency responses—critical for government services like bill payments and license renewals. Example: When you pay your electricity bill via eSewa, the compiler-generated code ensures your transaction is processed in milliseconds, not seconds.

• Khalti (Fintech): Relies on multi-pass compilers (e.g., Rust, Go) for secure transaction processing. Compilers help detect memory leaks and buffer overflows—critical for preventing fraud in mobile payments. Example: If a hacker tries to exploit a vulnerability in Khalti’s app, the compiler’s static type checking (Unit 7) catches unsafe operations before deployment.

• Ncell (Telecom): Uses just-in-time (JIT) compilation (a hybrid of interpreter+compiler) in mobile apps (e.g., Android’s Dalvik VM). This balances fast app launches (like Pathao’s ride-hailing) with efficient battery use. Example: When you open the Ncell app to check data balance, the JIT compiler optimizes frequently used code (e.g., network status checks) to reduce lag.

Phases of a Compiler

Compilers break translation into 9 phases, visualized below. Each phase has inputs, outputs, and interactions with the symbol table and error handler.

flowchart TD
    A["Source Program"] --> B["Lexical Analyzer\nInput: Source Code\nOutput: Tokens"]
    B --> C["Syntax Analyzer\nInput: Tokens\nOutput: Parse Tree"]
    C --> D["Semantic Analyzer\nInput: Parse Tree\nOutput: Intermediate Code + Symbol Table"]
    D --> E["Intermediate Code Generator\nInput: Semantic Tree\nOutput: Intermediate Code"]
    E --> F["Code Optimizer\nInput: Intermediate Code\nOutput: Optimized Intermediate Code"]
    F --> G["Code Generator\nInput: Optimized Code\nOutput: Target Code"]
    G --> H["Linker\nInput: Target Code + Libraries\nOutput: Executable"]

    % Symbol Table and Error Handler
    D -->|"Updates"| ST["Symbol Table"]
    ST -->|"Feeds"| C
    ST -->|"Feeds"| E
    ST -->|"Feeds"| G

    B -->|"Detects"| EH["Error Handler"]
    C -->|"Detects"| EH
    D -->|"Detects"| EH
    EH -->|"Reports"| A

Key Phases Explained

1. Lexical Analysis (Scanner)

• Role: Converts source code into tokens (keywords, identifiers, operators).
• Example: int x = 5 + y; → Tokens: [int, x, =, 5, +, y, ;]
• Input Buffering:
  • Uses a buffer-pair scheme with sentinels (EOF markers) to efficiently read source code in chunks.
  • Why? Reduces I/O overhead (critical for large programs like NEPSE’s trading software).

2. Syntax Analysis (Parser)

• Role: Checks grammatical correctness using a parse tree or abstract syntax tree (AST).
• Example Grammar: E → T | E + T T → F | T * F F → (E) | id
• Parsing Techniques:
  • Top-down (LL(1)): Predictive parsing (e.g., recursive descent).
  • Bottom-up (LR(1)): Shift-reduce parsing (used in gcc).

stateDiagram-v2
  [*] --> Parse
  Parse --> CheckGrammar
  CheckGrammar --> BuildAST
  BuildAST --> [*]
  CheckGrammar --> Error: SyntaxError
  Error --> [*]
  note right of Parse
    Input: Tokens
    Output: Parse Tree
  end note

flowchart TD
    A["E"] --> B["T"]
    A --> C["E + T"]
    B --> D["F"]
    B --> E["T * F"]
    D --> F["(E)"]
    D --> G["id"]
    C --> H["+"]
    E --> I["*"]

3. Semantic Analysis

• Role: Checks meaningful correctness (e.g., type compatibility, scope rules).
• Symbol Table: Stores variable names, types, and memory locations.
• Example:

  int x = "hello"; // Error: Type mismatch (int vs. string)
  

  Real-world tie: NTC’s traffic management system uses semantic analysis to ensure route variables (e.g., traffic_light_status) are correctly typed before generating control signals.

4. Intermediate Code Generation

• Role: Produces machine-independent code (e.g., 3-address code, quadruples).
• Example: x = 5 + y → (t1) 5 + y → t1, (t2) t1 → x

5. Code Optimization

• Techniques:
  • Constant folding: x = 5 + 3 → x = 8
  • Dead code elimination: Removing unused variables.
  • Loop optimization: Unrolling loops for speed.
• Example: Daraz’s recommendation engine uses loop optimizations to reduce latency when fetching product suggestions.

6. Code Generation

• Role: Converts intermediate code to target machine code.
• Example: Generating x86 assembly for x = a + b:

  MOV EAX, [a]
  ADD EAX, [b]
  MOV [x], EAX
  

One-Pass vs. Multi-Pass Compilers

Symbol Table: The Compiler’s Memory

Why It’s Essential

• Tracks variables, functions, and types.
• Used in all phases (syntax, semantic, code generation).
• Example: In Nepal Rastra Bank’s loan calculator, the symbol table ensures interest_rate is not redefined as a string.

Error Handling in Compilers

Types of Errors

1. Lexical Errors: Invalid tokens (e.g., ifx instead of if).
2. Syntax Errors: Grammar violations (e.g., missing ;).
3. Semantic Errors: Logical mistakes (e.g., dividing by zero).

Error Recovery Techniques

• Panic Mode: Skips invalid tokens until a valid one is found.
• Phrase-Level Recovery: Replaces invalid phrases with defaults.
• Example: In Pathao’s ride-matching algorithm, syntax errors in user input (e.g., go to kathmandu university) are corrected via phrase-level recovery to kathmandu_university.

Exam Tip: How to Score Full Marks

1. Block Diagram: Always draw the 9-phase compiler diagram with symbol table and error handler interactions. Label inputs/outputs of each phase.
2. Compiler vs. Interpreter: Compare speed, portability, and error handling with real-world examples (e.g., gcc vs. Python).
3. Symbol Table: Explain its role in semantic analysis and how it’s updated in each phase.
4. Error Handling: Describe where errors are caught (lexical, syntax, semantic) and recovery techniques.
5. One-Pass vs. Multi-Pass: Relate to optimization and complexity (e.g., gcc uses multi-pass for high optimization).
6. Real-World Tie: For every concept, link it to Nepali apps (eSewa, Khalti) or global tech (Google’s Go compiler).

Worked Example: Compiling x = 5 + y

Common Pitfalls in Exams

• Forgetting to mention symbol table updates in semantic analysis.
• Confusing lexical errors (invalid tokens) with syntax errors (grammar).
• Not linking concepts to real-world systems (e.g., eSewa’s performance).
• Drawing the block diagram without inputs/outputs.

Practice Questions (Self-Check)

1. Draw the block diagram of a compiler and label the symbol table’s role in 3 phases.
2. Explain how Khalti’s backend might use a multi-pass compiler for security.
3. What lexical error would occur in if (x > 10) if > is misspelled as >>?
4. How does NTC’s traffic light system use semantic analysis to validate routes?

Final Note: Compilers are the backbone of software efficiency. Mastering this unit means understanding how code transforms from human-readable to machine-executable—a skill critical for app development, cybersecurity, and system design in Nepal’s tech industry.

In the real world

• eSewa: Uses multi-pass compilers (C++/Java) to optimize high-frequency transactions (e.g., 10,000+ payments/sec during Dashain). The symbol table ensures variables like transaction_id and amount are correctly typed before generating machine code for low-latency responses (critical for government services like bill payments).

• Khalti: Relies on static type checking (semantic analysis) in Rust/Go to prevent buffer overflows in mobile payment apps. For example, when validating user_balance -= amount, the compiler checks if amount is a valid float before generating code to avoid crashes during transactions.

• Ncell’s JIT Compiler: In Android apps (e.g., Ncell Recharge), the one-pass optimization (like in yacc) quickly compiles frequently used code (e.g., network status checks) into native machine code during runtime, reducing app lag by 30% while recharging.