4 Feb 2004 21:28:17 -0500

Related articles |
---|

[2 earlier articles] |

Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-16) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? cgweav@aol.com (2004-01-16) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? cfc@world.std.com (Chris F Clark) (2004-01-17) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-22) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-22) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (Oliver Zeigermann) (2004-02-01) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? cgweav@aol.com (2004-02-04) |

Re: What is the trick of languages being LL(k+1), but not LL(k)? cgweav@aol.com (2004-04-15) |

From: | cgweav@aol.com (Clayton Weaver) |

Newsgroups: | comp.compilers |

Date: | 4 Feb 2004 21:28:17 -0500 |

Organization: | AOL http://www.aol.com |

References: | 04-02-021 |

Keywords: | parse, theory |

Posted-Date: | 04 Feb 2004 21:28:17 EST |

*>(<http://www.uwm.edu/~whopkins/cs/CompFAQ.txt>*

*>*

*>OK, I really read (and understood most of) this article - and I really*

*>found nothing related to my question nor anything new to me. I *must**

*>have missed the point. I have not even found anything related to what*

*>you called "the Hopkins reason"! Could you please clarify? Have you*

*>given the wrong link? Am I simply an idiot?*

*>*

*>Thanks in advance and cheers :)*

Recap:

You asked why a language was ll(k+1) rather than ll(k), and gave an

example grammar for a language.

Chris Clark explained where ambiguity would result when trying to

parse that example grammar with an ll(k) parser, and explained how an

ll(k+1) parser could resolve it without conflict.

You explained that you understood why the example *grammar* was

ll(k+1), but not why the *language* was ll(k+1).

I pointed you at Hopkins, who explains in the very beginning of his

document that:

"The underlying theme of this article is that formal languages,

automata, and grammars are all methods for algebraically describing

objects which reside in one of a hierarchy of (not so well-known)

algebraic systems that range from DIOIDS to QUANTALES."

Without yanking the whole chain of symbolic inference in that document

into this post, it is still clear that the same algebraic reasoning

from which one could infer that your grammar will have conflicts if

you attempt to parse it with an ll(k) parser (but not with an ll(k+1)

parser) also holds for the language whose constraints are expressed by

that grammar.

At any rate, here is another take on the field of Rewriting Systems

(which in the Wolfram resource hierarchy is treated as a branch of

discrete mathematics):

<http://library.wolfram.com/infocenter/MathSource/5109/>

The main point is, if you understand why the grammar is ll(k+1), then

you also understand why the language is ll(k+1). To assert that a

language whose constraints can be expressed by an "ll(k+1)" grammar

but not by an "ll(k)" grammar is thus an "ll(k+1)" language is merely

categorizing the language by grammar type. Whatever combinatorial

invariants are implied by the grammar hold for the set of valid

strings that is the language as well.

In sum, he question is like asking why a 6-centimer long stick is "a

6-centimeter stick". It's a 6-centimer stick because someone measured

it and that's how long it was. It could also be a "sun-bleached dry

stick" or "a stick of driftwood", but those alternate categorizations

would not necessarily be useful if you were trying to decide if a

drawer was wide enough to put it in sideways.

If you what want to know is how you make a ruler for grammars, feel

free to explore the discipline of discrete mathematics with particular

attention to rewriting systems.

HTH,

Clayton Weaver

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.