Grammaires et pretty print

Grammaires et pretty print

[Emmanuel Engel]

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  pour avoir une  chance de faire afficher
au debugger  ou aux  "print" que  j'insere partout  dans le   code les
informations  (de  facon lisible)  qui  me sont utiles  pour suivre le
deroulement de l'execution  du  programme. Par  ailleurs bien  souvent
j'ai ecrit un parser (avec camlyacc) pour ces structures de donnees.

Il me  semble qu'un outil qui  sait engendre  des parser devrait aussi
savoir faire du pretty-print. Je m'explique:

Un outil comme (caml)yacc (camlp4) prend  en entree une grammaire, des
(meta) regles pour  desambiguer cette grammaire et  rend un parser qui
reconnait les   expressions du  langage   engendre par  la  grammaire.
Pourquoi de  tels outils ne rendent pas   aussi un pretty-printer pour
les expressions  engendrees par la  grammaire ? Cela ne me semble plus
facile que le parsing:

Soit la grammaire non ambigue

E   -> E_1 + E   | E_1
E_1 -> E_2 * E_1 | E_2
E_2 -> cst | (E)

Engendrer  le    pretty-printer  de   maniere   systematique  avec  un
parenthesage minimal n'est pas difficile, il suffit d'ecrire une serie
de  fonction  mutuellement   recursives   qui  suivent exactement   la
structure de la grammaire:

let rec print_E = function
  x1 + x2 -> 
   print_E_1 x1;
   print_token +;
   print_E x2
 |x       ->
   print_E_1 x

and print_E_1 = function
  x1 * x2 ->
   print_E_2 x1;
   print_token *;
   print_E_1 x2
 |x ->
   print_E_2 

and print_E_2 = function
  cst -> 
    print cst 
 |x   ->
    print_token (;
    print x;
    print_token )


De tels outils n'existent pas. Il doit y  avoir une bonne raison, quel
est le point que j'ai loupe ??

-- 

- Emmanuel Engel

Re: Grammaires et pretty print

[Daniel de Rauglaudre]

[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).

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.

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.

----------

[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).

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.

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/
--------------------------------------------------------------------------

Re: Grammaires et pretty print

[Pierre Weis]

> [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/

Grammars and pretty print

[Daniel de Rauglaudre]

About grammars and pretty print...

I have implemented something for Camlp4. It is a syntax extension,
interpreting the statement extend as doing the entries extensions
and defining pretty printing functions. It is a prototype but you
can download it at address:
   ftp://ftp.inria.fr/INRIA/Projects/cristal/Daniel.de_Rauglaudre/
files:
   pa_extprint.cmo
   pa_extprint.ml (the source)

You must define a function named "print_token" taking a value of type
Token.t (camlp4 library) and printing it.

Example of use. File "foo.ml":
==================================================================
type ast =
    Plus of ast * ast
  | Minus of ast * ast
  | Mult of ast * ast
  | Div of ast * ast
  | Exp of ast * ast
  | Int of string
;;

let gram = Grammar.create (Plexer.make ());;
let test = Grammar.Entry.create gram "test";;
let expr = Grammar.Entry.create gram "expr";;

let print_token =
  function
    Token.Tterm x -> print_string x
  | Token.Tint x -> print_string x
  | _ -> ()
;;

EXTEND
  test: [[ x = expr; EOI -> x ]];
  expr:
    [ "plus" LEFTA
      [ x = expr; "+"; y = expr -> Plus (x, y)
      | x = expr; "-"; y = expr -> Minus (x, y) ]
    | "mult" LEFTA
      [ x = expr; "*"; y = expr -> Mult (x, y)
      | x = expr; "/"; y = expr -> Div (x, y) ]
    | "exp" RIGHTA
      [ x = expr; "^"; y = expr -> Exp (x, y) ]
    | "simple"
      [ i = INT -> Int i
      | "("; x = expr; ")" -> x ] ]
   ;
END;;
==================================================================

Result of
    camlp4o ./pa_extprint.cmo pr_o.cmo pr_extend.cmo gram.ml

==================================================================
type ast =
    Plus of ast * ast
  | Minus of ast * ast
  | Mult of ast * ast
  | Div of ast * ast
  | Exp of ast * ast
  | Int of string
;;

let gram = Grammar.create (Plexer.make ());;
let test = Grammar.Entry.create gram "test";;
let expr = Grammar.Entry.create gram "expr";;

let print_token =
  function
    Token.Tterm x -> print_string x
  | Token.Tint x -> print_string x
  | _ -> ()
;;

let rec pr_test x = pr_expr x; print_token Token.Teoi; ()
and pr_expr x =
  let rec p0 =
    function
      Plus (x, y) -> pr_expr x; print_token (Token.Tterm "+"); pr_expr y; ()
    | Minus (x, y) -> pr_expr x; print_token (Token.Tterm "-"); pr_expr y; ()
    | x -> p1 x
  and p1 =
    function
      Mult (x, y) -> pr_expr x; print_token (Token.Tterm "*"); pr_expr y; ()
    | Div (x, y) -> pr_expr x; print_token (Token.Tterm "/"); pr_expr y; ()
    | x -> p2 x
  and p2 =
    function
      Exp (x, y) -> pr_expr x; print_token (Token.Tterm "^"); pr_expr y; ()
    | x -> p3 x
  and p3 =
    function
      Int i -> print_token (Token.Tint i); ()
    | x ->
        print_token (Token.Tterm "(");
        pr_expr x;
        print_token (Token.Tterm ")");
        ()
  in
  p0 x
;;
EXTEND
  test:
    [ [ x = expr; EOI -> x ] ]
  ;
  expr:
    [ "plus" LEFTA
      [ x = SELF; "+"; y = SELF -> Plus (x, y)
      | x = SELF; "-"; y = SELF -> Minus (x, y) ]
    | "mult" LEFTA
      [ x = SELF; "*"; y = SELF -> Mult (x, y)
      | x = SELF; "/"; y = SELF -> Div (x, y) ]
    | "exp" RIGHTA
      [ x = SELF; "^"; y = SELF -> Exp (x, y) ]
    | "simple"
      [ i = INT -> Int i | "("; x = SELF; ")" -> x ] ]
  ;
END;;
==================================================================

Remark: if you have a version of camlp4 (camlp4 -v) anterior to
1.06+2, the previous command will display it with an incorrect
"declare" statement. It is just a pretty print bug that is fixed.
Take the patch in the ftp directory.

--------------------------------------------------------------------------
 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/
--------------------------------------------------------------------------