S- >aSb/A

A-> aA/epsilon

so it has a conflict first of S

?? may be

Dark Mode

Arjun
asked
in Compiler Design
Jan 26, 2019

1,059 views
5 votes

For which of the following languages a LL(1) grammar does not exist?

- $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$

- $\{ a^n b^m \mid m,n \geq 0 \}$

- $\{a^ib^j\mid i\geq j\}$

- $\{a^ib^j\mid i= j\}$

3 votes

An $LL(1)$ grammar has the following properties

- It should
**NOT**be ambiguous - It should
**NOT**have common prefix problem.(it should be left factored) - It should
**NOT**have left recursion.

The $LL(1)$ grammar for the given languages are as follows :-

Option $A.$

$\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$

$S \rightarrow aAb$

$A \rightarrow aAb| \epsilon | o$

Option $B.$

$\{ a^n b^m \mid m,n \geq 0 \}$

$S \rightarrow AB | \epsilon$

$A \rightarrow aA' $

$A' \rightarrow \epsilon | A $

$B \rightarrow bB' $

$A' \rightarrow \epsilon | B $

Option $C.$

$\{a^ib^j\mid i\geq j\}$

$S \rightarrow aS'$

$S' \rightarrow Sb | Ab$ ( Here $FIRST(S) \cap FIRST(A) \neq \phi $ )

$A \rightarrow aA' $

$A' \rightarrow \epsilon | A$

So this is $NOT$ a $LL(1)$ grammar.

Option $D.$

$\{a^ib^j\mid i= j\}$

if $i,j \geq 0 $

$S \rightarrow \epsilon |aSb$

if $i,j >0 $

$S \rightarrow aS'$

$S' \rightarrow b|Sb$

$\therefore$ For option $C$ we can't generate $LL(1)$ grammar.

0

I updated my answer.

**non-determinism** means that a grammar should not be like $A -> \alpha \beta_1 | \alpha \beta_2 $ type of productions...It will get confuse which production to use. This problem is solved using left factoring.

I think we can't directly look at a DCFL language and give a reason that it can't be LL(1) language. We have to write the grammar for the given language and after writing the grammar , we should try to make it non-ambiguous, left factored and non-left recursive.

if we succeed in doing this then the grammar that we get is a LL(1) grammar else if we are not able to follow any one of the constraints then it is not LL(1).

0

Well, thats not called non-determinism for grammar though the intention is correct.

And like a language can be inherently ambiguous - we can write an ambiguous grammar and try to make ti unambiguous - we can say from the language itself if it is not LL(1). That is why this question was made. Intuitive reasoning you already told as part of the given grammar.

And like a language can be inherently ambiguous - we can write an ambiguous grammar and try to make ti unambiguous - we can say from the language itself if it is not LL(1). That is why this question was made. Intuitive reasoning you already told as part of the given grammar.

2