Récursivité gauche

En informatique, et notamment en théorie des langages formels, en compilation et analyse syntaxique descendante, la récursivité gauche est un concept de grammaires formelles qui décrit un certain type de réapparition d'une variable dans une dérivation lors d'un processus d'analyse syntaxique.

Dans la terminologie des grammaires formelles et notamment des grammaires algébriques, une variable est récursive gauche s'il existe une règle de la grammaire dont le membre droit débute par cette variable (ce cas est dit récursivité directe) ou pour laquelle un mot dérivé débute par cette variable (cas de la récursivité indirecte).

L'élimination de la récursivité gauche est une étape préliminaire pour pouvoir utiliser l'analyse syntaxique descendante.

Définition

modifier

Une grammaire est récursive gauche s'il existe une variable   qui dérive en un mot du langage étendu[1] qui débute par cette variable, formellement si

 ,

  indique l'opération consistant à appliquer une ou plusieurs règle de grammaire, et où   est une suite de symboles terminaux et non terminaux.

Récursivité gauche directe

modifier

La récursivité gauche est directe si la définition est réalisée en une étape, c'est-à-dire si la grammaire possède une règle de la forme

 

  est une suite de symboles terminaux et non terminaux. Par exemple, la règle

 

d'une grammaire usuelle pour les expressions arithmétiques est récursive gauche directe. Un analyseur descendant pourrait l'implémenter par une procédure du type

function Expression()
{
    Expression();  match('+');  Terme();
}

ce qui provoque une boucle infinie d'appels récursifs à l’exécution.

Récursivité gauche indirecte

modifier

La récursivité gauche est indirecte si la définition est réalisée en plusieurs étapes. Formellement, elle demande l’existence d'une suite de règles selon le schéma suivant :

 
 
 
 

  sont des mots qui chacun peuvent dériver en le mot vide et   sont des mots quelconques. La dérivation

 

produit   comme premier symbole du mot dernier étendu.


Élimination de la récursivité gauche

modifier

Élimination de la récursivité directe

modifier

L'élimination de la récursivité directe procède par le remplacement de règles récursives gauche par d'autres, et l'introduction de nouveaux non-terminaux. Pour une variable récursive gauche  , on supprime d'abord la règle   si elle existe, puis on considère les règles restantes :

 

où:

  • chaque   est formé de symboles terminaux ou non terminaux, et
  • chaque   est un mot formé de symboles terminaux ou non terminaux et qui ne commence pas par  .

On remplace ces règles par deux ensembles de règles, un groupe de règles commençant par la variable  :

 

et un autre pour une nouvelle variable   (appelée le « reste » ou la « queue ») :

 

On répète ce processus jusqu'à épuisement des variables récursives gauches directes.

Cette méthode à l'inconvénient d'introduire des epsilon-règle ; une variante évite ce défaut, au prix de plus de règles. Les règles récursives gauches sont remplacées par[2] :

 
 

Exemples

modifier

Par exemple, dans une grammaire simplifiée des expressions arithmétiques, les règles :

 

peuvent être remplacées, pour supprimer la récursion gauche, par :

 
 .

L'image miroir du langage de Lukasiewicz a pour grammaire :

 .

on introduit une nouvelle variable   et on remplace les règles par :

 
 .

Puis, on substitue   à   dans la deuxième règle, et on obtient :

 
 .

On peut aussi écrire, avec la deuxième méthode :

 
 ,

puis remplacer la variable   dans les deuxièmes règles :

 
 .

Élimination de toute récursivité gauche

modifier

Une façon — brutale — d'éliminer toute récursivité gauche est de mettre la grammaire sous forme normale de Greibach. Plus simplement, on peut d'abord éliminer les ε-règles, c'est-à-dire les règles de la forme   et les règles triviales  . Ensuite, on numérote les variables, puis on opère sur les règles

 

pour avoir toujours  . Si pour une règle, cette condition n'est pas vérifiée, on remplace   par ses membres droits de règle. Plus formellement, l'algorithme est le suivant[3] :

Numéroter les variables en  
pour   
   pour  
      remplacer chaque production   par les productions
          , où
           sont toutes les productions de  
   éliminer la récursivité gauche directe pour les productions de  

Voici un exemple, tiré du livre de Hopcroft et Ullman[4] : On considère la grammaire

 
 

Seule la règle   doit être modifiée, on remplace   par son unique membre de règle  . La nouvelle grammaire est alors

 
 .

Comme le membre droit de la règle   commence par une variable de numéro inférieur, on substitue à la première occurrence de   les membres droits de règle   et  . Ainsi, la règle   est remplacée par les règles   et   La nouvelle grammaire est

 
 .

On obtient ainsi une grammaire où ne subsiste qu'une récursivité gauche directe pour la variable   que l'on élimine par la procédure précédente.

Un exemple traditionnel

modifier

La grammaire récursive gauche suivante est une grammaire traditionnelle pour décrire les expressions arithmétiques dans leur forme la plus rudimentaire :

E → E + T | T
T → T * F | F
F → (E) | id

Elle se transforme, en appliquant les règles ci-dessus, en :

E → T E’
E’→ +T E’ | ε
T → F T’
T’→ *F T’ | ε
F → (E) | id

On obtient une grammaire non récursive gauche et par conséquent on peut appliquer une analyse descendante sur celle-ci.

Note bibliographique

modifier

Les manuels de théorie des langages formels traitent indirectement de l'élimination de la récursivité gauche dans le cadre de la mise sous forme normale de Greibach. Les manuels de programmation, comme le « Dragon book », traitent l'élimination dans le cadre de l'analyse descendante; leur algorithme[3] 4.19 décrit la méthode esquissée ci-dessus plus en détail.

En linguistique informatique aussi ce problème est d'intérêt, comme le montre l'article suivant : Robert C. Moore, « Removing Left Recursion from Context-Free Grammars », Applied Natural Language Processing,‎ , p. 249-255 (lire en ligne)

Notes et références

modifier
  1. Un mot du langage étendu (en anglais « sentential form ») est un mot qui dérive de l’'axiome de la grammaire, mais qui est susceptible de contenir encore des variables.
  2. Ceci est la méthode préconisée par exemple dans : Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne).
  3. a et b Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman (trad. de l'anglais), Compilateurs : principes, techniques et outils : Avec plus de 200 exercices, Paris, Pearson, , 2e éd., 928 p. (ISBN 978-2-7440-7037-2 et 2744070378).
  4. John E. Hopcroft et Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley, , 242 p. (ISBN 0-201-02983-9, SUDOC 004772571), , page 55.

Articles connexes

modifier