LL parser / What is LL(n)

Top-down parser. Parses input from Left to right. Constructs a Leftmost derivation of the sentence.

The notation LL(n) means that the Parser looks ahead n tokens when parsing a sentence.

LL(1) are of great practical interest, since they are easy to construct and many languages are designed to be LL(1) because of this.

Implementation can be using:

  • table parsers
  • recursive descent parsers


Grammar, G

S -> E
E -> (E + E)
E -> i

Leftmost derivation for w = ((i + i) + i) is: S => E => (E + E) => ((E + E) + E) => ((i + E) + E) => ((i + i) + E) => ((i + i) + i)