Ace Test Series: Compilers - Parsers

Question

 

Comments

I'm not sure

C ??

---

Why are you not sure? This is a question with a procedure- you should have some answer rt?

---

Yes sir

What  I did RL(1) ---- left most derivation and scan the input from right hand side and  reduce accordingly

And got C

---

No. Leftmost derivation in reverse and rightmost derivation in reverse are not the same. Here, you have to do rightmost derivation in reverse.

---

Also, how will you detect Shift-Reduce or Reduce-Reduce conflicts?

---

But sir here it's given SRL(1) 

Not LR

---

I missed it - but is there such a parser?

---

$.aabbcc  \rightarrow a.abbcc  \rightarrow aa.bbcc  \rightarrow aab.bcc  \rightarrow aabb.cc  \rightarrow aabbc.c  \rightarrow aabbB.c  \rightarrow aabB.c  \rightarrow aaA.c  \rightarrow aA.c  \rightarrow A.c  \rightarrow Ac. \rightarrow AB. \rightarrow S. $

$Option \ C \Rightarrow B,B,A,A,A,B,S$

---

we can do it also by drawing dfa of slr parsing table and then using stack parse the input

---

@Soumya29 Why "bB" reduced to B and not A?

---

we can just draw a derivation tree. because its SLR(1) grammar, it should be unambiguous, which means you will have only one such tree possible.

now move from bottom to top by reducing right before left. you should get the answer.

---

I solved this question using handles as :  

@Arjun  Please verify it sir :

 

 

---

You cannot take such decisions to reach start symbol - must follow the SLR parsing table which needs to be made.

---

Ohk sir, but why cant we take decision that which will be reduced using handles ?

I also did using RMD in reverse and got answer as C

---

Sir wants to ask how are you making decisions while reducing bB

---

@Arjun sir, Using SLR(1) parsing table i tried to parse the above string.. no reduce reduce conflict was there..Only one B -> bB reduce move was possible.

By making DFA for it, i made sure that this grammar is LR(0) and so SLR(1), LALR(1) and LR(1) too. After that I just parsed the strings by reducing at "handles" only..

---

Answer c

Answer 1

As, None of the option says "Grammar is not SLR(1)", I am directly trying to parse the string here.

Try to derive the string from the given productions, by following Right most derivation.(Cause we are dealing with bottom-up parsers,this is useful at the end)

S->AB (B is bolded to indicate that it is expanding in the next step)

  ->Ac (you can see, we are producing 'B' first, as we are following Right most derivation)

  ->aAc

  ->aaAc

  ->aabBc

  ->aabbBc

  ->aabbcc

Now, start looking, bottom up, just like how, bottom up parsers do: Right most derivation in reverse.

We can observe the order : B,B,A,A,A,B,S.

So,  C is correct choice.

 

Comments

Can we same procedure for a given grammar,input string and any one of the lr parsers(lr(0),lr(1),lalr(1)),when asked to find the reduction order?