Grammaires de van Wijngaarden

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.

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.

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.

• 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).

• Grammaire formelle
• Hiérarchie de Chomsky
• Grammaire affixe
• Grammaire attribuée
• (en) Van Wijngaarden grammar