3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.