Re: Parsing Ada?

[Stephen Leake <stephen_leake@stephe-leake.org>]

Jacob Sparre Andersen <sparre@nbi.dk> writes:

> I have a project, which requires that I write/generate a parser for an
> Ada subset:

I'm guessing that the actual project requirements do not include "write
a parser", but rather talk about what information must be extracted from
the code. The decision to write a parser is a design decision. Since
that decision seems to be causing problems, it might be useful to
describe the project more fully, so we can suggest alternate solutions.

> + Only package specifications.
> + No use clauses.
> + No type, object or function declarations (only procedures).
> + Procedures can only have "in" parameters.
>
> I have attempted to use OpenToken to do the parsing, and although it
> seems to work fine as a parser, the options for extracting information
> from the parse tree are too limited (or maybe I just can't understand
> the documentation).

OpenToken does not generate a parse tree; you have to do that yourself
(if you actually need a tree) in either the tokens or the actions.

The OpenToken documentation is definitely lacking. The examples can be
helpful.

You don't describe what information you want to extract from the code,
so I don't know what features you need in the actions.

> I'm not that fond of generating the parser on-the-fly every time I run
> my program.  I would prefer to compile the grammar to Ada source text,
> which I then could compile into the program.

Original OpenToken provides a way to represent a grammar as Ada source. It
then generates the LALR parse tables at runtime; that is a burden on the
target system.

OpenToken wisi-generate represents the grammar in something close to
BNF, and then generates Ada code that represents the parse tables
directly.

One advantage of original OpenToken is that it is easy to specify
actions in Ada, with full access to the parsed tokens as they are
produced. With wisi-generate, it is not as easy to write appropriate
actions (what you want is almost definitely not directly supported by
wisi-generate at the moment).

> What open source parsers/parser generators are there for use in Ada
> programs?  And what are your experiences with them?

If you are processing compilable Ada code, then ASIS is a good approach;
the parser is already written and maintained, and you can focus on the
real project requirements.

Note that ASIS does not produce a parse tree either; it just gives you
structured access to the source. ASIS code tends to feel like a
recursive descent parser (at least, for the tools I've written in ASIS).

AdaControl (http://www.adalog.fr/en/adacontrol.html) provides a large
set of tools built on top of ASIS that you might find useful.

> So far I've found:
>
> + OpenToken
> + AdaGOOP
> + ayacc

I have not tried AdaGOOP.

ayacc is no longer maintained, and appears to be a simple translation of
C yacc (and thus hard to maintain!). It also does not generate a parse
tree for you; you have to provide the actions that do what you want.

As Dmitry points out, writing a recursive descent parser for a subset of
Ada should not be hard. More general parser tools are useful when you
need a parser quickly, or for grammars produced by others (that's my
goal with the Emacs package I'm working on).

If your project requirements might change in the future to expand the
subset, then a general parser tool will be easier to adapt than a
recursive descent design that takes advantage of the subset. Or using a
full Ada parser in the first place (ie ASIS, or ada-grammar.wy from
Emacs ada-mode) would be a good idea.

If you are required to verify that the source code conforms to the
subset, then a using a full Ada parser will complicate things; you have
to explicitly disallow lots of stuff, rather than explicitly allowing
only the subset.

I don't think the choice of parser tool is causing your problem, but I'm
not sure what your problem is.

-- 
-- Stephe