CODEWITHSUNDEEP
parsinglr-grammar
vesii
vesii

Reputation: 3128

Understanding when reducing in SLR grammar

I have the following grammar:

S -> x S y
S -> y A S y
A -> B z x
A -> x y
B -> B y
B -> epsilon

I have built the LR(0) items:

enter image description here

I want to build the SLR(1). This is the table I got to without including the finished rules (the ones that contain dot in the end and we conclude the reduce part from them):

enter image description here

And the final table that I got is:

enter image description here

As you can see, I get a Shift-Reduce conflict on line 3. In the answer they said that there should not be any conflicts. So I'm guessing I'm not inserting the reduce part right (that's why I splitted into to section for you to easy check my solution). I think that in the algorithm of building the table, we look on each rule that has dot at the end for the reduce part. As I understand, for each one we need to add reduce for the whole line (this part I'm not sure about). For example for, A -> x y o we need to add R4 (because it's the number of the rule) to all of the fields on line 9 (because it's I9). So For the B -> o on I3 I get R6 on the whole line which makes a conflict. Where am I wrong? When do we add reduce to the entries?

Upvotes: 0

Views: 837

Answers (1)

rici
rici

Reputation: 241771

As I understand, for each one we need to add reduce for the whole line.

Not quite. A reduce action for a rule which produces the non-terminal N is applied only to those lookahead symbols in FOLLOW(N). This restriction is obviously valid. If the next symbol cannot follow the non-terminal, then the parser will not be able to shift that symbol after the reduction. On the other hand, it is not a guarantee of success; even if the lookahead is in the FOLLOW set of the non-terminal, there is no guarantee that it is in the FIRST set of the particular state to which the parser will transition after performing the GOTO action. Refining the lookahead more is what distinguishes LALR parsers from SLR parsers.

In your grammar, FOLLOW(B) is {y, z}, so the reduce action will only be placed in those two cells, and not in the cell corresponding to x. So there is no conflict.

Upvotes: 0

Related Questions