Parser implementations in Paris

[Helene.Kirchner@loria.fr]

I forward you an e-mail from Frederic Voisin.
We will discuss it at the next Tools group meeting.
Helene

-----------------------------------------------------------------------

Dear All,

Since none of Michel Bidoit, or us (Christophe Tronche at Cachan and
Frederic Voisin at Orsay) are able to attend the next Tools meeting, you will
find below a summary of the current state of achievement from the Paris+Cachan
group in charge of developing CASL parsers. Note that People from Bremen
(Isabelle) and Aarhus (ASF+SDF) may also have some working prototypes...

1. Christophe has developed at Cachan a parser+scanner based on LL(2)
technology. The parser is currently restricted to basic and structured
specifications, i.e. it does not handle libraries or architectural
specifications (anyway, there are very few examples of the latter,
yet). Annotations are not supported yet.

Although the parser is probably not bug-free it seems mostly correct, up to
the current description of the syntax. People may want more flexibility
at the lexical level, for instance to declare operators including {, }, [ or ]
symbols INSIDE a sequence of symbols (as in [| __  |]). This seems to be
illegal in the current wording of the syntax that requires { and } to be
balanced within an identifier (and the above declaration uses two
ids: [| and \]). Note that changing the current wording to allow
[ and ] inside tokens may conflict with compound identifiers, as in
|[a] that can be a use of |[ __ ] applied to a, or the use of the (compound, 
generic) |[elem] : -> stuff[elem] instantiated with 'a'.

2. A set of specifications has been derived from the ones that were in the
Paris+Bremen early proposals so that each rule of the LL(2) grammar has been
tested at least once (see http://www.lsv.ens-cachan.fr/~tronche/cofi/).
Christophe is currently waiting for new specifications that could be used to
test the parser. This can easily be done by submitting your favorite examples
to his parser. For that, simply connect your internet browser to the above URL
and you can use Christophe's parser without having to install it on your
site.

An extension of the web interface will soon allow you to record your
specification (and the resulting output !) in files so we can build a
repository of test examples. This will be needed when performing
back-to-back testing of parsers developed at different sites.

3. Christophe has made some proposal (follow the link from the above
URL !) for some common output format for the various parsers
developed. The idea is to debug the parsers by comparing them against
each other in an automatic fashion on a common set of examples. To do
this, each parser should output the result of the parsing in a
precise, parser-independant way, hence the proposal. It is a LISP-like
format that mimic much of the rules of abstract syntax presented in
Peter's current proposal. The rules of the abstract syntax of the form
A ::= B | C are the only ones that have no equivalent in the proposed
format. We haven't felt tied by the proposed exchange formats for the
various tools, because our only point is to compare the parsers, not
to have a general communication mechanism. We now hope to reach a
consensus with every parsers'developers on the format that should be
output, and then to see it implemented in as many parsers as possible.

4. Frederic is finishing a prototype using Lalr technology (more precisely
using the SYNTAX compiler generation tool developed at INRIA, but that
results in a stand-alone parser+scanner written in C). No major problem was
revealed at the syntax level but the prototype still needs some work at
the interface between the scanner and the parser (mainly due to juxtaposition
of terms and the liberal way of naming operators that we have in CASL). This
should be finished "soon" and will produced as output a file that obeys
Christophe's format. A similar Web interface will be provided, allowing people
to test their specifications without having to download the parser.


This is the current state of CASL parsers, developed locally. The next steps
will be to check the various parsers one against the others, and then to
start the "real" work: semantics checks + outputting the real abstract
representation used by tools. For this latter phase, the efforts in Cachan and
Orsay will be merged and result in a single prototype.

Apologies again for not being able to attend the meeting, and we are really
looking forward reading your reactions and the minutes of the meeting.

Cheers,

Frederic + Christophe