Re: LR(n) parsers

In article 91-10-036 Steve Boswell <whatis@ucsd.edu> writes:
>What sort of easily-describable or commonly-occuring grammars are
>ambiguous for any amount of lookahead?


I don't know whether it could still be described as "common" or
as "easily describable", but Algol [68, of course] is full of such things.
To give three simple examples:


      a) In "BEGIN A a; B b; C c; D d; ....", A, B, C, D, ... could be mode
[type] names, in which case we are declaring identifiers a, b, c, d;
or they could [any or all of them] be monadic operators operating
[and presumably having side-effects] on the global variables a, b,
c, d. You can't in general tell until you reach the end of the
program, as the declarations of A, B, C, D don't have to precede
their uses.


      b) Both "BEGIN lots of grunge END" and "IF lots of grunge THEN ...."
may be abbreviated to "( lots of grunge ..." except that "END"
will be abbreviated to ")" and "THEN" to "|". This can't be
disambiguated until you get to the ")" or "|", and "lots of grunge"
may include arbitrarily many declarations and statements.


      c) "(foo, bar, baz, ...", where "foo" etc could be arbitrarily messy
units, could be the start of a collateral clause, or could be the
start of an abbreviation for "[1:foo, 1:bar, ...] SOMEMODE a",
declaring an array.


On the other hand, all of these ambiguities are "easily" resolved
in a multi-pass compiler; which surely is the usual resolution of a need
for long lookaheads.


--
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk
--

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