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?
Is $LL(k)$ for large $k$ considered harmful? If so, why?
grammars;parsing
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, and described in this paper 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: context-free is not enough, yet context-sensitive is way too powerful.