Worldlex Wiki Un analyseur prédictif est un analyseur descendant récursif qui ne nécessite pas de retour arrière . L'analyse prédictive n'est possible que pour les grammaires LL( k ) , c'est -à -dire les grammaires hors contexte pour lesquelles il existe un entier positif k permettant à un analyseur descendant récursif de déterminer la production à utiliser en examinant uniquement les k prochains jetons de l'entrée. Les grammaires LL( k ) excluent donc toutes les grammaires ambiguës , ainsi que toutes les grammaires contenant une récursivité gauche . Toute grammaire hors contexte peut être transformée en une grammaire équivalente sans récursivité gauche, mais la suppression de la récursivité gauche ne conduit pas toujours à une grammaire LL( k ). Un analyseur prédictif s'exécute en temps linéaire .
La descente récursive avec retour arrière est une technique qui détermine la production à utiliser en les testant successivement. Cette technique n'est pas limitée aux grammaires LL( k ), mais sa terminaison n'est garantie que si la grammaire est LL( k ). Même lorsqu'ils se terminent, les analyseurs syntaxiques utilisant la descente récursive avec retour arrière peuvent nécessiter un temps d'exécution exponentiel .
Bien que les analyseurs syntaxiques prédictifs soient largement utilisés et souvent privilégiés lors de la programmation manuelle, les programmeurs préfèrent généralement utiliser un analyseur syntaxique tabulaire généré par un outil dédié , que ce soit pour un langage LL( k ) ou avec un analyseur alternatif comme LALR ou LR . C'est notamment le cas si la grammaire n'est pas sous forme LL( k ) , car sa transformation en LL est nécessaire pour l'analyse syntaxique prédictive. Les analyseurs syntaxiques prédictifs peuvent également être générés automatiquement à l'aide d'outils comme ANTLR .
Les analyseurs prédictifs peuvent être représentés à l'aide de diagrammes de transition pour chaque symbole non terminal, où les arêtes entre les états initial et final sont étiquetées par les symboles (terminaux et non terminaux) du côté droit de la règle de production.
La grammaire de type EBNF suivante (pour le langage de programmation PL/0 de Niklaus Wirth , tirée de Algorithms + Data Structures = Programs ) est sous forme LL(1) :Les terminaux sont exprimés entre guillemets. Chaque non-terminal est défini par une règle de la grammaire, à l'exception d'ident et de number , qui sont considérés comme implicitement définis.
implémentation C
Ce qui suit est une implémentation d'un analyseur syntaxique descendant récursif pour le langage ci-dessus en C. L'analyseur lit le code source et se termine avec un message d'erreur si le code ne peut pas être analysé, se terminant silencieusement si le code est analysé correctement.
Remarquez la grande similitude entre l'analyseur prédictif ci-dessous et la grammaire ci-dessus. Chaque non-terminal de la grammaire possède sa propre procédure. L'analyse se déroule de haut en bas jusqu'au traitement du dernier non-terminal.
Le fragment de programme dépend des fonctions peeksymsuivantes : `lecture` consumesym, `consommation`, ` erroraffichage`, `message`. Ces fonctions sont supposées être fournies par l’analyseur lexical.
Exemples
Quelques générateurs d'analyseurs syntaxiques à descente récursive :
- TMG – un compilateur-compilateur ancien utilisé dans les années 1960 et au début des années 1970
- JavaCC
- Coco/R
- ANTLR
- Spirit Parser Framework – un framework de génération d'analyseurs syntaxiques descendants récursifs en C++ ne nécessitant aucune étape de précompilation
- parboiled (Java) – une bibliothèque d'analyse syntaxique PEG par descente récursive pour Java
L'interface C++ du compilateur Clang contient un analyseur syntaxique écrit à la main basé sur l'algorithme d'analyse syntaxique descendante récursive.