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

Chris F Clark wrote:
  > Oliver asked why the rule in the next line is LL(k+1)
  >
  >
  >>a : A^k B s | C ;




No.


My question was, why is the *language* described by this grammar
LL(k+1), but not LL(k):


s : A s a | ;


a : A^k B s | C ;


It is obvious this grammar is LL(k+1), but why is the *language*?


  >
  > This sounds supsiciously like a homework problem, so I will only give
  > a partial answer--one that should be sufficient for you to understand,
  > but not sufficient to allow you to turn it in as a homework answer.


Man, this is for crying out loud! Everytime I think I have gone deep
into something and have this last smart question, someone tells me "I
have just taught that do my undergraduate students" or "My dog just told
me", etc. ;) No! It is not a homework it is a serious question, I am
really interested!


  > The reason why the grammar is LL(k+1) is that is takes k tokens to get
  > through the A's and the k+1'st token is the B. No amount of rewriting
  > can get rid of those k A's (and still accept the same language). I
  > will leave it as an exercise to you to find the rule(s) which
  > "conflict(s)" with the "a" rule and can also start with k A's.


I know this grammar is LL(k+1), but I do not know *why* the language is...


  > That is the key concept of LL(k) processing. There must be a way
  > within the first k tokens of a rule to determine which rule applies.
  > If there are two possible rules that apply at the k-th token, then the
  > grammar is at least k+1.


It is about languages here, not grammars...


  > In practice, this is not such a bad limit as most "constructs" in most
  > programming languages have a unique starting token that tells you the
  > statement type--think of BASIC and how each line consists of a line
  > number followed by a unique keyword for each "type" of line. Even
  > languages like C have only one of several keywords that can begin a
  > declaration and not an assignment statement. The key part there is
  > that one must know which identifiers represent types and which
  > represent variables to make that ture, and hence the common hack of
  > tying the lexer to the symbol table.
  >
  > The one place this tends to get one in trouble is "expressions",
  > because in expressions the keyword (operator) is often infix (or
  > perhaps suffix) and you cannot tell "expression + expression" from
  > "expression * expression" by looking at the tokens of the first
  > expression (which may be of unbounded length). Thus, grammars for
  > expressions which are written with recursion on both the left and
  > right sides are not LL(k) for any k, even though they are simple for
  > humans to understand--the recursion on the left is the problem.
  > However, it is usually possible to recast those expressions into a
  > form where there is no left recursion, by making up names for the
  > different types of sub-expressions (e.g. factor, term, primary, etc.)
  > and making them not left recursive.
  >
  > To assure yourself that you understand the problem, is the reverse of
  > the language LL(k), and if so, for what k.
  >
  > s: a s A | ;
  > a: s B A^k | C;


Obviously, this grammar contains an infinite left recursion from s to a
and back to s. So it is not LL(k) for any k (as you just explained above)...


  > Hope this helps,


Sorry, no. The question was, *why* is it impossible to rewrite the
grammar to be LL(k) or even LL(1).


Oliver

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