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

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
--

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