Definition. LL(1) Condition

2025-01-24 ยท parsing LL

A context-free grammar satisfies the LL(1) condition if it satisfies the following three conditions:

  • All of its productions have pairwise disjoint first sets
  • If a concatenation of nonterminals ๐ดโŠ—๐ต appears in a production, then ๐ด has a disjoint followlast set from the first set of ๐ต
  • At most one production is nullable

This is essentially the type system of [1], which characterizes the LL(1) condition for context-free expressions.

Intutively, an LL(1) grammar can be parsed unambiguously, and without backtracking, by a predictive parser that only needs one token of lookahead.

References

A typed, algebraic approach to parsing โ†—
ll1-condition definition entries/parsing/ll1-condition.hel