Grammaire affixe

Une grammaire affixe est une sorte de grammaire formelle utilisée pour décrire la syntaxe de langages, inspirée de la description des langues naturelles[1].

De fait, c'est une variante opérationnelle des grammaires de van Wijngaarden (2ème forme).

Les règles d'une grammaire affixe ressemblent à celles de grammaires non-contextuelles, dont les noms-de-notion (ou non-terminaux) seraient paramétrés. Ces paramètres appelés affixes permettent de doter ces notions de modalités. Leur nom s'inspire de la linguistique, où des modalités peuvent régir les affixes (préfixes, infixes ou suffixes).

Si un même affixe apparaît plusieurs fois dans une règle, sa valeur est présumée la même chaque fois.

Exemple

Soit la grammaire non-contextuelle suivante :

Phrase → Sujet Prédicat "."

Sujet → Nom

Prédicat → Verbe Objet

Objet → Nom

Nom → Pierre | Marie

Nom → les parents | les enfants

Verbe → aime | aiment

Verbe → aide | aident

Cette grammaire décrit des phrases comme :

Pierre aime les enfants.
Marie aide Pierre.
les enfants aident les parents.
les parents aiment Marie.

Avec plus de noms, plus de verbes, plus de concepts, plus de règles, de nombreuses phrases françaises peuvent être décrites, ce qui semble prometteur.

Cependant, ce genre de grammaire décrit aussi de nombreuses phrases comme :

les parents aime Pierre. Pierre aident Marie.

alors que le français demande que sujet et verbe s'accordent en nombre.

Une grammaire affixe l'exprimera ainsi :

hyperrègles :

Phrase → Sujet+nombre Prédicat+nombre "."

Sujet+nombre → Nom+nombre

Prédicat+nombre → Verbe+nombre Objet

Objet → Nom+nombre

Nom+singulier → Pierre | Marie

Nom+pluriel → les parents | les enfants

Verbe+singulier → aide |aime

Verbe+pluriel → aident |aiment

métarègle :

nombre → singulier | pluriel.

En imposant dans sa première règle l'alignement en nombre du sujet et du prédicat (en fait, de son seul verbe), cette grammaire ne laisse que des phrases correctes, bien qu'on puisse dire que

Jean aime Jean.

devrait plutôt s'écrire

Jean s'aime.

Cela pourrait aussi se traiter à l'aide d'affixes, selon les moyens dont on dispose pour définir les relations entre affixes.

Types de grammaires affixes

Dans le cas le plus simple, les affixes ne peuvent prendre qu'un nombre fini de valeurs, et ces valeurs ne peuvent être qu'égales ou différentes. Dans ce cas, les affixes rendent les grammaires non-contextuelle plus compactes, sans augmenter leur puissance (classe 2 de N. Chomsky).

On peut aussi permettre aux affixes de prendre comme valeurs des chaines arbitraires, et d'en permettre la concaténation, les valeurs admissibles pour les affixes étant fixées par une grammaire non-contextuelle distincte, dite grammaires des affixes. On parle alors de grammaires à 2 niveaux ou grammaires vW2. Ce type de grammaire a été utilisé dans les rapports de définition du langage de programmation Algol 68[2].

Les règles définissant les notions sont alors dites règles de notion ou hyperrègles : ce sont des règles génériques.

Les règles définissant les affixes, ou règles d'affixes jouent le rôle de métarègles : elles organisent les affixes ou modalités, en esquissant une théorie du langage décrit.

Ainsi, pour l'exemple ci-dessus on prendrait :

nombre : singulier | pluriel

Étendre une règle d'affixe multiplie les possibilités, par exemple avec :

nombre : singulier | duel | pluriel

M. Sintzoff [3] et C.H.A. Koster ont montré qu'alors grammaires vW2 et grammaires affixes permettent de décrire des langages de classe 0. Bien que cela laisse de nombreuses questions indécidables, Cleaveland et Uzgalis ont montré la puissance concrète de ces formalismes pour les langages de programmation, dont ils peuvent décrire la syntaxe, la sémantique statique (contrôle de cohérence) et la sémantique dynamique[4].

Les grammaires affixes étendues (EAG) et les grammaires affixes à valeur dans un treillis fini (AGFL) sont des variantes destinées à trouver le meilleur compromis entre :

la puissance descriptive de langages formels ou de langues naturelles[5],
la capacité opérationnelle découlant du principe de Peter Lucas[6] percevant toute grammaire formelle comme notation algorithmique de l'analyseur du langage décrit.

Programmation au moyen de grammaires affixes

Au-delà de la formalisation de langages ou de langues, l'adaptation des grammaires affixes en vue d'une programmation grammaticale, base de nombreux outils, repose sur 3 points :

