Parsing C++, was Is YACC / PCCTS used in commercial compilers?

jlilley@empathy.com (John Lilley) writes:
>I believe that the Edison Design Group, which markets high-quality
>parser front-ends, uses their own custom parser-generator tools which
>are based on LALR(1) techniques with extensions.


jsa@edg.com (J. Stephen Adamczyk) writes:
> Thanks for the mention, especially the "high-quality" part, but our
> front ends use recursive descent, with a precedence modification when
> handling expressions.


J. Kanze <kanze@gabi-soft.fr> wrote:
>From the different compiler people I've talked to, I get the
>impression that recursive descent dominates for C++. I suspect that
>this is at least partially due to the fact that certain C++ constructs
>are best handled using back-tracking, and most compiler generators
>don't support back-tracking.


I'm not sure that I entirely agree. Yes, using recursive descent and
backtracking makes the implementation of the parser easier,
considering the many complex ambiguities that exist in C++, but I'm
not sure I would call that the "best" approach, at least not from an
efficiency point of view.


Backtracking incurs a high execution overhead, which increases with
the complexity of the tokens being parsed, unless the "common"
non-backtracked path is carefully chosen to be the most frequent case,
which is often hard to determine ahead of time. LALR(1) has a more or
less linear execution time, with respect to the size of the token
stream, and doesn't increase greatly with the complexity of the
arrangements.


I've been developing a C++ parser as part of my thesis work, and I've
been using yacc to do the parsing, and even to resolve all the
ambiguities, by building up special rules for the ambiguous cases, and
rules that exclude the ambiguious cases that are used along with them.
And then my ambiguous cases build up a stack of actions to defer until
the meaning is clear, at which time they are executed in the
appropriate manner, depending upon the resolution.


This is all part of my 'CParse' set of C++ classes for C++ parsing,
which I will be releasing to the net in the coming months, on my
webpage.


Yes, my yacc grammar is probably more complex to read and understand
than a simplified recursive descent, but it never has to backtrack,
and for a language as common as C++, having a fast parser would seem
to justify the implementation time and effort.




Just a few thoughts...
any comments?


--
Frank "Shaggy" Barrus: shaggy@csh.rit.edu; http://www.csh.rit.edu/~shaggy
--

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