Le système de grammaires attribuées FNC-2

Didier PARIGOT

Projet Oscar

FNC-2 est un système de traitement de grammaires attribuées moderne qui a pour but d'atteindre une qualité de production, grâce à ses caractéristiques suivantes :

Efficacité

les évaluateurs générés, basés sur le paradigme des séquences de visite, sont complètement déterministes; de plus, ce paradigme permet d'appliquer des techniques d'optimisation très efficaces. Les évaluateurs sont désormais aussi efficaces en temps et en place que des programmes écrits à la main utilisant un arbre comme structure de données interne.

Puissance d'expression

cette efficacité n'est pas obtenue au prix d'une perte de la puissance d'expression, puisque FNC-2 accepte les grammaires attribuées dans la très large classe des grammaires attribuées fortement non-circulaires. L'exploration de nouveaux formalismes permet une utilisation plus facile des grammaires attribuées (comme les grammaires attribuées génériques [LeBellec93, LeBellec93a Roussel95]) ou leur donne une plus grande puissance d'expression (comme les grammaires attribuées dynamiques [Parigot96a], qui subsument les grammaires attribuées circulaires et permettent de travailler sur des DAGs ou des peut être des graphes plus généraux).

Facilité d'utilisation

OLGA, le langage d'entrée de FNC-2, impose un haut degré de sécurité, de fiabilité et la productivité dans la programmation. Le langage d'entrée contient les sous-langages suivants:

• les syntaxes abstraites attribuées ASX;
• les grammaires attribuées;
• les déclarations et définitions de modules.

Polyvalence

les évaluateurs générés peuvent être interfacés avec de nombreux autres outils et être produits de différentes façon.

• Plusieurs évaluateurs d'attributs
  • évaluateur exhaustif;
  • évaluateur incrémental [Parigot88, Roudet94];
  • évaluator parallèle[ Marmol90, Jourdan92, Jourdan94, Marmol94].
• Plusieurs langages d'implémentation
  • version C;
  • version Le_Lisp sur le système Centaur [ Attali94, Roudet94, Rouzier93];
  • version fSDL sur le système de compilation CoSy;
  • version ML sur le système Caml [LeBatard95]

Quelques applications

• FNC-2 lui même, avec ses processeurs associés (70 000 lines)
• Pagode, le générateur de générateurde code compilateur COSY (50 000 lines)
• Un traducteur du langage E-LOTOS [Vivien97] (20 000 lines)
• Un génerateur de déparagrapheur d'arbres abstraits attribués (PPAT). Voir la liste complète des applications.

Processeurs associés

En plus d'FNC-2, viennent un ensemble de precesseurs associés qui facilitent le développement d'application complètes.

• un générateur de constructeurs d'arbres abstraits dirigés par les parseurs (ATC); deux instanciations de ATC ont été implantées, l'une à la tête de SYNTAX, et une autre à la tête de Lex et Yacc; [Zylberman90]
• un générateur de déparagrapheur d'arbres abstraits attribués (PPAT), basé sur la notion de boites de texte imbriquées de TeX; [Jouve90]
• un outil pour décrire les modules composant une application et gérant leur traitements (MKFNC2)
• une description d'application interactive (XFNC2) [Amilien92
• un système de trace de circularité (XVISU) [Amilien93 ]
• une composition descriptionnelle de, grammaires attribuées , i.e., la construction, à partir de deux grammaires attribuées ``pipelinées'', d'une troisième qui effectue le même calcul sans construire l'arbre intermédiaire; cela permet de profiter pleinement des avantages de la modularité sans embaras d'efficacité. [Roussel94a]
• des optimisations au niveau source des grammaires attribées, résultant de la composition descriptionnelle. [Roussel94a].

Comment récupérer le sytème FNC-2

Publications

Les principaux articles sur le système de grammaires attribuées FNC-2 sont:

• ``Design,implementation and evaluation of the FNC-2 attribute grammar system''
• ``Internals and Externals of the FNC-2 Attribute Grammar System''
• La liste des publications.