# Grammaires de van Wijngaarden

Ce sont des grammaires formelles ainsi nommées par référence à Aad van Wijngaarden.
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 :
Van Wijngaarden substitue :
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 :
Avec les métarègles :

### 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 :
Au-delà on aura :
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 :
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 :
Métarègle :
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 :
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.