Best viewed in 24pt and full-screen

Transformations de grammaires en Prolog

Nous avons dit plus haut que les constituent un outil de programmation simple d'emploi, puissant, et flexible. Elles présentent cependant une difficulté qui vient de ce que la stratégie de l'analyseur résultant de la traduction de en Prolog est en général directement héritée de celle du système Prolog sous-jacent. Or, la stratégie la plus souvent employée en Prolog correspond au niveau syntaxique à une analyse par descente récursive et est donc incomplète.

Une manière de compenser ce biais stratégique est de changer la stratégie de Prolog en choisissant par exemple une stratégie tabulée [Warren 92], et une autre est de changer la procédure de traduction de en Prolog. Nous avons choisi une troisième voie qui est de transformer les grammaires pour qu'elles soient compatibles avec une analyse par descente récursive.

Le principal obstacle à lever est celui de la récursivité à gauche, mais il faut aussi pouvoir effectuer des dépliages, ou des factorisations. Ces transformations sont bien formalisées pour les grammaires pures, mais pas du tout pour les grammaires à attributs (dont les sont un cas particulier). Conduire ces transformations à la main est une tâche réputée difficile. Au sujet de la transformation manuelle des , Cohen et Hickey parlent de «cunning» (ruse ou astuce) et «contortions» [Cohen et Hickey 87]. Nous avons donc voulu formaliser et automatiser ces transformations.

La transformation des n'est qu'un aspect de nos motivations. En fait, même quand le moteur d'analyse est plus complet que la descente récursive, on peut encore avoir besoin de transformer les grammaires pour améliorer les performances.

La difficulté de la transformation des grammaires à attribut vient évidemment des attributs. Quand une transformation introduit de nouveaux non-terminaux, quels sont leurs attributs ? Quand une transformation combine plusieurs règles de grammaire, comment se combinent les attributs ?

Nous avons modélisé les grammaires à attributs dans un formalisme qui sépare la partie syntaxique pure de la partie sémantique [Ridoux 96]. Nous notons Syntaxe Semantique l'adjonction d'un composant sémantique Semantique à un composant syntaxique pur Syntaxe. Le composant sémantique est exprimé comme une fonction des attributs des éléments syntaxiques purs qui retourne une formule logique ; c'est donc un prédicat. Par exemple, dans la règle , le composant sémantique est une fonction des attributs du non-terminal de tête et des deux non-terminaux du corps. En admettant la -équivalence*, on aurait pu écrire . On convient que les éléments syntaxiques purs sont toujours considérés de gauche à droite dans les arguments des composants sémantiques.

On peut rapprocher cette modélisation de la modélisation de la programmation par induction structurelle* en Prolog typé. Ici, le type est celui des arbres de dérivation et les constructeurs sont les règles de grammaires.

Les combinaisons d'attributs s'expriment donc par application de fonction et construction de formules logiques. Par exemple, le principe de l'élimination des récursivités gauches immédiates est exprimé de la manière suivante :

La transformation de la partie syntaxique pure est classique [Aho et al. 86] et toute la nouveauté réside dans la prise en compte des attributs. En admettant que le non-terminal est défini par des règles récursives à gauche, ayant pour composants sémantiques des , et des règles qui ne le sont pas, ayant pour composants sémantiques des , on peut le redéfinir par des règles dont aucune n'est récursive à gauche, et dont les composants sémantiques sont construits à partir des  et . En particulier, un non-terminal nouveau, , est introduit. Son attribut est une paire dont les composants sont désignés par notation pointée, et .

La combinaison de cette transformation et d'une transformation par dépliage permet d'éliminer les récursivités indirectes. Des manipulations symboliques, comprenant un peu d'évaluation partielle, permettent de formuler les nouvelles règles de grammaire dans leur syntaxe concrète.

Le système qui met en uvre cette formalisation transforme automatiquement les règles de grammaire suivantes, qui décrivent un nombre et sa valeur chiffre par chiffre en commençant par la droite,

nombre Nombre --> nombre Dizaines chiffre Unites ` ( Nombre is Unites + 10*Dizaines /* Horner */ ) .

nombre Chiffre --> chiffre Chiffre .

en les règles suivantes, qui commencent par la gauche :

nombre _135 --> chiffre Chiffre derec_nombre _135 Chiffre .

derec_nombre _127 Dizaines --> chiffre Unites ` ( Nombre is Unites + 10*Dizaines /* Horner */ ) derec_nombre _127 Nombre .

derec_nombre _141 _141 --> [] .

Si on se souvient de la relation entre et Prolog, on doit convenir qu'il s'agit en fait d'une transformation de programmes produits d'après un schéma particulier. En l'occurrence, la transformation décrite plus haut élimine réellement les récursivités à gauche d'un programme Prolog.

Le système que nous avons implémenté conserve autant que possible les identificateurs de variables et les commentaires des règles sources dans les règles produites. Cela permet d'augmenter la lisibilité des grammaires produites. C'est un aspect mal traité par la recherche sur les transformations de programme et qui constitue un mode rudimentaire d'explication de ce que fait le système. Il faut aussi noter que cela a un prix, en temps de programmation du système et en temps de calcul des transformations. Dans le cas de ce système, la traçabilité est la cause du doublement de la taille du programme.

On voit que le formalisme proposé est parent de Prolog par le fait qu'il combine -abstractions* et quantifications logiques. On peut donc suspecter que notre biais pour Prolog a guidé notre formalisation. Nous croyons qu'il faut considérer les choses d'une autre manière. Prolog met en uvre une formalisation de la métalangue employée pour manipuler les structures formelles. Il n'est donc pas étonnant que l'usage de la métalangue déjà formalisée mène plus directement au but. On peut même penser que cela se reproduira. Plus généralement, une autre raison pour laquelle un langage de programmation ne doit pas être considéré comme neutre (voir la section «La recherche en programmation»*) est qu'il offre une «vision du monde». Celle-ci encourage un style de formalisation des problèmes à résoudre.