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

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

$A\Rightarrow ^{+}A\alpha$,

où $\Rightarrow ^{+}$ indique l'opération consistant à appliquer une ou plusieurs règle de grammaire, et où $\alpha$ est une suite de symboles terminaux et non terminaux.

Récursivité gauche directe

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

$A\to A\alpha$

où $\alpha$ est une suite de symboles terminaux et non terminaux. Par exemple, la règle

$E\to E+T$

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

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 :

$A_{0}\to \beta _{0}A_{1}\alpha _{0}$

$A_{1}\to \beta _{1}A_{2}\alpha _{1}$

$\qquad \cdots$

$A_{n}\to \beta _{n}A_{0}\alpha _{n}$

où $\beta _{0},\beta _{1},\ldots ,\beta _{n}$ sont des mots qui chacun peuvent dériver en le mot vide et $\alpha _{0},\alpha _{1},\ldots ,\alpha _{n}$ sont des mots quelconques. La dérivation

$A_{0}\Rightarrow \beta _{0}A_{1}\alpha _{0}\Rightarrow ^{+}A_{1}\alpha _{0}\Rightarrow \beta _{1}A_{2}\alpha _{1}\alpha _{0}\Rightarrow ^{+}\cdots \Rightarrow ^{+}A_{0}\alpha _{n}\dots \alpha _{1}\alpha _{0}$

produit $A_{0}$ comme premier symbole du mot dernier étendu.

Élimination de la récursivité gauche

Élimination de la récursivité directe

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 $A$, on supprime d'abord la règle $A\to A$ si elle existe, puis on considère les règles restantes :

$A\rightarrow A\alpha _{1}\mid \ldots \mid A\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}$

où:

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

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

$A\rightarrow \beta _{1}A^{\prime }\mid \ldots \mid \beta _{m}A^{\prime }$

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

$A^{\prime }\rightarrow \alpha _{1}A^{\prime }\mid \ldots \mid \alpha _{n}A^{\prime }\mid \varepsilon$

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 :

$A\rightarrow \beta _{1}A'\mid \ldots \mid \beta _{m}A'\mid \beta _{1}\mid \ldots \mid \beta _{m}$

$A'\rightarrow \alpha _{1}A'\mid \ldots \mid \alpha _{n}A'\mid \alpha _{1}\mid \ldots \mid \alpha _{n}$

Exemples

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

$E\rightarrow E+E\mid I\mid N$

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

$E\rightarrow I\,E'\mid N\,E'$

$E'\rightarrow {}+E\,E'\mid \varepsilon$.

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

$S\rightarrow SSa\mid b$.

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

$S\rightarrow bT$

$T\rightarrow SaT\mid \varepsilon$.

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

$S\rightarrow bT$

$T\rightarrow bTaT\mid \varepsilon$.

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

$S\rightarrow bT\mid b$

$T\rightarrow SaT\mid Sa$,

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

$S\rightarrow bT\mid b$

$T\rightarrow bTaT\mid baT\mid bT\mid b$.

Élimination de toute récursivité gauche

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 $A\to \varepsilon$ et les règles triviales $A\to A$. Ensuite, on numérote les variables, puis on opère sur les règles

$A_{i}\to A_{j}\alpha$

pour avoir toujours $i<j$. Si pour une règle, cette condition n'est pas vérifiée, on remplace $A_{j}$ par ses membres droits de règle. Plus formellement, l'algorithme est le suivant :

Numéroter les variables en $A_{1},\ldots ,A_{n}$
pour  $i=1,\ldots ,n$
   pour $j=1,\ldots ,i-1$
      remplacer chaque production $A_{i}\to A_{j}\gamma$ par les productions
         $A_{i}\to \delta _{1}\gamma \mid \cdots \mid \delta _{k}\gamma$, où
         $A_{j}\to \delta _{1}\mid \cdots \mid \delta _{k}$ sont toutes les productions de $A_{j}$
   éliminer la récursivité gauche directe pour les productions de $A_{i}$

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

$A_{1}\to A_{2}A_{3},\quad A_{3}\to A_{1}A_{2}$

$A_{2}\to A_{3}A_{1},\quad A_{3}\to a,\quad A_{2}\to b$

Seule la règle $A_{3}\to A_{1}A_{2}$ doit être modifiée, on remplace $A_{1}$ par son unique membre de règle $A_{2}A_{3}$. La nouvelle grammaire est alors

$A_{1}\to A_{2}A_{3},\quad A_{3}\to A_{2}A_{3}A_{2}$

$A_{2}\to A_{3}A_{1},\quad A_{3}\to a,\quad A_{2}\to b$.

Comme le membre droit de la règle $A_{3}\to A_{2}A_{3}A_{2}$ commence par une variable de numéro inférieur, on substitue à la première occurrence de $A_{2}$ les membres droits de règle $A_{3}A_{1}$ et $b$. Ainsi, la règle $A_{3}\to A_{2}A_{3}A_{2}$ est remplacée par les règles $A_{3}\to A_{3}A_{1}A_{3}A_{2}$ et $A_{3}\to bA_{3}A_{2}$ La nouvelle grammaire est

$A_{1}\to A_{2}A_{3},\quad A_{3}\to A_{3}A_{1}A_{3}A_{2},\quad A_{3}\to bA_{3}A_{2}$

$A_{2}\to A_{3}A_{1},\quad A_{3}\to a,\quad A_{2}\to b$.

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

Un exemple traditionnel

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

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 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,‎ 2000, p. 249-255 (lire en ligne)

Articles connexes

• Grammaire régulière
• Analyse lexicale
• Analyse syntaxique
• Analyse LL
• Analyse LR
• Forme normale de Chomsky
• Forme normale de Greibach