[Solved]: Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

Problem Detail: 

How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar

Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$

Asked By : Iancovici

Answered By : Andrew

I do not believe one can obtain directly a minimum $k$ such that $G$ is a strong $LL(k)$ grammar. However, as it is possible to (dis)prove that a grammar is strong $LL(k)$, one can iterate the proof over $k$.

A grammar $G$ is strong $LL(k)$ iff for every pair of distinct production rules $A \to \alpha$ and $A \to \beta$ (with $\alpha \neq \beta$), we have:

$$ First_k( \alpha \; Follow_k(A) ) \; \cap \; First_k( \beta \; Follow_k(A) ) = \emptyset $$

The steps to obtain a $k$ for a certain grammar $G$ are thus as follows:

• For each $n > 0$:
  1. Check wether $G$ is $LL(n)$
  2. If so, try proving $G$ is $LL(n)$
  3. If not, we have found our $k = n - 1$

Some documents that might help with the actual proof:

• About first and follow sets (LL(1))
• Obtaining first and follow sets (LL(k)) with example

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10245

3.2K people like this

 Download Related Notes/Documents