Re: What is the trick of languages being LL(k+1), but not LL(k)?

(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

Return to the comp.compilers page.
Search the comp.compilers archives again.