Re: Is a contextfree Grammar ambiguous ?

> I'm not familiar with LR(oo) -- do you have a reference? It seems to
> me that infinite lookahead would imply general context-free parsing.
> Do you perhaps mean LR(k, oo), which Szymanski defined in 1972 as a
> generalization of Knuth's LR(k,t)?


There are currently no published papers on LR(oo). The term as I am
using it is the cognate of LL(oo) as I understand it from Terrence
Parr and Adrian Johnstone's work.


The essential idea in this work is that you allow k to grow until it
is large enough to parse your grammar. To handle truly unbounded k,
you also need a method of collapsing unbounded lookahead into a finite
set of states.


One variation on this is the LR-regular languages where the unbounded
lookahead has to be recognizable by a regular expression.


As I understand it, the LL(oo) versions handle unbounded lookahead by
processing it with the LL grammar (actually the LL(oo) grammar, since
one can apply transitive closure to the process). Thus, an LR(oo)
parser should process the lookahead with the LR(oo) grammar.


Conceptually, it is not difficult to build an LR parser that uses the
same LR language to generate the lookahead machines to resolve
conflicts. However, as I mentioned at the practical level there are
numerous nuances. For example, as I mentioned, if the lookahead
machine has a conflict, it should get resolved by a second lookahead
machine, and so on until closure. However, one neds to show that the
process terminates and does not generate an infinite set of lookahead
machines and more importantly find a way of mechanically testing that
the process will terminate, so that errors can be reported for
grammars where it will not terminate.


As to whether such a parsing technology could handle all context free
grammars, I am not certain. Actually, at one level one knows that
either the process will not have a valid termination condition or it
will not handle all context free grammars, since the unambiguity
problem is undecidable. I just don't know which of those problems the
method falls prey to yet.


It's only a spare time project, and as such only gets worked on as I
find both time and motivation.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : cfc@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres

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