I have a bit of trouble understanding the definition of LL(k) grammars.

Here it's defined as:

for every pair of production rules $A\rightarrow α$ and $A \rightarrow β$ the following condition holds.
$\text{FIRST}_k$ ( $\text{α FOLLOW}_k$ (A)) $\cap$ $\text{FIRST}_k$ ( $\text{β FOLLOW}_k$ (A)) $=\emptyset$

What does this mean concretely? What is the subscript $_k$?
Why is it for a "pair of production rules"?

  • 2
    $\begingroup$ 1) It means what's written there. 2) You need to unfold the definitions to figure out what $k$ means there; is comes from LL(k), obviously, a part of the definition you left out. 3) You check out pairs because you want to make sure there are no conflicts you can not resolve with $k$ items lookahead. $\endgroup$
    – Raphael
    Dec 16 '15 at 8:45

It's actually a definition of a strong LL(k) grammar.

First of all, see Raphael's comment.

In short, the condition means that while parsing $A$ you can choose the next production rule in a deterministic manner using only the next $k$ lookahead symbols.

An important thing is you don't need any context for that decision, i.e. you don't need to remember the previous steps in the left-most derivation that led you to the non-terminal $A$ to parse $A$ itself.

By the way, every LL(1) grammar is strong, but there are non-strong LL(k) grammars, $k > 1$.

If you need a more detailed explanation, then I think it's better to use a book for that (it's too long for an answer here). I'd suggest "Parsing Techniques - A Practical Guide" by Dick Grune et al.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.