Récursivité gauche

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La récursivité gauche est un type de récursivité. Il existe 2 types de récursivité gauche, la récursivité directe et indirecte. Une grammaire formelle est dite récursive gauche directe si elle s’écrit sous la forme suivante :

      E → E v     tel que v ne commence pas par E.

Une grammaire est dite récursive gauche indirecte si sa récursivité directe n’apparaît qu'après une ou plusieurs dérivations successives .

Pourquoi l’éliminer ?[modifier | modifier le code]

Il est évident que si on imagine une règle :

      E → E a b

Nous voyons tout de suite que dans une dérivation gauche nous allons entrer dans une boucle infinie :

      E → E a b → E a b a b → E a b a b a b…

L’analyse descendante va donc nécessiter l’élimination (si c’est possible) de la récursivité gauche.

Comment l’éliminer ?[modifier | modifier le code]

Pour trouver une grammaire non récursive équivalente à une autre qui l’est, nous utilisons les règles suivantes :

• E → E α | β    se transforme en :
         E → β E’
         E’→ α E’ | Ɛ

Exemples[modifier | modifier le code]

Exemple 1[modifier | modifier le code]

La grammaire récursive gauche suivante :

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

se transforme en appliquant la règle ci-dessus en :

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

Ainsi nous obtenons une grammaire non récursive gauche et par conséquent nous pouvons appliquer une analyse descendante sur celle-ci.

Exemple 2[modifier | modifier le code]

Soit la grammaire suivante :

   E → E a | b   où a et b ne commencent pas par E.

L’arbre de dérivation correspondant est :



En réécrivant cette grammaire sans récursivité à l’aide des règles énoncées ci-dessus nous obtenons :

   E → b E’
   E’→ a E’ | Ɛ

Ce qui donne l’arbre de dérivation suivant qui montre que l’on garde le même effet :

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]