Grammaires et types sensibles au contexte

1) Quelle est, le cas échéant, la relation entre le typage statique et les grammaires formelles?

2) En particulier, serait-il possible pour un automate borné linéaire de vérifier si, disons, un programme C ++ ou SML était bien typé? Un automate de pile imbriqué?

3) Existe-t-il un moyen naturel d'exprimer des règles de typage statiques en termes de grammaire formelle?

Il n'est pas possible pour les automates linéaires bornés de vérifier si les programmes C ++, et il est peu probable que cela soit possible pour LBA et pour vérifier si les programmes SML sont bien typés. C ++ possède un système de type Turing complet, car vous pouvez coder des programmes arbitraires en tant que métaprogrammes de modèle.

SML est plus intéressant. Il possède une vérification de type décidable, mais le problème est EXPTIME-complet. Par conséquent, il est peu probable qu'un LBA puisse le vérifier, sauf s'il y a un effondrement très surprenant dans la hiérarchie de la complexité. La raison en est que SML nécessite une inférence de type, et il existe des familles de programmes dont la taille du type augmente beaucoup plus rapidement que la taille du programme. À titre d'exemple, considérons le programme suivant:

fun delta x = (x, x)        (* this has type 'a -> ('a * 'a), so its return value
                               has a type double the size of its argument *)

fun f1 x = delta (delta x)  (* Now we use functions to iterate this process *)
fun f2 x = f1 (f1 x)        
fun f3 x = f2 (f2 x)        (* This function has a HUGE type *)

Pour les systèmes de type plus simples, tels que C ou Pascal, je pense qu'il est possible pour un LBA de le vérifier.

Au début de la recherche sur les langages de programmation, les gens utilisaient parfois les grammaires van Wingaarden (alias les grammaires à deux niveaux) pour spécifier des systèmes de types pour les langages de programmation. Je crois qu'Algol 68 a été spécifié de cette façon. Cependant, on me dit que cette technique a été abandonnée pour des raisons essentiellement pragmatiques: il s'est avéré assez difficile pour les gens d'écrire des grammaires qui spécifiaient ce qu'ils pensaient spécifier! (En règle générale, les grammaires écrites par les utilisateurs génèrent des langues plus grandes que prévu.)

De nos jours, les gens utilisent des règles d'inférence schématiques pour spécifier des systèmes de types, ce qui est essentiellement un moyen de spécifier des prédicats comme le point le moins fixe d'une collection de clauses Horn. La satisfaction pour les théories de Horn de premier ordre est indécidable en général, donc si vous voulez capturer tout ce que font les théoriciens des types, alors le formalisme grammatical que vous choisissez sera plus fort que ce qui est vraiment pratique.

Je sais qu'il y a eu un certain travail sur l'utilisation de grammaires d'attributs pour implémenter des systèmes de types. Ils affirment qu'il y a des avantages en ingénierie logicielle pour ce choix: à savoir, les grammaires d'attribut contrôlent très strictement le flux d'informations, et on me dit que cela facilite la compréhension du programme.

Pour autant que je sache, la correction de type a tendance à être indécidable pour des cas intéressants, de sorte que les grammaires formelles ne peuvent clairement pas capturer tous les systèmes de types auxquels vous pouvez penser.

Je sais que les principaux générateurs de compilateurs autorisent des prédicats arbitraires pour les règles qui empêchent l'exécution d'une règle si le prédicat n'est pas évalué true, par exemple { type(e1) == type(e2) } (expression e1) '+' (expression e2). Ce concept peut facilement être formalisé; des restrictions appropriées sur les prédicats autorisés peuvent alors produire une décidabilité par les LBA.

$k$$k+1$