# How to generate an LL(2) parse table?

The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that:

predict(nonterminal, production) ==
if epsilon in FIRST(production):
first(production) union follow(nonterminal)
else:
first(production)


where production is a sequence of symbols which can include nonterminals, terminals, and epsilon.

what's the algorithm for an LL(2) parse table?

## 1 Answer

There is a pretty reasonable discussion in this essay from the SLK parser generator.

Basically, you just need to extend $$FIRST$$ and $$FOLLOW$$ to be $$FIRST_k$$ and $$FOLLOW_k$$, meaning the first / following $$k$$ symbols. The basic principle is the same, but when $$k > 1$$ there is a complication, leading to the distinction between "strong" and regular grammars.

The naming is a bit counterintuitive; the parsing table for a strong grammar can be generated by an easier but less powerful algorithm, so the strong grammars are in a sense weaker; they make a stronger guarantee about predictability.