3
$\begingroup$

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

enter image description here

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.