Re: C++ intermediate representation.

> Parsing C++ properly is no mean feat. C++'s grammar is ambiguous, as
> well as the basic type/identifier ambiguity C has, C++ has its own
> ambiguities. The new GCC's 3.4.x and 4.0 both use recursive descent
> with backtracking parser technology rather than LALR(1) or Generalized
> LR.
>
> The Elsa project, Elkhound's (a GLR parser generator) seems to have gotten
> stuck with parsing STL.
>
> http://www.cs.berkeley.edu/~smcpeak/elkhound/
>
> Recursive descent with backtracking may well be the simplest solution.


I will not argue with the assertion that parsing C++ is no mean feat.


I'm also not surprised that gcc is doing so with a recursive descent
backtracking parser. Many people write recursive descent parser
generators when faced with hard problems. In general, they claim that
the result is more maintainable, more correct, more simple, mother-
hood, apple-pie, and goodness. Since, enough of them say, perhaps
there is some truth to it. However, I am not convinced. I've worked
on some recursive descent parsers and later written equivalent
grammars and found the grammars to be more maintainable.


Irrespective of my opinion on the topic, there is three facts to
consider.


First, there is no grammar that one can parse with a backtracking
recursive descent parser that cannot be parsed with a GLR parser. I
believe Bernard Lang proved that any grammar that could be parsed with
an Earley parser could be parsed with a GLR parser. The parallel
processing that a GLR parsing does is equivalent in power to any
backtracking method.


Second, even if one is convinced that a backtracking recursive descent
parser is the desired implementation, there are many fine tools that
will create recursive descent parsers with backtracking from grammars.
Thus, one doesn't have write the parser by hand. Writing a grammar
and using a tool to translate it into code allows the grammar to be
checked that it is formally correct--something that is much harder to
do with code (and I've never heard of anyone doing on a hand-written
parser).


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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