Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

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

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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.