[PDF] 05/06 - 2.2.3 Récursivité gauche

View - Download 05/06 - 2.2.3 Récursivité gauche

Previous PDF

Next PDF

Universit´e Paris 7 - LI324 - 05/06Ch2. Langages alg´ebriques

2.2.3 R´ecursivit´e gauche

Un symbole non terminalAd"une grammaire est ditr´ecursifsiA?-→αAβavecα,β? (X?V)?. Siα=ε,Aest ditr´ecursif (`a) gauche. Une grammaire comportant au moins un symbole non terminal r´ecursif gauche est dite r´ecursive gauche. (Idem droite). La r´ecursivit´e gauche pose divers probl`emes en analyse,et dans l"application de certains algorithmes de transformation de grammaire. C"est la raison pour laquelle on cherche `a

´eliminer cette r´ecursivit´e, ce qui est toujours possible, car on dispose d"un th´eor`eme :

Tout langage alg´ebrique peut ˆetre g´en´er´e par une grammaire alg´ebrique non r´ecursive gauche La d´emonstration de ce th´eor`eme, comme souvent en pareilcas, repose sur un algorithme qui, ´etant donn´ee une grammaire alg´ebrique r´ecursive gauche, produit une grammaire alg´ebrique non r´ecursive gauche qui reconnaˆıt le mˆeme langage. Il faut proc´eder en deux temps : d"une part, on va ´eliminer lar´ecursivit´e directe

(ou imm´ediate), puis ´eliminer lar´ecursivit´e indirecte. On pr´esente ici l"algorithme en

commen¸cant par un cas simple, qu"on g´en´eralise avant d"´eliminer finalement toutes les

r´ecursivit´es. R`egle simpleAu niveau d"une r`egle, cela peut se faire simplement : A→Aα|β, (avecβ?=Au), devient :A→βA? A ?→αA?|ε La r`egleA→Aαpermet de g´en´erer un nombre quel- conque de chaˆıne(s)α, mais pour que la d´erivation soit effectivement productive, il est n´ecessaire que la r´ecursion s"arrˆete, c"est-`a-dire queAdonneβ. On charge alors une r`egle de commencer par ceβ, et ensuite on a une r`egle r´ecursive (mais pas gauche), pour engendrer autant de fois que n´ecessaire lesα.A A A A

β A

α A?

???αA? Bien entendu, on produit un arbre syntaxique diff´erent dansles deux cas. G´en´eralisationPour chaque non terminal r´ecursif, on propose : A ?-→α1A?|α2A?|...|αmA?|ε

ExempleE-→E+T|T

T-→T?F|F

F-→(E)|ase trouve transform´e enE-→TE? E ?-→+TE?|ε

T-→FT?

T ?-→ ?FT?|ε

F-→(E)|a

Appliqu´e `a chaque non terminal r´ecursif, cet algorithmesupprime les sources de r´ecursivit´e

8 Universit´e Paris 7 - LI324 - 05/06Ch2. Langages alg´ebriques gauchedirectes. Mais, comme on peut le voir avec l"exemple suivant, il y a potentiellement dans les grammaires des sources de r´ecursivit´e indirectes, qu"il faudra ´eliminer aussi.

S-→Aa|b

A-→Ac|Sd|cqui devientS-→Aa|bR`egle conserv´ee

A-→SdA?|cA?R`egle transform´ee

A ?-→cA?|ε

La r´ecursivit´e directe de la r`egleA-→Aαest supprim´ee, mais on n"a pas ´elimin´e la

r´ecursivit´e indirecteA-→Sγ-→Aα?γ.

Elimination de la r´ecursivit´e indirecte

Id´ee de l"algorithme : pour les paires de r`egles du typeA→A?δetA?→Aη, on"anticipe»

les d´erivations probl´ematiques :A→Aηδ, et on applique l"algorithme pr´ec´edent.

Suppression de toutes les r´ecursivit´es

Donn´eesGgrammaire alg´ebrique propre

R´esultatG?grammaire sans r´ecursivit´e `a gauche, t.q.LG=LG?. M´ethodeSoit (A1,A2,...An) la liste ordonn´ee desAi?V.

Pour toutide 1 `anfaire{

Pour toutjde 1 `ai-1 faire{

SiAi-→Ajαexiste, la remplacer par :Ai-→δ1α|δ2α|...|δhα o`uAj-→δ1|δ2|...|δh ´Eliminer la r´ecursivit´e imm´ediate desAi-productions Exemple : grammaire pr´ec´edenteS-→Aa|b

A-→Ac|Sd|c

Ordre des non-terminaux (arbitraire) :{A1=S,A2=A}

-i= 1 :∅ -i= 2;j= 1 : - La r`egleA-→Sdest concern´ee (Ai(=2)→Aj(=1)α) - On la remplace parA-→Aad|bd - On"d´er´ecursive»toutes lesA(i)-productions : Les r`eglesA→Aad|Ac|c|bddeviennent?A-→cA?|bdA? A ?-→adA?|cA?|ε - Fin

La grammaire r´esultante est?????S-→Aa|b

A-→cA?|bdA?

A ?-→adA?|cA?|εou?????S-→Aa|b

A-→cA?|bdA?|c|bd

A ?-→adA?|cA?|ad|c ExerciceAppliquer le mˆeme algorithme `a la grammaire suivante, grammaire de la liste.

S→(L)|a

L→L,S|S

9quotesdbs_dbs22.pdfusesText_28

[PDF] Corrigé Série d exercices n°4 : Les fonctions et procédures

[PDF] Bases d 'algorithmique

[PDF] COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE

[PDF] FICHE n°6 : PROGRAMMER DES BOUCLES - Maths-et-tiques

[PDF] fiche maternelle algorithme imprimer- pdf documents

[PDF] Fiche enseignant ALGORITHMES NIVEAU : GRANDE SECTION

[PDF] Algorithme et numération - Académie de Nancy-Metz

[PDF] L 'atelier des petites chenilles en PS Etape 1 - académie de Caen

[PDF] reproduire une suite algorithmique - Accueil DSDEN 22

[PDF] Rappels : Tableaux et Matrices

[PDF] N°96 - spécial mouvement intra 2016pub - Snes

[PDF] Algorithmique et programmation : les bases (Algo) Corrigé

[PDF] TP7 : le théor`eme du point fixe en action sous MATLAB

[PDF] Séance de travaux pratiques n° 1

[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep