Grammaire affixe

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.

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

mode : indicatif | conditionnel | subjonctif | impératif | participe |infinitif

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.

Summarize Fact Check

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].

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.

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.

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.

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.