CSE411: Introduction to Compilers

Lexer (Scanner)

Jooyong Yi (UNIST)

Lexing

        position  =  initial  +  rate   *   60               source program
                           ↓
        |------------------------------------|
        |      Lexical Analyzer (Lexer)      |
        |------------------------------------|
                           ↓
        <ID, 1> <=> <ID, 2> <+> <ID, 3> <*> <INT, 60>        a sequence of tokens

How would you write a lexer?

How would you write a lexer?

        position  ⟼ ID
        initial   ⟼ ID
        rate      ⟼ ID

        60        ⟼ INT
        15        ⟼ INT
        0         ⟼ INT

        =         ⟼ =
        +         ⟼ +
        *         ⟼ *

Regular Expression for INT?

        60        ⟼ INT
        15        ⟼ INT
        0         ⟼ INT

Regular Expression for INT

        60        ⟼ INT
        15        ⟼ INT
        0         ⟼ INT

'0' | ('1'| '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9') ('0'| '1'| '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')*

• Shorthand notation: 0 | [1-9] [0-9]*

Regular Expression for ID?

        position  ⟼ ID
        initial   ⟼ ID
        RATE      ⟼ ID
        a_123     ⟼ ID
        _abc      ⟼ ID
        a_        ⟼ ID

Regular Expression for ID

        position  ⟼ ID
        initial   ⟼ ID
        RATE      ⟼ ID
        a_123     ⟼ ID
        _abc      ⟼ ID
        a_b_      ⟼ ID

[a-zA-Z_] [a-zA-Z0-9_]*

Regular Expressions

• 'a', 'int', 'if': An ordinary character or a string stands for itself literally.
• : The empty string
• : Alternation, choosing from or .
• [0-9]: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
• : Concatenation, an followed by an .
• : Repetition (zero or more times)
• : Repetition (one or more times)
• : Optional, zero or one occurrences of .

• Input (RE): 0 | [1-9] [0-9]*
• Q: Is '0' INT?
• Q: Is '10' INT?
• Q: Is '01' INT?

• Q: Given an arbitrary input string s, how can we determine if it is an INT?

RE and DFA (Deterministic Finite Automaton)

• Input (RE): 0 | [1-9] [0-9]*
• Output (DFA):

RE and DFA (Deterministic Finite Automaton)

Let be a regular expression. Then there exists a deterministic finite automaton that accepts .

How can we convert RE into DFA?

• Input (RE): 0 | [1-9] [0-9]*
• Output (DFA):

How can we convert RE into DFA?

• Input (RE): ID | IF
  • ID: [A-Za-z_] [A-Za-z0-9_]*
  • IF: 'if'
• Output (DFA):

How can we convert RE into DFA?

• Input (RE): ID | IF
  • ID: [A-Za-z_] [A-Za-z0-9_]*
  • IF: 'if'
• Output (DFA):

How can we convert RE into DFA?

• Input (RE): ID | IF
  • ID: [A-Za-z_] [A-Za-z0-9_]*
  • IF: 'if'
• Intermediate Output (NFA):

DFA and NFA

• DFA and NFA
  • : a finite set of states.
  • : an input alphabet.
    • For DFA only:
  • : the initial state
  • : a set of final (accepting) states
  • : a transition function.
    • For DFA:
    • For NFA:

Theorems

• Let be a regular expression. Then there exists a deterministic finite automaton that accepts .

• Let be a regular expression. Then there exists an NFA that accepts .
• For every NFA , there exists a DFA such that and accept the same language.
• There exists an algorithm to convert any NFA into an equivalent DFA .

How can we convert RE into DFA?

• RE NFA DFA

RE NFA

• RE:
• NFA:

RE NFA

• RE:
• NFA:
  

RE NFA

• RE:
• NFA:

RE NFA

• RE:
• NFA:
  

RE NFA

• RE:
• NFA:

RE NFA

• RE:
• NFA:
  

NFA DFA

How to transform NFA to DFA?

NFA DFA

• Map multiple NFA states to a single DFA state

NFA DFA

• Bisimulate both automata

NFA DFA

NFA DFA

NFA DFA

NFA DFA

NFA DFA

NFA DFA

NFA --> DFA

NFA DFA

Subset Construction Algorithm

1. Create the DFA start state: =

-Closure

• Given a set and its -closure ,

-Closure

• Given a set , its -closure is the smallest set satisfying the following:

Subset Construction Algorithm

2. For each DFA state and each input character , find all NFA states reachable by : .
3. Include all states reachable afterward through -transitions: .
4. Make a DFA transition: .

Subset Construction Algorithm

D0 := ε-closure({N0})
D := {D0}
W := {D0}  // worklist
while W ≠ ∅:
   remove Q from W
   for α in Σ:
      T := ∅
      for S in Q:
         T := T ∪ δ_N(S, α)
      T' := ε-closure(T)
      D' := D ∪ {T'}
      δ_D(Q, α) = T' // update δ_D
      if T' ∉ D:
         W := W ∪ {T'}
      D := D'
F_D = {Q ∊ D | Q ∩ F_N ≠ ∅} // define F_D