Conflicts in SLR parse-tables
Introduction:
When reduce actions are added to SLR parse-tables, it might add one to a place where there is already a shift action, or may add reduce actions for several different productions to the same place. When either of this happens, we no longer have a unique choice of action, i.e., we have a conflict. The first situation is called a shift-reduce conflict and the other case a reduce conflict. Both may occur in the same place.
Conflicts are often caused by ambiguous grammars, but (as is the case for LL parsers) even some non-ambiguous grammars may generate conflicts. If a conflict is caused by an ambiguous grammar, it is usually (but not always) possible to find an equivalent unambiguous grammar. Methods for eliminating ambiguity were discussed in sections 3.4 and 3.5. Alternatively, operator precedence declarations may be used to disambiguate an ambiguous grammar, as we shall see in section 3.16. But even unambiguous grammars may in some cases generate conflicts in SLR tables.
In some cases, it is still possible to rewrite the grammar to get around the problem, but in a few cases the language simply is not SLR. Rewriting an
Summary of SLR parse-table construction:
1. Add the production S’ -> S, where S is the start symbol of the grammar.
2. Make an NFA for the right-hand side of each production.
3. If an NFA state s has an outgoing transition on a nonterminal N, add epsilon transitions from s to the starting states of the NFAs for the right-hand sides of the productions for N.
4. Convert the combined NFA to a DFA. Use the starting state of the NFA for the production added in step 1 as the starting state for the combined NFA.
5. Build a table cross-indexed by the DFA states and grammar symbols (terminals including $ and non-terminals). Add shift actions for transitions on terminals and go actions for transitions on non-terminals.
6. Calculate FOLLOW for each nonterminal. For this purpose, we add one more start production: S’’ ->S’$.
7. When a DFA state contains an accepting NFA state marked with production number p, where the nonterminal for p is N, find the symbols in FOLLOW(N) and add a reduce p action in the DFA state at all these symbols. If production p is the production added in step 1, add an accept action instead of a reduce p action.
Un-ambiguous grammar to eliminate conflicts is somewhat of an art. Investigation of the NFA states that form the problematic DFA state will often help identifying the exact nature of the problem, which is the first step towards solving it. Sometimes, changing a production from left-recursive to right-recursive may help, even though left-recursion in general is not a problem for SLR-parsers, as it is for LL(1)-parsers.