Explaining why a grammar is not LL(1)

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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)

Answer 4

This grammar is not LL(1) due to the production: $S\;\rightarrow \varepsilon$. In fact, for a grammar to be LL(1) in the presence of an alternative which can drive the empty string, the others should not begin with a follower of the non terminal in the left hand of the production rule ($S$ here); But in this case, the followers of $S$ are: $FOLLOW(S) =\{a,b,\#\}$, and, sadly, the two other productions begin both with a follower of $S$.
Hope this help.
Good Luck!

Answer 5

Grammar should follow below rules to be LL(1)

1. It should not be Ambiguous.(Remove Ambiguity)
2. It should not be Left Recursive.(Remove Left Recursion)
3. It should not be a Non-deterministic.(Apply Left Factoring)

If any of the above rule is not satisfied then grammar is not LL(1). But if grammar follows all of above rules then we have to check following thing

• Dose Parsing table have more than one entry in one cell.

How to check this then?

If there is epsilon production and first and follow have intersection then grammar is not LL(1)

In your grammar S have a epsilon production follow and first have intersection.