7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ "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. $\endgroup$ – usul Apr 18 '15 at 2:49
  • 1
    $\begingroup$ 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, which does provide motivation for the question in a modern context. $\endgroup$ – Niel de Beaudrap Apr 18 '15 at 5:54
  • 1
    $\begingroup$ @usul good point! I don't think the prof explained that it's the maximum necessary lookahead; this makes much more sense. $\endgroup$ – Jules Apr 20 '15 at 20:35
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer! The ANTLR paper is a fantastic reference. $\endgroup$ – Jules Apr 20 '15 at 20:36
  • 1
    $\begingroup$ 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)? $\endgroup$ – András Salamon Apr 22 '15 at 14:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Boson Apr 22 '15 at 14:41
  • $\begingroup$ @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. $\endgroup$ – András Salamon Apr 23 '15 at 0:40
  • $\begingroup$ @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? $\endgroup$ – Boson Apr 23 '15 at 9:15

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.