Combinateur d'analyseurs — Wikipédia
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é [1] 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 [2] et l'analyse monadique en 1996[3]. SD Swierstra a également exposé les aspects pratiques des combinateurs d'analyseurs en 2001. [4] En 2008, Frost, Hafiz et Callaghan [5] 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
[modifier | modifier le code]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
[modifier | modifier le code]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 :
- Un analyseur
terme x
reconnaît le terminalx
. Si le jeton à la positionj
dans la chaîne d'entrée estx
, cet analyseur renvoie un ensemble de singletons contenantj + 1
; sinon, il renvoie l'ensemble vide.
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 entrep
etq
comme suit :
- Le séquençage des analyseurs se fait avec le combinateur d'analyseur ⊛. Comme ⊕, il est utilisé comme opérateur infixe entre
p
etq
. Mais il applique le premier analyseursp
à la position d'entréej
, et s'il y a un résultat réussi de cette application, alors le deuxième analyseursq
est appliqué à chaque élément du jeu de résultats renvoyé par le premier analyseurs. ⊛ renvoie finalement l'union de ces applications de q.
Exemples
[modifier | modifier le code]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é en position 1
d'une séquence d'entrée à 5 inconnues, selon les définitions ci-dessus, il renverrait un ensemble de résultats {5,4,3,2}
.
Lacunes et solutions
[modifier | modifier le code]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.[6] 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. [7]
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. [8] 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. [9] 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. [5] [10]
Notes
[modifier | modifier le code]- Frost et Launchbury 1989.
- Hutton 1992.
- (en-GB) Hutton et Meijer, « Monadic Parser Combinators », Université de Nottingham (rapport), (lire en ligne, consulté le )
- Swierstra 2001.
- Frost, Hafiz et Callaghan 2008.
- Frost et Szydlowski 1996.
- Frost 2003.
- Frost et Hafiz 2006.
- Frost, Hafiz et Callaghan 2007.
- cf. X-SAIGA — executable specifications of grammars
Bibliographie
[modifier | modifier le code]- William H. Burge, Recursive Programming Techniques, Addison-Wesley, coll. « The Systems programming series », (ISBN 978-0201144505, lire en ligne
)
- Richard Frost et John Launchbury, « Constructing natural language interpreters in a lazy functional language », The Computer Journal, vol. 32, no 2, , p. 108–121 (DOI 10.1093/comjnl/32.2.108
, lire en ligne [archive du ])
- Richard A. Frost et Barbara Szydlowski, « Memoizing Purely Functional Top-Down Backtracking Language Processors », Sci. Comput. Program., vol. 27, no 3, , p. 263–288 (DOI 10.1016/0167-6423(96)00014-7
, lire en ligne)
- Richard A. Frost, Monadic Memoization towards Correctness-Preserving Reduction of Search, , 66–80 p. (ISBN 978-3-540-40300-5, lire en ligne)
- Richard A. Frost et Rahmatullah Hafiz, « A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time », ACM SIGPLAN Notices, vol. 41, no 5, , p. 46–54 (DOI 10.1145/1149982.1149988, S2CID 8006549, lire en ligne)
- Richard A. Frost, Rahmatullah Hafiz et Paul Callaghan, « Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars », Proceedings of the 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE, , p. 109–120 (CiteSeerx 10.1.1.97.8915)
- Richard A. Frost, Rahmatullah Hafiz et Paul Callaghan, Parser Combinators for Ambiguous Left-Recursive Grammars, vol. 4902, coll. « ACM-SIGPLAN », , 167–181 p. (ISBN 978-3-540-77441-9, DOI 10.1007/978-3-540-77442-6_12, CiteSeerx 10.1.1.89.2132)
- Graham Hutton, « Higher-order functions for parsing », Journal of Functional Programming, vol. 2, no 3, , p. 323–343 (DOI 10.1017/s0956796800000411, S2CID 31067887, CiteSeerx 10.1.1.34.1287)
- Chris Okasaki, « Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function? », Journal of Functional Programming, vol. 8, no 2, , p. 195–199 (DOI 10.1017/S0956796898003001, S2CID 59694674)
- S. Doaitse Swierstra, « Combinator parsers: From toys to tools », Electronic Notes in Theoretical Computer Science, vol. 41, , p. 38–59 (DOI 10.1016/S1571-0661(05)80545-6
, lire en ligne)
- Philip Wadler, How to replace failure by a list of successes — A method for exception handling, backtracking, and pattern matching in lazy functional languages, vol. 201, coll. « Lecture Notes in Computer Science », , 113–128 p. (ISBN 978-0-387-15975-1, DOI 10.1007/3-540-15975-4_33)
Liens externes
[modifier | modifier le code]- 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