CSE411: Introduction to Compilers

Lexer (Scanner)

Jooyong Yi (UNIST)

Interface of Lexer

         |-------|            
Source → | Lexer | → tokens 
Program  |       |          
         |-------|          

Token

What is token in the context of a programming language?

Token

A token is the most basic unit in the grammar of a programming language.

Token

How many units do you find in the following C program snippet?

int

(1). 1 unit consisting of int
(2). 2 units consisting of i and nt (or in and t)
(3). 3 units consisting of i, n, and t

Token

How many units do you find in the following C program snippet?

int val = 10;

Lexing (Scanning) Example

                |-------|            
int val = 10; → | Lexer | → int ID ASSIGN NUM ;
                |-------|                          

Lexing (Scanning) Example

                |-------|            
int val = 10; → | Lexer | → int ID ASSIGN NUM ;
                |-------|                          

• A token is also called a lexical token, hence the name lexer.

How to Write a Lexer?

How to Write a Lexer?

• Option #1: write a lexer yourself

Alternative Option: Synthesizing a Lexer

             |-------------|    
             |    Lexer    |        
             | Synthesizer |
             |-------------|
                    |
               synthesizes   
                    ↓
                |-------|            
int val = 10; → | Lexer | → int ID ASSIGN NUM ;
                |-------|                          

Lexer Synthesizer Examples

• Lex
• flex

> man lex

FLEX(1)                               Programming                                              FLEX(1)

NAME
       flex - the fast lexical analyser generator

SYNOPSIS
       flex [OPTIONS] [FILE]...

DESCRIPTION
       Generates programs that perform pattern-matching on text.

Input to Lex

        Specification for the lexer
                    ↓
             |-------------|    
             |    Lexer    |        
             | Synthesizer |
             |-------------|
                    |
               synthesizes   
                    ↓
                |-------|            
int val = 10; → | Lexer | → int ID ASSIGN NUM ;
                |-------|                          

What to Give as the Specification for Lex?

Specification for the NUM Token

What is a single expression that represents the following?

• 1
• 21
• 411
• ...

Specification for the NUM Token

What is a single expression that represents the following?

• 1
• 21
• 411
• ...

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

Regular Expression (RE) as the Specification for Lex

        Specification for the lexer written in RE
                    ↓
             |-------------|    
             |    Lexer    |        
             | Synthesizer |
             |-------------|
                    |
               synthesizes   
                    ↓
                |-------|            
int val = 10; → | Lexer | → int ID ASSIGN NUM ;
                |-------|                          

Regular Expressions

• a: An ordinary character stands for itself.
• "ab": Quotation, a string in quotes stands for itself literally. E.g., "if"
• : 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 .

Regular Expression Example

What is a single expression that represents the following?

• 1, 21, 411, ...
• -1, -21, -411, ...
• +1, +21, +411, ...

Regular Expression Example

What is a single expression that represents the following?

• 1, 21, 411, ...
• -1, -21, -411, ...
• +1, +21, +411, ...

(-|+)? [1-9] [0-9]*

Regular Expression Example

What is a single expression that represents the following?

• 1, 21, 411, ...
• -1, -21, -411, ...
• +1, +21, +411, ...

(-|+)? [1-9] [0-9]*
(-|+|) [1-9] [0-9]*

Language of a Regular Expression

• Let be .
• Then the language of , denoted with , includes: 1, 21, 411, ...

Alphabets, Strings, and Languages

1. An alphabet is a finite non-empty set of symbols.
   • e.g.,
2. A string is a finite sequence of symbols chosen from an alphabet.
   • e.g., 1, 21, 411,
3. Given an alphabet ,
   • : the set of strings over of length .
   • the set of all strings over alphabet :
4. A language is a subset of where all strings in satisfy the property of .

Languages of Regular Expressions

• (a) {a}
• ("ab") {"ab"}
• ([0-9]) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• ( )

Synthesized Lexer

What does a synthesized lexer look like?

Synthesized Lexer

• Input: [1-9] [0-9]*
• Output:
  

RE and DFA (Deterministic Finite Automaton)

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

RE --> DFA

Try the following tool: https://github.com/yakout/compiler

• Caveat: most programs are not bug-free. Do not blindly rely on the tool.

DFA and NFA (Non-deterministic Finite Automaton)

• 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:

RE --> NFA --> DFA

Theory: For every NFA , there exists a DFA such that and accept the same language.

RE --> NFA

1. RE:
2. NFA:
   

RE --> NFA

1. RE:
2. NFA:
   

RE --> NFA

1. RE:
2. NFA:
   

Thompson's Construction

RE -- Thompson's construction --> 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

• Input: NFA:
• Output: DFA

Note that

• 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:

How to obtain

• Input: NFA:
• Output: DFA

We need a function that satisfies:

Property of

• (the same is true for and )

Property of

• (the same is true for and )

-Closure

• is an -closure.

-Closure

• Given a set and its -closure ,

-Closure

• Given a set , its -closure satisfies the following:

Another formal definition (also showing how to compute):

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

Subset Construction Algorithm

• Input: NFA:
• Output: DFA

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      

Our Example

d0 := ε-closure({n0})
D := {d0}
W := {d0}  // worklist
...

d0 = {0, 1, 2, 4, 7}
W0 = {0, 1, 2, 4, 7}

Our Example

   remove q from W
   for α in Σ:
      T := ∅
      for s in q:
         T := T ∪ δ_N(s, α)
      T' := ε-closure(T)

α = a
T = {3, 8}
T' = {1, 2, 3, 4, 6, 7, 8}

Our Example

      D' := D ∪ {T'}
      δ_D(q, α) = T' // update δ_D
      if T' ∉ D:
         W := W ∪ {T'}

T' = {1, 2, 3, 4, 6, 7, 8}
D = {{0, 1, 2, 4, 7}}
D' = {{0, 1, 2, 4, 7}, {1, 2, 3, 4, 6, 7, 8}}
δ_D({0, 1, 2, 4, 7}, a) = {1, 2, 3, 4, 6, 7, 8}