Action table SLR(0) parser

Question

Hello,

I have a question regarding the computation of the action table of SLR(0) parser.

Considering the FSA, I make the following steps to compute the action table:

1. "accept" in the $ column of the state that contains the item S' --> S.
2. Shifts and GoTos by considering all edges

Now I struggle with the reductions and I have the following questions:

1. Of course only the states that have no outgoing edges (if there are no conflicts) may contain reductions, but why do the b and $ columns always contain the same reductions and the a column never contains one?
2. Is it right that there is a R/S conflict in stat q3 because there is a Shift and a Reduce in the same state?
3. Do I have to consider the FOLLOW-Sets of the NTs and if yes, at which point?

I hope I have pointed my problems out clearly enough. Thank you for any help advance!

Best regards
MB

Answer 1

Hi, ballatma =)

1. If this would be the LR(0) table, we would also put the productionrules into the a column. But this is the SLR(1) action Table and therfore we only place a reduce rule if B → γ.  and the input token is in FOLLOW(B).  The follow set for A,S,B is ($,b). Therfore we only place the rules into the $,b columns.

2. No, thre is no conflict in q3. There must be eather two reduces or one reduce and one shift in one and the same row and colmn. You can see an example on slide 192. Think of it as If i you are  in state X and the input is b you want to do the action in row X and column b. But if there are two actions, you dont know which to take.

3. yes you have to =)  1. answers this .