- Récursivité gauche
-
La récursivité gauche est un type de récursivité.
Une grammaire formelle est dite récursive gauche si elle s’écrit sous la forme suivante :
E → E v tel que v ne commence pas par E.
Sommaire
Pourquoi l’éliminer ?
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 ?
Pour trouver une grammaire non récursive équivalente à une autre qui l’est, nous utilisons les règles suivantes :
- • E → E a | b se transforme en :
- E → β E’
- E’→ α E’ | Ɛ
Exemples
Exemple 1
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
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 → β E’
- E’→ α E’ | Ɛ
Ce qui donne l’arbre de dérivation suivant qui montre que l’on garde le même effet :
Voir aussi
Articles connexes
Wikimedia Foundation. 2010.
