Compiler: Bottom Up Parser

Question

Given answer is (D), how?

Comments

Option D) If stack contain $aaS$, then on reading $aaS$ from start state we reaches state containing $S->aS.$ which is a reduce item hence it will reduce to this production.

Option A) and Option B)  Reading this we reaches state containing three items but none of them is reduce one

Option C) There is no path defined for $aa$

---

only b can also cause reduction,right ?

---

yes. only b can also cause reduction.

---

can someone explain step  by step?

---

This is how actually parser works!

Name states 0,1,2,3 from top to bottom and left to right(According to given diagram)

on stack initially 0 state will be present.And as you start reading characters first input will be started from 0th state.

so 0->a->1->a->1->S ->4(reduce) (Recall that in the table 4th state will have all R's since this is LR(0) )

Follow this link

https://www.cs.colostate.edu/~cs453/yr2014/Slides/12-LR0-SLR.ppt.pdf

---

@Ashwin Kulkarni How?
why not D?

---

Look at grammar,Can you generate bb?

---

@skby
It is written in question reduction can only done if and only if there is path labelled from start state...... here path is $bb$ which is not possible in given automation. 

---

I'm sorry I was asking for D

---

option D) is correct...!!

---

I was saying about string "b".

Yes option D is correct!!

I was not saying about option B :p

Answer 1

look at my assumption ,

we know that every  BOTTOM  PARSER is an DCFL ,that means STACK can be used.

now, push the non terminals into stack  WHICH ARE ONLY derivable from the given grammer  llike we do in PUSH DOWN AUTOMETA.

1) SINGLE  "a" cannot be derived from the G, eliminate it .

2)cannot  END with "a" and more over  starting symbol doesnt have  EPSILON production ,SO eliminate it

3) TWO "b"s cannot be derived from the grammer ,so eliminate it

4)  THIS can be derived,now push the string into the  STACK , this string can be satisfied by PDA by popping up of any number of  a's  when b is on the top of the stack

              push aas into the stack by taking 

              S ->aS/b

 but , SINGLE   'b' can also be derivable and accepted by PDA ,it can also be an ANSWER if it is in the given in options

Answer 2

Assume that we are using bottom up parser using stack,answer will be option D.check this,