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^[1] qui débute par cette variable, formellement si

A \Rightarrow^{+} A α

,

où $\Rightarrow^{+}$ indique l'opération consistant à appliquer une ou plusieurs règles de grammaire, et où $α$ 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 α

où $α$ 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 β_{0} A_{1} α_{0}

A_{1} \to β_{1} A_{2} α_{1}

\dots

A_{n} \to β_{n} A_{0} α_{n}

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

A_{0} \Rightarrow β_{0} A_{1} α_{0} \Rightarrow^{+} A_{1} α_{0} \Rightarrow β_{1} A_{2} α_{1} α_{0} \Rightarrow^{+} \dots \Rightarrow^{+} A_{0} α_{n} \dots α_{1} α_{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 \to A α_{1} ∣ \dots ∣ A α_{n} ∣ β_{1} ∣ \dots ∣ β_{m}

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 $A$ .

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

A \to β_{1} A^{'} ∣ \dots ∣ β_{m} A^{'}

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

A^{'} \to α_{1} A^{'} ∣ \dots ∣ α_{n} A^{'} ∣ ε

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] :

A \to β_{1} A^{'} ∣ \dots ∣ β_{m} A^{'} ∣ β_{1} ∣ \dots ∣ β_{m}

A^{'} \to α_{1} A^{'} ∣ \dots ∣ α_{n} A^{'} ∣ α_{1} ∣ \dots ∣ α_{n}

Exemples

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

E \to E + E ∣ I ∣ N

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

E \to I E^{'} ∣ N E^{'}

E^{'} \to + E E^{'} ∣ ε

.

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

S \to S S a ∣ b

.

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

S \to b T

T \to S a T ∣ ε

.

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

S \to b T

T \to b T a T ∣ ε

.

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

S \to b T ∣ b

T \to S a T ∣ S a

,

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

S \to b T ∣ b

T \to b T a T ∣ b a T ∣ b T ∣ 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 ε$ 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} α

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^[3] :

Numéroter les variables en  $A_{1}, \dots, A_{n}$ 
pour   $i = 1, \dots, n$ 
   pour  $j = 1, \dots, i - 1$ 
      remplacer chaque production  $A_{i} \to A_{j} γ$  par les productions
          $A_{i} \to δ_{1} γ ∣ \dots ∣ δ_{k} γ$ , où
          $A_{j} \to δ_{1} ∣ \dots ∣ δ_{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^[4] : On considère la grammaire

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

A_{2} \to A_{3} A_{1}, A_{3} \to a, 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}, A_{3} \to A_{2} A_{3} A_{2}

A_{2} \to A_{3} A_{1}, A_{3} \to a, 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 b A_{3} A_{2}$ La nouvelle grammaire est

A_{1} \to A_{2} A_{3}, A_{3} \to A_{3} A_{1} A_{3} A_{2}, A_{3} \to b A_{3} A_{2}

A_{2} \to A_{3} A_{1}, A_{3} \to a, 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^[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)

Notes et références

↑ 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.
↑ Ceci est la méthode préconisée par exemple dans : Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne).
1 2 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, 2007, 2^e éd., 928 p. (ISBN 978-2-7440-7037-2 et 2744070378).
↑ John E. Hopcroft et Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley, 1969, 242 p. (ISBN 0-201-02983-9, SUDOC 004772571), , page 55.

Articles connexes

Portail de la programmation informatique

Portail de la logique

Portail de l'informatique théorique

[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é, 2008 [détail de l’édition] (lire en ligne).

[DB-3] 1 2 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, 2007, 2^e é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, 1969, 242 p. (ISBN 0-201-02983-9, SUDOC 004772571), , page 55.

[1]

[2]

[3]

[4]