Re: Ada 95 grammar for aflex?

["Ira D. Baxter" <idbaxter@semdesigns.com>]

> > Robert Dewar wrote:
> >
> > In article <3A69BA8F.A26A531E@uol.com.br>,
> >   Cesar Rabak <csrabak@uol.com.br> wrote:
> > > On your lines it continues with "...C++ was not a new
> > > experimental language, it was an almost compatible superset
> > > of C - and at that tim nobody had been able to write an
> > > LARL(1) grammar for C. The LARL(1) grammar used by ANSI C was
> > > constructed by Tom Pennello about a year and
> > > half later - far too late to benefit me and C++."
> >
> > I find that a bit odd, there has been no problem in
> > constructing the necessary grammars for parsing C with these
> > kind of tools, and they have been around for years, but that's
> > not the issue.
> >
> > The issues are
> >
> > a) these tools generate rather slow parsers. This is fixable.

And maybe it doesn't matter that much.  After all, if parsing is only 10%
of the compile time...

> >
> > b) these tools generate junk error messages. This is also
> > quite fixable. ...

> > If you are not interested in error recovery, there is
> > absolutely no difficulty in writing a table driven parser
> > for C++.

Even if you are interested in error recovery, you can build
good error recovery in a table driven parser.
You just can't use the simple hack provided by YACC and its clones.

> > To be fair, many other C++ compilers give equally horrible
> > error messages, but they do not seem to suffer from the time
> > penalty in parsing to such an extent.
>
> > Parsing should take zero time. In my assembly language scanner
> > and parser for Ada 83, which runs at something approaching
> > ten million lines a minute on a fast PC, perhaps more, I have
> > not run it for a while, parsing takes less than 10% of the
> > total time (the rest is I/O and lexical analysis).

That's impressively fast, but it depends on what you mean by "parsing".
Our automatically generated
parsers automatically capture identifier
and other kinds of strings and place them in string dictionaries,
carry out integer and floating point value conversions,
produce abstract syntax trees,
capture and attach comments and source line information
to AST nodes, etc.

If you stick to just and-coded lexing and recursive descent recognition,
you can go pretty fast.  When you start to add other work,
(all the above) it slows down some (remember Amdahl's law).

Its still OK.  Even with all
extra work, and not a lot of optimization, we manage
to generate parsers that do several thousand lines per second
(180K lines/minute).   We assume with hard work
(the kind you do to produce "assembly langauge parsers"),
we can generate parsers that are twice as fast.


--
Ira D. Baxter, Ph.D.,CTO           email: idbaxter@semdesigns.com
Semantic Designs, Inc.              web: http://www.semdesigns.com
12636 Research Blvd. C-214    voice: (512) 250-1018 x140
Austin, TX 78759-2200             fax: (512) 250-1191