|Algorithms ACA99SRV@sheffield.ac.uk (Steve Vernon) (2002-04-10)|
|Re: Algorithms firstname.lastname@example.org (2002-04-13)|
|Re: Algorithms email@example.com (Joachim Durchholz) (2002-04-16)|
|Re: Algorithms firstname.lastname@example.org (Vladimir Makarov) (2002-04-17)|
|Re: Parsing Algorithms email@example.com (Ira D. Baxter) (2002-04-19)|
|From:||"Ira D. Baxter" <firstname.lastname@example.org>|
|Date:||19 Apr 2002 22:55:21 -0400|
|References:||02-04-069 02-04-077 02-04-096 02-04-109|
|Posted-Date:||19 Apr 2002 22:55:21 EDT|
"Vladimir Makarov" <email@example.com> wrote in message
> .... Computers are fast enough now to use Earley
> parser for many tasks.
> ,,, 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
Tomita (GLR) parsers are pretty good at this. We parse about 10K
lines/sec of Java source on 200 Mhz Pentium II, including building the
trees, which ought to be something better than 25K lines/sec on the
equivalent 500Mhz Pentium III. (Our C numbers are slower, because we
try to parse the preprocessor directives and end up with rather a lot
of dead parsers).
>. 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. Using the same translation
>the problem is solved (more accurately, you postpone the solution to
>a semantic analyzer).
This capability is a property of any parser that can handle an
ambiguous parse. Our GLR parsers construct ambiguous trees, and we
often resolve those in a later attribute-evaluation pass which
computes symbol tables.
Ira D. Baxter, Ph.D. CTO Semantic Designs, Inc.
Return to the
Search the comp.compilers archives again.