les règles de notions (ou hyperrègles) sont traitées en spécifications exécutables ;
les règles d'affixes sont traitées en déclarations de types contraignant ces spécifications exécutables ;
certaines valeurs d'affixes doivent être établies par des lectures ou des calculs, ou exploitées par des écritures ; pour cela, des fragments de code apparaissent comme membre droit de quelques règles, afin de fournir des primitives de lecture, d'écriture et de calcul[7].

Représentation des affixes

Elle s'est d'abord développée selon deux points de vue :

tout affixe est une chaîne de caractères (mais on risque de devoir les analyser);
tout affixe a sa représentation fixée dans le langage support, au risque d'incohérences (CDL2, LET).

L'évolution du domaine a favorisé des représentations moins problématiques :

AGFL correspond au cas le plus simple (nombre fini de valeurs d'affixes), les treillis permettant l'efficacité en traitant différentes valeurs "en parallèle" ;
EAG utilise des chaines, des entiers ou des tuples ; les règles d'affixes ne sont pas obligatoires, le défaut étant "chaine".
CDL3, StarLet, LET+ emploient des arbres, des entiers ou des chaines selon les règles d'affixes.

Modage des affixes

L'orientation des passages de paramètres crée d'autres variantes : elle peut être :

facultative : EAG ;
indiquée et vérifiée : CDLs et LETs.

Emplois

La mise en œuvre de ces idées ont donné :

le langage CDL (Compiler Design Language) et ses successeurs (CDL2, CDL3... puis l'atelier AGFL développés à partir des années 1970 à l'Université de Nimègue(NL),
le langage LET (Langage d'Écriture de Traducteurs) et ses successeurs StarLET[8] et LET+, développés à partir de 1976 par J. Beney et al., à l'INSA de Lyon.

D'abord conçus pour faciliter la construction de compilateurs[9], ces langages et leurs environnements ont mené à d'autres applications comme l'édition de textes, l'analyse automatique de dépêches AFP, la classification automatique de documents[10], et, dans un genre différent, la conception interactive de divers langages ad hoc, par le maquettage/prototypage évolutif de leurs compilateurs.

Remarque

Bien que ce formalisme soit en principe proche des grammaires d'attributs, des grammaires de métamorphose[11] ou des DCG [12], la distinction entre notion nécessaire et notion possible, et le fait que les affixes sont toujours typés et souvent modés, facilitent grandement la détection d'erreurs et d'incohérences dans les grosses applications.

Notes

déjà abordée par C.H.A Koster dans : C.H.A. Koster & L. Meertens. Basic English, a Generative Grammar for a Part of English. Technical Report, Euratom Seminar Machine en Talen, Univ. of Amsterdam, 1962.
van Wijngaarden, Mailloux, Peck, Koster, Sintzoff, Lambert, Meertens, Fisker: Revised Report on the Algorithmic Language ALGOL 68, 1975, Acta Informatica, 5: 1-236
Sintzoff, M., 1967, Existence of van Wijngaarden syntax for every recursively enumerable set, Annales de la Société Scientifique de Bruxelles 2, 115-118
Cleveland & Uzgalis "Grammars for Programming Languages", 1977, Computer Science Library, Elsevier .
voir C.H.A. Koster, 1991, Affix grammars for natural languages in: Attribute Grammars
corroboré par Cleveland & Uzgalis, op. cit.
on en minimise le nombre car si elles sont nécessaires, elles sont aussi un point faible du contrôle de cohérence.
Beney J., Présentation du langage STARLET/GL, 1989 rev. 2001
tels qu'un compilateur PL1/C pour Control Data France: Maranzana M., Martin J.F., Frécon L., 1990, Un Traducteur de PL1/Multics vers C/VE, TSI, vol.9, no 5, p. 399-42. (source : 24 000 lignes LET ; compilateur produit : 94 000 lignes C non documentées).
travaux engagés pour l'anglais, le néerlandais, le latin, le français, le russe et l'arabe
Colmerauer A., 1975, Les grammaires de métamorphose, Groupe Intelligence Artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II
Pereira F., Warren D., 1980, Definite Clause Grammars for Language Analysis - A Survey of the Formalism and a Comparison with Augmented Transition Networks. Artificial Intelligence no 13, p. 231-278

Bibliographie

Bases

C.H.A. Koster, 1970, Affix Grammars, In: Proceedings of IFIP Conference on ALGOL 68 Implementation, Munich, North Holland Publ. Cy.
C.H.A. Koster. 1991, Affix Grammars for natural languages. In: Attribute Grammars, Applications and Systems, International Summer School SAGA, Prague, Czechoslovakia. Lecture Notes in Computer Science, volume 545. Springer-Verlag.
C.H.A. Koster. 1991, Affix Grammars for programming languages. In: Attribute Grammars, recueil ci-dessus.
C.H.A.Koster, J.Beney, 1991, On the borderline between grammars and programs, 3rd International symposium PLILP, Passau, Allemagne, août 1991, Lecture Notes in Computer Science n^o 528, Springer-Verlag 1991
M. Sutter, 2001, Informal introduction to the Extended Affix Grammars formalim, and its Compiler.

Métacompilation

J.Beney, L.Frécon, 1980, Langage et système d'écriture de traducteurs, RAIRO Informatique, vol 14, n^o 4, p. 379-394
J.Beney, J.F.Boulicaut, Des spécifications grammaticales à la programmation logique, le compromis Starlet, Bigre+Globule n 45, octobre 1985, p. 81-86
J.F.Boulicaut, J.Beney, 1988, Méta-compilation et programmation, des règles méthodologiques pour assister la construction de programmes, Génie Logiciel et Systèmes experts n^o 11, 1988, p. 36-48
J.Beney, J.F.Boulicaut, 1990, STARLET: an affix-based compiler compiler designed as a logic programming system, 3rd International Workshop on Compiler Compilers, CC'90, Schwerin (GDR), Lecture Notes in Computer Science n^o 477, p. 71-85, Springer-Verlag 1990
C. H. A. Koster, J. Beney, 1991 rev. 1993, CDL3 Textbook, Rapport interne de l'université Catholique de Nimègue, 120 pages,
J.-F. Boulicaut, J.Beney, Translator writing within a wide-spectrum framework. In: P.Fritzon (ed.): Proceedings of the poster session, 5th International Conference on Compiler Construction CC'94, Edinburgh, 7-9 April 1994, p. 11-20

Compilation et Conception de langage

Maranzana M., Martin J.F., Frécon L., Un Traducteur de PL1/Multics vers C/VE , TSI, vol. 9 ,1990, n^o 5, p. 399-422
Sidhoum H., Babout M., Frécon L., 1990, Ampère2, un langage de programmation pour la physique, The European Journal of Physics, vol. 11, p. 163-171

Langues

De Brito M., 1991, Réalisation d'un analyseur morphosyntaxique pour la reconnaissance du syntagme nominal : utilisation des grammaires affixes, thèse Université de Lyon, ENSSIB.
E. Farkas, C.H.A. Koster, P. Köves and M. Naszodi, 1991, Towards an Affix Grammar for the Hungarian language. In: A. György (Ed.), Proceedings CIS'91 conference on intelligent Systems, John von Neumann Society for Computing Sciences, Budapest, p. 233-246.
C.H.A. Koster and R. Willems. Towards an Affix Grammar for Turkish. In: M. Baray and B. Ozguc (Eds.), Computer and Information Science VI, Elsevier, Amsterdam 1991, pag. 1067-1076.
E. Oltmans. 1994, AMAZON in AGFL. Een contextvrije herschrijfgrammatica voor de structurele component van het AMAZON/CASUS-systeem, beschreven in het AGFL-formalisme. Masters Thesis (en néerlandais, 177 pages). University of Nijmegen. (résumé en anglais ; développement d'une large grammaire du néerlandais).

Documentation automatique

Maria Paula Santalla del Rio, 2002, A Formal Grammar of Spanish for Phrase-Level Analysis Applied to Information Retrieval, Lalia, 14, Series Maior, University of Santiago de Compostela, Santiago de Compostela.
C.H.A. Koster and C.P.A. Tiberius, 1997, AGFL grammars for full-text information retrieval. In: A. Ralli et al (Eds.), Working Papers in Natural Language Processing, Ekdosis Diavlos, Athens, 1997, p. 139-154.
C.H.A. Koster, J. Beney, S. Verberne and M. Vogel, 2011,Phrase-Based Document Categorization, In Current Challenges in Patent Information Retrieval, Springer, The Information Retrieval Series, Vol. 29, Part 4, p. 263-286.
C.H.A. Koster, M.Seutter, J. Beney, 2003, Multi-Classification of Patent Applications with Winnow, Proceedings PSI 2003, Springer LNCSn°2890, 2003, p. 545-554.
J.Beney, C.H.A. Koster, 2003, Classification supervisée de brevets: d'un jeu d'essai au cas réel, Actes du XXI^e congrès Inforsid, p. 50-59.
C.H.A. Koster, M.Seutter & J. Beney, 2001, Classifying Patent Applications with Winnow, Proceedings Benelear, p. 19-26.

Voir aussi

Grammaire formelle
Grammaires de van Wijngaarden
Compilateur de compilateur
Grammaire attribuée
(en) Affix grammar over a finite lattice
(en) Extended Affix Grammar
(en) Van Wijngaarden grammar
(en) « Some publications about Affix Grammars, AGFL and the AGFL system », sur AGFL-project (Affix Grammars over a Finite Lattice)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.