Re: Parsing Algorithms

"Ira D. Baxter" <>
19 Apr 2002 22:55:21 -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 (Vladimir Makarov) (2002-04-17)
Re: Parsing Algorithms (Ira D. Baxter) (2002-04-19)
| List of all articles for this month |

From: "Ira D. Baxter" <>
Newsgroups: comp.compilers
Date: 19 Apr 2002 22:55:21 -0400
Organization: Compilers Central
References: 02-04-069 02-04-077 02-04-096 02-04-109
Keywords: parse, practice
Posted-Date: 19 Apr 2002 22:55:21 EDT

"Vladimir Makarov" <> 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
> optimizations.

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.

Post a followup to this message

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