Re: Help Resolving Shift Reduce Conflicts In Bison Grammar

To get rid of shift/reduce conflicts, the basic technique is to split
the rules that are causing the reduction part of the conflict into two
rules and to use the appropriate rule(s) based on the following
context of the use. So you need to look at the symbols that come
after the terminal you're trying to split, where that terminal appears
on the right hand side of a rule. The problem comes when the terminal
is the last thing on the right hand side. In that case, you need to
unfactor the rule (eliminating the terminal, but resulting in more
rules) until you can find the following context.


Lets start by reordering your grammar to be a little compact:


text : /* empty */ | text textElement
textElement: inlineElement | paragraph
inlineElement : TEXTBLOCK | BOLD inlineText BOLD_END
inlineText : /* empty */ | inlineText inlineElement
paragraph: PARA inlineText optParaEnd
optParaEnd: /* empty */ | PARA_END


The problem you have is shift/reduce errors on the reduction of optParaEnd.
optParaEnd only appears as the last terminal on a rhs, so we need to
unfactor it. That gives us:


paragraph: PARA inlineText | PARA inlineText PARA_END


We still have no FOLLOW context, because everywhere paragraph appears on
the right side of a rule, its the last thing. So continue to unfactor:


textElement: inlineElement | PARA inlineText | PARA inlineText PARA_END


Still no FOLLOW context, more unfactoring is needed:


text : /* empty */ | text inlineElement
                                      | text PARA inlineText
                                      | text PARA inlineText PARA_END


Now we can finally see the FOLLOW context of the conflict. The specific
rule triggering the conflict is now "text: text PARA inlineText", and
it conflicts with a following context of inlineElement. So we need to
split the 'text' rule into those parts that conflict and those that do
not, and change the uses that conflict to only use the non-conflicting
part:


text : text1 | text2


text1 : /* empty */ | text1 inlineElement
                                        | text PARA inlineText PARA_END


text2 : text PARA inlineText


The resulting grammar has no conflicts.


text : text1 | text2
text1 : /* empty */ | text1 inlineElement | text PARA inlineText PARA_END
text2 : text PARA inlineText
inlineElement : TEXTBLOCK | BOLD inlineText BOLD_END
inlineText : /* empty */ | inlineText inlineElement




Chris Dodd
chrisd@reservoir.com

Return to the comp.compilers page.
Search the comp.compilers archives again.