Ada 95 grammar for aflex?

Ada 95 grammar for aflex?

[Ralf Reißing]

I'd like to make lexical analysis of Ada 95 code, 
so I am looking for an Ada 95 grammar for aflex. 

All I found so far was a lex grammar mentioned in the FAQ, e.g. at
ftp://ajpo.sei.cmu.edu/public/ada9x/rm9x/lexer9x.l, but the file
can not be found on the server anymore.

Alternatively I'd be interested in an Ada package that does the
job of a lexical analyser which splits an Ada file into a token
stream. I've taken a look at the lexical analyser of gnat, but it
seems to be quite complex and heavily coupled to other gnat
packages.

TIA,
	Ralf

Re: Ada 95 grammar for aflex?

[Frode Tenneboe]

Ralf Rei�ing <reissing@informatik.uni-stuttgart.de> wrote:
: I'd like to make lexical analysis of Ada 95 code, 
: so I am looking for an Ada 95 grammar for aflex. 

: All I found so far was a lex grammar mentioned in the FAQ, e.g. at
: ftp://ajpo.sei.cmu.edu/public/ada9x/rm9x/lexer9x.l, but the file
: can not be found on the server anymore.

You might find what you are looking for here:

ftp://ftp.fh-mannheim.de/pub/software/languages/ada/docs/standards/95lrm_rat/

 -Frode

-- 
^ Frode Tenneb�                    | email: ft@edh.ericsson.se      ^
| Ericsson Radar AS. N-1788 Halden |                                |
| Phone: +47 69 21 41 47           | Frode@IRC                      |
| with Standard.Disclaimer; use Standard.Disclaimer;                |

Re: Ada 95 grammar for aflex?

[Ted Dennison]

In article <3A6703BD.5D78D62@informatik.uni-stuttgart.de>,
  Ralf =?iso-8859-1?Q?Rei=DFing?= <reissing@informatik.uni-stuttgart.de>
wrote:
> I'd like to make lexical analysis of Ada 95 code,
> so I am looking for an Ada 95 grammar for aflex.

Go to http://www.adaic.org/standards/ada95.html and follow the
appropriate links.


> Alternatively I'd be interested in an Ada package that does the
> job of a lexical analyser which splits an Ada file into a token
> stream. I've taken a look at the lexical analyser of gnat, but it
> seems to be quite complex and heavily coupled to other gnat
> packages.

Take a look at OpenToken at
http://www.telepath.com/dennison/Ted/OpenToken/OpenToken.html

It comes with an Ada lexical analyzer (along with lots of examples).
There's a good chance it will do exactly what you want.

--
T.E.D.

http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Mario Amado Alves]

> [...] I've taken a look at the lexical analyser of gnat [...]

Where is it? I'd like to take a look at this also, as I am looking for an
alternative to lex/yacc, ASIS, OpenToken.

| |,| | | |RuaFranciscoTaborda24RcD 2815-249CharnecaCaparica 351+939354005
|M|A|R|I|O|
|A|M|A|D|O|DepartmentoDeInformaticaFCT/UNL 2825-114 Caparica 351+212958536
|A|L|V|E|S|                                                  fax 212948541
| | | | | |                 maa@di.fct.unl.pt                FCT 212948300

Re: Ada 95 grammar for aflex?

[Robert Dewar]

In article <mailman.979902730.6955.comp.lang.ada@ada.eu.org>,
  comp.lang.ada@ada.eu.org wrote:
> > [...] I've taken a look at the lexical analyser of gnat
[...]
>
> Where is it? I'd like to take a look at this also, as I am
> looking for an alternative to lex/yacc, ASIS, OpenToken.


The lexical analyzer for GNAT can be found in the GNAT sources,
available from any GNAT mirror site.


Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Cesar Rabak]

Robert Dewar wrote:
> 
> In article <mailman.979902730.6955.comp.lang.ada@ada.eu.org>,
>   comp.lang.ada@ada.eu.org wrote:
> > > [...] I've taken a look at the lexical analyser of gnat
> [...]
> >
> > Where is it? I'd like to take a look at this also, as I am
> > looking for an alternative to lex/yacc, ASIS, OpenToken.
> 
> The lexical analyzer for GNAT can be found in the GNAT sources,
> available from any GNAT mirror site.

But, IIRC, it was hand made and not written in a language like
[f]lex/yacc. Did this change?

Re: Ada 95 grammar for aflex?

[Robert Dewar]

In article <3A68877B.C7AF95D2@uol.com.br>,
  Cesar Rabak <csrabak@uol.com.br> wrote:
> Robert Dewar wrote:
> >
> > In article
<mailman.979902730.6955.comp.lang.ada@ada.eu.org>,
> >   comp.lang.ada@ada.eu.org wrote:
> > > > [...] I've taken a look at the lexical analyser of gnat
> > [...]
> > >
> > > Where is it? I'd like to take a look at this also, as I
am
> > > looking for an alternative to lex/yacc, ASIS, OpenToken.
> >
> > The lexical analyzer for GNAT can be found in the GNAT
sources,
> > available from any GNAT mirror site.
>
> But, IIRC, it was hand made and not written in a language
like
> [f]lex/yacc. Did this change?

