Combinateur d'analyseurs

En programmation informatique, un combinateur d'analyseurs est une fonction d'ordre supérieur qui accepte plusieurs analyseurs en entrée et renvoie un nouvel analyseur en sortie. Dans ce contexte, un analyseur est une fonction acceptant des chaînes en entrée et renvoyant une structure en sortie, généralement un arbre d'analyse ou un ensemble d'indices représentant les emplacements dans la chaîne où l'analyse s'est arrêtée avec succès. Les combinateurs d'analyseurs permettent une stratégie d'analyse descendante récursive qui facilite la construction et les tests modulaires par morceaux. Cette technique d'analyse est appelée analyse combinatoire . Les analyseurs utilisant des combinateurs ont été largement utilisés dans le prototypage de compilateurs et de processeurs pour des langages spécifiques à un domaine tels que des interfaces en langage naturel vers des bases de données, où des actions sémantiques complexes et variées sont étroitement intégrées au traitement syntaxique. En 1989, Richard Frost et John Launchbury ont démontré l'utilisation de combinateurs d'analyseurs pour construire des interpréteurs de langage naturel. Graham Hutton a également utilisé des fonctions d'ordre supérieur pour l'analyse de base en 1992 et l'analyse monadique en 1996. SD Swierstra a également exposé les aspects pratiques des combinateurs d'analyseurs en 2001. En 2008, Frost, Hafiz et Callaghan ont décrit un ensemble de combinateurs d'analyseurs dans Haskell qui résolvent le problème de longue date de la récursivité à gauche et fonctionnent comme un outil complet d'analyse descendante en temps et en espace polynomiaux. Dans tout langage de programmation doté de fonctions de première classe, les combinateurs d'analyseurs peuvent être utilisés pour combiner des analyseurs de base afin de construire des analyseurs pour des règles plus complexes. Par exemple, une règle de production d'une grammaire hors-contexte (CFG) peut avoir une ou plusieurs alternatives et chaque alternative peut consister en une séquence de symboles non-terminaux et/ou terminaux, ou l'alternative peut consister en un seul non-terminal, terminal ou chaîne vide (élément neutre de la concaténation).