RE: C++ intermediate representation.

I quoted Stroustrup:


> > (Stroustrup states recently that "today, most production C++
> > compilers have hard-coded recursive descent parsers. Note that part
> > of the reason for that is compactness, speed, and quality of error
> > messages." [Stroustrup 2003])


Ralph Boland replied:


> I tend to think the goal of parser generator tools is to be so
> effective that all parsers (except perhaps trivial ones) be built
> using parser generator tools. This means they need to achieve a level
> of "compactness, speed, and quality of error messages" amoung other
> things that is competive with hand written parsers if not better.


In fact, if speed optimization is a goal, it's sometimes possible to
make a generated parser that is faster than a hand optimized
version. The paper in which I cited Stroustrup shows just such a C++
grammar and its results.


> In the case of C++ we appear to be behind.


I've been working on an O(n) C++ grammar (without ad hockery) for some
years now. It's top-down adaptive. It's no small chore.


> How far behind are we?
>
> How far behind are we for other common languages?


It's even possible to write grammars that produce an O(n) parser for a
large portion of Perl without resorting to ad hockery. Perl is a
*very* nasty language to write a formal grammar for, compared to C++.


Languages such as Lua and C# -- quite easy to write grammars that yield
linear parsers.


> What are the most important areas for parser generator tools to
> improve upon first?


> Building good utilities for effective debugging of grammars is not
> overly difficult so why such a poor job is done in this area is beyond
> me.


Such tools exist. The Grammar Forge has a production profiler with
high resolution, for instance, and hit/miss counting. The key to doing
this is to code the hooks for profiler instrumentation right into the
parsing engine, from day one, and to optimize the engine extensively
against "typical" input.


--
Chev. Quinn Tyler Jackson
Computer Scientist, Novelist, Poet


http://members.shaw.ca/qjackson/

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