Re: Grammaires et pretty print

From: Pierre Weis (Pierre.Weis@inria.fr)
Date: Wed Dec 03 1997 - 18:38:29 MET


From: Pierre Weis <Pierre.Weis@inria.fr>
Message-Id: <199712031738.SAA20905@pauillac.inria.fr>
Subject: Re: Grammaires et pretty print
In-Reply-To: <199712022058.VAA02811@jaune.inria.fr> from Daniel de Rauglaudre at "Dec 2, 97 09:58:55 pm"
To: daniel.de_rauglaudre@inria.fr (Daniel de Rauglaudre)
Date: Wed, 3 Dec 1997 18:38:29 +0100 (MET)

> [English version further]
>
> > J'ai une question sur les grammaires et le pretty-print. Chaque fois
> > que je doit debugger un programme, je suis toujours plus ou moin amene
> > a definir des pretty printer
> > ...
> > De tels outils n'existent pas. Il doit y avoir une bonne raison, quel
> > est le point que j'ai loupe ??
>
> Le problème est que ça marche bien pour les grammaires simples. Dès
> que ça se complique un peu, ça ne marche plus aussi bien. En plus, pour
> peaufiner le truc, il faut ajouter des directives de pretty print
> (ajouter des blancs, des breaks, etc).

Effectivement, c,a ne marche bien que pour les grammaires
``injectives'', au sens ou` elles ne comportent pas de re`gles qui
ge'ne`rent deux fois le me^me arbre de syntaxe abstraite (sinon a`
l'inversion l'un des patrons (filtres ou patterns) devient inutile.

Conside'rez par exemple une grammaire qui comporterait des ``macros
syntaxiques'', c'est-a`-dire des constructions qui sont expanse'es
directement lors de l'analyse syntaxique. Par exemple, la re`gle
suivante permet de faire l'analyse syntaxique de l'ope'rateur boole'en
&&:

...
| [< e1 = expression; 'Kwd "&&"; e2 = expression >] -> If (e1, e2, Bool False)

A` l'inversion, on obtiendra (au passage, notez l'emploi des nouvelles
fonctionalite's du module Format avec sa nouvelle fonction printf):

| If (e1, e2, Bool False) ->
    printf "@[%a@ &&@ %a@]" (expression) e1 (expression) e2

ce qui fait que toutes les expressions ``if then else'' avec false en
partie else seront de'compile'es avec &&, ce qui n'est pas force'ment
souhaitable.

Plus grave encore, conside'rez des alias parfaits comme & aliasant &&
(comme dans la syntaxe actuelle de Caml Light et Objective Caml). On
obtient:

...
| [< e1 = expression; 'Kwd "&&"; e2 = expression >] -> If (e1, e2, Bool False)
| [< e1 = expression; 'Kwd "&"; e2 = expression >] -> If (e1, e2, Bool False)

A` l'inversion, e'videmment:

| If (e1, e2, Bool False) ->
    printf "@[%a@ &&@ %a@]" (expression) e1 (expression) e2
| If (e1, e2, Bool False) ->
    printf "@[%a@ &@ %a@]" (expression) e1 (expression) e2

Le deuxie`me cas est strictement inutilisable. On a le me^me proble`me
si l'on veut de'compiler un langage avec les constructions ``let'' et
``where''.

> Néanmoins, je suis d'accord, personnellement, quand je fais un pretty
> printer, et en particulier ceux de Camlp4, pr_o et pr_r, je les
> écrits symétriquement des parseurs (mais manuellement), en reprenant
> les mêmes noms de fonctions. C'est bien pratique. Mais, à mon sens, je
> trouve que ça ne s'automatise pas très bien.

Je suis d'accord avec toi. Cependant fournir un outil d'inversion
automatique n'est pas tre`s difficile, mais pourtant tre`s utile: cela
donne une premie`re approche du programme a` e'crire, qu'on fignole
ensuite a` la main. A` moins qu'on ne modifie la grammaire ou la
de'finition du type pour que l'outil ge'ne're le programme qu'on
souhaite obtenir...

> Avant tout, il manque peut-être déjà une couche au dessus de Format,
> par exemple de la syntaxe pour ce module. J'ai ça dans un coin. Mais,
> comme je n'utilise pas Format dans mes pretty prints de Camlp4, je
> n'ai pas eu l'occasion de la bien tester.

Il me semble qu'une couche au-desssus de Format n'est pas le proble`me
majeur (si l'on utilise la fonction printf de Format, on a une syntaxe
un peu cryptique bien su^r, mais assez compacte et simple). Le
proble`me majeur est sans doute les indications d'impression (boi^tes
et coupures) a` mettre dans les analyseurs syntaxiques. Mais surtout
le proble`me est de savoir si ce trait en vaut la chandelle: je
rappelle que nous diposions d'une syntaxe pour le formattage et d'un
programme d'inversion de grammaire il y a 7 ou 8 ans, mais que ce
trait a disparu sans que grand monde ne s'y oppose.

