patternMinor
Ambiguous Grammar and SLR parsing table : No conflicts?
Viewed 0 times
slrambiguousparsinggrammarandtableconflicts
Problem
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#48459, answer score: 2
Revisions (0)
No revisions yet.