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

"J.Lampe" <lampe@math.tu-dresden.de>
9 Jan 1997 21:59:13 -0500

          From comp.compilers

Related articles
Is YACC / PCCTS used in commercial compilers? johnr@ims.com (1996-12-07)
Re: Is YACC / PCCTS used in commercial compilers? jlilley@empathy.com (1996-12-15)
Re: Is YACC / PCCTS used in commercial compilers? jsa@edg.com (1996-12-17)
Re: Is YACC / PCCTS used in commercial compilers? kanze@gabi-soft.fr (1997-01-02)
Parsing C++, was Is YACC / PCCTS used in commercial compilers? feb6399@osfmail.isc.rit.edu (1997-01-04)
Re: Parsing C++, was Is YACC / PCCTS used in commercial compilers? dlmoore@ix.netcom.com (David L Moore) (1997-01-07)
Re: Parsing C++, was Is YACC / PCCTS used in commercial compilers? lampe@math.tu-dresden.de (J.Lampe) (1997-01-09)
Re: Parsing C++, was Is YACC / PCCTS used in commercial compilers? adrian@dcs.rhbnc.ac.uk (1997-01-12)
| List of all articles for this month |

From: "J.Lampe" <lampe@math.tu-dresden.de>
Newsgroups: comp.compilers
Date: 9 Jan 1997 21:59:13 -0500
Organization: Techn. University Dresden
References: 96-12-051 96-12-102 96-12-124 97-01-011 97-01-037
Keywords: parse, C++, performance

Frank Barrus wrote:
>
> 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 think the impact of backtracking is widely overestimated. Usually
there are just a few tokens to be handled until it becomes clear
whether a certain branch will fail or not. Of course, one can
construct mad grammars with exploding complexity, but I doubt that
they can be parsed by one of the more efficient schemes.


I've done some measurments with a (not fully - it accepts the first
match) backtracking parser tool. Independent from the size of the
source, max. half of the total time was spent for investigation in
non-succeeding branches.


Jurgen Lampe
lampe@math.tu-dresden.de
http://www.math.tu-dresden.de/wir/staff/lampe/lampe.html
--


Post a followup to this message

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