Subject: [Tools-discuss] Eustathius, a program to generate texts from formal grammars

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 26 Oct 2006 15:40:36 +0200

It may have a place in http://tools.ietf.org/inventory/verif-tools?

http://www.bortzmeyer.org/eustathius-test-grammars.html

Eustathius is a set of programs to test ABNF grammars by parsing them 
and generating texts which obey the grammar.

You can use it to test ABNF in documents like the RFC or to test a 
parser that you have written.

Eustathius can be downloaded (en ligne sur 
http://www.bortzmeyer.org/files/eustathius.tar.gz). It will require an 
Haskell compiler to build.

You are free to use it, accoding to the GPL.

Here is a sample grammar (you can find many others, typically extracted 
from the RFCs in the tests/ directory of the distribution) of a 
Lisp-like programming language:

program = expr

expr = spaces "(" spaces *(expr / term ) spaces ")" spaces

term = 1*ALPHA

spaces = *WSP

And here is the result of parsing with
abnf-parse, a program of Eustathius:

% ./abnf-parse tests/minilisp.abnf
program : expr
expr : Seq[spaces ( spaces 0*10Choice[expr term] spaces ) spaces]
term : 1*10ALPHA
spaces : 0*10WSP
...
All the rules:
expr:  (UNsafe)
term:  (Safe)
...
 (Safe are the rules for which there is at least a terminal in
the next N steps.)

After that, you can use Eustathius to generate sample programs, for 
instance to give them to your parser:

% ./abnf-generate -s program tests/minilisp.abnf
(        (      eWbejp   (  )(   kwMRMhvamEcGMLTDWGhTlooAXHQmzmwYiqEMn
)       erDZ)LXfhB ()ZtkatUFlSZ         (yrKg    (daaLeuAxXFGZq)
) (ObMi(y       )  CoqZBW(qET  )                )               )  

Remember that the ABNF grammar only describes the syntax. Some semantic 
rules are not, or cannot be expressed in the grammar and therefore, 
Eustathius can produce texts which are not legal. For instance, in RFC 
3339, you find a grammar to generate dates and it does not protect 
against months > 12, so Eustathius can do:

 % ./abnf-generate -s date tests/date.abnf
2679-73-08

Thanks to Kim-Minh Kaplan (http://www.kim-minh.com/) for his help and 
the discussions.

_______________________________________________
Tools-discuss mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tools-discuss

---

From: Lars Eggert <[email-masked]>
Date: Thu, 26 Oct 2006 16:12:39 +0200

> and generating texts which obey the grammar.

Very cool!

Anyone have a script handy that can extract ABNF from RFCs?

With that, we could then automate the check for well-formedness of  
ABNF that the latest PROTO writeup requires (item 1.j of the writeup  
in http://tools.ietf.org/wg/proto/draft-ietf-proto-wgchair-doc- 
shepherding/draft-ietf-proto-wgchair-doc-shepherding-08.txt)

Lars
-- 
Lars Eggert                                     NEC Network Laboratories

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 26 Oct 2006 16:21:12 +0200

On Thu, Oct 26, 2006 at 04:12:39PM +0200,
 Lars Eggert <[email-masked]> wrote 

> Anyone have a script handy that can extract ABNF from RFCs?

I did it by hand. From the text version, it is obviously
difficult. Shouldn't we use <artwork type='abnf'> in RFC 2629bis,
which is precisely intended for that purpose?

http://xml.resource.org/authoring/README-dev.html#anchor11

---

From: Lars Eggert <[email-masked]>
Date: Thu, 26 Oct 2006 16:26:36 +0200

> which is precisely intended for that purpose?

Right, but typically I don't have the XML sources of IDs I need to  
review.

Lars

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 26 Oct 2006 16:58:39 +0200

On Thu, Oct 26, 2006 at 04:26:36PM +0200,
 Lars Eggert <[email-masked]> wrote 

> Right, but typically I don't have the XML sources of IDs I need to  

<troll>That's why XML format should be mandatory</troll>

Also, there are other problems:

* not all RFC have a collected ABNF (is there a policy about that?),
it is sometimes spread in various places in the document,

* there are often references to other RFC and there is no format for
this cross-referencing, it is free-text between angle brackets like
in RFC 4408:

   dot-atom         = <unquoted word as per [RFC2822]>
   quoted-string    = <quoted string as per [RFC2822]>

and sometimes not even that like in RFC 4501:

   dnsauthority    = host [ ":" port ]
                                ; See RFC 3986 for the
                                ; definition of "host" and "port".

---

From: Jari Arkko <[email-masked]>
Date: Thu, 26 Oct 2006 18:11:22 +0300

>                                 ; definition of "host" and "port".
And sometimes even without any mention of where
to search for the missing definitions :-( Well, there's
typically a reference somewhere in the document,
but you have to search all references or understand
the draft in order to find out...

(The getauthors tool has a heuristic to recognize
which drafts have ABNF in them, but not to find
the actual pieces. The heuristic is based on the
string ABNF and the reference, if I remember
correctly.)

--Jari

---

From: Henrik Levkowetz <[email-masked]>
Date: Thu, 26 Oct 2006 17:29:40 +0200

Hi Stephane,

> and generating texts which obey the grammar.

Thanks, I've added it to the inventory page.

Best,

	Henrik

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 26 Oct 2006 21:55:48 +0200

On Thu, Oct 26, 2006 at 05:29:40PM +0200,
 Henrik Levkowetz <[email-masked]> wrote 

> Thanks, I've added it to the inventory page.

May I suggest to add abnfgen as well, since it was the first?

http://www.quut.com/abnfgen/

Also, if people find these tools interesting and useful, wouldn't it
be a good idea to have them stored directly on tools.ietf.org, to
guarantee future availability?

---

From: Henrik Levkowetz <[email-masked]>
Date: Thu, 26 Oct 2006 22:17:53 +0200

Hi again,

> http://www.quut.com/abnfgen/

Sure. Added.

> guarantee future availability?

If a tool author would like to make a useful and relevant tool available
on tools.ietf.org, I'd be very happy to put it up there.  As most of us,
I'm however sufficiently busy to not easily find time to explicitly contact
and encourage individual tool creators to do so; but I'm positive to the
idea, and will work with anybody that would like their tool hosted on the
tools servers to arrange that.

Regards,

	Henrik

---

From: "Bill Fenner" <[email-masked]>
Date: Thu, 26 Oct 2006 14:52:38 -0700

> > and generating texts which obey the grammar.

Yes indeed, I had this intention when I wrote my parser but didn't
have the energy to go beyond parsing and error handling.

> Anyone have a script handy that can extract ABNF from RFCs?

Funny you should ask.  Try http://rtg.ietf.org/~fenner/ietf/aex

It has all sorts of heuristics to extract ABNF bits from the middle of
drafts.  It fails the hardest on documents with SDP examples in them,
since SDP looks awfully like ABNF.

  Bill

---

From: Tony Hansen <[email-masked]>
Date: Thu, 26 Oct 2006 17:56:02 -0400

Obviously, if anyone else contacts the author of a tool and encourages
them to contact Henrik about having it hosted on tools.ietf.org, I'm
sure that would be okay.

	Tony Hansen
	[email-masked]

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 27 Oct 2006 11:07:34 +0200

On Thu, Oct 26, 2006 at 02:52:38PM -0700,
 Bill Fenner <[email-masked]> wrote 
 a message of 19 lines which said:

> Try http://rtg.ietf.org/~fenner/ietf/aex
> 
> drafts.  

Cool also! 

It has problems with the following RFC:

* 2646: The frequent mention of "Format=Flowed" confuses it
* 2822: The free text at the end of 4.5.4 is included.
* 3339 : The free text at the end of 5.6 is included

---

From: "Bill Fenner" <[email-masked]>
Date: Fri, 27 Oct 2006 08:39:00 -0700

> * 2646: The frequent mention of "Format=Flowed" confuses it

Many of these are, unfortunately, nearly-valid ABNF.

> * 2822: The free text at the end of 4.5.4 is included.

It thinks this text is a continuation of the previous rule, since it's indented.

> * 3339 : The free text at the end of 5.6 is included

Similarly, this text appears to be a continuation.

aex's tradeoff is to over-extract; I have to edit its output about 40%
of the time but it always (as far as I've been able to tell) gets all
the ABNF in a document.  I'll see if I can straightforwardly teach aex
what characters can appear unquoted in ABNF, that will help some of
the false positives (I think all the examples you gave have commas in
the false positives, for example)

  Bill