Fournir un système de type pour la spécification de l'analyseur/lecteur ?

Question

On pense souvent que les langages de programmation fonctionnels tels que Ocaml ou F# ont un système de types qui nous permet de passer plus de temps à écrire du code et moins de temps à le déboguer, par rapport au codage dans des langages dynamiques tels que Python ou JavaScript.

Je suis en train d'écrire une spécification d'analyseur syntaxique à utiliser avec FsLexYacc, le lexer et l'analyseur syntaxique de F#. La spécification de l'analyseur ressemble à ceci, pour l'analyse des nombres entiers et des noms d'identifiants :

%token <int> CSTINT
%token <string> NAME
...
Expr: 
  NAME {VAR $1}
 |CSTINT {CSTI $1}

Ce type de code n'est plus écrit dans les langages de programmation de fonctions et n'est donc plus "protégé" par le système de types. Des bogues étranges peuvent facilement s'y glisser, je suppose (mais je n'en suis pas tout à fait sûr).

Question : Existe-t-il des travaux (théoriques ou pratiques) qui tentent de résoudre ce problème en fournissant une sorte de système de type également pour la spécification de l'analyseur/lecteur ?

Answer 1

Oui, il y a eu un certain nombre de recherches dans ce domaine.

Il convient de noter que, bien que la pile de valeurs sémantiques utilisée dans les algorithmes d'analyse syntaxique de la RL ait des types hétérogènes, l'algorithme lui-même est sans risque pour les types. Mais bien sûr, il peut y avoir des erreurs dans l'implémentation de l'algorithme, et il serait donc idéal que le compilateur lui-même puisse vérifier que le code produit par le générateur d'analyseur syntaxique est correctement typé. Cela s'avère possible, et un certain nombre d'implémentations ont été produites.

Je n'ai pas de bibliographie complète à portée de main, mais j'ai sous la main deux articles, tous deux publiés en 2006, qui semblent pertinents :

• Vers des analyseurs LR typés et efficaces par François Pottier et Yann Régis-Gianas :

  Les générateurs d'analyseurs LR fournis avec de nombreuses implémentations de langages de programmation fonctionnels produisent un code non typé, inutilement inefficace, ou les deux. Nous montrons qu'en utilisant des types de données algébriques généralisés, il est possible de produire des analyseurs syntaxiques bien typés (de sorte qu'ils ne peuvent pas se planter ou échouer de manière inattendue) et néanmoins efficaces.

• Dérivation d'un analyseur fonctionnel typé LR par Ralf Hinze et Ross Paterson :

  Ce document décrit une implémentation purement fonctionnelle de l'analyse syntaxique LR. Nous dérivons formellement nos analyseurs en une série d'étapes commençant par l'inverse de l'impression. Contrairement aux implémentations traditionnelles de l'analyse syntaxique LR, les analyseurs résultants sont entièrement typés, sans pile et sans table. Les fonctions d'analyse syntaxique recherchent des alternatives en parallèle, chaque alternative étant représentée par un argument de continuation. L'implémentation directe offre de nombreuses possibilités d'optimisation et les premières mesures montrent d'excellentes performances par rapport aux analyseurs conventionnels pilotés par des tables.

Answer 2

Vous pouvez définir votre analyseur en utilisant FParsec . Vous bénéficierez ainsi de tous les avantages du système de types F#. Ce qui précède pourrait être décrit comme suit en utilisant FParsec en F# :

type Expression = StringExpr of String | NumberExpr of int

let alphanumericString = letter .>>. (manyChars (letter <|> digit)) 
                          >>= (fun (c,s)-> preturn (StringExpr(c.ToString()+s)))

let number = manyChars digit 
                 >>= (fun n -> preturn (NumberExpr (Int32.Parse n)))

let expression = alphanumericString <|> number