Thu, 06 Nov 2008 18:12:48 -0500

Related articles |
---|

How test if language is LL(k) or LR(k) ? a.moderacja@gmail.com (Borneq) (2008-10-23) |

Re: How test if language is LL(k) or LR(k) ? cfc@shell01.TheWorld.com (Chris F Clark) (2008-10-28) |

Re: How test if language is LL(k) or LR(k) ? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-10-29) |

Re: How test if language is LL(k) or LR(k) ? rpboland@gmail.com (Ralph Boland) (2008-10-31) |

Re: How test if language is LL(k) or LR(k) ? cfc@shell01.TheWorld.com (Chris F Clark) (2008-11-06) |

Re: How test if language is LL(k) or LR(k) ? torbenm@pc-003.diku.dk (2008-11-07) |

Re: How test if language is LL(k) or LR(k) ? ulf.schwekendiek@googlemail.com (ulf.schwekendiek@googlemail.com) (2008-11-07) |

Re: How test if language is LL(k) or LR(k) ? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-11-07) |

Re: How test if language is LL(k) or LR(k) ? torbenm@pc-003.diku.dk (2008-11-10) |

Re: How test if language is LL(k) or LR(k) ? cfc@shell01.TheWorld.com (Chris F Clark) (2008-11-10) |

Re: How test if language is LL(k) or LR(k) ? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-11-12) |

From: | Chris F Clark <cfc@shell01.TheWorld.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 06 Nov 2008 18:12:48 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 08-10-044 08-10-053 08-11-005 |

Keywords: | parse, theory |

Posted-Date: | 06 Nov 2008 20:26:22 EST |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.