Lexical Analysis

What is a Compiler?

Analogy: A translator who converts a book from French to English. But a compiler does more — it also checks that the French makes grammatical sense (syntax), that the sentences are meaningful (semantics), and produces an efficient English translation (code generation).

Compiler phases:

Source code
    ↓  Lexical Analysis (Lexer)     → Token stream
    ↓  Syntax Analysis  (Parser)    → Parse tree / AST
    ↓  Semantic Analysis            → Annotated AST
    ↓  Intermediate Code Generation → 3-address code
    ↓  Code Optimisation            → Optimised IR
    ↓  Code Generation              → Machine code

Lexical Analysis — Breaking Code Into Words

Analogy: Reading a sentence word by word. "The quick brown fox" → [The] [quick] [brown] [fox]. The lexer does this for code: int x = 5; → [int] [x] [=] [5] [;]

Input:  int count = 42 + base;

Output tokens:
  (KEYWORD,     "int")
  (IDENTIFIER,  "count")
  (ASSIGN,      "=")
  (INTEGER,     "42")
  (PLUS,        "+")
  (IDENTIFIER,  "base")
  (SEMICOLON,   ";")

Tokens, Lexemes, and Patterns

Pattern:  A rule describing the form of a token
          (described by a regular expression)

Lexeme:   The actual character sequence matching the pattern

Token:    (token_type, lexeme) pair sent to parser

Example:
  Pattern for IDENTIFIER: [a-zA-Z_][a-zA-Z0-9_]*
  Lexeme:                  "count"
  Token:                   (IDENTIFIER, "count")

Regular Expressions for Tokens

Integer literal:   [0-9]+
Float literal:     [0-9]+.[0-9]+
Identifier:        [a-zA-Z_][a-zA-Z0-9_]*
Whitespace:        [    
]+            ← usually discarded
Keywords:          if | else | while | for | int | float ...
Single-line comment: //[^
]*          ← discarded

Operator shortcuts:
  +    *    ?    represent one-or-more, zero-or-more, zero-or-one
  [abc] means a or b or c
  [0-9] means any digit
  [^x]  means any character EXCEPT x

Building a Lexer: RE → NFA → DFA

Step 1: Thompson's Construction (RE → NFA)
  Each regular expression is converted to a small NFA
  with ε-transitions connecting pieces

Step 2: Subset Construction (NFA → DFA)
  Combine NFA states into DFA states (each DFA state = set of NFA states)
  Worst case: 2^n DFA states from n-state NFA (usually much fewer)

Step 3: DFA Minimisation
  Merge indistinguishable states → smaller, faster DFA

Step 4: Run the DFA on input
  O(n) time for input of length n — very efficient!

Longest Match and Priority Rules

When multiple patterns could match, the lexer applies two rules:

Rule 1: LONGEST MATCH WINS
  Input: "count123"
  Pattern "count" matches 5 chars, "[a-z][a-z0-9]*" matches 8 chars
  → Lexer picks the longer match: "count123" as IDENTIFIER

  Input: ">>"
  Could be: ">" followed by ">" (two GREATER_THAN)
  But ">>" is a longer match: RIGHT_SHIFT token
  → Lexer picks ">>" as RIGHT_SHIFT

Rule 2: TIE-BREAKING BY RULE ORDER (keywords before identifiers)
  Input: "if"
  Matches both KEYWORD pattern AND IDENTIFIER pattern (equal length)
  → Rule listed first wins: KEYWORD "if"

  Input: "iflag"
  Matches IDENTIFIER pattern (8 chars), KEYWORD "if" only matches 2 chars
  → Longest match: "iflag" is IDENTIFIER (not keyword "if"!)

Symbol Table

The lexer creates symbol table entries for identifiers:

Symbol table maps: name → (type, scope, address, ...)

Lexer fills in: name
Later phases fill in: type (semantic analysis), address (code generation)

Scoping: nested scopes represented as a stack of hash tables
  Inner scope can shadow outer scope (same name, different meaning)

Lexer vs Parser — What Each Can Handle

Lexer uses FINITE AUTOMATA (Regular Languages):
  ✓ Token patterns: identifiers, numbers, keywords, operators
  ✗ Nested structures: balanced parentheses, matched braces
  ✗ Context dependencies: cannot check if variable was declared

Parser uses PUSHDOWN AUTOMATA (Context-Free Languages):
  ✓ Nested structures: if-else, function definitions, expressions
  ✓ Matching: { with }, ( with )
  ✗ Context: cannot check types or declarations

Quick Check

Q1. Input: "while123". Is this a keyword or identifier? Answer: Identifier. Longest match: "while123" (9 chars) matches IDENTIFIER. "while" keyword only matches 5 chars. Longest match wins.

Q2. How many memory accesses does a DFA-based lexer require per character? Answer: O(1) per character — just look up the next state in the DFA transition table. Total: O(n) for input of length n.

Q3. Why cannot a lexer handle balanced parentheses? Answer: Balanced parentheses require COUNTING the depth (how many are open). Finite automata have finite memory (finite states) and cannot count arbitrarily. A pushdown automaton (with a stack) is needed.

Key Points