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

Example

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)

References

https://en.wikipedia.org/wiki/LL_parser#Constructing_an_LL(1)_parsing_table