LL Parser Uses Leftmost Derivation

LL parser, as given by Interpreting LL Parsing Table

  • decides what production to use
  • uses stack to remember this right-hand side

Parsing is opposite of grammar derivation

For grammar

E ::= T | T + E
T ::= ID

a leftmost derivation of ID+ID+ID from E is:

 T +  E
ID +  E
ID +  T +  E
ID + ID +  E
ID + ID +  T
ID + ID + ID

When LL parser considers this step

ID +  E


  • 'ID' was in the input and parser checked it was there
  • it keeps '+ E' on stack (reversed) to remember what remains to be parsed

LL parser decides which production to take immediately when seeing the non-terminal on top of stack

  • then expects to see this right-hand side in input