Cours langages et compilation analyse descendante prédi...

Théorie des langages : Cours langages et compilation analyse descendante prédictiv
Télécharger PDF
LangagesetCompilation
Analysedescendanteprédictive
Intro duction
GrammairesLL(1)
Unefamilledegrammairesanalysablesdefaçonecace.
Caractéristiquesdel'analyseLL(1)• analysedescendante
Constructiondel'arbrede
dérivationselonl'ordrepréxé:
onpartdelaracine(l'axiome)et
ondescendverslesfeuilles(les
terminaux)endéveloppantlen÷ud
interne(unevariable)leplusàgauche. •
analyseprédictive
Pourdévelopp erlen÷ud,onchoisit
larègleàappliquerenprévisualisant
lesymb olecourantdumotanalysé.xc xS X? 2
Intro duction
ExempleS→+SS|∗SS|a
LeschaînesdérivéesdeScommencenttoutesparunterminal
distinct
;Àpartirduterminalcourantdumotanalysé,onsait
déterminerlab onnerègle.+∗a SS→+SSS→∗SSS→a
Analysedumot∗a+aaS S∗ SSS ∗S aS S∗ Sa S+ SSS ∗S aS +S aS S∗ Sa S+ Sa Sa ∗a +a a3 Intro duction
ExempleS→aSbS|ε
Lechoixdevientplusdélicatlorsquelagrammairecomprenddes
ε-pro ductions.Quelcritèredoit-onprendreencomptep ourchoisir
entrelarègleS→aSbSetlarègleS→ε?
Onestamenéàconsidérerlesterminauxquip euventsuivreS.
Conventionpratique,onintro duitunterminalparticulier$p our
marquerlandumotàanalyser.
$etb(maispasa)p euventseretrouveràdroitedeS.
;Onsaitalorsdéterminerlarègleàappliquerauvuduterminal
courant.$ab SS→εS→aSbSS→ε4 Intro duction
ExempleS→aSbS|ε
satabled'analyse$ab SS→εS→aSbSS→ε
Analysedumotab$S Sa Sb SS aS εb SS aS εb Sε ab $5 Intro duction
Conditionp ouruneanalyseLL(1)àchaqueétap e,
p ourlavariableXàdévelopp eretleterminalcourantcenentrée,
lechoixdeladérivationàappliquerdoitêtredéterministe.
Llecturedel'entréedelagaucheversladroite(Lefttorightscanning)
Lconstructiond'unedérivationgauche(Leftderivation)
1symb oledel'entréep ourprédirelab onnerègle
L'analyseLL(1)sebasesurunetablequiindique,p ourlavariable
Xetleterminalc,larèglecorrecteàappliquer.
Pourconstruirecettetabled'analyse,ondétermineaupréalable:
1.lesvariableseaçables
2.lesensemblesPremier
3.lesensemblesSuivant6 Lesvariableseaçables
Unechaîneα∈N∗ estditeeaçablesilemotvidesedérivedeα:α ∗→ε Calculdesvariableseaçables
Onconstruitparrécurrencesuri,l'ensembleEi desvariablesA.E 0
={A∈N:A→ε∈P}E i+1
={A∈N:A→α∈Petα∈E∗ i} ArrêtlorsqueEi+1 =Ei (aub outd'auplus|N|étap es)Exemple    S→XY X→aXb|εY→cZ|Ze Z→dcZ|εE 0
={X,Z}=E1 7
LesensemblesPremier
Soitαunechaînede( Σ∪N) ∗
.Premier(α)estl'ensembledes
terminauxquidébutentleschaînesdérivéesdeα:{ a∈Σ :α∗ →aβoùβ∈(Σ∪N)∗ }
CalculdesensemblesPremier
Pourunterminala:
Premier(aβ) ={a}
PourunevariableX:
Premier(X) =⋃ X→β∈P
Premier(β)
Premier(Xβ)={ Premier(X)siXn'estpaseaçable
Premier(X)∪Premier(β)sinon8 LesensemblesPremierExemple    S→XY X→aXb|εY→cZ|Ze Z→dcZ|ε
CalculdesensemblesPremierp ourlesvariables:
Premier(S)=Premier(XY)S→XY
=Premier(X)∪Premier(Y)Xeaçable
Premier(X)=Premier(aXb)X→aXb|ε={a} Premier(Y)=Premier(cZ)∪Premier(Ze)Y→cZ|Ze
={c}∪Premier(Z)∪{e}Zeaçable
Premier(Z)=Premier(dcZ)Z→dcZ|ε={d} 9
LesensemblesSuivant
SoitXunevariable.Suivant(X)estl'ensembledesterminauxqui
p euventapparaîtreaprèsXdansunedérivation:{ a∈Σ :S∗ →αXaβoùα,β∈(Σ∪N)∗ }i.e. Suivant(X) =⋃ Y→αXβ∈P
Premier(βSuivant(Y))
CalculdesensemblesSuivant
Mettre$dansSuivant(S)(oùSestl'axiome)
PourchaquevariableX,examinerchaquepro ductionY→αXβ
oùXestàdroite:• Siβ6=ε,ajouterlesélémentsdePremier(β)
àSuivant(X)• Siβ∗ →ε,ajouterlesélémentsdeSuivant(Y)
àSuivant(X)10 LesensemblesSuivantExemple    S→XY X→aXb|εY→cZ|Ze Z→dcZ|ε
CalculdesensemblesSuivant:
Suivant(S)contient$
Suivant(X)
S→XY;Premier(YSuivant(S))⊆Suivant(X)
;Premier(Y)⊆Suivant(X)(Ynoneaçable)
X→aXb;b∈Suivant(X)
Suivant(Y)
S→XY;Suivant(S)⊆Suivant(Y)
Suivant(Z)
Y→cZ;Suivant(Y)⊆Suivant(Z)
Y→Ze;e∈Suivant(Z)
Z→dcZ;Suivant(Z)⊆Suivant(Z)11 LesvariablesEaçablesetlesensemblesPremieretSuivantExemple    S→XY X→aXb|εY→cZ|Ze Z→dcZ|ε
Bilandescalculs:
EaçablePremierSuivant
Snona cd e$X ouiab cd eY noncd e$Z ouid$e12 Constructiondelatabled'analyse
Tableàdeuxdimensionsindexéeparlesvariablesetlesterminaux
Pourtoutepro ductionX→α:• AjouterX→αàl'entréeT[X,a]p ourtoutterminaladans
Premier(α)• Siαesteaçable,ajouterX→αdanslacaseT[X,a]p our
toutterminaladansSuivant(X)    S→XYX→aXb|ε Y→cZ|ZeZ→dcZ|ε EaçablePremierSuivant
Snonacde$
Xouiabcde
Ynoncde$Zouid$e $abcde
SS→XYS→XYS→XYS→XY
XX→aXbX→εX→εX→εX→ε
YY→cZY→ZeY→Ze
ZZ→εZ→dcZZ→ε13 GrammaireLL(1)
Dénition
UnegrammaireestLL(1)s'ilexisteauplusunepro ductionpar
entréedanslatable.
Prop osition
UnegrammaireestLL(1)sip ourtoutepairedepro ductions
A→αetA→β,ona:Premier (
αSuivant(A)) ∩Premier( βSuivant(A)) =∅
AinsiunegrammaireneserapasLL(1)s'ilona:• soitunconitPremier/Premier,i.e.,deuxrègles
A→α|βtellesque:Premier(α)∩Premier(β)6=∅• soitunconitPremier/Suivant,i.e.,deuxrèglesA→α|βavecβ ∗
→εtellesque:Premier(α)∩Suivant(A)6=∅14 GrammaireLL(1)Exemple    S→XY X→aXb|εY→cZ|Ze Z→dcZ|ε
estunegrammaireLL(1)
Satabled'analysecomprendauplusunealternativeparcase.
;Lechoixdelarègleàappliquersefaitdefaçondéterministe.$abcde SS→XYS→XYS→XYS→XY
XX→aXbX→εX→εX→εX→ε
YY→cZY→ZeY→Ze
ZZ→εZ→dcZZ→ε15 GrammaireLL(1)Exemple    S→XY|Z X→aXb|εY→bX Z→bZc|c
n'estpasunegrammaireLL(1)
IlexisteunconitPremier/Premierp ourlesrèglesS→XYetS→Z Premier(XY) =Premier(X)∪Premier(Y) ={a,b}Xeaçable
Premier(Z) ={b,c}
;Premier(XY)∩Premier(Z) ={b}6=∅$b··· ···S S→XYS→Z 16
GrammaireLL(1)Exemple {S→aXb X→bX|ε
n'estpasunegrammaireLL(1)
IlexisteunconitPremier/Suivantp ourlesrèglesX→bXetX→ε Premier(bX) ={b}
Suivant(X) ={b}
;Premier(X)∩Suivant(X) ={b}6=∅$b··· ···X X→bXX→ε 17
AnalyseurLL(1)
Pourexaminerunmot,l'analyseurLL(1)utiliselatabled'analyse
précédemmentconstruiteetunepile.
Initialement,lapilecontientlemarqueurdendemot$et
l'axiome.
Latabled'analyse
delagrammaireLL(1)Lapile Lemotanalyséludegaucheàdroitec $$ SS L'arbred'analyse
àconstruire
AnalyseurLL(1) 18
AnalyseurLL(1)
Àchaqueétap e,onexamineleterminalcourantcdumotanalysé
etlesommetdelapile(premiersymb olenontraitédel'arbreen
construction).• Soitlesommetdelapileestunterminala:• sia6=c,
l'analyses'arrêteetretourneÉCHEC• sia=c= $,
l'analyses'arrêteetretourneSUCCéS• sia=c6= $,
aestdépiléetonavancedanslalecturedumotanalysé• SoitlesommetdelapileestunevariableX:• sil'entréeT[X,c]estvide,
l'analyses'arrêteetretourneÉCHEC• sil'entréeT[X,c]contientunerègleX→α,
Xestdépiléetαestempiléenpartantdeladroite
(parexemple,siX→YzT,Testempilé,puisz,puisY).19 AnalyseurLL(1)$abcde SS→XYS→XYS→XYS→XY
XX→aXbX→εX→εX→εX→ε
YY→cZY→ZeY→Ze
ZZ→εZ→dcZZ→ε
MotanalyséPile
abdce$S$S→XYS XY
abdce$XY$X→aXbSX aX bY abdce$aX bY$assortiment20 MotanalyséPile
abdce$XbY$X→εSX aX εb Y
abdce$bY$assortiment
abdce$Y$Y→ZeSX aX εb YZ e
abdce$Ze$Z→dcZSX aX εb YZ dc Ze abdce$dc Z e$assortiment21 MotanalyséPile
abdce$cZ e$assortiment
abdce$Ze$Z→εSX aX εb YZ dc Zε e
abdce$e$assortimentabdce$ $SUCCES
Lecoûtdel'analysedumotestlinéaireenlatailledel'arbre.22 AnalyseurLL(1)$abcde SS→XYS→XYS→XYS→XY
XX→aXbX→εX→εX→εX→ε
YY→cZY→ZeY→Ze
ZZ→εZ→dcZZ→ε
MotanalyséPile
abbab$S$S→XY
abbab$XY$X→aXb
abbab$aX bY$assortiment
abbab$XbY$X→ε
abbab$bY$assortiment
abbab$Y$ECHEC23 RendreunegrammaireLL(1)
Prop osition
Unegrammairenep eutpasêtreLL(1)sielleest:
soitambiguë,
soitrécursivegauche,
soitn'estpasfactoriséeàgauche.
Onp eutmo dierlagrammairep ourtenterdelarendreLL(1)mais
lerésultatn'estpasgaranti.
Prop osition
Ilexistedesgrammairesnonambiguës,nonrécursivesgaucheet
factoriséesàgauchequinesontpasLL(1).24 RendreunegrammaireLL(1)
ParéliminationdelarécursivitégaucheExemple  E→E+T|T T→T∗F|F
F→(E)|nb
n'estpasLL(1)carrécursivegauche
IlexisteunconitPremier/Premierp ourlesrèglesE→E+Tet
E→TàcausedelarécursivitégauchedeE
etunconitPremier/Premierp ourlesrèglesT→T∗FetT→F
àcausedelarécursivitégauchedeT$(nb)+∗ EE→E+T E→TE→E+T E→TT T→T∗FT→F T→T∗FT→F FF→(E)F→nb25 RendreunegrammaireLL(1)
Paréliminationdelarécursivitégauche
SupprimerlarécursivitégaucherendcettegrammaireLL(1)   E→E+T|TT→T∗F|F F→(E)|nb        E→TYY→+TY|ε T→FZ
Z→ ∗FZ|ε
F→(E)|nb26 RendreunegrammaireLL(1)
Paréliminationdelarécursivitégauche        E→TYY→+TY|ε T→FZ
Z→ ∗FZ|ε
F→(E)|nb
EaçablePremierSuivant
Enon(nb$ )
Youi+$ )T non(nb$ ) +
Zoui∗$ ) +
Fnon(nb∗$ ) +$(nb)+∗ EE→TYE→TY
YY→εY→εY→+TY
TT→FZT→FZ
ZZ→εZ→εZ→εZ→∗FZ
FF→(E)F→nb27 RendreunegrammaireLL(1)
ParsubstitutionetfactorisationExemple    E→TR T→id|(E)|AR→+E|ε A→id[E]
n'estpasLL(1)
IlexisteunconitPremier/Premierp ourlesrèglesT→idetT→A $id······ TT→id T→A28 RendreunegrammaireLL(1)
Parsubstitutionetfactorisation
Oneectueunesubstitutionavantdefactoriseràgauche.E→TR T→id|(E)|AR→+E|ε A→id[E]• SubstitutionE→TR T→id|(E)|id[E]R→+E|ε •
FactorisationàgaucheE→TR T→id X|(E)X→[E]|ε R→+E|ε29 RendreunegrammaireLL(1)
Parsubstitutionetfactorisation
OnobtientunegrammaireLL(1)    E→TR
T→id X|(E)X→[E]|ε R→+E|ε
EaçablePremierSuivant
Enonid($ ) ]T nonid($ ) ] +X oui[$ ) ] +
Roui+$ ) ]
$+id()[]
EE→TRE→TR
TT→id XT→(E)
XX→εX→εX→εX→[E]X→ε
RR→εR→+ER→εR→ε30 RendreunegrammaireLL(1)
ourendrel'analysedéterministe
Lagrammairedesinstructionsdebranchementsconditionnels{ I→si E alors I sinon I|si E alors I|aE→b mêmefactorisée  I→si E alors I J|a
J→sinon I|εE→b n'estpasLL(1)carambiguë.I siE balors Isi Eb alorsI aJ εJ sinonI aI siE balors Isi Eb alorsI aJ sinonI aJ εlemotsi balors sib alorsa sinon
aadmetdeuxarbresd'analyse31 RendreunegrammaireLL(1)
ourendrel'analysedéterministe
L'ambiguïtéengendreunconitPremier/Suivantp ourlesrègles
J→sinonIetJ→ε
$sinon······ JJ→ε
J→sinonIJ→ε ···
Aveclaconventionusuelled'asso cier
lesinonaveclesilepluspro che,on
p eutrendrel'analyseurdéterministe
etleforceràpro duirel'arbrevoulu
enprivilégiantlarègleJ→sinon I
audétrimentdelarègleJ→ε.I siE balors Isi Eb alorsI aJ sinonI aJ ε32 AnalyseLL(k)
Généralisationdel'analyseLL(1)avecprévisualisationnonpasjuste
d'unsymb olemaisd'unnombrexékdesymb oles.Unegrammaire
estLL(k)sil'analyseurp eutchoisirdefaçondéterministelarègleà
appliquerenexaminantlesksymb olescourantsdel'entrée.Onnote: •w| k= {
wsiwestdelongueurauplusk
lepréxedelongueurkdewsinon• Premierk (α)={w|k :α∗ →w}• Suivantk (A)={w:∃β,γt.q.S→βAγetw∈Premierk (γ)}
Prop osition
UnegrammaireestLL(k)sip ourtoutepairedepro ductions
A→αetA→β,ona:Premier k( αSuivantk (A)) ∩Premierk (
βSuivantk (A)) =∅33 AnalyseLL(k)Exemple {S→abX|ε X→Saa|b
n'estpasunegrammaireLL(1)
EaçablePremierSuivantSouia$a X
nona b$a
ConitPremier/Suivant:Premier(abX)∩Suivant(S)6=∅$ab SS→εS→abX S→ε
XX→SaaX→b34 AnalyseLL(k){ S→abX|εX→Saa|b estunegrammaireLL(2)
EaçablePremier2 Suivant2 Souiab$aa
Xnonaa ab b$aa
Enprévisualisantdeuxlettres,iln'yaplusdeconit:Premier 2
(abX)∩Suivant2 (S) =∅$aaabb SS→εS→εS→abX
XX→SaaX→SaaX→b35 AnalyseLL(k)$aaabb SS→εS→εS→abX
XX→SaaX→SaaX→b
MotanalyséPile
abaa$S$S→abXabaa$ abX$assortimentabaa$ bX$assortiment
abaa$X$X→Saa
abaa$Saa$S→ε
abaa$aa$assortimentabaa$ a$assortiment
abaa$$SUCCES36 AnalyseLL(k)Fait Ilexistedesgrammairesniambiguës,nirécursivesgauchequine
sontLL(k)p ouraucunk.Exemple  S→A|B A→aAb|c
B→aBbb|da k
∈Premierk (A)∩Premierk (B)p ourtoutk
;ConitPremier/Premierp ourtoutkExemple {
S→aSb|bSa|εPremier k
(aSb)∩Suivantk (S) ={a}{a,b}k−2 {b}p ourtoutk
;ConitPremier/Suivantp ourtoutk37 AnalysesyntaxiqueavecANTLR
ANTLR4meten÷uvreuneanalysedescendanteprédictivequia
lescaractéristiquessuivantes• factorisationàgauchedelagrammaireautomatique• suppressionautomatiquedesrécursivitésgauchesimmédiates
(maispasdesrécursivitésgauchesindirectes,e.g.
A→Bα,B→Aβ)• résolutiondecertainesambiguïtés• enjouantsurl'ordredespro ductionsp ourlevercellesliéesaux
prioritésdesop érateurs• p ourlesambiguïtésduesàl'asso ciativité,pardéfaut
l'asso ciations'eectueàgaucheoudefaçonexpliciteàdroite,
e.g.l'exp onentielle,expr:expr′ ∧′ 〈assoc=right〉expr• basésurunestratégieLL(k)• enrichid'unmécanismeadditionnelquip ermetdetraiterplus
quelesgrammairesLL(k)maisquiinduitalorsunsurcoûtentemps 38
Cours langages et compilation analyse descendante prédi...

Publicité 1

Publicité 2

نموذج الاتصال
