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

J.Lampe (lampe@math.tu-dresden.de) wrote:
: 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.


In general I absolutely support Jurgen. Some of you will know about my
RDP parser generator which is an LL(1) tool. We haven't put out a
version recently because we have been working on its big brother GRDP
(generalised recursive descent parsing). Our strategy is to build a
parser generator which can generate parsers for any grammar (including
ambiguous ones) and then offer the user advice on how to improve
performance by factorising the grammar and employing a few other
useful transformations. We don't apply transformations automatically
bacause that can lead to pretty unreadable parsers (not that that
would worry a YACC user, of course!) and make it hard for users to put
their semantic actions in. The project has given us a lot of insights
into the kinds of grammars that real people write. They are mostly
pretty linear already, but it certainly is possible to write grammars
that generate parsers with exponentially bad performance.


We will be putting out some papers and new tools fairly soon covering
the general area of prototyping with general parsers and then tuning
them for production use.


                                                      Adrian


--
    Dr Adrian Johnstone, Dean of the Science Faculty, Dept of Computer Science,
        Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email: adrian@dcs.rhbnc.ac.uk Tel: +44 (0)1784 443425 Fax: +44 (0)1784 443420
--

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