No, but the question (see quote above) was a request
specifically for information on the GNAT lexical analyzer.

To use something like lex for a lexical analyzer in a
production compiler is a real mistake, because the resulting
lexical analyzer is much less efficient than a straightforward
hand written analyzer, tends to produce much worse error
messages, and saves a negligible amount of effort.

Lex is fine for occasional use in generating command language
user interfaces, but it not a tool for real compilers.

As for yacc, this particular tool is dreadfully out of date,
generates perfectly awful error messages (since it is not
informed by decades of work on error recovery), and also if
you are not careful tends to generate slow parsers.

As for the issue of whether a modern up to date parser
generator (see the work of Fisher and Charles, IBM and NYU,
in this area, which was used for Ada/Ed) is the right choice,
or a hand written parser, that's still an arguable discussion.

GNAT is a hand written parser, and is intended as a
demonstration of what can be achieved by hand writing parsers
with respect to error recovery (e.g. its ability to distinguish
between semicolon and IS in subprograms and correct wrong
usage).

Recently there have been discussions of the parser in g++.
Amazingly, this parser takes significant time, indicating one
of the results of less than careful use of automated parsers.
Parsing should take no detectable time if a parser is well
written. There is by the way an active funded project to
replace the g++ parser with a hand written version.



Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Cesar Rabak]

Robert Dewar wrote:
> >
> > But, IIRC, it was hand made and not written in a language
> like
> > [f]lex/yacc. Did this change?
> 
> No, but the question (see quote above) was a request
> specifically for information on the GNAT lexical analyzer.

Yes, I just understood that the OP was thinking of a "grammar" file.

> 
> To use something like lex for a lexical analyzer in a
> production compiler is a real mistake, because the resulting
> lexical analyzer is much less efficient than a straightforward
> hand written analyzer, tends to produce much worse error
> messages, and saves a negligible amount of effort.

I second this, we learned this by hard way while working in a parser for
ASN.1 in the earlier 90s...

> 
> Lex is fine for occasional use in generating command language
> user interfaces, but it not a tool for real compilers.
> 
> As for yacc, this particular tool is dreadfully out of date,
> generates perfectly awful error messages (since it is not
> informed by decades of work on error recovery), and also if
> you are not careful tends to generate slow parsers.
> 
> As for the issue of whether a modern up to date parser
> generator (see the work of Fisher and Charles, IBM and NYU,
> in this area, which was used for Ada/Ed) is the right choice,
> or a hand written parser, that's still an arguable discussion.

I was thinking exactly if this had changed, and it seems that not. Thank
you for the present status!

> 
> GNAT is a hand written parser, and is intended as a
> demonstration of what can be achieved by hand writing parsers
> with respect to error recovery (e.g. its ability to distinguish
> between semicolon and IS in subprograms and correct wrong
> usage).

I remember this being discussed in an earlier paper describing GNAT (and
GIGI) by NYU. I passed that to my professors in compiler design at that
time (after I finished their courses just in case!).

> 
> Recently there have been discussions of the parser in g++.
> Amazingly, this parser takes significant time, indicating one
> of the results of less than careful use of automated parsers.
> Parsing should take no detectable time if a parser is well
> written. There is by the way an active funded project to
> replace the g++ parser with a hand written version.

If this is a consolation. B. Stroustrup in his book "The Design and
Evolution of C++" reports that "...in retrospect, for me and C++ it was
a bad mistake [to use YACC].", pg. 69.

On your lines it continues with "...C++ was not a new experimental
language, it was an almost compatible superset of C - and at that time
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++."

So it seems that it still holds: if you're developing a professional
compiler, do it by hand!

Cesar

Re: Ada 95 grammar for aflex?

[Robert Dewar]

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.

b) these tools generate junk error messages. This is also
quite fixable. GNAT gives better error messages than Ada/Ed,
but at the time, people regarded Ada/Ed as having excellent
error messages, among the best around.

If you are not interested in error recovery, there is
absolutely no difficulty in writing a table driven parser
for C++. The problem with g++ is that it has grown rusty
with all kinds of kludges, and no one has had the nerve
to redo it from scratch which is what was needed :-)

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



Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Cesar Rabak]

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.
> 
> b) these tools generate junk error messages. This is also
> quite fixable. GNAT gives better error messages than Ada/Ed,
> but at the time, people regarded Ada/Ed as having excellent
> error messages, among the best around.

We agree on these.

> 
> If you are not interested in error recovery, there is
> absolutely no difficulty in writing a table driven parser
> for C++. The problem with g++ is that it has grown rusty
> with all kinds of kludges, and no one has had the nerve
> to redo it from scratch which is what was needed :-)

