edited by
15,095 views
45 votes
45 votes

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

  1. Only S1
  2. Only S2
  3. Both S1 and S2
  4. Neither S1 and S2
edited by

5 Answers

Best answer
72 votes
72 votes

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.

edited by
30 votes
30 votes
Answer is D

Grammar is ambiguous
15 votes
15 votes

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.

9 votes
9 votes

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.

Answer:

Related questions

29 votes
29 votes
2 answers
1