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

A grammar can not be parsed by any parse if it is ambiguous. how to check if it is ambiguous? the only way possible is by deriving a non terminal using 2 parse trees.

---

If we construct the LR(1) parser for the given grammar we will get a reduce-reduce conflict for the string c$.

Correct me, if I am wrong.

---

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

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

What is the problem for grammar being ambiguous?

---

Sir , ambiguous grammar can not be parsed by top down or bottom up parsers right?

---

Yes, but operator precedence parser(a Bottom-up parser) can parse some of the ambiguous grammars, although LR and LL parsers cant.

---

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

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