# Explaining why a grammar is not LL(1)

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?

-
Compute the LL(1) parse table and use it to answer the question. Your grammar is LL(1) if each cell in the table has at most 1 grammar rule. In other words, at least one table entry has more than 1 rule implies that your grammar is not in LL(1): en.wikipedia.org/wiki/… –  saadtaame Jan 4 '13 at 17:25

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 $S\To^* uAv \To uax$, we must have used unique $A\to\alpha$, 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.

-

If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1).

In general, you compute the LL(1) parse table and use it to answer the question. Your grammar is LL(1) if each cell in the table has at most 1 grammar rule. In other words, at least one table entry has more than 1 rule implies that your grammar is not in LL(1): http://en.wikipedia.org/wiki/LL_parser#Constructing_an_LL.281.29_parsing_table

-
Isn't there any properties of the LL(1)-grammars, that you can check if violated ? –  mrjasmin Jan 4 '13 at 17:39

No left recursion in an LL(1) grammar.

A grammar with A → αβ1 | αβ2 is not LL(1).

If any entry is multiply defined then G is not LL(1). Possible reasons:  If G is ambiguous  If G is left recursive  If G is not left-factored  Grammar is not LL(1)

-