HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
suchdeterminingminimumthatstronggrammarlookaheadset

Problem

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$

Solution

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$:



  • Check wether $G$ is $LL(n)$



  • If so, try proving $G$ is $LL(n)$



  • 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

Context

StackExchange Computer Science Q#10245, answer score: 2

Revisions (0)

No revisions yet.