Grammaires de van Wijngaarden

Ce sont des grammaires formelles ainsi nommées par référence à Aad van Wijngaarden.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La mise en forme de cet article est à améliorer (juin 2023).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

On distingue :

La première forme (GvW1) qui transcrit simplement les grammaires non-contextuelles du type Backus-Naur, avec un statut particulier des terminaux permettant des tolérances lexicales ; elle ne permet de décrire que des langages de classe 2 au sens de Chomsky.
La seconde forme (GvW2) qui généralise la première, pour en faire une grammaire à deux niveaux, permettant de décrire des langages de classe 0 ou 1 au sens de Chomsky ; elle permet une définition formelle précise mais gérable des langages.

Grammaires de première forme

À une grammaire de Backus-Naur du type :

<instruction> ::≔ <instruction simple> | <instruction composée>
<instruction composée> ::≔ <instruction conditionnelle> | <instruction itérative >
<instruction itérative> ::≔ <clause ><groupe>
<groupe> ::≔ DEBUT <suite d’instructions> FIN
<suite d’instructions > ::≔ <instruction> ; <suite d’instructions> | <vide>

Van Wijngaarden substitue :

instruction : 		        instruction simple ; instruction composée.
instruction composée :          instruction conditionnelle ; instruction itérative. 
instruction itérative :  	clause, groupe.
groupe :  		        symbole début, suite d’instructions, symbole fin.
suite d’instructions : 	        instruction, symbole pv, suite d’instructions ; vide.

Cette notation n’utilise que des minuscules. Comme souvent, la ponctuation permet de supprimer les méta-crochets "<,>" : la virgule concatène, le point-virgule remplace la barre « | ». Mais ici, le mot-clé symbole est réservé : c’est le préfixe des terminaux, supposés définis par ailleurs dans une table fournissant pour chacun une représentation principale – la seule officielle – mais aussi des représentations secondaires tolérées, évitant les « fausses erreurs ».

symbole	rep. principale	autre	...
pv	;	<NL>
début	BEGIN	DEBUT	{
fin	END	FIN	}

Grammaires de seconde forme

Elles sont apparues en chapitre 0 des rapports Algol 68.

Ce sont des grammaires à deux niveaux, dont les règles sont soumises à des modalités définies par une deuxième grammaire. Ce mécanisme permet de remplacer un grand nombre (éventuellement infini) de règles par un nombre réduit de règles paramétrées. Il est ainsi possible de décrire des langages contextuels (classe 0).

Ces grammaires ont émergé dans les années 1960 pour décrire langues ou langages avec une grammaire précise mais restant gérable, la précision des grammaires étant particulièrement cruciale pour l’analyse. Les grammaires non contextuelles alors utilisées auraient nécessité une très grande quantité de règles distinctes bien que formant des paquets similaires. L’idée a été de les remplacer par un couple générateur formé :

D’une hyper-grammaire formant des hyper-règles, ou schémas paramétrés de règles au sens usuel,
D’une méta-grammaire fournissant les règles de développement des hyper-règles.

Hyper-grammaire

On part d’une grammaire de première forme, dans laquelle tout mot dans un nom de notion, s’il est écrit en majuscules, désigne une modalité (techniquement, une méta-variable substituable).

Méta-grammaire

On adapte une grammaire de première forme à la définition des méta-notions utilisées dans l’hyper-grammaire. Pour cela, le premier membre des règles, en majuscules, désigne la méta-notion définie ; dans le second membre, tout mot dans un nom de notion, s’il est écrit en majuscule, désigne une partie substituable.

Dérivations

On obtient une dérivation d’une hyper-règle en remplaçant partout une métavariable par une même production : c'est le principe du remplacement uniforme. Chaque dérivation définit une proto-notion. On débouche finalement sur une règle classique chaque fois qu’il ne reste plus de méta-variable. Au contraire, on parle d’impasse si on ne peut atteindre ce stade.

Exemple

Comment stipuler que, dans un programme, les appels de fonction supposent des listes de valeurs comme arguments, et les variables indicées des listes d’indices, listes similaires bien que différentes ?

On peut formaliser les 2 séparément, mais peut-être aurons-nous des listes similaires pour les appels de procédure, les constructeurs d’ensemble… Tentons une formalisation extensible des 2 premiers cas. En convenant qu’une suite de majuscules désigne une méta-variable, nous aurons par exemple les hyper-règles :

sélecteur GENRE : identificateur GENRE, liste GENRE de valeurs.
liste GENRE de TRUCS : marque gauche GENRE, liste de TRUCS, marque droite GENRE.
liste de TRUCS : TRUC, suite de TRUCS.
suite de TRUCS : symbole virgule, suite de TRUCS ; vide.
marque PLACE table :  symbole crochet PLACE.
marque PLACE fonction : symbole parenthèse PLACE.

Avec les métarègles :

GENRE :: table ; fonction.
TRUC ::  valeur ; ….
PLACE :: gauche ; droite.

Expansion combinatoire

On obtient une dérivation d’une hyper-règle en remplaçant partout une méta-variable par une même production (principe du remplacement uniforme). Par exemple, en substituant « table » à « GENRE », on obtient :

sélecteur table : identificateur table, liste table de valeurs .

Au-delà on aura :

liste table de valeurs : marque gauche table, liste de valeurs, marque droite table :
symbole crochet gauche, liste de valeurs, marque droite table :
symbole crochet gauche, valeur, suite de valeurs, marque droite table :
symbole crochet gauche, valeur, symbole virgule, suite de valeurs, marque droite table :
symbole crochet gauche, valeur, symbole virgule, valeur, marque droite table.

