Ambiguous Grammar and SLR parsing table : No conflicts?

Question

We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-then-else grammar which is pretty much ambiguous.

So I started with the following rules ( as given in Principles of Compiler Design, Aho and Ullman, 2002 Reprint)

$$ S \rightarrow iCtSS' \\ S \rightarrow iCtS \\ S \rightarrow a \\ S' \rightarrow eS \\ S' \rightarrow \epsilon \\ C \rightarrow b \\ $$

S is the statement, and C is the condition. All apart from S', S and C are terminals, and epsilon refers to null.

The given grammar is written in a way that conforms to recursive descent parsing.

Augmented the grammar as

$$ S\prime\prime \rightarrow .S \\ S \rightarrow .iCtSS' \\ S \rightarrow .iCtS \\ S \rightarrow .a \\ S' \rightarrow .eS \\ S' \rightarrow .\epsilon \\ C \rightarrow .b \\ $$

And then generated the instances-set as

$$ I_{0} [ S\prime\prime \rightarrow .S, S \rightarrow .iCtSS', S \rightarrow .iCtS, S \rightarrow .a, S' \rightarrow .eS, S' \rightarrow .\epsilon, C \rightarrow .b]\\ I_{1} [S \rightarrow i.CtSS', S \rightarrow i.CtS, C\rightarrow.b]\\ I_{2} [S \rightarrow a.]\\ I_{3} [S'\rightarrow e.S, S \rightarrow .iCtSS\prime, S \rightarrow .iCtS]\\ I_{4} [S \rightarrow \epsilon.]\\ I_{5} [C \rightarrow b.]\\ I_{6} [S \rightarrow iC.tSS\prime, S\rightarrow iC.tS]\\ I_{7} [S\prime \rightarrow eS.]\\ I_{8} [S \rightarrow iCt.SS\prime, S \rightarrow iCt.S, S \rightarrow .iCtSS\prime, S\rightarrow.iCtS, S\rightarrow.a]\\ I_{9} [S \rightarrow iCtS.S', S \rightarrow ICtS., S' \rightarrow .eS, S' \rightarrow .\epsilon]\\ I_{10} [S \rightarrow iCtSS'.]\\ $$

Based on these sets that I made, I constructed a parsing table

However, as per my derivation of the instance-sets, there were no conflicts in the table (the grammar being ambiguous), I was not sure if I worked it out correctly. One thing that adds to the dilemma that there has been no instance where S was the first non terminal in grammar, and so there are no states that can accept the final variable S during parsing.

Can anyone please help me with this? I checked it further online and they mentioned that the ambiguous grammar tended to have conflicts, but there were none in this case. Where am I going wrong?

Thanks.

Answer 1

In state 9, you can reduce either $S$ or $S'$, as well as the possible shift action for $e$. So there are both reduce/reduce and shift/reduce conflicts.

The production $S' \rightarrow \epsilon$ cannot be correct; there is already a production $S \rightarrow iCtS$ for an if without an else, so if $S'$ can derive the empty string, $S \rightarrow iCtSS'$ is ambiguous. Once you remove that, you will still have the shift-reduce conflict with $e$. (Since an SLR parser doesn't use lookahead to restrict reduce actions, the entire row for a state with a reduce action must consist of precisely that reduce action. But this particular grammar is ambiguous, so using LALR(1), for example, won't help.)

Finally, $\epsilon$ is not a symbol; it is simply a way of making an empty symbol sequence visible. So it cannot be the head of a column the action table, and also it cannot be on the right hand side of the dot in an item.