The Gateway to Computer Science Excellence

+34 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*

- Only S1
- Only S2
- Both S1 and S2
- Neither S1 and S2

+15

The given grammar is ambiguous as more than one parse tree 'c', and no LL(k) or LR(k) exist for any value of k.

+2

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

+47 votes

Best answer

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

+2

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

shouldnt it be first of F and H not disjoint??

shouldnt it be first of F and H not disjoint??

+2

By LR(1) do they mean SLR(1) parser or CLR(1) parser ??? I know this grammar is neither of both .. But in general LR(1) means SLR(1) right ?

0

I still didn't get it. The statement is:

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

G

i.e. we can have an LL(1) parser that can parse **all strings "generated" using** grammar G.

Strings generated by G is p, c and d.

So, Yes we can have an LL(1) parser that can parse these strings.

The question is **NOT** asking if the given grammar *itself* is LL(1)

+16 votes

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,170 answers

193,841 comments

94,047 users