Je suis Charlie

Autres trucs


Seulement les RFC

Seulement les fiches de lecture

Mon livre « Cyberstructure »


Eustathius, a program to generate texts from formal grammars

First publication of this article on 26 October 2006

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. 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 (specified in RFC 5234) 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

Similar or useful programs:

  • abnfgen is very similar to Eustathius. Written in C, it has interesting options which Eustathius currently does not have.
  • bnfparser (untested by me).
  • Other tools can be found at the IETF tools page.
  • Another ABNF tool in Haskell, which I did not notice before writing Eusthathius is included in hsemail.

Thanks to Kim-Minh Kaplan for his help and the discussions.

Version PDF de cette page (mais vous pouvez aussi imprimer depuis votre navigateur, il y a une feuille de style prévue pour cela)

Source XML de cette page (cette page est distribuée sous les termes de la licence GFDL)