CSE411

CSE411: Introduction to Compilers

LL(1) Parsing

Jooyong Yi (UNIST)

2026 Fall
CSE411

Table-Based Parsing

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |
T  |  F T' |        |       | F T'  |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |
F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------
  • Parse (int + int) * int
2026 Fall
CSE411
Stack Remaining input Action
E $ ( int + int ) * int $ δ[E, (] = T E'
T E' $ ( int + int ) * int $ δ[T, (] = F T'
F T' E' $ ( int + int ) * int $ δ[F, (] = ( E )
( E ) T' E' $ ( int + int ) * int $ Match (
E ) T' E' $ int + int ) * int $ δ[E, int] = T E'
T E' ) T' E' $ int + int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' $ int + int ) * int $ δ[F, int] = int
int T' E' ) T' E' $ int + int ) * int $ Match int
T' E' ) T' E' $ + int ) * int $ δ[T', +] = ε
E' ) T' E' $ + int ) * int $ δ[E', +] = + T E'
+ T E' ) T' E' $ + int ) * int $ Match +
T E' ) T' E' $ int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' $ int ) * int $ δ[F, int] = int
int T' E' ) T' E' $ int ) * int $ Match int
T' E' ) T' E' $ ) * int $ δ[T', )] = ε
E' ) T' E' $ ) * int $ δ[E', )] = ε
) T' E' $ ) * int $ Match )
T' E' $ * int $ δ[T', *] = * F T'
* F T' E' $ * int $ Match *
F T' E' $ int $ δ[F, int] = int
int T' E' $ int $ Match int
T' E' $ $ δ[T', $] = ε
E' $ $ δ[E', $] = ε
$ $ Accept
2026 Fall
CSE411

Table-Based Parsing

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |
T  |  F T' |        |       | F T'  |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |
F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------
  • Parse ((int + int) * int
2026 Fall
CSE411
Stack Remaining input Action
E $ ( ( int + int ) * int $ δ[E, (] = T E'
T E' $ ( ( int + int ) * int $ δ[T, (] = F T'
F T' E' $ ( ( int + int ) * int $ δ[F, (] = ( E )
( E ) T' E' $ ( ( int + int ) * int $ Match first (
E ) T' E' $ ( int + int ) * int $ δ[E, (] = T E'
T E' ) T' E' $ ( int + int ) * int $ δ[T, (] = F T'
F T' E' ) T' E' $ ( int + int ) * int $ δ[F, (] = ( E )
( E ) T' E' ) T' E' $ ( int + int ) * int $ Match second (
E ) T' E' ) T' E' $ int + int ) * int $ δ[E, int] = T E'
T E' ) T' E' ) T' E' $ int + int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' ) T' E' $ int + int ) * int $ δ[F, int] = int
int T' E' ) T' E' ) T' E' $ int + int ) * int $ Match int
T' E' ) T' E' ) T' E' $ + int ) * int $ δ[T', +] = ε
E' ) T' E' ) T' E' $ + int ) * int $ δ[E', +] = + T E'
+ T E' ) T' E' ) T' E' $ + int ) * int $ Match +
T E' ) T' E' ) T' E' $ int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' ) T' E' $ int ) * int $ δ[F, int] = int
int T' E' ) T' E' ) T' E' $ int ) * int $ Match int
T' E' ) T' E' ) T' E' $ ) * int $ δ[T', )] = ε
E' ) T' E' ) T' E' $ ) * int $ δ[E', )] = ε
) T' E' ) T' E' $ ) * int $ Match inner )
T' E' ) T' E' $ * int $ δ[T', *] = * F T'
* F T' E' ) T' E' $ * int $ Match *
F T' E' ) T' E' $ int $ δ[F, int] = int
int T' E' ) T' E' $ int $ Match int
T' E' ) T' E' $ $ δ[T', $] = ε
E' ) T' E' $ $ δ[E', $] = ε
) T' E' $ $ Error: expected ), found end of input
2026 Fall
CSE411

How to construct a parsing table?

2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |       |        |       |       |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       |        |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |       |        |       |       |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        |       |       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |       |        |       |       |     |     |
-------------------------------------------------     -------------------------------------------------
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |       |        |       |       |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       |        |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |       |        |       |       |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        |       |       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |       |        |       |       |     |     |
-------------------------------------------------     -------------------------------------------------
  • Where should T E' be placed in the parsing table?
  • Is E => T E' => ... => int ... possible?
  • Is E => T E' => ... => ( ... possible?
  • Is E => T E' => ... => + ... possible?
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |       |        |       |       |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       |        |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |       |        |       |       |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        |       |       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |       |        |       |       |     |     |
-------------------------------------------------     -------------------------------------------------
  • Is E => T E' => ... => int ... possible?
  • Is E => T E' => ... => ( ... possible?
  • Is E => T E' => ... => + ... possible?
  • What terminal can T E' start with?