So we're detecting an opportunity for improvement! 

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

I never thought about this, and in fact with the monolithic binaries
they come I can't figure a way to benchmark the parsing of other
compilers.

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

Taking in account the functions of the parser, it makes all sense to me.
In fact it could be considered one of the "quality attributes" of a
compiler! So bad life is not so easy.

Cesar

Re: Ada 95 grammar for aflex?

[Larry Hazel]

Robert Dewar wrote:
> If you are not interested in error recovery, there is
> absolutely no difficulty in writing a table driven parser
> for C++. The problem with g++ is that it has grown rusty
> with all kinds of kludges, and no one has had the nerve
> to redo it from scratch which is what was needed :-)
> 
So Robert, are you going to write a new parser for g++ in Ada and show them up?

Larry

Re: Ada 95 grammar for aflex?

[Robert Dewar]

In article <3A6A418E.80F1ADC@uol.com.br>,
  Cesar Rabak <csrabak@uol.com.br> wrote:
> So we're detecting an opportunity for improvement!

Not really, there's nothing new here that has not been
known for a long time :-)



Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Robert Dewar]

In article <3A6A69A1.6A38AAC7@mindspring.com>,
  Larry Hazel <lhazel@mindspring.com> wrote:

> So Robert, are you going to write a new parser for g++ in Ada
> and show them up?

The new parser for g++ is being written by the code sourcery
folks, and I assume the language is traditional C :-)


Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Larry Hazel]

Robert Dewar wrote:
> 
> In article <3A6A69A1.6A38AAC7@mindspring.com>,
>   Larry Hazel <lhazel@mindspring.com> wrote:
> 
> > So Robert, are you going to write a new parser for g++ in Ada
> > and show them up?
> 
> The new parser for g++ is being written by the code sourcery
> folks, and I assume the language is traditional C :-)

But wouldn't it be neat to have a C++ compiler written in Ada that outperforms
other C++ compilers?

Larry

Re: Ada 95 grammar for aflex?

[Larry Kilgallen]

In article <3A6B1CCF.AC1363E1@mindspring.com>, Larry Hazel <lhazel@mindspring.com> writes:
> Robert Dewar wrote:
>> 
>> In article <3A6A69A1.6A38AAC7@mindspring.com>,
>>   Larry Hazel <lhazel@mindspring.com> wrote:
>> 
>> > So Robert, are you going to write a new parser for g++ in Ada
>> > and show them up?
>> 
>> The new parser for g++ is being written by the code sourcery
>> folks, and I assume the language is traditional C :-)
> 
> But wouldn't it be neat to have a C++ compiler written in Ada that outperforms
> other C++ compilers?

Only if it also had fewer defects.

But then it would be _great_ !!!

Re: Ada 95 grammar for aflex?

[Ira D. Baxter]

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

Re: Ada 95 grammar for aflex?

[Robert Dewar]

In article <t6olt4ohqu4la7@corp.supernews.com>,
  "Ira D. Baxter" <idbaxter@semdesigns.com> wrote:

> Even if you are interested in error recovery, you can build
> good error recovery in a table driven parser.

This is arguable. Here's a specific challenge. In the context
of a bottom up table driven parser, implement the error
recovery that GNAT does for semicolon used in place of IS and
vice versa (this is a particularly tough one).

Reall the issue is good vs excellent :-)

> That's impressively fast, but it depends on what you mean by
> "parsing".

I mean determining whether the given string is in the language
and giving a semi-decent error msg if it is not.

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

This would indeed slow things down (by probably a factor of 2
at most), so we would still be at millions of lines per minute.

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

Right, so that is perhaps a factor of 10-100 away from what
I can achieve in my asm program, which is what I would expect.

It is definitely the case that parsing efficiency is not
critical (or should not be :-), so the issue driving table
driven vs hand written parsers is indeed dealing with error
detection and recovery in an excellent manner!



Sent via Deja.com
http://www.deja.com/

Re: Ada 95 grammar for aflex?

[Warren W. Gay VE3WWG]

Larry Kilgallen wrote:
> 
> In article <3A6B1CCF.AC1363E1@mindspring.com>, Larry Hazel <lhazel@mindspring.com> writes:
> > Robert Dewar wrote:
> >>
> >> In article <3A6A69A1.6A38AAC7@mindspring.com>,
> >>   Larry Hazel <lhazel@mindspring.com> wrote:
> >>
> >> > So Robert, are you going to write a new parser for g++ in Ada
> >> > and show them up?
> >>
> >> The new parser for g++ is being written by the code sourcery
> >> folks, and I assume the language is traditional C :-)
> >
> > But wouldn't it be neat to have a C++ compiler written in Ada that outperforms
> > other C++ compilers?
> 
> Only if it also had fewer defects.
> 
> But then it would be _great_ !!!

Why encourage more C++?  Let it suffer from it's own problems ;-)

-- 
Warren W. Gay VE3WWG
http://members.home.net/ve3wwg