CSE411: Introduction to Compilers

Lexer (Scanner)

Jooyong Yi (UNIST)

Lexing and Parsing

        position  =  initial  +  rate   *   60
                           ↓
        |------------------------------------|
        |      Lexical Analyzer (Lexer)      |
        |------------------------------------|
                           ↓
        <id, 1> <=> <id, 2> <+> <id, 3> <*> <int, 60>
                           ↓
        |------------------------------------|
        |      Syntax Analyzer (Parser)      |
        |------------------------------------|
                           ↓
                       =
                      / \
                <id,1>   +
                        / \
                   <id,2>  *
                          / \
                    <id,3>   <int,60>                   

Lexing

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

Terminologies

• Token
  • the most basic unit in the grammar of a programming language.
  • a.k.a., lexeme

Terminologies

• Token
  • the most basic unit in the grammar of a programming language.
  • a.k.a., lexeme
• Lexing
  • the process of converting a sequence of characters into a sequence of lexemes.

Learning Objective

• Understand how to extract tokens from a source program

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

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, 401, ...
• -1, -21, -401, ...
• +1, +21, +401, ...

Regular Expression Example

What is a single expression that represents the following?

• 1, 21, 401, ...
• -1, -21, -401, ...
• +1, +21, +401, ...

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

Regular Expression Example

What is a single expression that represents the following?

• 1, 21, 401, ...
• -1, -21, -401, ...
• +1, +21, +401, ...

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

Using RE as the Specification Language for Lex

           Specification for INT: (-|+)?[1-9][0-9]*
        Specification for ASSIGN: =
            Specification for ID: [a-zA-Z] [a-zA-Z0-9]* 
                    ↓
             |-------------|    
             |    Lexer    |        
             | Synthesizer |
             |-------------|
                    |
               synthesizes   
                    ↓
                |-------|            
     x = -401 → | Lexer | → ID ASSIGN INT
                |-------|                          

Potential Alternative

           Specification for INT: 1, -21, 401, ...
        Specification for ASSIGN: =
            Specification for ID: x, y, x2, xy, ...
                    ↓
             |-------------|    
             |    Lexer    |        
             | Synthesizer |
             |-------------|
                    |
               synthesizes   
                    ↓
                |-------|            
     x = -401 → | Lexer | → ID ASSIGN INT
                |-------|                          

Language of a Regular Expression

• Let be (-|+)? [1-9] [0-9]*.
• Then the language of , denoted with , includes: 1, -21, 401, ...

Program Synthesis

             1, -21, 401, ...
                    ↓
             |-------------|    
             |   Program   |        
             | Synthesizer |
             |-------------|
                    |
               synthesizes   
                    ↓
           (-|+)?[1-9][0-9]*

Synthesized Lexer

What does a synthesized lexer look like?

Synthesized Lexer

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

Lex Example

• scanner.l

> flex scanner.l
> gcc -o scanner lex.yy.c
> echo "x = -401" | ./scanner

RE and DFA (Deterministic Finite Automaton)

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

RE and DFA (Deterministic Finite Automaton)

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

How to turn RE into DFA?

How to turn RE into DFA?

• RE NFA DFA

DFA and NFA (Non-deterministic Finite Automaton)

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:

RE, DFA and NFA

• RE NFA DFA
  • For every NFA , there exists a DFA such that and accept the same language.
  • Let be a regular expression. Then there exists a DFA that accepts .
  • Let be a regular expression. Then there exists an NFA that accepts .

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

• 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