snippetMinor
How to generate an LL(2) parse table?
Viewed 0 times
generatetableparsehow
Problem
The algorithms I've seen for building an LL(1) parse table involve calculating
where production is a sequence of symbols which can include nonterminals, terminals, and epsilon.
what's the algorithm for an LL(2) parse table?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#71420, answer score: 2
Revisions (0)
No revisions yet.