Re: disambiguating transformations

Bart Massey <>
Sun, 26 Sep 1993 23:02:54 GMT

          From comp.compilers

Related articles
disambiguating transformations (Matt Melchert) (1993-09-22)
Re: disambiguating transformations (Stephen J Bevan) (1993-09-24)
Re: disambiguating transformations (1993-09-25)
Disambiguating an arbitrary CFL (was: disambiguating transformations) (1993-09-25)
Re: disambiguating transformations (Bart Massey) (1993-09-26)
Re: disambiguating transformations thinx! (Jos Horsmeier) (1993-09-27)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Bart Massey <>
Keywords: parse, theory
Organization: University of Oregon Computer and Information Sciences Dept.
References: 93-09-099 93-09-120
Date: Sun, 26 Sep 1993 23:02:54 GMT

> 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

Bart Massey

Post a followup to this message

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