15 Apr 2004 12:27:45 -0400

Related articles |
---|

[3 earlier articles] |

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: | 15 Apr 2004 12:27:45 -0400 |

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

References: | 04-02-021 |

Keywords: | parse |

Posted-Date: | 15 Apr 2004 12:27:45 EDT |

(In case I still wasn't clear on the answer to the question...)

On the question of whether a *language* is ll(k) or ll(k+1) for some

value of k:

The question only makes sense in the context of a grammar for the

language and a parsing order, like ll(), lr(), lalr(), etc. The

language itself is merely a set of sequences of tokens. A *formal*

language is a set of sequence of tokens with constraints that when

applied to an input sequence determine whether that input sequence of

tokens falls within the set of valid sequences of tokens for that

language. A grammar is one possible representation of those

constraints.

Because "ll(k+1)" as a characteristic of a formal language is only

coherent in the context of a grammar for the language and an ll()

parser, then whatever "minimum lookahead for for an unambiguous ll()

parse" is found to be a characteristic of the grammar is also a

characteristic of the language implied by that grammar. In effect you

are using the grammar and ll() parsing technique to "measure" and

categorize the set of sequences of tokens that is the language.

A categorical distinction between a grammar and the language implied

by that grammar may be valid in some contexts, but it is not valid in

the context of parser lookahead and ambiguity. In a categorization by

grammar type, the grammar and language have the same algebraic

properties and reference the same set of sequences of tokens.

The pointer to Hopkins' paper on algebraic models of formal languages,

grammars, and automata was provided not because it provides a formula

in which one can plug in a grammar and some representation of a parser

order (ll, lr, lalr, etc) and then have "minimum lookahead without

parsing amibiguity" pop out as a solution, but rather because it

demonstrates that languages and grammars can be modelled algebraically

and more or less how it is done.

That would seem to be a necessary first step if one seeks to derive an

algebraic approach for determining minimum lookahead given a grammar

for a formal language and a selected parsing order.

Aside: I discovered a definition of a DIOID in this proof of "unique

readability" of a variation on a "well-formed formula":

<http://mathquest.com/discuss/sci.math/a/t/301595>

HTH,

Clayton Weaver

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.