LL vs. LR, was Compiler Compiler Compiler

>It may depend on how the LL(k) parser is implemented. Experimental
>results by Terence Parr (sorry, I've lost the reference, but it was
>probably either on www.antlr.org or www.polhode.com/pccts.html)
>suggested that function-call overhead is actually extremely small now,
>so a generated recursive-descent parser was faster than its equivalent
>table-driven LL(k) parser. This may also have something to do with
>the fact that the tables are either compressed (and therefore require
>a certain amount of additional manipulation to find the correct value)
>or very large (and therefore don't fit in the processor's cache).
>Table-driven parsers' main loop tends to be fairly large too.


In the case of k=1, the LL(1) parse algorithm is compact and
efficient. It either matches a token against the input or does a
single table lookup to find the predicted production. That production
consists of a sequence of integers that is pushed onto the parse
stack. By contrast, a recursive-descent program generally uses a
select statement to decide which function to call next. This overhead
can be large, depending on the number of cases, and is in addition to
the function call overhead.


For k>1, LL(k) parsing is intractable for the same reason as LR(k) and
even LR(1): too many states. Strong LL(k) greatly reduces the number
of states by using less of the left context of the parse. There are
only two table-driven strong LL(k) parsing methodologies. Aho/Ullman's
and mine. Yoshida and Takeuchi (1992) have shown that the space
requirements for the Aho/Ullman algorithm are too great to make it
useful for a typical programming language. As mentioned, compression
only converts the space complexity to computational. So, a comparison
of recursive-descent with the Aho/Ullman method does not really
address the general question of table-driven vs. recursive-descent
performance. It simply shows the obvious result that a linear
algorithm is faster than a non-linear one. More to the point would be
to compare the LL(1) method to recursive-descent parsing.


>Indeed, the table-driven LL parser's prediction stack is almost
>certain to be implemented on the heap as a linked list or dynamically
>sized array, whereas the recursive-descent stack is the standard
>program stack. Programming languages tend to be a lot faster with
>stack-allocation than with dynamic memory allocation.


SLK generated parsers use a form of the standard LL(1) parse stack. It
is a 128 integer array implemented as a local variable in the parse
function.


I have added a preprocessed-C recognizer to the download section of my
web page. It is a Win32 executable that can be used for direct
performance comparison with others.


http://pages.prodigy.net/dr_feriozi


----------------------------------------------------------------
Yoshida K. and Y. Takeuchi (1992). "An algorithm for constructing
a semi-LL(2) grammar's parsing table," J. Inf. Process. (Japan)
Vol. 15, No. 1, pp. 93-107.

Return to the comp.compilers page.
Search the comp.compilers archives again.