Re: Parsing Algorithms

"Ira D. Baxter" <idbaxter@semdesigns.com>
19 Apr 2002 22:55:21 -0400

          From comp.compilers
Related articles
Algorithms ACA99SRV@sheffield.ac.uk (Steve Vernon) (2002-04-10)
Re: Algorithms haberg@matematik.su.se (2002-04-13)
Re: Algorithms joachim_d@gmx.de (Joachim Durchholz) (2002-04-16)
Re: Algorithms vmakarov@redhat.com (Vladimir Makarov) (2002-04-17)
Re: Parsing Algorithms idbaxter@semdesigns.com (Ira D. Baxter) (2002-04-19)
| List of all articles for this month |
From: "Ira D. Baxter" <idbaxter@semdesigns.com>
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" <vmakarov@redhat.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
> 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.
http://www.semdesigns.com

Post a followup to this message

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