2026 Fall
CSE411

FIRST(T E')

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)
  • FIRST(T E') = FIRST(T) = FIRST(F T') = FIRST(F) = {int, (}
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |  T E' |        |       |  T E' |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       |        |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |       |        |       |       |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        |       |       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |       |        |       |       |     |     |
-------------------------------------------------     -------------------------------------------------
  • FIRST(T E') = FIRST(T) = FIRST(F T') = FIRST(F) = {int, (}
2026 Fall
CSE411

Computing FIRST

FIRST() for is defined as follows:

  • If (i.e., is a terminal), then
  • If is a production of the given grammar , then
  • Suppose (i.e., is a nonterminal) and production (where ) exists in the given grammar .
    • If , then
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |  T E' |        |       |  T E' |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       | + T E' |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |  F T' |        |       |  F T' |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        | * F T'|       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------     -------------------------------------------------
  • FIRST(+ T E') = {+}
  • FIRST(F T') =
  • FIRST(* F T') = {*}
  • FIRST(int) = {int},
  • FIRST((E)) = {(}
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |  T E' |        |       |  T E' |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       | + T E' |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |  F T' |        |       |  F T' |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        | * F T'|       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------     -------------------------------------------------
  • FIRST(+ T E') = {+}
  • FIRST(F T') = FIRST(F) = {int, (}
  • FIRST(* F T') = {*}
  • FIRST(int) = {int}
  • FIRST((E)) = {(}
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |  T E' |        |       |  T E' |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       | + T E' |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |  F T' |        |       |  F T' |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        | * F T'|       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------     -------------------------------------------------
  • Where should ε be placed in the parsing table?
2026 Fall
CSE411
  • When is ε used?
Stack Remaining input Action
E $ ( int + int ) * int $ δ[E, (] = T E'
T E' $ ( int + int ) * int $ δ[T, (] = F T'
F T' E' $ ( int + int ) * int $ δ[F, (] = ( E )
( E ) T' E' $ ( int + int ) * int $ Match (
E ) T' E' $ int + int ) * int $ δ[E, int] = T E'
T E' ) T' E' $ int + int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' $ int + int ) * int $ δ[F, int] = int
int T' E' ) T' E' $ int + int ) * int $ Match int
T' E' ) T' E' $ + int ) * int $ δ[T', +] = ε
E' ) T' E' $ + int ) * int $ δ[E', +] = + T E'
+ T E' ) T' E' $ + int ) * int $ Match +
T E' ) T' E' $ int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' $ int ) * int $ δ[F, int] = int
int T' E' ) T' E' $ int ) * int $ Match int
T' E' ) T' E' $ ) * int $ δ[T', )] = ε
E' ) T' E' $ ) * int $ δ[E', )] = ε
) T' E' $ ) * int $ Match )
T' E' $ * int $ δ[T', *] = * F T'
* F T' E' $ * int $ Match *
F T' E' $ int $ δ[F, int] = int
int T' E' $ int $ Match int
T' E' $ $ δ[T', $] = ε
E' $ $ δ[E', $] = ε
$ $ Accept
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |  T E' |        |       |  T E' |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       | + T E' |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |  F T' |        |       |  F T' |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        | * F T'|       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------     -------------------------------------------------
  • Where should ε be placed in the parsing table?
  • Is T'...=> +... possible?
  • Is E'...=> )... possible?
2026 Fall
CSE411

Parsing Table Construction

E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                                

-------------------------------------------------     -------------------------------------------------
   |  int  |  +     |   *   |  (    |  )  |  $  |        |  int  |  +     |   *   |  (    |  )  |  $  |
-------------------------------------------------     -------------------------------------------------   
E  |  T E' |        |       | T E'  |     |     |     E  |  T E' |        |       |  T E' |     |     |
E' |       | + T E' |       |       |  ε  |  ε  |     E' |       | + T E' |       |       |     |     |
T  |  F T' |        |       | F T'  |     |     |     T  |  F T' |        |       |  F T' |     |     |
T' |       |  ε     | * F T'|       |  ε  |  ε  |     T' |       |        | * F T'|       |     |     |
F  |  int  |        |       |  (E)  |     |     |     F  |  int  |        |       |  (E)  |     |     |
-------------------------------------------------     -------------------------------------------------
  • Is T'...=> +... possible?
  • Is E'...=> )... possible?
  • What terminal can follow T'? What terminal can follow E'?
2026 Fall
CSE411

Computing FOLLOW

for is defined as follows:

  • If is the start nonterminal, then .
  • If there exists a production , then _________
2026 Fall
CSE411

Computing FOLLOW

for is defined as follows:

  • If is the start nonterminal, then .
  • If there exists a production , then
2026 Fall
CSE411

Computing FOLLOW

for is defined as follows:

  • If is the start nonterminal, then .
  • If there exists a production , then
  • If there exists a production , then __________
2026 Fall
CSE411

Computing FOLLOW

for is defined as follows:

  • If is the start nonterminal, then .
  • If there exists a production , then
  • If there exists a production , then
2026 Fall
CSE411

Computing FOLLOW

for is defined as follows:

  • If is the start nonterminal, then .
  • If there exists a production , then
  • If there exists a production , then
  • If there exists a production and ,
    then __________
2026 Fall
CSE411

Computing FOLLOW

for is defined as follows:

  • If is the start nonterminal, then .
  • If there exists a production , then
  • If there exists a production , then
  • If there exists a production and ,
    then
2026 Fall
CSE411
  • If is the start nonterminal, then .
  • If there exists a production , then
  • If there exists a production , then
  • If there exists a production and ,
    then 
E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                  

---------------------------------
    |   FIRST    |    FOLLOW    
---------------------------------    
 E  | {int, (}   |  {$
 E' | {+, ε}     |
 T  | {int, (}   |
 T' | {*, ε}     |
 F  | {int, (}   |
---------------------------------
2026 Fall
CSE411
  • If is the start nonterminal, then .
  • If there exists a production , then
  • If there exists a production , then
  • If there exists a production and ,
    then 
E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                  

---------------------------------
   FIRST    |    FOLLOW    
---------------------------------    
 E  | {int, (}   |  {$, )}
 E' | {+, ε}     |  {$, )} 
 T  | {int, (}   |  {+, $, )}
 T' | {*, ε}     |  {+, $, )}
 F  | {int, (}   |  {*, +, $, )}                                                                
---------------------------------
2026 Fall
CSE411
E : T E'
E': + T E' | ε
T : F T'
T': * F T' | ε
F: int | (E)                                                                                                

---------------------------------
   FIRST    |    FOLLOW    
---------------------------------    
 E  | {int, (}   |  {$, )}
 E' | {+, ε}     |  {$, )} 
 T  | {int, (}   |  {+, $, )}
 T' | {*, ε}     |  {+, $, )}
 F  | {int, (}   |  {*, +, $, )}                                                                
---------------------------------            

-------------------------------------------------  
   |  int  |  +     |   *   |  (    |  )  |  $  |  
-------------------------------------------------  
E  |  T E' |        |       | T E'  |     |     |  
E' |       | + T E' |       |       |  ε  |  ε  |  
T  |  F T' |        |       | F T'  |     |     |  
T' |       |  ε     | * F T'|       |  ε  |  ε  |  
F  |  int  |        |       |  (E)  |     |     |  
-------------------------------------------------
2026 Fall
CSE411

Parsing Table Construction Algorithm

  • For each production in grammar do:
    • for each terminal do:
    • If , for each
2026 Fall
CSE411

LL(1) Parsing

  • The first L: scanning from left to right.
  • The second L: using the left-most derivation.
  • 1: using one lookahead token.
2026 Fall
CSE411
  • Does the following perform the left-most derivation?
Stack Remaining input Action
E $ ( int + int ) * int $ δ[E, (] = T E'
T E' $ ( int + int ) * int $ δ[T, (] = F T'
F T' E' $ ( int + int ) * int $ δ[F, (] = ( E )
( E ) T' E' $ ( int + int ) * int $ Match (
E ) T' E' $ int + int ) * int $ δ[E, int] = T E'
T E' ) T' E' $ int + int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' $ int + int ) * int $ δ[F, int] = int
int T' E' ) T' E' $ int + int ) * int $ Match int
T' E' ) T' E' $ + int ) * int $ δ[T', +] = ε
E' ) T' E' $ + int ) * int $ δ[E', +] = + T E'
+ T E' ) T' E' $ + int ) * int $ Match +
T E' ) T' E' $ int ) * int $ δ[T, int] = F T'
F T' E' ) T' E' $ int ) * int $ δ[F, int] = int
int T' E' ) T' E' $ int ) * int $ Match int
T' E' ) T' E' $ ) * int $ δ[T', )] = ε
E' ) T' E' $ ) * int $ δ[E', )] = ε
) T' E' $ ) * int $ Match )
T' E' $ * int $ δ[T', *] = * F T'
* F T' E' $ * int $ Match *
F T' E' $ int $ δ[F, int] = int
int T' E' $ int $ Match int
T' E' $ $ δ[T', $] = ε
E' $ $ δ[E', $] = ε
$ $ Accept
2026 Fall