Re: Algorithms

Vladimir Makarov <>
17 Apr 2002 23:22:56 -0400

          From comp.compilers

Related articles
Algorithms (Steve Vernon) (2002-04-10)
Re: Algorithms (2002-04-13)
Re: Algorithms (Joachim Durchholz) (2002-04-16)
Re: Algorithms (Ralph Boland) (2002-04-17)
Re: Algorithms (Vladimir Makarov) (2002-04-17)
Re: Algorithms (Joachim Durchholz) (2002-04-19)
Re: Parsing Algorithms (Ira D. Baxter) (2002-04-19)
| List of all articles for this month |

From: Vladimir Makarov <>
Newsgroups: comp.compilers
Date: 17 Apr 2002 23:22:56 -0400
Organization: Red Hat (Toronto)
References: 02-04-069 02-04-077 02-04-096
Keywords: parse
Posted-Date: 17 Apr 2002 23:22:56 EDT

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

    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

    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

Post a followup to this message

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