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.

Idée de base

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). Si un analyseur simple est disponible pour chacune de ces alternatives, un combinateur d'analyseurs peut être utilisé pour combiner chacun de ces analyseurs, renvoyant un nouvel analyseur qui peut reconnaître une ou toutes les alternatives.

Dans les langages qui prennent en charge la surcharge d'opérateurs, un combinateur d'analyseurs peut prendre la forme d'un opérateur infixe, utilisé pour assembler différents analyseurs pour former une règle complète. Les combinateurs d'analyseurs permettent ainsi de définir des analyseurs dans un style intégré, dans un code dont la structure est similaire aux règles de la grammaire formelle. En tant que telles, les implémentations peuvent être considérées comme des spécifications exécutables avec tous les avantages associés tels que la lisibilité.

Les combinateurs

Pour garder la discussion relativement simple, nous discutons des combinateurs d'analyseur uniquement en termes de reconnaisseurs . Si la chaîne d'entrée est de longueur L et que ses membres sont accessibles via un index j, un module de reconnaissance est un analyseur qui renvoie, en sortie, un ensemble d'indices représentant les positions auxquelles l'analyseur a terminé avec succès la reconnaissance d'une séquence de jetons qui a commencé à la position j. Un ensemble de résultats vide indique que le module de reconnaissance n'a pas reconnu de séquence commençant à l'index j . Un ensemble de résultats non vide indique que le module de reconnaissance se termine avec succès à différentes positions.

• Le module de reconnaissance vide reconnaît la chaîne vide. Cet analyseur réussit toujours, renvoyant un ensemble singleton contenant la position actuelle :

$vide(j)=\{j\}$

• Un analyseur terme x reconnaît le terminal x . Si le jeton à la position j dans la chaîne d'entrée est x, cet analyseur renvoie un ensemble de singletons contenant j + 1 ; sinon, il renvoie l'ensemble vide.

$terme(x,j)={\begin{cases}\left\{\right\},&j\geq L\\\left\{j+1\right\},&j^{e}{\mbox{ élement de }}entree=x\\\left\{\right\},&{\mbox{sinon}}\end{cases}}$

Notons qu'il peut y avoir plusieurs manières distinctes d'analyser une chaîne tout en terminant au même index : cela indique une grammaire ambiguë . Les analyseurs simples ne reconnaissent pas ces ambiguïtés ; chaque indice de finition possible n'est répertorié qu'une seule fois dans le jeu de résultats. Pour un ensemble de résultats plus complet, un objet plus compliqué tel qu'un arbre d'analyse doit être renvoyé.

En suivant les définitions de deux analyseurs de base p et q, nous pouvons définir deux principaux combinateurs d'analyseur pour l'alternative et le séquençage :

• Le combinateur d'analyseur "alternatif", ⊕, applique les deux analyseurs sur la même position d'entrée j et résume les résultats renvoyés par les deux analyseurs, qui sont finalement renvoyés comme résultat final. Il est utilisé comme opérateur infixe entre p et q comme suit :

$(p\oplus q)(j)=p(j)\cup q(j)$

• Le séquençage des analyseurs se fait avec le combinateur d'analyseur ⊛. Comme ⊕, il est utilisé comme opérateur infixe entre p et q . Mais il applique le premier analyseurs p à la position d'entrée j, et s'il y a un résultat réussi de cette application, alors le deuxième analyseurs q est appliqué à chaque élément du jeu de résultats renvoyé par le premier analyseurs. ⊛ renvoie finalement l'union de ces applications de q.

$(p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}$

Exemples

Considérons une grammaire hors-contexte très ambiguë, s ::= 'x' ss | ε . En utilisant les combinateurs définis précédemment, nous pouvons définir de manière modulaire des notations exécutables de cette grammaire dans un langage fonctionnel moderne (par exemple Haskell ) comme s = terme 'x' <*> s <*> s <+> vide . Lorsque l'analyseur s est appliqué sur une séquence d'entrée xxxxx à la position 1, selon les définitions ci-dessus, il renverrait un ensemble de résultats {5,4,3,2} .

