Récursivité gauche

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

${\displaystyle A\to A\alpha }$

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

${\displaystyle 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.

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 :

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

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

${\displaystyle \qquad \cdots }$

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

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

${\displaystyle 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 ${\displaystyle A_{0}}$ comme premier symbole du mot dernier étendu.

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

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

où:

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

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

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

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

${\displaystyle 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[2] :

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

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

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

${\displaystyle E\rightarrow E+E\mid I\mid N}$

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

${\displaystyle E\rightarrow I\,E'\mid N\,E'}$

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

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

${\displaystyle S\rightarrow SSa\mid b}$.

on introduit une nouvelle variable ${\displaystyle T}$ et on remplace les règles par :

${\displaystyle S\rightarrow bT}$

${\displaystyle T\rightarrow SaT\mid \varepsilon }$.

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

${\displaystyle S\rightarrow bT}$

${\displaystyle T\rightarrow bTaT\mid \varepsilon }$.

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

${\displaystyle S\rightarrow bT\mid b}$

${\displaystyle T\rightarrow SaT\mid Sa}$,

puis remplacer la variable ${\displaystyle S}$ dans les deuxièmes règles :

${\displaystyle S\rightarrow bT\mid b}$

${\displaystyle T\rightarrow bTaT\mid baT\mid bT\mid b}$.

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

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

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

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

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

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

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

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

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle A_{2}}$ les membres droits de règle ${\displaystyle A_{3}A_{1}}$ et ${\displaystyle b}$. Ainsi, la règle ${\displaystyle A_{3}\to A_{2}A_{3}A_{2}}$ est remplacée par les règles ${\displaystyle A_{3}\to A_{3}A_{1}A_{3}A_{2}}$ et ${\displaystyle A_{3}\to bA_{3}A_{2}}$ La nouvelle grammaire est

${\displaystyle 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}}$

${\displaystyle 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 ${\displaystyle A_{3}}$ que l'on élimine par la procédure précédente.