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

On Oct 28, 3:13 pm, Chris F Clark <c...@shell01.TheWorld.com> wrote:
> Borneq <a.modera...@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.


Could you provide references for this?; preferably how to construct
example grammars. or the example grammars themselves.


Could there exist an algorithm the can construct a parser for any
LR(k) grammar for any finite k without determining k? Note that,
since such an algorithm may also construct parsers for some grammars
which are not LR(k) for any k, such an algorithm could not tell you if
the grammar is LR(k) for any k.


> 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.


Is there not an algorithm to convert any LR(k) grammar into an LR(1)
or even LR(0) grammar?


Regards,


Ralph Boland

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