GATE CSE 2015 | Set 3 | Question: 31

Question

Consider the following grammar G

$S  \rightarrow F \mid H$

$F \rightarrow p \mid c$

$H \rightarrow d \mid c$ 

Where $S$, $F$, and $H$ are non-terminal symbols, $p, d$, and $c$ are terminal symbols. Which of the following statement(s) is/are correct?

S1: LL(1) can parse all strings that are generated using grammar G

S2: LR(1) can parse all strings that are generated using grammar G

• A. Only S1
• B. Only S2
• C. Both S1 and S2
• D. Neither S1 and S2

Comments

Given, grammars are ambiguous so neither LL(1) nor LR(1) can handle it .

---

Also another shortcut method for that types of pattern F -> S|H , ambiguious if -> [First(S) Intersection First(H) != ϕ]

---

$\text{Given Grammar is Ambiguous, and  LL(1) and LR(k) parsers can't }$ $\text{ parse ambiguous grammars, only the Operator Precedence parser}$$\text{ can parse some Ambiguous Grammars.}$

Answer 1

A parser works on the basis of given grammar. It takes the grammar as it is. Parser does not work on the basis of the yield of the grammar. Also, while constructing the LL(1) parser table, that entry for terminal 'c' will contain multiple entries. So, LL(1) parser cannot be constructed for the given grammar.

$S  \rightarrow F | H$

$F \rightarrow p | c$

$H \rightarrow d | c$ 

That $\{p, d, c\}$ are the strings generated by the grammar is absolutely correct. But LL(1) and LR(1) can parse these strings successfully only if the grammar is unambiguous and like given below...

$S \rightarrow P | D | C$

$P \rightarrow p$

$D \rightarrow d$

$C \rightarrow c$

Please note the difference between these two grammars. Both derive the same strings, but in different manner. With the grammar given in the question, both top-down and bottom-up parsers will get confused while deriving "$c$". Top-down parser will get confused between $F \rightarrow c$  and $H \rightarrow c$. Similarly, bottom-up parser will get confused while reducing "$c$". This confusion in case of bottom-up parsing is technically termed as "reduce-reduce" conflict. 

While top-down parsing, first(F) and first(H) are not disjoint, so the grammar cannot be LL(1). Therefore, LL(1) parser cannot parse it.

Hence, the answer should be option (D). Neither S1 nor S2.

Comments

No ...LL(1) grammar means for that grammar there is LL(1) parser takes grammar as input and generates parsing table that will be used to parse the strings generated by that given grammar without any conflicts.

---

And how is the parsing table constructed ? Using grammar itself right ?

---

@Rishabh Gupta 2 what a great point. But it says “using” grammar G, otherwise, it would have been possible. I literally ignored that fact. Thanks

Answer 2

Answer is D

Grammar is ambiguous

Comments

string “C” is producing more than one time by parser tree

---

if Grammar is ambiguous, the top down parser cannot appropriately choose which production to apply to derive string from S.  In case of LL(1) parser, it can take decision only once (as no backtracking), and hence, ambiguity creates problem.

Similarly, in case of Bottom Up parser, parser may not be able to  choose the appropriate handle if grammar is ambiguous.

is it correct @Arjun sir?

---

D 💯 NOT LL1

NOT LR1

Answer 3

For $LL(1),$
For first production,

So, there is '$c$ ' common in both the $first(s)$ in the production of $S.$ So not $LL(1).$
For $LR(1),$

Since $R-R$ conflict is present. So, not $LR(1).$
Hence, Option $(D)$ is the correct answer.

Answer 4

S -> F -> c

S -> H -> c 

since two parse trees are possible grammar is ambiguous and cannot be accepted by either LL(1) or LR(1).Only operator precedence parser have the ability to parse some ambigous grammar.

Comments

Grammar is ambiguous then s1 and s2 both are false ans D

Answer 5

.....

Comments

Nicely explained!!

Answer 6

For deriving a terminal c ,we have S-> F->c and S->H->c . There are two parse trees for same terminal c.Hence the grammar is ambiguous and can't be LL1 or LR1