LL(1) Grammar

• Definition: A simple BNF grammar is LL(1) if for all nonterminals X:
  if X appears on the left-hand side of two productions X=E1. and X=E2. then
  • first(E1) $\cap$ first(E2) = $\emptyset$.
  • either (neither E1 nor E2 is nullable)
    or (exactly one, say E1 is nullable and first(X) $\cap$ follow(E2) = $\emptyset$.
• LL(1) stands for "left-to-right-parse, leftmost derivation, 1 symbol lookahead".
• Recursive descent parsers work only for LL(1) grammars.
• Elimination of left recursion and left-factoring work often, but not always.