<p>The parsing table of a $LL(k)$ grammar grows exponentially in $k$.
This is however the worst-case scenario, which is not typical, as Niel pointed out:
For an $LL(k)$ grammar $G$, $k$ is the size of the maximal lookahead needed across $L(G)$.
But it appears that in practice, the need for a $k$ lookahead is restricted to a small portion to the language, so that the size of the parsing table remains reasonable.</p>

<p>We face here a quite common problem of theoretical complexity not reflecting the practical experience.
Beyond $LL(k)$ are $LL(*)$ grammars, whose lookahead is adaptative, so as to keep the parsing table no larger than necessary.
$LL(*)$ technique is examplified by <a href="http://www.antlr.org" rel="nofollow">ANTLR</a>, and described in this <a href="http://www.antlr.org/papers/LL-star-PLDI11.pdf" rel="nofollow">paper</a> by Terence Parr.</p>

<p>Finally, I would say that many teachers focus on $LL(1)$ to emphasize that $LL(1)$ suffices to parse most languages in <em>practice</em>.
Philosophically, our programming languages lie somewhere between Deterministic and Non-Deterministic Pushdown Automata, but in fact way closer to DPA than to the full NPA.
A similar observation can be done for <a href="http://en.wikipedia.org/wiki/Mildly_context-sensitive_grammar_formalism" rel="nofollow">natural languages</a>: context-free is not enough, yet context-sensitive is way too powerful.</p>

CC BY-SA 3.0
2015-04-20T20:36:41.743Z
Thanks for the answer! The ANTLR paper is a fantastic reference.
Jules
CC BY-SA 3.0
2015-04-22T14:13:20.437Z
Is there a formal proof that $LL(k)$ requires something like $c^k \log n$ bits of space, where $n$ is the number of symbols in the alphabet?  Or is the statement "the parsing table grows exponentially in $k$" (in the worst case) an informal observation, like "SAT takes exponential time" (in the worst case)?
András Salamon
CC BY-SA 3.0
2015-04-22T14:41:17.743Z
@András It is the very definition of $LL(k)$: non-determinism in the pushdown automaton can be solved by looking ahead at most $k$ characters. The parsing table associates a state to each pair $(s,u)$ (where $s$ is a state in the automaton, and $u$ a word of length $k$).
The worst case is not avoidable, although such languages are somewhat artificial.
Boson
CC BY-SA 3.0
2015-04-23T00:40:26.437Z
@Boson: that sounds like an informal argument.  Clearly $O(c^k \log n)$ is an upper bound, since that is enough to construct a parsing table.  But it may be possible to formalise what it means to parse the language but without requiring a parsing table to be used to do so, so this is only a lower bound for the class of algorithms that construct a parsing table.
András Salamon
CC BY-SA 3.0
2015-04-23T09:15:01.477Z
@AndrásSalamon: Given a context-free grammar $G$ and a word $u$, whether $u \in L(G)$ is done in polynomial time (e.g. with CYK algorithm).
In practice, $u$ is quite long (typically a compilation unit) and we want time _linear_ in $|u|$.
Lookahead achieves such linear time in $|u|$, at the cost of space to store the parsing table (convenient if you want to parse several words, e.g. a compiler).
The $k$-lookahead parsing algorithm thus runs in time $\mathcal{O}(f(k) |u|)$ *on the class of $LL(k)$ grammars*.
If I understand well, you ask about a lower bound on $f(k)$, am I right?
Boson
CC BY-SA 3.0
2015-04-23T09:46:45.020Z
@Boson: yes, I'd be interested in proving (or reading a proof of) an exponential dependence of space used on $k$.  This is of purely theoretical interest, I understand that usually $k$ is small and parsers have to be as close to constant time per input symbol as possible.
András Salamon
CC BY-SA 3.0
2015-04-23T15:19:59.860Z
@AndrásSalamon: I wanted to be sure I got your question right. 
The parsing table only depends on the grammar and $k$, so there is no need to store it. You could recompute it every time you need it and still achieve complexity linear in $u$ with no space overhead...
Still, I do not think you can avoid time exponential in $k$ to decide what is the next rule to use, but I have no proof for it.
Interesting question, though.
Boson
CC BY-SA 3.0
2015-04-20T18:14:29.290Z
2015-04-20T18:14:29.290Z
Boson
<p>I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well).</p>

<p>Over the course of the semester, the prof mentioned that grammars should be optimized to $LL(1)$ whenever possible. Unfortunately, he never explained properly why such grammars are "better." Wouldn't a greater lookahead make for more effective predictive parsing? Or is it considered harmful taking into account physical resource (RAM, CPU) constraints? Or do parsers with more lookahead simply become more complex than they're worth?</p>

CC BY-SA 3.0
2015-04-18T02:49:53.397Z
*"Wouldn't a greater lookahead make for more effective predictive parsing?"* I'm not sure what you mean here ... $LL(k)$ means that it is sometimes *necessary* to read $k$ symbols ahead in order to make the correct parse at the current point, while $LL(1)$ only needs to look one symbol ahead.
usul
CC BY-SA 3.0
2015-04-18T05:54:26.583Z
I expect that 'predictive' is an unfortunate word-choice here. Of course, by using greater lookahead, one can obtain a greater variety of grammars, but at the cost of greater complexity (both in the sense of complication, and in the sense of resource-usage) to implement or use. However, [it would appear that the worst-case behaviour is not typical](http://en.wikipedia.org/wiki/LL_parser#Constructing_an_LL.28k.29_parsing_table), which does provide motivation for the question in a modern context.
Niel de Beaudrap
CC BY-SA 3.0
2015-04-20T20:35:36.653Z
@usul good point! I don't think the prof explained that it's the *maximum necessary lookahead*; this makes much more sense.
Jules
<grammars><parsing>
Is $LL(k)$ for large $k$ considered harmful? If so, why?
Jules
# Is $LL(k)$ for large $k$ considered harmful? If so, why?

(Asked by: username_0 on 2015-04-16)

I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well).

