récursivité gauche

théorie formelle des langages informatiques , la récursivité gauche est un cas particulier de récursivité où une chaîne de caractères est identifiée comme appartenant à un langage par sa décomposition en une chaîne de ce même langage (à gauche) et un suffixe (à droite). Par exemple, la chaîne « a » peut être identifiée comme une somme car elle se décompose en « a » , également une somme, et « a » , un suffixe approprié.

En termes de grammaire hors contexte, un non -terminal est récursif à gauche si le symbole le plus à gauche dans l'une de ses productions est lui-même (dans le cas d'une récursion à gauche directe) ou peut être rendu lui-même par une séquence de substitutions (dans le cas d'une récursion à gauche indirecte). si et seulement s'il existe un symbole non terminal qui peut dériver vers une forme propositionnelle ayant lui-même pour symbole le plus à gauche. Symboliquement,, où indique l'opération consistant à effectuer une ou plusieurs substitutions, et est une séquence quelconque de symboles terminaux et non terminaux. récursivité gauche directe La récursivité directe à gauche se produit lorsque la définition peut être satisfaite par une seule substitution. Elle requiert une règle de la forme suivante : où est une séquence de non-terminaux et de terminaux. Par exemple, la règle est directement récursive à gauche. Un analyseur syntaxique descendant récursif de gauche à droite pour cette règle pourrait ressembler à ceci : où sont des séquences pouvant chacune produire la chaîne vide, tandis que peuvent être n'importe quelles séquences de symboles terminaux et non terminaux. Notez que ces séquences peuvent être vides. La dérivation puis donne comme étant le plus à gauche dans sa forme phraséologique finale.

Utilisations

La récursivité gauche est couramment utilisée comme une convention pour rendre les opérations associatives à gauche : une expression a+b-c-d+eest évaluée comme (((a+b)-c)-d)+e. Dans ce cas, cet ordre d'évaluation peut être obtenu syntaxiquement grâce aux trois règles grammaticales.

Ces méthodes permettent uniquement d'analyser le comme étant composé du et , où à son tour est composé du et , tandis que est composé du et , etc. $a+b-c-d+e a+b-c-d e a+b-c-d a+b-c d a+b-c a+b c$

Suppression de la récursivité gauche

La récursivité gauche pose souvent problème aux analyseurs syntaxiques, soit parce qu'elle les conduit à une récursivité infinie (comme c'est le cas pour la plupart des analyseurs descendants ), soit parce qu'ils attendent des règles sous une forme normale qui l'interdit (comme c'est le cas pour de nombreux analyseurs ascendants

où:

chacune est une séquence non vide de non-terminaux et de terminaux, et
chaque est une séquence de non-terminaux et de terminaux qui ne commence pas par .

Remplacez-les par deux séries de productions, une série pour :

et un autre ensemble pour le nouveau non-terminal (souvent appelé « queue » ou « reste ») :

Répétez ce processus jusqu'à ce qu'il ne reste plus de récursion directe à gauche.

Prenons comme exemple l'ensemble de règles

On pourrait réécrire ceci pour éviter la récursivité gauche comme suit :

Suppression de toute récursion restante

Le processus décrit ci-dessus peut être étendu pour éliminer toute récursion gauche, en convertissant d'abord la récursion gauche indirecte en récursion gauche directe sur le non-terminal le plus élevé d'un cycle.

Entrées Une grammaire : un ensemble de non-terminaux et leurs productions

Résultat : Une grammaire modifiée générant le même langage mais sans récursivité gauche.

Pour chaque non-terminal :
1. Répétez l'opération jusqu'à ce qu'une itération ne modifie pas la grammaire :
  1. Pour chaque règle , étant une séquence de terminaux et de non-terminaux :
    1. Si commence par un non-terminal et :
      1. Laissons - le sans son chef .
      2. Supprimer la règle .
      3. Pour chaque règle :
        Ajoutez la règle .
2. Supprimez la récursivité gauche directe comme décrit ci-dessus.

L'étape 1.1.1 consiste à développer le non-terminal initial du membre de droite d'une règle , mais seulement si . Si était une étape d'un cycle de productions donnant lieu à une récursion gauche, alors cela a raccourci ce cycle d'une étape, mais souvent au prix d'une augmentation du nombre de règles.

L'algorithme peut être vu comme établissant un ordre topologique sur les non-terminaux : il ne peut exister une règle que si . Notez que cet algorithme est très sensible à l'ordre des non-terminaux ; les optimisations se concentrent souvent sur le choix judicieux de cet ordre. $i j > i$

L'associativité est particulièrement vulnérable ; les opérateurs associatifs à gauche apparaissent généralement dans des configurations similaires à celles des opérateurs associatifs à droite avec la nouvelle grammaire. Par exemple, en partant de cette grammaire :

Les transformations standard permettant de supprimer la récursivité gauche donnent les résultats suivants :

L'analyse de la chaîne « 1 - 2 - 3 » avec la première grammaire d'un analyseur LALR (qui peut gérer les grammaires récursives à gauche) aurait donné l'arbre d'analyse suivant :

Analyse récursive à gauche d'une double soustraction

Cet arbre d'analyse regroupe les termes à gauche, donnant la sémantique correcte (1 - 2) - 3 .

L'analyse avec la seconde grammaire donne

Analyse récursive à droite d'une double soustraction

Ce qui, correctement interprété, signifie 1 + (-2 + (-3)) , également correct, mais moins fidèle à l'entrée et beaucoup plus difficile à implémenter pour certains opérateurs. Remarquez comment les termes à droite apparaissent plus profondément dans l'arbre, à l'instar d'une grammaire récursive à droite qui les organiserait pour 1 - (2 - 3) .

Prise en charge de la récursivité gauche dans l'analyse syntaxique descendante

Une grammaire formelle contenant une récursivité gauche ne peut être analysée par un analyseur LL(k) ou tout autre analyseur descendant récursif naïf , à moins d'être convertie en une forme récursive droite faiblement équivalente . En revanche, la récursivité gauche est privilégiée pour les analyseurs LALR car elle consomme moins de mémoire que la récursivité droite . Cependant, des analyseurs descendants plus sophistiqués peuvent implémenter des grammaires hors contexte générales grâce à la réduction de la complexité. En 2006, Frost et Hafiz ont décrit un algorithme qui prend en charge les grammaires ambiguës avec des règles de production récursives gauches directes . Cet algorithme a été étendu à un algorithme d'analyse syntaxique complet afin de prendre en charge la récursivité gauche indirecte et directe en temps polynomial , et de générer des représentations compactes de taille polynomiale du nombre potentiellement exponentiel d'arbres d'analyse syntaxique pour les grammaires hautement ambiguës par Frost, Hafiz et Callaghan en 2007. Les auteurs ont ensuite implémenté l'algorithme sous la forme d'un ensemble de combinateurs d'analyse syntaxique écrits dans le langage de programmation Haskell .