LL vs. LR, was Compiler Compiler Compiler

"Dan Feriozi" <dr_feriozi@prodigy.net>
15 Apr 2001 22:50:08 -0400

          From comp.compilers

Related articles
Compiler Compiler Compiler danwang+news@cs.princeton.edu (Daniel C. Wang) (2001-03-22)
Re: Compiler Compiler Compiler mike@dimmick.demon.co.uk (Mike Dimmick) (2001-03-26)
Re: Compiler Compiler Compiler joachim_d@gmx.de (Joachim Durchholz) (2001-04-04)
LL vs. LR, was Compiler Compiler Compiler mike@dimmick.demon.co.uk (Mike Dimmick) (2001-04-10)
LL vs. LR, was Compiler Compiler Compiler dr_feriozi@prodigy.net (Dan Feriozi) (2001-04-15)
| List of all articles for this month |

From: "Dan Feriozi" <dr_feriozi@prodigy.net>
Newsgroups: comp.compilers
Date: 15 Apr 2001 22:50:08 -0400
Organization: Compilers Central
References: 01-03-095 01-03-122 01-04-026 01-04-053
Keywords: parse, LALR, LL(1)
Posted-Date: 15 Apr 2001 22:50:08 EDT

>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

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.


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.

Post a followup to this message

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