Théorie des langages : Cours langages et compilation analyse syntaxique ascendante
Télécharger PDFLangagesetCompilation
Analysesyntaxiqueascendante1 Analysesyntaxiqueascendante
Constructiondel'arbrededérivationselonl'ordrep ost xé:
onpartdesfeuilles(lesterminaux)etonremonteàlaracine.
Deuxop érations:
lacréationdesfeuillespardécalage
laconstructiondesn÷udsinternesparréduction.2 Analysesyntaxiqueascendante E→E+T|TT→T∗F|F F→id
Lesop érationsdedécalageet
deréductions'eectuentdans
l'ordreduparcoursp ost xéde
l'arbrededérivation.
id,F→id,T→F,E→T,+,
id,F→id,T→F,∗,id,F→id,
T→T∗F,E→E+T
Lasuiteinversedesréductions
dansl'ordreduparcoursp ost-
xédonneladérivationdroite
dumotanalysé.
Analysedumotid+id∗idE ET Fid +T TF id∗ Fid E→E+TE→T T→FF→id T→FF→id F→idT→T∗F E→E+T→E+T∗F→E+T∗id→E+F∗id→E+id∗id→
T+id∗id→F+id∗id→id+id∗id3 Analysesyntaxiqueascendante
Appro chenon-déterministe
Enpratiqueonutiliseunepilep ourréaliseruneanalyseascendante
pardécalage/réduction.
Cettepilecontientaudépartunmarqueurparticulier$.
L'analyseurlitlemotàanalyser(complétédumarqueur$)de
gaucheàdroite.
Ilop ère• soitendécalantuncaractèredumotverslapile• soitparréduction,àconditionqu'iltrouveausommetdela
pileunechaîneβcorresp ondantàlapartiedroited'une
pro ductionA→βqu'onremplacealorsparA
etcecidefaçonnondéterministeendevinantlesb onnesop érations.4 Analysesyntaxiqueascendante
Appro chenon-déterministe
Analysedumotid∗idendevinantlesb onnesop érations.
MotPileArbre
id∗id$$decalerid
id∗id$$idreduireF→idid F
id∗id$$FreduireT→Fid FT id∗id$$Tdecalerid ∗F T
id∗id$$T∗decalerid ∗id FT 5. .. .. .
id∗id$$T∗decalerid ∗id FT id∗id$$T∗idreduireF→idid ∗id FT F
id∗id$$T∗FreduireT→T∗Fid ∗id FT FT id∗id$$TreduireE→Tid ∗id FT FT E
id∗id$$E n6 Automatecaractéristique
L'analyseurdoitidenti erausommetdelapileleschaînesquisont
partiedroited'unepro ductiondelagrammaireetcecidemanièree cace. Àceteet,onvaconstruireunautomate niquivadécrirele
comp ortementausommetdelapile.
Uneconventionutileparlasuiteestd'augmenterlagrammaire
d'unenouvellevariableinitetdelarègleinit→S.
initestalorslenouvelaxiomeetremplacel'ancienaxiomeS.7 Lesélémentsdel'automate
ItemLR(0)
X→α•βoùX→αβestunerègledelagrammaire
et•estunsymb oleparticulier
cequiadéjàétéanalysé•cequ'onattendαβ partie
analysée··· X
LesitemsX→α•sontditscompletsα partieanalyséeX OnaquatreitemsLR(0)asso ciésàlapro ductionA→Abc:
A→•Abc,A→A•bc,A→Ab•cetl'itemcompletA→Abc•
Leseulitemasso ciéàuneε-pro ductionA→εestl'itemcompletA→• 8
L'automate nicaractéristique
L'AFNavecε-transitionsquicaractériselesitemsvalides:
l'alphab et:Σ∪N
lesétats:lesitemsLR(0)
lesétatsd'acceptation:lesitemsLR(0)complets
l'étatinitial:l'iteminit→•S
lafonctiondetransition:troistyp esdetransition
-décalage
X→α•aβX→αa•βa -réductionX→α•YβX→αY•βY -prédictionX→α•YβY→•δ ε
p ourtoutepro ductionY→δ9 Lestransitions• décalageαaβ partie
analyséea ···X αaβpartie analyséea ···X •
réductionαYβ ai ···aj ···X δY ai ···aj αYβa i···a j··· 10• prédictionαYβ partie
analyséeX δY 11
l'AFNavecε-transitionsinit→•E E→•E+TE→•T init→E•E→E•+T T→•T∗FT→•F E→E+•TE→T•∗F F→•idF→id•E→E+T• E→T∗•FE→T∗F•E→T• T→F•ε εE Eε εT +T εF T∗ idF εε εε εεε Lagrammaireaugmentée init→EE→E+T|T T→T∗F|FF→id 12
Déterminisationdel'AFNavecε-transitions
Lesétatsdel'AFDsontdesensemblesd'itemsLR(0).
Onutilisel'op érationdeclôturep oursupprimerlesε-transitions:
Cloture(I)l'ensembledesitemsaccessiblesàpartird'unitemde
Ipardesε-transitions
c'estleplusp etitensemblecontenantIettelquesiX→
α•YβestdansIetY→γestunepro ductiondela
grammairealorsY→•γestdansCloture(I)
Latransitionétiquetéeparunterminalouunevariableestdé nieainsi δ(I,e) =Cloture( {X→αe•β:X→α•eβ∈I}) L'étatinitialestCloture( {init→•S}) .
Seulslesétatsnonvidesaccessiblesàpartirdel'étatinitialviala
fonctionδsontconstruits.
Lesétatsd'acceptationsontceuxquicontiennentunitemcomplet.13 Lesétatsdel'AFD
0étatinitialinit→•E E→•E+TE→•T T→•T∗FT→•F F→•id
1=δ(0,E)init→E• E→E•+T
2=δ(0,T)E→T• T→T•∗F
3=δ(0,F)T→F• 4=δ(0,id)F→id• itemshérités parclôture 14
5=δ(1,+)E→E+•T T→•T∗FT→•F F→•id
6=δ(2,∗)T→T∗•F F→•id
7=δ(5,T)E→E+T• T→T•∗F
δ(5,F) =3, δ(5,id) =4
8=δ(6,F)T→T∗F• δ(6,id) =4clôture clôture15 L'AFDinit→•E E→•E+TE→•T T→•T∗FT→•F F→•id0 init→E•E→E•+T 1E→T• T→T•∗F2 E→E+•TT→•T∗F T→•FF→•id 5T→F• 3E→E+T• T→T•∗F7 T→T∗•FF→•id 6T→T∗F• 8F→id• 4E TF +∗ Fid TF id∗ id16 Constructiondelatabled'analyseLR(0)
Latableaenlignelesétatsdel'automateetencolonnele
marqueur$,lesterminauxetvariablesdelagrammaire.
PourchaqueétatIdel'automate:• p ourchaquetransitionIa −→Jétiquetéeparunterminala
ajouterl'actiondécalerJàl'entréetable[I,a]• p ourchaquetransitionIX −→JétiquetéeparunevariableX,
enregistrerJàl'entréetable[I,X]
Pourchaqueétatd'acceptationIdel'automate:• SiIcontientl'itemcompletinit→S•
ajouterl'actionaccepteràl'entréetable[I,$]etl'action
rejeteràl'entréetable[I,$]p ourtoutterminala• PourtoutautreitemcompletX→α•deI,
ajouterl'actionréduireX→αauxentréestable[I,a]p our
toutaterminaloumarqueurde ndemot17 Constructiondelatabled'analyseLR(0) Z→E eofE→E+T|T T→idinit→•Z Z→•EeofE→•E+T E→•TT→•id 0init→Z• 1Z→E•eof E→E•+T2 E→T•3 T→id•4 E→E+•TT→•id 5Z→Eeof• 6E→E+T• 7Z ET ideof +T id
$eof+idETF0d4231 1accepterrejeterrejeterrejeter2d6d5 3rE→TrE→TrE→TrE→T
4rT→idrT→idrT→idrT→id5d47 6rZ→EeofrZ→EeofrZ→EeofrZ→Eeof
7rE→E+TrE→E+TrE→E+TrE→E+T18 Latabled'analyseLR(0) init→EE→E+T|T T→T∗F|FF→id 01 23 57 68 4E Tid F+ ∗Fid TF id∗ $+∗idETF0d4123 1accepterrejeter d5
rejeterrejeter
2rE→TrE→TrE→T d6rE→T 3rT→FrT→FrT→FrT→F
4rF→idrF→idrF→idrF→id5d473 6d48
7rE→E+TrE→E+TrE→E+T d6rE→E+T 8rT→T∗FrT→T∗FrT→T∗FrT→T∗F19 GrammaireLR(0)
Dé nition
UnegrammaireestLR(0)s'ilexisteauplusuneactionparentrée
danslatableLR(0).
UnegrammaireneserapasLR(0)sil'ona:• soituncon itdécaler/réduire
unétatdel'AFDcaractéristiquecontientconjointement
unitemnoncompletX→α•aβoùaestunterminal
etunitemcompletY→γ•• soituncon itréduire/réduire
unétatdel'AFDcaractéristiquecontientdeuxitemscomplets
X→α•etY→β•
pasdecon itdécaler/décalerp ossible,l'automateestdéterministe20 GrammaireLR(0)
Lagrammaire Z→E eofE→E+T|T T→id
estLR(0).
Lesétatsdesonautomate
caractéristiquen'induisent
pasdecon it.init→•Z Z→•EeofE→•E+T E→•TT→•id 0init→Z• 1Z→E•eof E→E•+T2 E→T•3 T→id•4 E→E+•TT→•id 5Z→Eeof• 6E→E+T• 7Z ET ideof +T id
$eof+idETF0d4231 1accepterrejeterrejeterrejeter2d6d5 3rE→TrE→TrE→TrE→T
4rT→idrT→idrT→idrT→id5d47 6rZ→EeofrZ→EeofrZ→EeofrZ→Eeof
7rE→E+TrE→E+TrE→E+TrE→E+T
L'analyseestalorsdéterministecaruneactionauplusestp ossibleà
chaqueétap e.21 GrammaireLR(0)
Lagrammaire E→E+T|TT→T∗F|F F→id
n'estpasLR(0)
Troisétatsengendrentdescon itsdutyp edécaler/réduire.init→E• E→E•+TE→T• T→T•∗FE→E+T• T→T•∗F
$+∗idETF0d4123 1accepterrejeter d5
rejeterrejeter
2rE→TrE→TrE→T d6rE→T 3rT→FrT→FrT→FrT→F
4rF→idrF→idrF→idrF→id5d473 6d48
7rE→E+TrE→E+TrE→E+T d6rE→E+T 8rT→T∗FrT→T∗FrT→T∗FrT→T∗F22 AnalyseurLR(0)
Pourexaminerunmot,l'analyseurLR(0)utiliselatabled'analyse
LR(0)etunepile.
Initialementlapilecontientl'étatinitial0.
Lemotcomplétédumarqueurde n$estludegaucheàdroite.
Àchaqueétap eonexaminelesymb olecourantcdumotanalyséet
l'étatqausommetdelapile• Sitable[q,c] =décalerralors
empilercpuisr,etavancerdanslalecturedumotanalysé• Sitable[q,c] =réduireX→αalors
dépiler2|α|symb oles,étantdonnérlenouvelétatausommet
delapileempilerXpuisδ(r,X),eta cherX→α• Sitable[q,c] =accepteralorsretournerSUCCéS• SinonretournerÉCHEC23 AnalyseurLR(0)
$eof+idETZ0d4231 1accepterrejeterrejeterrejeter2d6d5 3rE→TrE→TrE→TrE→T
4rT→idrT→idrT→idrT→id5d47 6rZ→EeofrZ→EeofrZ→EeofrZ→Eeof
7rE→E+TrE→E+TrE→E+TrE→E+T
MotanalyséPileAction
id+ideof$0decaler4
id+ideof$0id4reduireT→idδ(0,T) =3
id+ideof$0T3reduireE→Tδ(0,E) =2
id+ideof$
0E2decaler5
id+ideof$0E2+5decaler4
id+ideof$
0E2+5id4reduireT→idδ(5,T) =7
id+ideof$
0E2+5T7reduireE→E+Tδ(0,T) =2
id+ideof$0E2decaler6
id+ideof$0E2eof6reduireZ→Eeofδ(0,Z) =1
id+ideof$
0Z1accepter24 GrammaireSLR
Onparled'analyseSLRlorsquelesensemblesSuivantsontprisen
comptep ourdéterminersiuneactionréduireestp ossibleounon.
UnegrammaireestalorsditeSLRlorsquetouslescon itsp euvent
êtretranchésparl'examendesensemblesSuivant. E→E+T|TT→T∗F|F F→id
n'estpasLR(0)
cartroisétatsengendrentdescon itsdutyp edécaler/réduire.init→E• E→E•+TE→T• T→T•∗FE→E+T• T→T•∗F
Enfait,cescon itsp euventêtretranchés
parl'examendesensemblesSuivant.Suivant init$E$+ T$+∗F $+∗
L'actionréduireparunerègleX→αn'estenvisagéequesile
pro chainsymb oled'entréeestdansSuivant(X).25 Constructiondelatabled'analyseSLR
Latableaenlignelesétatsdel'automateetencolonnele
marqueur$,lesterminauxetvariablesdelagrammaire.
PourchaqueétatIdel'automate:• p ourchaquetransitionIa −→Jétiquetéeparunterminala
ajouterl'actiondécalerJàl'entréetable[I,a]• p ourchaquetransitionIX −→JétiquetéeparunevariableX,
enregistrerJàl'entréetable[I,X]
Pourchaqueétatd'acceptationIdel'automate:• SiIcontientl'itemcompletinit→S•
ajouterl'actionaccepteràl'entréetable[I,$]• PourtoutautreitemcompletX→α•deI,
ajouterl'actionréduireX→αauxentréestable[I,a]
p ourtoutterminaladansSuivant(X)26 Latabled'analyseSLR0 12 35 76 84 ET idF +∗ FidT Fid ∗Suivant init$E$+ T$+∗F$+∗ $+∗idETF0d4123 1accepterd5
2rE→TrE→Td6
3rT→FrT→FrT→F
4rF→idrF→idrF→id5d473 6d48
7rE→E+TrE→E+Td6
8rT→T∗FrT→T∗FrT→T∗F27 AnalyseurSLR
L'analyseurSLRfonctionnecommel'analyseurLR(0).
Pourexaminerunmot,l'analyseurSLRutiliselatabled'analyse
SLRetunepile.
Initialementlapilecontientl'étatinitial0.
Lemotcomplétédumarqueur$estludegaucheàdroite.
Àchaqueétap eonexaminelesymb olecourantcdumotanalyséet
l'étatqausommetdelapile• Sitable[q,c] =décalerralors
empilercpuisr,etavancerdanslalecturedumotanalysé• Sitable[q,c] =réduireX→αalors
dépiler2|α|symb oles,étantdonnérlenouvelétatausommet
delapileempilerXpuisδ(r,X),eta cherX→α• Sitable[q,c] =accepteralorsretournerSUCCéS• SinonretournerÉCHEC28 AnalyseurSLR
$+∗idETF0d4123 1accd52r2r2d6 3r4r4r44r5r5r5 5d4736d48 7r1r1d68r3r3r4 1E→E+T2E→T 3T→T∗F4T→F 5F→id
MotanalyséPileAction
id+id∗id$0decaler4
id+id∗id$0id4reduireF→idδ(0,F) =3
id+id∗id$0F3reduireT→Fδ(0,T) =2
id+id∗id$
0T2reduireE→Tδ(0,E) =1
id+id∗id$0E1decaler5
id+id∗id$0E1+5decaler4
id+id∗id$0E1+5id4reduireF→idδ(5,F) =329 AnalyseurSLR. .. .. .. .. id+id∗id$
0E1+5id4reduireF→idδ(5,F) =3
id+id∗id$
0E1+5F3reduireT→Fδ(5,T) =7
id+id∗id$0E1+5T7decaler6
id+id∗id$0E1+5T7∗6decaler4
id+id∗id$0E1+5T7∗6id4reduireF→idδ(6,F) =8
id+id∗id$
0E1+5T7∗6F8reduireT→T∗Fδ(5,T) =7
id+id∗id$
0E1+5T7reduireE→E+Tδ(0,E) =1
id+id∗id$0E1SUCCES
$+∗idETF0d4123 1accd52r2r2d6 3r4r4r44r5r5r5 5d4736d48 7r1r1d68r3r3r4 1E→E+T2E→T 3T→T∗F4T→F 5F→id30 AnalyseLR(1)
Unemétho dequidé nitplus nementqu'aveclesensembles
Suivant,leslettresp ouvantsuivreunevariablep endantla
construction.
Onredé nitl'AFNcaractéristiquep ourl'analyseLR(1)
LesétatssontmaintenantdesitemsLR(1)delaforme
[A→α•β,a]oùA→αβunerègledelagrammaire
etaunterminal.
cequiadéjàétéanalysé•cequ'onattend,aterminalquip eutsuivreA
L'étatinitialestceluiquicontient[init→S•,$]
Lesétatsd'acceptationsontceuxavecdesitems[Y→δ•,c]
Lestransitionssontdé niesainsi
[X→α•aβ,b]a −→[X→αa•β,b]
[X→α•Yβ,b]Y −→[X→αY•β,b]
[X→α•Yβ,b]ε −→[Y→•δ,c]
p ourtoutepro ductionY→δettoutcdansPremier(βb)31 AnalyseLR(1)
Ondéterminiseensuitel'AFN.
Laconstructiondelatabled'analyseLR(1)estsimilaireàcellede
latableSLRsaufp ourlesréductions.
Onajoutel'actionréduireX→αàl'entréetable[I,a]
uniquementsiIcontientl'item[X→α•,a].
LagrammaireestLR(1)sisatableestsanscon it.L'analyseest
alorsdéterministe.
L'analyseLR(1)estpluspuissantequelesanalysesSLRetLL(1).
L'inconvénientestqu'onseretrouveavecuntrèsgrandnombre
d'états.;Compromis:analyseLALR...32 AnalyseLR(1)
Lagrammaire S→X|cbX→aXb|Y Y→c
n'estpasSLR.
L'automatecaractéristique
desitemsLR(0)donnépar
Grammophoneprésenteun
con itdécaler/réduiredans
l'état3.
Cecon itnep eutêtretran-
chéavecuneanalyseSLRcar
bappartientàSuivant(Y).···b··· ···3 decaler6
reduireY→c33 AnalyseLR(1)
Lagrammaire S→X|cbX→aXb|Y Y→c
estLR(1).
L'automatecaractéristiquedesitemsLR(1)neprésentepasdecon it.34 AnalyseLR(1)
Latabled'analyseLR(1)construiteavecGrammophoneaauplus
uneactionparentrée.35 AnalyseLRetambiguïté
LagrammaireE→E+E|E∗E|nbestambiguë.
Cen'estdoncpasunegrammaireLR.
Cep endant,onp eutsupprimerlescon itsdécaler/réduireenforçant
l'applicationdesrèglesdeprioritéetd'asso ciativitédesop érateurs.
Pouruncon it
décalerB→Z•op1T
réduireA→Xop2Y•• siop1estprioritairesurop2
onchoisitl'actiondécalerB→Z•op1T• siop2estprioritairesurop1
onchoisitl'actionréduireA→Xop2Y•• siop1etop2ontmêmepriorité• privilégierl'asso ciativitégauche
;choisirl'actionréduireA→Xop2Y•• privilégierl'asso ciativitédroite
;choisirl'actiondécalerB→Z•op1T36 L'automatecaractéristiqueinit→•E E→•E+EE→•E∗E E→•nb0 init→E•E→E•+E E→E•∗E1 E→E+•EE→•E+E E→•E∗EE→•nb 2E→E+E• E→E•+EE→E•∗E 3E→E∗•E E→•E+EE→•E∗E E→•nb4 E→E∗E•E→E•+E E→E•∗E5 E→nb•6 E+ E+ ∗∗ E∗ +id idid
L'état1induitdeuxcon itsdécaler/réduirequiserésolventen
insp ectantlatabledesSuivant.
L'état3induitdeuxcon itsdécaler/réduiresur+et∗.
L'état5induitdeuxcon itsdécaler/réduiresur+et∗.37 Supprimerlescon its$+∗nbE 0d61
1accepterd2d42d63 3rE→E+ErE→E+E d2rE→E+E d44d65 5rE→E∗ErE→E∗E d2rE→E∗E d4
6rE→nbrE→nbrE→nb
Leverlescon itsetrendrel'analysedéterministeenappliquantles
règlesusuellesdeprioritéetd'asso ciativité:• prioritédelamultiplicationsurl'addition• asso ciativitégauchedel'addition• asso ciativitégauchedelamultiplication
38