Re: How test if language is LL(k) or LR(k) ?

Borneq <a.moderacja@gmail.com> writes:


> Where k is not specified.
> I would not testing if is LL(1),LL(2),LL(3) to infinity but test if
> language if LL(k) and would be nice if algorithm return k, find k for
> LL(k) LR(K) in finite time.


The algorithms which generate parsers from grammars get to "conflict"
points when they need to disambiguate the grammar, and at those points
one can essentially iterate to find k (and then take the max k over
all the points to determine k for a given grammar). In some cases,
you can easily establish that there is no such k.


However, there are other cases where the existence of k cannot be
easily proven or disproven. There are ways of constructing grammars
such that if you can prove they are non-ambiguous (and have a k, such
that they are LR(k), you can show that certain arbitrary Turing
machines halt. Since, the latter problem cannot be solved
algorithmically, neither can the former.


Thus, if you start by iterating on increasing k's, your program may
never halt. Thus, simply increasing k at each conflict point is not a
panacea to your problem. The best answer such an algorithm can
produce is that your grammar isn't LL(k) or LR(k) for values of k less
than this. And, by the way, the memory requirements for even
performing those experiments grow exponentially(note below), so it
isn't even useful in a practical sense.


Note, that the above description applied to grammars (not languages),
which although seemingly identical are not. You can have a language,
but not a grammar (in BNF or other equivalent notation) for that
language. Moreover, certain properties can be proven to hold for some
languages even without a grammar. For example, if you know that a
language is LR(5), you then know that the language is also LR(1).
That does not mean you can find the LR(1) grammar for the language,
just that it exists.


note from above: One of Terence Parr's innovations was discovering the
"linear approximate lookahead algorithm" which grows linearly, but
only gets an approximate solution to the problem. However, it does
make LL(k) parsing practical for many cases.


On a related note, I once investigated how one could compute the
closure of LR(k) grammars, and have an algorithm to do so (other than
just simply iterating over k) implemented in Yacc++. Unfortunately,
even that algorithm does not necessarily terminate on any given
grammar (and cannot due to the Turing limitation), and still has
exponential memory bounds. I am currently working with a researcher,
who I'm hoping will take the work further.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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