Message-Id: <9303171031.AA15612@pauillac.inria.fr>
Subject: Re: Stream patterne matching
To: cr@dcs.ed.ac.uk
Date: Wed, 17 Mar 1993 11:31:10 +0100 (MET)
In-Reply-To: <26877.9303152045@damsay.dcs.ed.ac.uk> from "cr@dcs.ed.ac.uk" at Mar 15, 93 08:45:23 pm
From: Michel.Mauny@inria.fr (Michel Mauny)
Christophe e'crit:
> Un autre petit probleme avec le pattern matching : le fait qu'il soit
> predictif (c.a.d. qu'il decide uniquement sur le premier element du stream).
>
> Cela n'est pas grave : si l'on veut matcher [< '0 ; '1>] ou [< '0 ; '2 >],
> on ecrit [< '0 ; f c >] ou f match [< '1 >] ou [< '2 >].
>
> Est-ce que le compilateur ne pourrait pas faire cela automatiquement ?
>
> C'est a dire faire cette decomposition des qu'un certain nombre de patterns
> consecutifs commencent par une suite de patterns egaux (au noms des variables
> pres) ?
>
> Cela simplifierait l'ecriture de la plupart des grammaires courantes. Tout en
> sachant bien que la semantique est la meme.
On nous a de'ja` fait cette demande un certain nombre de fois, et ma
re'ponse a toujours e'te' ne'gative. Bien que je comprenne l'utilite'
et la ne'cessite' de la factorisation gauche sur des *grammaires*,
elle me semble dangereuse sur des *analyseurs*, car pas tre`s claire
se'mantiquement.
La factorisation gauche d'une grammaire BNF produit une grammaire
*e'quivalente* a` la grammaire originale (i.e. engendrant le me^me
langage).
Les de'finitions d'analyseurs a` base de streams ne sont pas des
grammaires, me^me si quelquefois la structure d'un analyseur
reconnaissant un langage L peut e^tre semblable a` la structure de la
grammaire BNF engendrant ce me^me langage L.
Une factorisation gauche d'un analyseur ne produit en ge'ne'ral pas un
analyseur e'quivalent.
On me re'pondra "Yaka de'finir la se'mantique des analyseurs en
fonction d'une e'ventuelle factorisation gauche". Le proble`me, c'est
que dans la situation actuelle, l'application d'un analyseur
parame'tre' pp a` un analyseur p est ope'rationnellement e'quivalente
a` l'analyseur obtenu par substitution de la valeur de p au parame`tre
formel de pp dans le corps de pp (ca s'appelle la beta-reduction dans
le lambda-calcul, excusez-moi d'enfoncer des portes ouvertes):
En d'autres termes, si pp = function a -> E(a), et p est un analyseur
quelconque, alors:
pp p <-> E(p') ou` p' est la valeur de p
Pour e^tre comple`tement rigoureux, il faut travailler dans la
se'mantique ope'rationnelle du lambda-calcul par valeur avec filtrage,
des environnements, etc.
Or, il se peut que E(p') soit factorisable a` gauche, et que (pp p) ne
le soit pas. Le comportement de E(p') et de (pp p) n'est donc en
ge'ne'ral pas e'quivalent en cas de factorisation gauche.
Et qu'on ne me re'ponde pas que ce n'est pas grave: qui n'a pas
abstrait une sous-expression dans une fonction afin d'obtenir une
fonction plus ge'ne'rale? Quand on fait ca, on est endroit d'espe'rer
des programmes e'quivalents, pour le moins.
Pour re'sumer, attendons d'avoir une notion de grammaire a` partir
desquelles on calculera des parsers en faisant toutes les
optimisations possibles et imaginables. Le point, c'est que ces
optimisations seront juge'es correctes relativement a` une certaine
se'mantique de ces grammaires, et feront partie du processus de
compilation de ces grammaires en des analyseurs.
Michel