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

I wrote:
>> 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.


Ralph Boland <rpboland@gmail.com> writes:


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


The rub comes with grammars which may be ambiguous. There is no LR(k)
parser for an ambiguous language--all LR(k) languages are unambiguous.
From wikipeida:


    The general question of whether a grammar is not ambiguous is
    undecidable. No algorithm can exist to determine the ambiguity of a
    grammar because the undecidable Post correspondence problem can be
    encoded as an ambiguity problem.


And, TMs can mechanically be transformed into Post Correspondence
Problems. Thus, if you have an algorithm the can tell you if an
arbitrary grammar is ambiguous, you can use that to construct a
machine which determines if a TM halts, by converting the TM into the
corresponding PCP, which is then encoded as an a grammar ambiguity
problem and then runs your ambiguity algorithm. Viola, a solution to
the halting problem, not.


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


If I understand what you are asking, the GLR algorithm does
essentially that. If your grammar is LR(k) for some k, eventually the
parse forest will resolve down to a (single) parse tree and you have
the LR(k) parse for said input. However, if your language is
ambiguous, the GLR method won't always tell you that it's ambiguous,
and for some input there will be a parse forest that doesn't resolve
into a single tree, because it is ambiguous. And, unless you stumble
across an ambiguous sentence in your input, you may never know whether
your language is ambiguous or not.


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


Not that I am aware of. I'm pretty certain I saw somewhere a proof
that there can't be. However, my paper archives are still in MA with
me in AZ (and too extensive to rummage though in any event), and
Google doesn't show anything obvious. As I recall, even the proof
that any LR(k) language is an LR(1) language was non-constructive,
which it would have to be if there is no algorithm--otherwise the
construction would be the algorithm.


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.