12 Jan 2004 13:28:49 -0500

Related articles |
---|

What is the trick of languages being LL(k+1), but not LL(k)? oliver@zeigermann.de (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)? oliver@zeigermann.de (Oliver Zeigermann) (2004-01-12) |

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)? 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) |

From: | Oliver Zeigermann <oliver@zeigermann.de> |

Newsgroups: | comp.compilers |

Date: | 12 Jan 2004 13:28:49 -0500 |

Organization: | T-Online |

References: | 04-01-027 04-01-033 |

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 ;

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.