Path: news.daimi.aau.dk!olevi
From: olevi@daimi.aau.dk (Ole Villumsen)
Newsgroups: comp.lang.beta
Subject: Ambiguous vs. unambiguous grammar (was Re: Adding methods without renaming the class (was ...))
Date: 2 Jan 1996 10:12:28 GMT
Organization: DAIMI, Computer Science Dept. at Aarhus University
Lines: 63
Message-ID: <4cb0ec$c17@krone.daimi.aau.dk>
References: <4aodps$70h@netnews.upenn.edu> 	<4b6p2p$dua@fbi-news.Informatik.Uni-Dortmund.DE> 	<4b9apo$aop@krone.daimi.aau.dk> <4bkilb$g47@netnews.upenn.edu> <wog68f1xr15.fsf@gyda.ifi.uio.no>
NNTP-Posting-Host: lithium.daimi.aau.dk

Alf-Ivar Holm <alfh@gyda.ifi.uio.no> writes:

>F08 in the FAQ refers to the grammar, not the compiler.  The fragment
>system is part of the implementation and has an alias between
><attributes> and <attributesDecl>, i.e. the above is possible.  

>(On the other hand, I don't know why the grammar would be ambiguous if
><attributes> were allowed to generate itself.)

That depends. If you only want to allow attributes to generate
itself in the beginning or in the end, there is no problem.

      attributes ::= attributes ; attributeDecl

and

      attributes ::= attributeDecl ; attributes

are both fine. (They are called left recursive and right recursive
respectively. For implementation reasons, one of the versions
is usually preferred, but I don't recall which.)

But in the fragment system, we would really like to have attributes
generate itself *in the middle*, and several times. The following example
is from the FAQ list:

   (# a: @integer;
      <<SLOT lib1: attributes>>;
      b: ^ text;
      <<SLOT lib2: attributes>>;
      c: (# ... #)
   #)

This could be generated by

      attributes ::= attributes ; attributes

*but*, this is ambiguous. To see this, just look at a simpler example:

   a: ...; b: ...; c: ...

This can be derived in two ways: You can have the first "attributes"
generate the a and b declarations, and the second generate the c declaration;
*or*, the first attributes could generate a: ... and the second the
declarations of b and c.

In fact, if you want to replace fragment forms only and strictly
(that is, forbid the aliasing done in the compiler),
then this ambiguity is necessary to allow the flexibility of the
fragment system. Suppose I wanted the effect of the declaration
of a, b and c above, but I wanted to put a and b into a slot.
Suppose you wanted the same effect, but in your program it
was more concenient to put b and c into a slot. The only way we
could both have it our way, would be with a grammar that allowed
both derivations of the same code - that is, an ambiguous grammar.

The FAQ keeper might as well change "such a grammar is very likely
to be ambiguous" to simply "such a grammar is ambiguous".

Ole V.

(I am assuming throughout that attribues can also generate attributeDecl,
which is a single declaration.)