> ----------
>
> [Question why there are no automatic pretty printers provided with
> grammars camlyacc and Camlp4]
>
> The problem is that it works well for simple grammars. When they
> become more complicate, it is not so easy. Moreover, when you want to
> ameliorate the thing, you have to add directives of pretty print
> (spaces, breaks, etc).

That's true. Inversion of grammars works pretty-well for ``injective
grammars'', i.e. grammars with a only one rule to generate a given
Abstract Syntax Tree. Otherwise, after inversion, some patterns become
useless.

Consider for instance a grammar with ``syntactic macros'', that is
constructs that are directly expanded into the AST. For instance the
following grammar rule parses the && boolean operator with direct
expansion:

...
| [< e1 = expression; 'Kwd "&&"; e2 = expression >] -> If (e1, e2, Bool False)

Inverting this rule you get (notice the new syntax for module Format,
with the new Format.printf function):

| If (e1, e2, Bool False) ->
    printf "@[%a@ &&@ %a@]" (expression) e1 (expression) e2

This implies that all ``if then else'' with false in the else part
will be decompiled as && operators application, which may be
undesirable.

If you add aliases, such as && and & (as in Objective Caml and Caml
Light), you get the grammars rules:

...
| [< e1 = expression; 'Kwd "&&"; e2 = expression >] -> If (e1, e2, Bool False)
| [< e1 = expression; 'Kwd "&"; e2 = expression >] -> If (e1, e2, Bool False)

If you invert these rules:

| If (e1, e2, Bool False) ->
    printf "@[%a@ &&@ %a@]" (expression) e1 (expression) e2
| If (e1, e2, Bool False) ->
    printf "@[%a@ &@ %a@]" (expression) e1 (expression) e2

The second case is useless. It's even worse if you want to print a
language with complex equivalent constructions (that modify the
structure of the program), such as ``let'' and ``where'' constructs.

> I agree with you: personnally, when I make pretty printers, e.g. those
> of Camlp4, pr_r and pr_o, I write them symmetrically of the parsers
> (but manually), with the same names for the functions. It is Ok. But,
> according to me, I think it is difficult to automaticize.

I agree as well. However, a tool inverting grammars is not so
difficult to write, but still useful: this gives you a sketch of the
pretty-printing program you want to write, you then have to modify it
as necessary. Unless you choose to modify the grammar or the AST, until
the inversion tool succeeds to generate the prettty-printing program
you want...

> First, I think that a layer above Format is missing, for example some
> syntax for this module. I wrote something. But, because I do not use
> Format for my pretty printers of Camlp4, I did not test this syntax
> much.
> --------------------------------------------------------------------------
> Daniel de RAUGLAUDRE
>
> Projet Cristal - INRIA Rocquencourt
> Tel: +33 (01) 39 63 53 51
> Email: daniel.de_rauglaudre@inria.fr
> Web: http://pauillac.inria.fr/~ddr/
> --------------------------------------------------------------------------

I'm afraid, I don't think that a syntax layer above Format is the
major problem (if you use Format.printf, you get a admittedly strange,
but compact and simple, input syntax for Format). The main problem is
to add pretty-printing annotations to the grammars (include boxes and
break hints to grammar rules). Moreover, the very problem is to decide
if we want to write an inversion program: we had one in the very old
times (7 or 8 years ago), but this feature silently desapeared from
further versions of Caml. Nobody to fight for it. May be everybody is
convinced that that writing a pretty-printer is just a smop.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:13 MET