GATE Overflow | Compiler Design | Test 1 | Parsing | Question: 9

Question

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

• A. $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n  b^{n} \mid n \geq 1 \}$
  
• B. $\{ a^n b^m \mid m,n \geq 0 \}$
  
• C. $\{a^ib^j\mid i\geq j\}$
  
• D. $\{a^ib^j\mid i= j\}$

Comments

but in the question it's not mentioned whether i>=0 or j>=0 @abhishek

---

What is the ans? and why?

---

@aditi19

A language can have many grammars but a grammar can produce only 1 language.

Answer 1

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

1. It should NOT be ambiguous
2. It should NOT have common prefix problem.(it should be left factored)
3. 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.

Comments

@Arjun Sir, please check the answer.

---

It should NOT have non-determinism

What does non-determinism mean for a grammar?

Rest part of the answer is fine though why C does not have ant LL(1) grammar can have some reasoning.

---

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).

 

 

---

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.