Re: disambiguating transformations

> I am looking for an algorithm which will take a (possibly) ambiguous context-
> free grammar and perform transformations on it to yield an equivalent
> non-ambiguous context-free grammar. Does such a thing exist? If not, do we
> know why not? Any ideas or references would be appreciated.
..
> [Is this even decidable? -John]


No, it's only semi-decidable, which doesn't necessarily inhibit the
usefulness of a tool which works most of the time in practice. (If I
recall correctly, whether a grammar is LR(1) is also only semi-decidable.)
The kinds of ambiguity which are typically introduced in programming
language CFGs are often fairly easy to detect and remove automatically.
Perhaps the biggest problem with such a tool is what to do about
automatically removing the ambiguity in the presence of conflicting
semantic actions for the ambiguous portion of the grammar.


Probably the biggest example of the way this is done now is that LR parser
generators ala YACC allow ambiguous grammars, and resolve by preferring
shift actions over reduce actions, and preferring the first reduce action
over other reduce actions. Most YACC grammars for Algol-like languages
use this fact to write the if-then-else rule ambiguously and still handle
dangling else.


Here's an example of the kind of tool that the poster might want --
automate removal of subproductions from an LL(1) grammar, using the order
the clauses appear in the grammar to determine priority. For example,
given the ambiguous CFG


expr ::= int suffix { emit( "move $1,r0" ); }.
suffix ::= /*epsilon*/
| <+> <0> suffix
| <+> int suffix { emit( "add $2,r0,r0" ); }.
int ::= <0> | <1> | <2>.


for ternary addition, the transformed grammar might look like


expr ::= int suffix { emit( "move $1,r0" ); }.
int ::= <0> | <1> | <2>.
suffix ::= /*epsilon*/
| <+> anint.
anint ::= <0> suffix
| <1> suffix { emit( "add $2,r0,r0" ); }
| <2> suffix { emit( "add $2,r0,r0" ); }.


The example doesn't really show the full utility of the technique, but it
sure is nice to be able to do this kind of thing sometimes. I would
wildly guess that the fact that it is decidable whether an LL(1) grammar
is a cover of another LL(1) grammar is enough to make such a tool
constructible.


Bart Massey
bart@cs.uoregon.edu
--

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