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.

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

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

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

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.

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.

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

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

• Portail de la programmation informatique
• Portail de la logique
• Portail de l'informatique théorique