Re: Algorithms

Joachim Durchholz wrote:
>
> Two Eiffel compilers use Earley parsers, and they are reasonably fast
> (at least in the parsing stage). I have never looked into these
> parsers, so I can't draw any conclusions from this observation.
>
> Regards,
> Joachim
> [Earley parsers get slow when they're parsing something ambiguous so they
> have to carry multiple parses. If your language is mostly unambiguous they
> should be OK. It's also my impression that they earned their reputation of
> slowness when computers were a lot slower and had far less memory than they
> have now. -John]


Yes, that is right. Computers are fast enough now to use Earley
parser for many tasks. Also Earley's algorithm can be considerably
improved with the point of view of used memory and parsing speed. As
example, I'd propose to look at the implementation of Earley algorithm
in Ammunition of Cocom toolset on


http://cocom.sourceforge.net/


    There are many tricks in the algorithm implementation. As the
result the algorithm implementation is sufficiently fast and does not
require much memory. It parses a 10K line C program for 1/3 sec and
uses 5Mb memory on 500Mhz PentiumIII under Linux. Gcc (with -O2)
compiles the same program for 3.5 sec and for 1.2 sec without
optimizations.


    You could implement a much better error recovery in Earley's parser
than one in YACC/BISON. The mentioned implementation uses a minimal
cost error recovery. It also implements a simple syntax directed
translation. You don't need to modify grammar in many cases when you
use Earley parser. For example, you don't need to modify a grammar to
solve the classical problem for C (usage of an identifier defined in
typedef). You could even use an ambiguous grammar. For example,
Oberon(2) has the following rules which result in an ambiguous grammar


        Designator : Designator '(' Qualident ')' # des_and_par (0 2)


        Factor : Designator '(' ExprList ')' # des_and_par (0 2)


Using the same translation the problem is solved (more accurately, you
postpone the solution to a semantic analyzer).


Vladimir Makarov

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