Search code examples
parsinggrammartheory

Theory: LL(k) parser vs parser for LL(k) grammars

I'm concerned about the very important difference between the therms: "LL(k) parser" and "parser for LL(k) grammars". When a LL(1) backtracking parser is in question, it IS a parser for LL(k) grammars, because it can parse them, but its NOT LL(k) parser, because it does not use k tokens to look ahead from a single position in the grammar, but its exploring with backtracking the possible cases, regardless that it still uses k tokens to explore. Am I right?

The question may break down to the way the look-ahead is performed. If the look-ahead is actually still processing the grammar with backtracking, that does not make it LL(k) parser. To be LL(k) parser the parser must not use the grammar with backtracking mechanism, because then it would be "LL(1) parser with backtracking that can parser LL(k) grammars". Am I right again?

I think the difference is related to the expectation that LL(1) parser is using a constant time per token, and LL(k) parser is using at most k * constant (linear to the look-ahead) time per token, not an exponential time as it would be in the case of a backtracking parser.

Update 1: to simplify - per token, is the parsing LL(k) expected to run exponentially in respect to k or in a linear time in respect to k?

Update 2: I have changed it to LL(k) because the question is irrelevant to the range of which k is (integer or infinity).

Solution

  • I suggest you to read the chapter 5.1 of Aho Ullman Volume 1.

    https://dl.acm.org/doi/book/10.5555/578789

    1. A LL(k) parser is a k-predictive algorithm (k is the lookahead integer >= 1).
    2. A LL(k) parser can parse any LL(k) grammar. (chapter 5.1.2)
    3. for all a, b you have a < b => LL(b) grammar is also a LL(a) grammar. But the reverse is not true.
    4. A LL(k) parser is PREDICTIVE. So there is NO backtracking.
    5. All LL(k) parsers are O(n) n is the length of the parsed sentence.
    6. It is important to understand that a LL(3) parser do not parse faster than a LL(1). But the LL(3) parser can parse MORE grammars than the LL(1). (see the point #2 and #3)