LL(k) Parsing

  • LL1 Parsing
    • Determine if grammar is LL1 (A -> a | b)
      • FIRST(a) ^ FIRST(b) = null
        • both a and b do not lead to string start with c
        • a and b can not both lead to epsilon epsilon
      • If b leads to epsilon, FIRST(a) and FOLLOW(A) does not intersect.
    • Ambiguity quick check
      • Left Refactored
      • No Left Recursive
      • Ambiguous
      • Still may not be LL(1)

Most PL CFGs are not LL(1)

For each production A → a in G do:

- For each terminal t in First(a) do
    T[A, t] = a

- If ep in First(a), for each t in Follow(A) do
    T[A, t] = a

- If ep in First(a) and $ in Follow(A) do
    T[A, $] = a