Et ainsi, on établit qu’un nom de tableau doit être suivi d’une liste de valeurs entre crochets, séparées par des virgules ; et qu'un nom de fonction appelle une liste de valeurs entre parenthèses, séparées aussi par des virgules.

En ajoutant d’autres GENRES et/ou d’autres TRUCS, on introduirait simplement d’autres constructions utilisant par exemple des listes entre accolades, ou toute autre paire de caractères spéciaux.

Or si une méta-variable admet k productions finales, toute hyper-règle qui l’emploie produira k proto-notions par substitution.

Une hyper-règle utilisant 3 méta-variables admettant respectivement 3, 5 et 7 productions préfigure ainsi 3∙5∙7 = 105 règles similaires mais distinctes.

Sélectivité

La dérivation réussit si, finalement, on n’a que des symboles terminaux (y compris « vide », vu comme symbole à 0 caractère). On parle au contraire d’ impasse si la dérivation ne peut déboucher sur une collection de symboles terminaux. On appellera plus particulièrement prédicat les hyper-notions qui mènent soit à une impasse, soit à « vide », présumé toujours présent, sans autre effet ; elles sont utilisées pour expliciter des contraintes.

1. Considérons le cas classique de l’affectation ; on donne en général une règle :

affectation :  variable, symbole reçoit, expression.

suivie d’une longue note sur la concordance des types entre l’expression source et la variable destinataire.

Pour imposer que les deux soient de même type, on écrira ici : Hyperrègle :

affectation :  variable TYPE, symbole reçoit, expression TYPE.

Métarègle :

TYPE :: entier ; booléen ; caractère ; rangée de TYPE ; ref de TYPE.

Le remplacement uniforme impose alors que variable et expression ait le même type (une valeur de TYPE).

La méta-règle TYPE fournit une famille de types : ici, ce sont les types primitifs entier, booléen, caractère ; ou toute rangée (suite) de valeurs du même type ; ou toute référence à une valeur typée. La récursivité de la définition de TYPE lui permettra de couvrir si nécessaire une « rangée de références à une rangée de rangée de rangée (table à 3 dimensions) d’entiers ». 'Remarquons que la récursivité de TYPE nous donne une infinité de types possibles.

2. Supposons qu’on désire une affectation plus souple : on écrira :

Hyperrègles :

affectation :  variable TYPE1, symbole reçoit, expression TYPE2, où TYPE1 accepte TYPE2.

où TYPE accepte TYPE : vide.
où entier accepte booléen : vide.
où entier accepte caractère : vide.

L’hyperrègle « où….accepte…. » définit ici un prédicat de concordance des types. Elle ne correspond à aucun symbole extérieur.

ses substituts sont considérés comme vrai s’ils débouchent sur un second membre vide, ce qui est le cas ici pour tout couple (type, type) et pour les couples (entier, booléen) et (entier, caractère) qui expriment que dans une affectation une variable entière accepte valeurs booléennes et caractères ;
ses substituts sont considérés comme faux s’ils ne trouvent pas d’hyper-règles leur permettant de déboucher : les cas autres que les précédents sont des impasses.

3. D’un point de vue linguistique, ce genre de prédicats peut exprimer les règles d’accord, notamment quand un même groupe nominal comporte des graphies séparément ambiguës. De telles règles facilitent l’analyse précise ou l'écriture correcte des phrases.

Puissance

Ces grammaires peuvent décrire des langages de Classe 0 dès lors que la méta-grammaire est de classe 2. (M. Sintzoff). Si la méta-grammaire est de classe 3, elles ne sont plus qu’une forme condensée de grammaires de classe 2.

Algol 68 a montré leur utilité pour définir un langage puissant et auto-extensible, l’utilisateur pouvant, par la création de nouveaux types et de nouveaux opérateurs, tirer le langage vers son domaine d’application, en constituant des algèbres ad hoc.

Le Rapport Révisé Algol 68 a montré en outre que les règles prédicats permettent de décrire et contrôler la sémantique statique d'un tel langage de programmation, dans la variété de ses applications.

Van Wijngaarden a postulé que les grammaires étaient des langages de programmation, ce que montre sous divers aspects l’ouvrage de Cleaveland et Uzgalis.

Voir aussi

Bibliographie

J. Buffet, P. Arnal, A. Quéré et A. van Wijngaarden, Définition du langage algorithmique ALGOL 68, Hermann, coll. « Actualités scientifiques et industrielles », 1972, 222 p. (présentation en ligne).
(en) James Craig Cleaveland et Robert C.. Uzgalis, Grammars for Programming Languages, American Elsevier Publishing Company, 1977, 154 p. (ISBN 9780444001870, présentation en ligne).
(en) M. Sintzoff, « Existence of van Wijngaarden syntax for every recursively enumerable set », Annales de la Société scientifique de Bruxelles: Sciences mathématiques, astronomiques et physiques, Secrétariat de la Société scientifique, vol. 80 à 83,‎ 1969, p. 115-118 (résumé)
(en) A. van Wijngaarden (dir.), B.J. Mailloux (dir.), J.E.L. Peck, C.H.A. Koster, C.H. Lindsey, M. Sintzoff, L.G.L.T. Meertens et R.G. Fisker, Revised Report on the Algorithmic Language Algol 68, Springer Berlin Heidelberg, 1976, 238 p. (ISBN 9783540075929, présentation en ligne).

Articles connexes

Portail de l’informatique