Lacunes et solutions

Les combinateurs d'analyseurs, comme tous les analyseurs de descente récursive, ne sont pas limités aux grammaires hors-contexte et ne font donc pas de recherche globale d'ambiguïtés dans les ensembles d'analyse LL( k )

Premier _k et Suivant _k . Ainsi, les ambiguïtés ne sont connues qu'au moment de l'exécution si et jusqu'à ce que l'entrée les déclenche. Dans de tels cas, l'analyseur de descente récursive peut par défaut (peut-être inconnu du concepteur de la grammaire) sur l'un des chemins ambigus possibles, entraînant une confusion sémantique (crénelage) dans l'utilisation du langage. Cela conduit à des bogues par les utilisateurs de langages de programmation ambigus, qui ne sont pas signalés au moment de la compilation, et qui sont introduits non pas par une erreur humaine, mais par une grammaire ambiguë. La seule solution qui élimine ces bogues est de lever les ambiguïtés et d'utiliser une grammaire sans contexte.

Les implémentations simples des combinateurs d'analyseur présentent certaines lacunes, qui sont courantes dans l'analyse descendante. L'analyse combinatoire naïve nécessite un temps et un espace exponentiels lors de l'analyse d'une grammaire ambiguë hors-contexte. En 1996, Frost et Szydlowski ont démontré comment la mémorisation peut être utilisée avec des combinateurs d'analyseurs pour réduire la complexité à un temps polynomial. Plus tard, Frost a utilisé des monades pour construire les combinateurs pour un enfilage systématique et correct de la table mémo tout au long du calcul.

Comme toute analyse descendante récursive, les combinateurs d'analyseur conventionnels (comme les combinateurs décrits ci-dessus) ne se termineront pas lors du traitement d'une grammaire récursive à gauche (par exemple s ::= s <*> terme 'x'|vide ). Un algorithme de reconnaissance qui s'adapte aux grammaires ambiguës avec des règles récursives directes à gauche est décrit par Frost et Hafiz en 2006. L'algorithme réduit l'analyse récursive à gauche par ailleurs toujours croissante en imposant des restrictions de profondeur. Cet algorithme a été étendu à un algorithme d'analyse complet pour s'adapter à la récursivité gauche indirecte et directe en temps polynomial et pour générer des représentations compactes de taille polynomiale du nombre potentiellement exponentiel d'arbres d'analyse pour les grammaires très ambiguës par Frost, Hafiz et Callaghan dans 2007. Cet algorithme étendu s'adapte à la récursivité gauche indirecte en comparant son «contexte calculé» avec le «contexte actuel». Les mêmes auteurs ont également décrit leur implémentation d'un ensemble de combinateurs d'analyseurs écrits dans le langage de programmation Haskell basé sur le même algorithme.

Notes

L’argument 1 (valeur 2) n’existe pas dans le modèle appelé

Liens externes

• parser-combinator : implémentation du combinateur d'analyseur Common Lisp
• Parsec : bibliothèque de combinateurs d'analyseurs monadique de niveau industriel pour Haskell
• parsec : version Go de Parsec
• FParsec : adaptation F# de Parsec
• csharp-monad : portage C# de Parsec
• Jparsec : Portage Java de Parsec
• Arcsecond : bibliothèque de combinateurs d'analyseurs monadiques conforme à Javascript fantasy-land
• Ramble : Implémentation du combinateur d'analyseur R
• nom : Implémentation du combinateur d'analyseurs Rust en utilisant zéro copie.
• pyparsing : Implémentation du combinateur d'analyseur Python, bien qu'il ne s'appelle pas ainsi dans sa documentation.
• ts-parsec : bibliothèque de combinateurs d'analyseur TypeScript
• Diesel : bibliothèque de combinateurs d'analyseurs Swift
• NimbleParsec : bibliothèque de combinateurs d'analyseurs Elixir