CSE411: Introduction to Compilers

LL(*) and ALL(*)

Jooyong Yi (UNIST)

Early History of Parsing

  • Recursive Descent Parsing: Conway (1963)
  • LL(k): Lewis and Stearns (1968)
  • LR(k): Knuth (1965)
  • SLR and LALR: DeRemer (1971)
  • Yacc: well-known LALR(1) parser generator (1975)

LL(*) Parsing

s : ID                      (1)
  | ID '=' expr             (2)
  | 'unsigned'* 'int' ID    (3)
  | 'unsigned'* ID ID       (4)                                                                        

LL(1) table
-------------------------------------------------
   |  ID   | unassigned |   int   |   =   |  $  |
-------------------------------------------------   
s  |   ?   |            |         |       |     |
-------------------------------------------------

LL(*) Parsing

s : ID                      (1)
  | ID '=' expr             (2)
  | 'unsigned'* 'int' ID    (3)
  | 'unsigned'* ID ID       (4)                                                                        

LL(1) table
-------------------------------------------------
   |  ID   | unassigned |   int   |   =   |  $  |
-------------------------------------------------   
s  |  1,2  |            |         |       |     |
-------------------------------------------------

LL(*) Parsing

s : ID                      (1)
  | ID '=' expr             (2)
  | 'unsigned'* 'int' ID    (3)
  | 'unsigned'* ID ID       (4)                                                                        

LL(2) table
-------------------------------------------------
   |  ID $  | ID  =  | ....
-------------------------------------------------   
s  |    1   |   2    | ....
-------------------------------------------------

LL(*) Parsing

s : ID                      (1)
  | ID '=' expr             (2)
  | 'unsigned'* 'int' ID    (3)
  | 'unsigned'* ID ID       (4)                                                                        

LL(2) table
------------------------------------------------------------------------------
   |  ID $  | ID  =  | unsigned int | unsigned ID | unsigned unsigned |....
------------------------------------------------------------------------------
s  |    1   |   2    |       3      |      4      |        ?          |....
------------------------------------------------------------------------------

LL(*) Parsing

s : ID                      (1)
  | ID '=' expr             (2)
  | 'unsigned'* 'int' ID    (3)
  | 'unsigned'* ID ID       (4)
  • LL(*) uses a lookahead DFA to determine the next production to apply.

center

LL(*) Parsing

   t : '-'* ID                 (1)
     | expr ';'                (2)
expr : INT                     (3)
     | '-' expr                (4)
  • Backtracking is used when the lookahead DFA fails to determine the next production.

center

ALL(*): Adaptive LL(*)

  • Main observation
    • LL(*) builds a lookahead DFA for a given grammar.
    • LL(k) builds a parsing table for a given grammar.

ALL(*): Adaptive LL(*)

  • Main observation

    • LL(*) builds a lookahead DFA for a given grammar.
    • LL(k) builds a parsing table for a given grammar.

  • Key idea of ALL(*)

    • Build a lookahead DFA for a given input.
    • The lookahead DFA is built at runtime while performing parsing.

ALL(*): Adaptive LL(*)

S : A c                     (S.1)
  | A d                     (S.2)
A : a A                     (A.1)
  | b                       (A.2)
  • Consider inputs b c and b d.

ALL(*): Adaptive LL(*)

S : A c                     (S.1)
  | A d                     (S.2)
A : a A                     (A.1)
  | b                       (A.2)
  • Consider inputs b c and b d.
Static Dynamic
center center

Reflection

Compare LL(k) and LL(*)

  • Think about runtime overhead and flexibility.

Compare LL(*) and ALL(*)

  • Think about runtime overhead and flexibility.

References