|What is the trick of languages being LL(k+1), but not LL(k)? firstname.lastname@example.org (Oliver Zeigermann) (2004-01-07)|
|Re: What is the trick of languages being LL(k+1), but not LL(k)? cfc@shell01.TheWorld.com (Chris F Clark) (2004-01-09)|
|Re: What is the trick of languages being LL(k+1), but not LL(k)? email@example.com (Oliver Zeigermann) (2004-01-12)|
|Re: What is the trick of languages being LL(k+1), but not LL(k)? firstname.lastname@example.org (2004-01-16)|
|Re: What is the trick of languages being LL(k+1), but not LL(k)? email@example.com (Oliver Zeigermann) (2004-01-22)|
|Re: What is the trick of languages being LL(k+1), but not LL(k)? firstname.lastname@example.org (Oliver Zeigermann) (2004-02-01)|
|From:||Oliver Zeigermann <email@example.com>|
|Date:||12 Jan 2004 13:28:49 -0500|
|Keywords:||parse, LL(1), theory|
|Posted-Date:||12 Jan 2004 13:28:49 EST|
Chris F Clark wrote:
> Oliver asked why the rule in the next line is LL(k+1)
>>a : A^k B s | C ;
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
> 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).
Return to the
Search the comp.compilers archives again.