I'm writing an SLR(1) parser from the following grammar:
1) S -> aSb
2) S -> cB
3) B -> cB
4) B -> ε
First of all, I started with finding the associated LR(0) automaton with the augmented grammar adding the S' -> S production and starting to compute the various states. The states that I found are:
I0 = {S'->•S, S->•aSb, S->•cB}
𝛿(I0, S) = I1; 𝛿(I0, a) = I2; 𝛿(I0, c) = I3;
I1 = {S'->S•}
I2 = {S->a•Sb, S->•aSb, S->•cB}
𝛿(I2, S) = I4; 𝛿(I2, a) = I2; 𝛿(I2, c) = I3
I3 = {S->c•B, B->•cB, B->•ε}
𝛿(I3, B) = I5; 𝛿(I3, ε) = I6; 𝛿(I3, c) = I7;
I4 = {S->aS•b}
𝛿(I4, b) = I8;
I5 = {S->cB•}
I6 = {B->ε•}
I7 = {B->c•B, B->•cB, B->•ε}
𝛿(I7, B) = I9; 𝛿(I7, ε) = I6; 𝛿(I7, c) = I7;
I8 = {S->aSb•}
I9 = {B->cB•}
And here there is the LR(0) automaton:
After that, I did the parser table (but I don't think it is needed in order to answer my question) so I have a doubt: is the epsilon transition handled in the right way? I mean, I treated it as a normal character since we have to reduce by the rule number 4 at some point. If I'm wrong, how should I treat that transition? Thanks in advance, hoping this is helpful for other people as well.
no , there is no need to create the State I6
Confusion may have arise in Y->Ɛ . When you place a dot in the augmented productions for example S->A.B it means that A is completed and B is yet to be completed (by completion here means progress in parsing) . Similarly if you write Y->.Ɛ , it means Ɛ is yet to be over, but we also know that Ɛ is null string i.e nothing therefore Y->.Ɛ is interpreted as Y->.
you can use The JFLAP Software and see it's documentation about SLR(1)
