Redirected
recategorized by
1,916 views
0 votes
0 votes

Consider the following grammar $G$:

  • $S \rightarrow A \mid B$
  • $A \rightarrow a \mid c$
  • $B \rightarrow b \mid c$

where $\{ S, A, B\}$ is the set of non-terminals, $\{ a, b, c, \}$ is the set of terminals.

Which of the following statement(s) is/are correct?

  • $S_1$: $LR(1)$ can parse all strings that are generated using grammar $G$.
  • $S_2$: $LL(1)$ can parse all strings that are generated using grammar $G$.

Choose the correct answer from the code given below:

  1. Only $S_1$
  2. Only $S_2$
  3. Both $S_1$ and $S_2$
  4. Neither $S_1$ nor $S_2$
recategorized by

2 Answers

2 votes
2 votes

Neither S1 nor S2.

 

S1: LR(1) parser will have Reduce -Reduce conflict. In Initial state, due to shift on terminal 'c'  two productions will go to the same state, Productions A->c . , $ and B -> c . , $  under the same lookaheads and results in R-R conflict.

 

S2: It is not LL(1), Under S, we have two production for terminal c.

 

2 votes
2 votes
First(A) = {a,c}

First(B) = {b,c}

S → A | B ===> First(A) ∩ First(B) ≠ ∅ ===> it can't be LL(1)

 

Checking LR(1) or NOT ? just construct LR(1) items

Item 0 :-

     S'  → S, \$

     S → .A, \$

     S → .B, \$

     A → .a, \$

     A → .c, \$

     B → .b, \$

     B → .c, \$

 

on this item, with terminal c, we will go to, let Item K,

Item K :-

     A → c., \$

     B → c., \$

Which is Reduce - Reduce Conflict ==> can't be parsed by LR(1)

 

PS :- the string "c" have more than one Left Most derivation ==> Ambiguous grammar ==> can't be either LL(1) or LR(1)
edited by
Answer:

Related questions

11 votes
11 votes
1 answer
1
0 votes
0 votes
2 answers
2
Arjun asked Jan 2, 2019
2,361 views
​​​​​Match List-I with List-II and choose the correct answer from the code given below :$\begin{array}{|c|c|c|c|} \hline & \textbf{List I} & & \textbf{List II} ...
1 votes
1 votes
1 answer
3
Arjun asked Jan 2, 2019
5,632 views
​​A box contains six red balls and four green balls. Four balls are selected at random from the box. What is the probability that two of the selected balls will be re...