Tue, 28 Oct 2008 17:13:58 -0400

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

[3 later articles] |

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

Newsgroups: | comp.compilers |

Date: | Tue, 28 Oct 2008 17:13:58 -0400 |

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

References: | 08-10-044 |

Keywords: | parse, theory |

Posted-Date: | 29 Oct 2008 19:20:28 EDT |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.