Problem Detail: I need some help with explaining why a grammar is not LL(1). Let us take the following grammar: $$ begin{align} S rightarrow & aB mid bA mid varepsilon A rightarrow & aS mid bAA B rightarrow & b end{align} $$ This is my attempt: For the grammar to be LL(1) it is a necessary condition that for any strings $c_1γ$ and $c_2β$, derivable from $S rightarrow aB$ and $A rightarrow aS$ respectively, we have $c_1 ne c_2$. But, $S rightarrow aB$ and $A rightarrow aS$, hence $c_1 = c_2$ and the grammar is not LL(1). Is my reasoning right? Thanks in advance.
Asked By : mrjasmin
Answered By : Hendrik Jan
I am afraid your reasoning is not exactly right. A grammar is LL(1) if we can predict the production used from the current nonterminal $A$ to be rewritten and the next terminal $a$ in the string. $newcommand{To}{Rightarrow}$ Using $To$ to denote leftmost derivation, if $STo^* uAv To uax$, we must have used unique $Atoalpha$, independent on $x$. The problem that usually arizes is when $A$ is rewitten into $varepsilon$ and $a$ is produced by the next nonterminal. Try to construct another example.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7761
