The Gateway to Computer Science Excellence
+34 votes
3.6k views

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
in Compiler Design by Veteran (105k points)
edited by | 3.6k views
+16
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.
+1
@Manu sir

How can you say that the given grammar is ambiguous??
+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
0
In this Question as we can see it is Ambiguous Grammar than can we directly declare that it is not  LL(1) as well as LR(1).
I  know that ambiguous grammar can't be LL(1) But is it also true for LR(1)?
0
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.

4 Answers

+48 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.

by (341 points)
edited by
0
If we do CLR(1) parser then also it is not possible?
+4
+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??
+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 ?
+6
0
yeah thank u ...got it ...
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)

0
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.
+1
And how is the parsing table constructed ? Using grammar itself right ?
+16 votes
Answer is D

Grammar is ambiguous
by Active (1.2k points)
0
What is the problem for grammar being ambiguous?
+12
Sir , ambiguous grammar can not be parsed by top down or bottom up parsers right?
+5
Yes, but operator precedence parser(a Bottom-up parser) can parse some of the ambiguous grammars, although LR and LL parsers cant.
+6 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.

by Active (2k points)
0
Grammar is ambiguous then s1 and s2 both are false ans D
0 votes
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
by (405 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,500 answers
195,548 comments
101,003 users