Over the course of the semester, the prof mentioned that grammars should be optimized to $LL(1)$ whenever possible. Unfortunately, he never explained properly why such grammars are "better." Wouldn't a greater lookahead make for more effective predictive parsing? Or is it considered harmful taking into account physical resource (RAM, CPU) constraints? Or do parsers with more lookahead simply become more complex than they're worth?

**Tags:** grammars, parsing
> **Comments:**
> **username_1**: *"Wouldn't a greater lookahead make for more effective predictive parsing?"* I'm not sure what you mean here ... $LL(k)$ means that it is sometimes *necessary* to read $k$ symbols ahead in order to make the correct parse at the current point, while $LL(1)$ only needs to look one symbol ahead.  
> **username_2**: I expect that 'predictive' is an unfortunate word-choice here. Of course, by using greater lookahead, one can obtain a greater variety of grammars, but at the cost of greater complexity (both in the sense of complication, and in the sense of resource-usage) to implement or use. However, [it would appear that the worst-case behaviour is not typical](http://en.wikipedia.org/wiki/LL_parser#Constructing_an_LL.28k.29_parsing_table), which does provide motivation for the question in a modern context.  
> **username_0**: @usul good point! I don't think the prof explained that it's the *maximum necessary lookahead*; this makes much more sense.  

---

## 1 answers

### Answer by username_3 on 2015-04-20. Score: 4 | Accepted answer

The parsing table of a $LL(k)$ grammar grows exponentially in $k$.
This is however the worst-case scenario, which is not typical, as Niel pointed out:
For an $LL(k)$ grammar $G$, $k$ is the size of the maximal lookahead needed across $L(G)$.
But it appears that in practice, the need for a $k$ lookahead is restricted to a small portion to the language, so that the size of the parsing table remains reasonable.

We face here a quite common problem of theoretical complexity not reflecting the practical experience.
Beyond $LL(k)$ are $LL(\*)$ grammars, whose lookahead is adaptative, so as to keep the parsing table no larger than necessary.
$LL(\*)$ technique is examplified by [ANTLR](http://www.antlr.org), and described in this [paper](http://www.antlr.org/papers/LL-star-PLDI11.pdf) by Terence Parr.

Finally, I would say that many teachers focus on $LL(1)$ to emphasize that $LL(1)$ suffices to parse most languages in *practice*.
Philosophically, our programming languages lie somewhere between Deterministic and Non-Deterministic Pushdown Automata, but in fact way closer to DPA than to the full NPA.
A similar observation can be done for [natural languages](http://en.wikipedia.org/wiki/Mildly_context-sensitive_grammar_formalism): context-free is not enough, yet context-sensitive is way too powerful.

> **Comments:**
> **username_0**: Thanks for the answer! The ANTLR paper is a fantastic reference.  
> **username_4**: Is there a formal proof that $LL(k)$ requires something like $c^k \log n$ bits of space, where $n$ is the number of symbols in the alphabet?  Or is the statement "the parsing table grows exponentially in $k$" (in the worst case) an informal observation, like "SAT takes exponential time" (in the worst case)?  
> **username_3**: @András It is the very definition of $LL(k)$: non-determinism in the pushdown automaton can be solved by looking ahead at most $k$ characters. The parsing table associates a state to each pair $(s,u)$ (where $s$ is a state in the automaton, and $u$ a word of length $k$). The worst case is not avoidable, although such languages are somewhat artificial.  
> **username_4**: @Boson: that sounds like an informal argument.  Clearly $O(c^k \log n)$ is an upper bound, since that is enough to construct a parsing table.  But it may be possible to formalise what it means to parse the language but without requiring a parsing table to be used to do so, so this is only a lower bound for the class of algorithms that construct a parsing table.  
> **username_3**: @AndrásSalamon: Given a context-free grammar $G$ and a word $u$, whether $u \in L(G)$ is done in polynomial time (e.g. with CYK algorithm). In practice, $u$ is quite long (typically a compilation unit) and we want time _linear_ in $|u|$. Lookahead achieves such linear time in $|u|$, at the cost of space to store the parsing table (convenient if you want to parse several words, e.g. a compiler). The $k$-lookahead parsing algorithm thus runs in time $\mathcal{O}(f(k) |u|)$ *on the class of $LL(k)$ grammars*. If I understand well, you ask about a lower bound on $f(k)$, am I right?  
> **username_4**: @Boson: yes, I'd be interested in proving (or reading a proof of) an exponential dependence of space used on $k$.  This is of purely theoretical interest, I understand that usually $k$ is small and parsers have to be as close to constant time per input symbol as possible.  
> **username_3**: @AndrásSalamon: I wanted to be sure I got your question right.  The parsing table only depends on the grammar and $k$, so there is no need to store it. You could recompute it every time you need it and still achieve complexity linear in $u$ with no space overhead... Still, I do not think you can avoid time exponential in $k$ to decide what is the next rule to use, but I have no proof for it. Interesting question, though.  

---

