cha自上而下語(yǔ)法分析實(shí)用

會(huì)計(jì)學(xué)1cha自上而下語(yǔ)法分析實(shí)用2023/1/172內(nèi)容回顧(續(xù))最左(最右)推導(dǎo)在推導(dǎo)的任何一步α==*>β(其中α和β是句型)，都對(duì)α中的最左(最右)非終結(jié)符進(jìn)行替換句型分析(句子分析)識(shí)別一個(gè)符號(hào)串是否為某文法的句型(句子)的過(guò)程也就是某文法的某個(gè)推導(dǎo)的構(gòu)造過(guò)程設(shè)文法G為:E→E+T|TT→T*F|FF→(E)|i請(qǐng)問(wèn)符號(hào)串i+i*i是否為該文法的句子?

EE+TT*FFFTiii自上而下自下而上章節(jié)目錄第1頁(yè)/共91頁(yè)2023/1/1734.1語(yǔ)法分析的功能p67任務(wù)分析并判定輸入的單詞符號(hào)串是否符合該語(yǔ)言的語(yǔ)法規(guī)則(上下文無(wú)關(guān)文法)實(shí)質(zhì)就是按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子(合法程序，語(yǔ)句，表達(dá)式等)詞法掃描器語(yǔ)法分析器語(yǔ)義處理單詞符號(hào)語(yǔ)法樹(shù)第2頁(yè)/共91頁(yè)2023/1/174語(yǔ)法分析器的設(shè)計(jì)思想和輸出設(shè)計(jì)思想判斷是否能從文法的開(kāi)始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串或者,判斷能否建立一棵與輸入串匹配的語(yǔ)法分析樹(shù)輸入單詞符號(hào)串輸出語(yǔ)法分析樹(shù)格式化的程序合法的表達(dá)式、語(yǔ)句、函數(shù)出錯(cuò)處理要求盡快發(fā)現(xiàn)錯(cuò)誤，準(zhǔn)確定位可能時(shí)進(jìn)行恢復(fù)處理，繼續(xù)語(yǔ)法分析第3頁(yè)/共91頁(yè)2023/1/175常用語(yǔ)法分析方法p66語(yǔ)法分析算法可分為兩大類(lèi):自上而下分析法從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式向下推導(dǎo)，尋找與輸入符號(hào)串匹配的推導(dǎo)自下而上分析法從輸入串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)兩種方法反映了兩種不同的語(yǔ)法樹(shù)的構(gòu)造過(guò)程自上而下——從樹(shù)根推導(dǎo)到樹(shù)葉自下而上——從樹(shù)葉歸約到樹(shù)根第4頁(yè)/共91頁(yè)2023/1/176上下文無(wú)關(guān)文法（２型文法）編程語(yǔ)言的語(yǔ)法大都可用2型文法來(lái)描述沒(méi)有一種方法能夠有效地分析所有上下文無(wú)關(guān)文法存在無(wú)法處理的2型文法每種方法能夠處理一部分上下文無(wú)關(guān)文法每種方法都有適用范圍章節(jié)目錄第5頁(yè)/共91頁(yè)2023/1/1774.2自上而下分析面臨的問(wèn)題p67基本方法對(duì)任何輸入串,試圖從文法的開(kāi)始符號(hào)出發(fā)，自上而下地為輸入串建立一棵語(yǔ)法樹(shù)，或者說(shuō)為輸入串尋找一個(gè)最左推導(dǎo)。過(guò)程本質(zhì)是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程如何選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)?第6頁(yè)/共91頁(yè)2023/1/178自上而下分析舉例p67例文法G[S]S→xAyA→ab|a

判斷輸入串w=xay是否為該文法的句子？SxAy試探ab失敗回溯a試探成功分析結(jié)束SxAy==>xay==>問(wèn)題產(chǎn)生回溯的原因是什么?第7頁(yè)/共91頁(yè)2023/1/179自上而下分析面臨的問(wèn)題p68公共左因子——產(chǎn)生回溯例文法G:S→xAyA→ab|a無(wú)法確定非終結(jié)符A面臨輸入符號(hào)a時(shí)選用哪個(gè)關(guān)于A的候選式左遞歸——無(wú)限循環(huán)例文法G:S→Sa|abaw=abaaaSSaSa…無(wú)法確定何時(shí)用S→aba產(chǎn)生式進(jìn)行推導(dǎo)某些文法導(dǎo)致自上而下分析具有不確定性章節(jié)目錄第8頁(yè)/共91頁(yè)2023/1/17104.3LL(1)分析法p68為了構(gòu)造不帶回溯的自上而下分析算法消除文法的左遞歸消除回溯、提取左因子LL(1)分析條件LL(1)文法章節(jié)目錄第9頁(yè)/共91頁(yè)2023/1/17114.3.1左遞歸的消除p69關(guān)于非終結(jié)符P的規(guī)則直接左遞歸定義：若P→Pα｜βα、β∈Ｖ*例如E→E+T｜T（含有E的左遞歸）

T→T*F｜F（含有T的左遞歸）

F→(E)｜i

第10頁(yè)/共91頁(yè)2023/1/1712間接左遞歸的定義p68間接左遞歸定義：若P==+>Pαα∈Ｖ*例如間接左遞歸

S→AaA→Sb|b

S==>Aa==>Sba即S==+>Sb用S的產(chǎn)生式右部替換A右部的S得：

A→Aab|b

變成A的產(chǎn)生式含有直接左遞歸第11頁(yè)/共91頁(yè)2023/1/1713消除直接左遞歸的方法p69改寫(xiě)為等價(jià)的右遞歸形如：P→Pα｜βα非ε，β不以P開(kāi)始改寫(xiě)為：P→βP’（P’為新增加的非終結(jié)符）

P'→αP'｜ε改寫(xiě)前產(chǎn)生式可產(chǎn)生短語(yǔ)

P==>Pα==>βα

改寫(xiě)后產(chǎn)生式可產(chǎn)生短語(yǔ)

P==>βP’==>βαP'==>βαε等價(jià)第12頁(yè)/共91頁(yè)2023/1/1714舉例：表達(dá)式文法直接左遞歸的消除E→E+T｜TT→T*F｜FF→(E)｜iE→TE’

E'→+TE'｜εT→F

T’T'→*FT'｜εF→(E)｜i第13頁(yè)/共91頁(yè)2023/1/1715消除多個(gè)直接左遞歸p69若有多個(gè)左遞歸的產(chǎn)生式如：P→Pα1|Pα2

|…|Pαm|β1|β2

|…|βn消除左遞歸后變?yōu)椋?/p>

P→β1P’|β2P’|…|βnP’ P’→α1P’|α2

P’|…|αmP’|ε消除左遞歸要求文法：

1.無(wú)回路（A==*>A）

2.無(wú)空產(chǎn)生式（A→ε）第14頁(yè)/共91頁(yè)2023/1/1716消除直接左遞歸課堂練習(xí)例如有文法：

K→Ka|Kb|Kc|d|eBEGIN消除左遞歸后變?yōu)椋?/p>

K→dK’|eK’

K’→aK’|bK’|cK’|ε第15頁(yè)/共91頁(yè)2023/1/1717間接左遞歸消除舉例p70

S→Qc｜c(diǎn)

Q→Rb｜b

R→Sa｜aS=>Qc=>Rbc=>Sabc

是間接左遞歸消除方法1：將非終結(jié)符排序：

RQS將R的右部代入Q，S：

Q→Sab｜ab｜bS→Qc｜c(diǎn)（不變）將Q的右部代入S：

S→Sabc｜abc｜bc｜c(diǎn)消除S的直接左遞歸：

S→abcS’｜bcS’|cS’S’→abcS’|εQ→Sab｜ab|bR→Sa｜a整理化簡(jiǎn)：刪除Q，R（無(wú)用）消除左遞歸后得：

S→abcS’｜bcS’|cS’S’→abcS’|ε第16頁(yè)/共91頁(yè)2023/1/1718間接左遞歸消除舉例（續(xù)）p70

S→Qc｜c(diǎn)

Q→Rb｜bR→Sa｜a消除方法2：將非終結(jié)符排序：

SQR將S的右部代入Q，R：

Q→Rb｜b（不變）

R→Qca｜c(diǎn)a|a將Q的右部代入R：

R→Rbca｜bca|ca|a消除R的直接左遞歸：

R→bcaR’｜c(diǎn)aR’|aR’R’→bcaR’|ε整理化簡(jiǎn)：S，Q（有用）消除左遞歸后得：

S→Qc｜c(diǎn)Q→Rb｜bR→bcaR’｜c(diǎn)aR’|aR’R’→bcaR’|ε第17頁(yè)/共91頁(yè)2023/1/1719消除左遞歸算法p701.以某種順序?qū)⑽姆ǖ姆墙K結(jié)符排列

P1，P2，…,Pn

2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的規(guī)則改寫(xiě)成

Pi→δ1γ|δ2γ|…|δkγ,其中

Pj→δ1|δ2|…|δk是關(guān)于Pj的所有規(guī)則;

消除Pi的直接左遞歸

END3.化簡(jiǎn)由2所得的文法，即去除那些從開(kāi)始符號(hào)出發(fā)永遠(yuǎn)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生式當(dāng)非終結(jié)符的排列順序不同時(shí)，變換后的文法形式可能不同，但是它們都和原文法是等價(jià)的節(jié)目錄第18頁(yè)/共91頁(yè)2023/1/17204.3.2消除回溯、提左因子p71消除回溯目的對(duì)文法的任何非終結(jié)符，當(dāng)它去匹配輸入串時(shí)，能夠根據(jù)輸入符號(hào)，準(zhǔn)確地選擇合適的候選式去匹配若需要非終結(jié)符A去匹配輸入串，A的候選式為A→α1|α2|…|αn

，A所面臨的第一個(gè)輸入符號(hào)為a時(shí)，A能準(zhǔn)確地選擇αi去執(zhí)行匹配任務(wù)，則無(wú)需回溯第19頁(yè)/共91頁(yè)2023/1/1721提取公共左因子方法p71對(duì)于所有形如

A→αβ1｜αβ2｜...｜αβn｜γ的規(guī)則其中，α為左因子，γ不以α開(kāi)頭改寫(xiě)為A→αA'｜γ其中A’為新增加的非終結(jié)符

A'→β1｜β2｜...｜βn例如

S→xAyA→ab|a提左因子后變換為

S→xAyA→aA’A’→b|ε節(jié)目錄第20頁(yè)/共91頁(yè)2023/1/17224.3.3LL(1)分析條件p71FIRST集合的定義與計(jì)算FOLLOW集合的定義與計(jì)算LL(1)文法的定義LL(1)分析節(jié)目錄第21頁(yè)/共91頁(yè)2023/1/1723FIRST(α)集合的定義p71設(shè)G=(ＶT，ＶN，S，P）α∈Ｖ*

FIRST(α)={a|α==*>a…，a∈ＶT}若α==*>ε，則ε∈FIRST(α)FIRST(α)是α的所有可能推導(dǎo)的首遇終結(jié)符號(hào)或ε，是選擇產(chǎn)生式的依據(jù)αa

……

E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜iFIRST((E))={(}（E）==0>（E）FIRST（TE’）={（，i}TE’==>FT’E’==>（E）T’E’TE’==>FT’E’==>iT’E’第22頁(yè)/共91頁(yè)2023/1/1724FIRST(α)的計(jì)算法FIRST(α)={a｜α==*>a…，a∈ＶT}若α==*>ε，則ε∈FIRST(α)計(jì)算文法符號(hào)X的FIRST（X）計(jì)算文法符號(hào)串α=X1X2…Xn的FIRST(α)第23頁(yè)/共91頁(yè)2023/1/1725FIRST(X)的計(jì)算法p78重復(fù)以下計(jì)算，直到FIRST（X）不再增大為止:1)若X∈ＶT，則FIRST(X)={X}。例FIRST（+）={+}FIRST（i）={i}2)若X∈ＶN，若有X→a…，則將a加入FIRST(X)；例E'→+TE'+∈FIRST（E’）

F→（E）|i（，i∈FIRST（F）若有X→ε，則將ε加入FIRST(X)。例E’→εε∈FIRST（E’）第24頁(yè)/共91頁(yè)2023/1/1726若有X→Y1…Yi-1Yi…Yk

，并對(duì)于某個(gè)i， 有1≤j≤i-1，ε∈FIRST（Yj），即Y1，…，Yi-1==*>ε，則將所有FIRST(Yj)-{ε}∪FIRST(Yi)-{ε}

加入FIRST(X)中；-{ε}-{ε}3)若有X→Y…，且Y∈ＶN

，則FIRST(Y)-{ε}加入FIRST(X);例F→(E)|iFIRST(F)={（，i}T→FT'FIRST(T)=FIRST(F)-{ε}={（，i}若所有Y1,…,Yk==*>ε，則將ε加入到FIRST(X)。第25頁(yè)/共91頁(yè)2023/1/1727計(jì)算X→Y1…Yi-1Yi…YkFIRST(X)集舉例若有文法G為：

X→Y1Y2Y3Y4Y5

Y1→a｜εY2→b｜εY3→c｜εY4→d｜εY5→e｜fFIRST集Y1Y2Y3Y4Y5Xa，εb，εc，εd，εe，fa,b,c,d,e,fεε因?yàn)閅5==*>ε，所以ε∈FIRST（X）ε==*>ε==*>ε因?yàn)閅5==*>ε，所以ε∈FIRST（X）第26頁(yè)/共91頁(yè)2023/1/1728計(jì)算表達(dá)式文法FIRST(X)集舉例文法G為：

E→TE’ E'→+TE'｜ε T→FT' T'→*FT'｜ε F→(E)｜i先找以終結(jié)符開(kāi)頭的產(chǎn)生式FIRST(F)={(,i}FIRST(E')={+，ε}FIRST(T')={*,ε}再找右部以非終結(jié)符開(kāi)頭的產(chǎn)生式FIRST(T)=FIRST(F)FIRST(E)=FIRST(T)={(,i}第27頁(yè)/共91頁(yè)2023/1/1729計(jì)算FIRST(X)集合課堂練習(xí)={a，c，d，q}文法G為：

S→Ap｜Bq A→a｜c(diǎn)A B→dB｜ε

BEGIN先找以終結(jié)符開(kāi)頭的產(chǎn)生式FIRST(A)={a,c}FIRST(B)={d,ε}再找右部以非終結(jié)符開(kāi)頭的產(chǎn)生式FIRST(S)=FIRST(A)-{ε}∪FIRST(B)-{ε}因?yàn)锽==>εε∈FIRST(S),因?yàn)镾==*>ε∪FIRST(q)第28頁(yè)/共91頁(yè)2023/1/1730FIRST(α)的計(jì)算法設(shè)α=X1

X2…Xi-1Xi…Xn，按以下方法構(gòu)造集合則FIRST(α)=FIRST（

X1

)；若任何1≤j≤i-1,2≤i≤n,ε∈FIRST(Xj)則Xi前所有FIRST(Xj

)-{ε}和FIRST(Xi

)加入到FIRST(α)中；若所有的1≤j≤n，ε∈FIRST(Xj)則把ε也加入FIRST(α)中；若α=ε，則FIRST(α)={ε}若ε∈FIRST(X1)即X1==>ε第29頁(yè)/共91頁(yè)2023/1/1731計(jì)算表達(dá)式文法候選式FIRST(α)集舉例候選式的FIRST集FIRST(TE’)=FIRST(T)={(,i}FIRST(+TE’)={+}FIRST(FT’)=FIRST(F)={(,i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)={i}FIRST(ε)={ε}文法G為：

E→TE’E'→+TE’|εT→FT’

T'→*FT’|εF→(E)|i非終結(jié)符的FIRST集FIRST(E)={(,i}FIRST(E')={+,ε}FIRST(T)={(,i}FIRST(T')={*,ε}FIRST(F)={(,i}第30頁(yè)/共91頁(yè)2023/1/1732計(jì)算FIRST(α)集合課堂練習(xí)文法G為：S→Ap｜Bq A→a｜c(diǎn)A B→dB｜ε非終結(jié)符的FIRST集FIRST(S)={a,c,d,q}FIRST(A)={a,c}FIRST(B)={d,ε}BEGIN候選式的FIRST集FIRST(Ap)=FIRST(A)={a,c}FIRST(Bq)=FIRST(B)-{ε}∪FIRST(q)={d,q}FIRST(a)={a}FIRST(cA)={c}FIRST(dB)=eme20swFIRST(ε)={ε}小節(jié)目錄第31頁(yè)/共91頁(yè)2023/1/1733FOLLOW(A)集合的定義p73A∈ＶN

FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，則#∈FOLLOW（A）#—輸入串的結(jié)束符也可看作是句子的括號(hào)#S#FOLLOW(A)表示了句型中可能緊跟在A后面的終結(jié)符號(hào)S…Aa…E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i

）∈FOLLOW（E）S

==>TE’==>FT’E’==>（E）T’E’

+

∈FOLLOW（T）S==>TE’==>T+TE’

#∈FOLLOW（E）S==0>E

第32頁(yè)/共91頁(yè)2023/1/1734FOLLOW(A)的計(jì)算法p79FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，則#∈FOLLOW（A）重復(fù)以下計(jì)算，直到每個(gè)FOLLOW(A)不再增大為止：1)將#

加入到FOLLOW(S)中例#∈FOLLOW(E)2)若A→αBβ,

則將FIRST(β)-{ε}加入FOLLOW(B)

例E→TE’FIRST(E’)-{ε}加入FOLLOW(T)T→FT’FIRST(T’)-{ε}加入FOLLOW(F)第33頁(yè)/共91頁(yè)2023/1/1735FOLLOW(A)的計(jì)算法（續(xù)）3)若A→αB

，或A→αBβ，且β==*>ε，即ε∈FIRST(β)，A≠B

則將FOLLOW(A)所有元素加入FOLLOW(B)

ε例E→TE’FOLLOW(E)加入FOLLOW(E’)E→T

E’E'→εFOLLOW(E)加入FOLLOW(T)T→FT’FOLLOW(T)加入FOLLOW(T’)T→F

T’FOLLOW(T)加入FOLLOW(F)T'→ε第34頁(yè)/共91頁(yè)2023/1/1736計(jì)算表達(dá)式文法的FOLLOW集舉例#∈FOLLOW（開(kāi)始符號(hào)）對(duì)每個(gè)非終結(jié)符查看其在產(chǎn)生式右邊的出現(xiàn)G：E→TE’E'→+TE’|εT→FT’T'→*FT’|εF→(E)|i#∈FOLLOW(E)相同不需處理=FIRST(E’)-{ε}FOLLOW(T)∪FOLLOW(E)={+,),#}FOLLOW(F)=FIRST(T’)-{ε}∪FOLLOW(T)={*,+,),#}FOLLOW(E)={),#}FOLLOW(E')=FOLLOW(E)={),#}FOLLOW(T')=FOLLOW(T)={+,),#}第35頁(yè)/共91頁(yè)2023/1/1737計(jì)算FOLLOW(A)集合課堂練習(xí)文法G為：S→Ap｜Bq A→a｜c(diǎn)A B→dB｜ε非終結(jié)符的FIRST集FIRST(S)={a,c,d,q}FIRST(A)={a,c}FIRST(B)={d,ε}BEGIN

非終結(jié)符FOLLOW集FOLLOW(S)={#}FOLLOW(A)=FIRST(p)-{ε}={p}FOLLOW(B)=FIRST(q)-{ε}={q}小節(jié)目錄第36頁(yè)/共91頁(yè)2023/1/1738i+i#的推導(dǎo)過(guò)程p72設(shè)有文法GE→TE’

E’→+TE’|ε

T→FT’

T’→*FT’|ε

F→(E)|iP79i∈FIRST(i)+∈FIRST(+TE’)+∈FOLLOW(T’)#∈FOLLOW(E’)#∈FOLLOW(T’)ＥＴＥ’ＦＴ’iε＋ＴＥ’ＦＴ’iεε生成語(yǔ)法分析樹(shù)第37頁(yè)/共91頁(yè)2023/1/1739推導(dǎo)過(guò)程的分析輸入輸出輸入：符號(hào)串(有序的)輸出：結(jié)構(gòu)化的符號(hào)串(樹(shù)結(jié)構(gòu))產(chǎn)生式的選擇根據(jù)當(dāng)前符號(hào)（單詞）語(yǔ)法分析樹(shù)的表示按照使用序列排列的產(chǎn)生式序列第38頁(yè)/共91頁(yè)2023/1/1740消除回溯的條件p71非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選α和β，滿足：

FIRST(α)∩FIRST(β)=φ

當(dāng)要求A

匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選去執(zhí)行任務(wù)，這個(gè)候選就是那個(gè)終結(jié)首符集含a的α第39頁(yè)/共91頁(yè)2023/1/1741非終結(jié)符A的自動(dòng)匹配p73當(dāng)非終結(jié)符A面臨輸入符號(hào)a，但a不屬于A的任何候選首符集，如果A有候選式A→ε(A的某個(gè)候選首符集包含ε)，可以讓A自動(dòng)得到匹配，即A匹配于空字ε，但輸入符號(hào)不讀進(jìn)要想讓A自動(dòng)匹配成功，需要考察FOLLOW(A)

第40頁(yè)/共91頁(yè)2023/1/1742無(wú)回溯的自上而下分析的文法的條件p73文法不含左遞歸對(duì)于文法的每個(gè)非終結(jié)符A的任何兩個(gè)不同的產(chǎn)生式A→α|β 1)FIRST(α)∩FIRST(β)=φ 2)α==*>和β==*>不能同時(shí)成立

3)如果β==*>，則

FISRT(α)∩FOLLOW(A)=φ滿足以上條件的文法稱(chēng)為L(zhǎng)L(1)文法第41頁(yè)/共91頁(yè)2023/1/1743表達(dá)式文法是LL(1)文法滿足條件（3）：

E’→εFIRST(+TE’)={+}FOLLOW(E’)={),#}φT’→εFIRST(*FT’)={*}FOLLOW(T’)={+,),#}φ

文法G是LL（1）文法滿足條件（1）：已消除左遞歸滿足條件（2）：FIRST(+TE’)={+}FIRST(ε)={ε}φFIRST(*FT’)={*}FIRST(ε)={ε}φFIRST((E))={(}FIRST(i)={i}φ文法G：E→TE'E'→+TE‘|ε

T→FT'T'→*FT‘|ε

F→(E)｜i小節(jié)目錄第42頁(yè)/共91頁(yè)2023/1/1744LL(1)分析p73含義第一個(gè)L表示從左向右掃描輸入符號(hào)串第二個(gè)L表示生成最左推導(dǎo)1表示讀入一個(gè)符號(hào)可確定下一步推導(dǎo)LL(1)文法能夠?qū)斎氪M(jìn)行有效的無(wú)回溯的自上而下分析第43頁(yè)/共91頁(yè)2023/1/1745LL(1)分析p73對(duì)于文法G，當(dāng)面臨的輸入符號(hào)為a，要用非終結(jié)符A進(jìn)行匹配時(shí)，假設(shè)A的所有產(chǎn)生式為A→α1|α2|…|αn 1)若a∈FIRST(αi)，則指派αi去執(zhí)行任務(wù)

2)若a不屬于任何候選首符集，則： ①若ε屬于某個(gè)FIRST(αi)且

a∈FOLLOW(A)，則讓A與ε自動(dòng)匹配 ②否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤小節(jié)目錄第44頁(yè)/共91頁(yè)2023/1/1746

4.4遞歸下降分析程序構(gòu)造p74不帶回溯的自上而下分析程序分析程序一組遞歸過(guò)程每個(gè)非終結(jié)符一個(gè)子過(guò)程LL（1）文法構(gòu)造分析程序從開(kāi)始符號(hào)所對(duì)應(yīng)的過(guò)程開(kāi)始運(yùn)行子過(guò)程的功能：對(duì)相應(yīng)非終結(jié)符產(chǎn)生式右部進(jìn)行語(yǔ)法分析第45頁(yè)/共91頁(yè)2023/1/1747例表達(dá)式文法的遞歸下降分析器消除左遞歸后的表達(dá)式文法G為：

E→TE' E'→+TE’|ε T→FT' T'→*FT’|ε F→(E)|i可以證明

G是一個(gè)LL（1）文法E()E’()T()T’()F()5個(gè)非終結(jié)符構(gòu)造5個(gè)子過(guò)程第46頁(yè)/共91頁(yè)2023/1/1748遞歸下降分析器構(gòu)造說(shuō)明p74C語(yǔ)言

E（）

{ T;

E’; }E’TE（1）E（）：完成對(duì)E→TE’的右部分析PASCAL語(yǔ)言 procedureE; begin

T;

E’; end;右部有非終結(jié)符時(shí)，調(diào)用該非終結(jié)符對(duì)應(yīng)的子過(guò)程來(lái)完成第47頁(yè)/共91頁(yè)2023/1/1749遞歸下降分析器構(gòu)造說(shuō)明E’(){ if(c==‘+’){p++;

T;

E’;}}E’TE’（2）E’（）：完成對(duì)E’→+TE’|ε的右部分析procedureE’; ifsym=‘+’thenbeginadvance;

T;E’;end；+其它非+字符自動(dòng)匹配εadvance：把輸入指針ip下移一位sym：當(dāng)前所面臨的輸入符號(hào)第48頁(yè)/共91頁(yè)2023/1/1750表達(dá)式文法的遞歸下降分析器舉例C語(yǔ)言練習(xí)T(){ F;

T’;}(3)T():T→FT’procedureT; begin

F;

T’; end;T’FT第49頁(yè)/共91頁(yè)2023/1/1751表達(dá)式文法的遞歸下降分析器舉例(4)T’():T’→*FT’|εC語(yǔ)言練習(xí)T’(){ if(c==‘*’){p++;F;T’;}}procedureT’; ifsym=‘*’thenbeginadvance;

F;T’;end；T’F*其它非*字符自動(dòng)匹配εT’第50頁(yè)/共91頁(yè)2023/1/1752表達(dá)式文法的遞歸下降分析器舉例(5)F():F→(E)|i

EF()i其它非(,i字符出現(xiàn)語(yǔ)法錯(cuò)誤procedureF;beginifsym='('thenbeginadvance;E;ifsym=‘)’thenadvanceelseerror{括號(hào)不匹配}endelseifsym=‘i’thenadvance elseerror

{F面臨非（，i輸入符號(hào)，語(yǔ)法錯(cuò)誤}

end第51頁(yè)/共91頁(yè)2023/1/1753Ｆ的子程序C語(yǔ)言練習(xí)F(){ if(c==‘(‘){p++;E;if(c==‘)’)p++;elseerror;}/*括號(hào)不匹配*/

elseif(c==‘i’)p++;elseerror;/*F面臨非(,i輸入符號(hào)，語(yǔ)法錯(cuò)誤*/

}EF()i其它非(,i字符出現(xiàn)語(yǔ)法錯(cuò)誤第52頁(yè)/共91頁(yè)2023/1/1754i+i的遞歸下降分析過(guò)程

ＥＴＥ’ＦＴ’Ｔ＋Ｅ’iεＦＴ’iεε生成語(yǔ)法分析樹(shù)i+i#匹配成功返回，指針下移自動(dòng)匹配，返回自動(dòng)匹配，返回自動(dòng)匹配，返回匹配成功繼續(xù)，指針下移匹配成功返回，指針下移分析成功結(jié)束第53頁(yè)/共91頁(yè)2023/1/1755遞歸下降分析程序優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：1）直觀、簡(jiǎn)單、可讀性好2）便于擴(kuò)充缺點(diǎn)：1)遞歸算法的實(shí)現(xiàn)效率低2)處理能力相對(duì)有限3)通用性差，難以自動(dòng)生成第54頁(yè)/共91頁(yè)2023/1/1756

遞歸下降分析程序課堂練習(xí)文法G為：

S→(T)|a+S|a

T→T,S|S 消除左遞歸：

S→(T)|a+S|a

T→ST’

T’→，ST’|ε提取左因子：

S→(T)|aS’

S’→+S|ε

T→ST’T’→，ST’|ε4個(gè)子程序：

S（）S’（）

T（）T’（）

BEGIN第55頁(yè)/共91頁(yè)2023/1/1757

遞歸下降分析程序課堂練習(xí)答案（1）S→(T)|aS’S(){if(c=‘(‘)/*匹配第一候選式*/{p++;T;

if(c=‘)’)p++;elseerror;/*括號(hào)不匹配*/}elseif(c=‘a(chǎn)’){p++;S’;}/*匹配第二候選式*/elseerror;/*語(yǔ)法錯(cuò)誤*/}第56頁(yè)/共91頁(yè)2023/1/1758

遞歸下降分析程序課堂練習(xí)答案(2)S’→+S|ε

S’(){if(c=‘+‘){p++;

S;}}(3)T→ST’T(){S;

T’;}(4)T’→,ST’|εT’(){if(c=‘,’){p++;

S;

T’;}}章節(jié)目錄第57頁(yè)/共91頁(yè)2023/1/17594.5預(yù)測(cè)分析程序p76簡(jiǎn)介預(yù)測(cè)分析程序的工作過(guò)程預(yù)測(cè)分析表的構(gòu)造綜合練習(xí)章節(jié)目錄第58頁(yè)/共91頁(yè)2023/1/1760

預(yù)測(cè)分析程序簡(jiǎn)介p76實(shí)現(xiàn)LL(1)分析的另一種有效方法使用一張二維分析表（預(yù)測(cè)分析表）和一個(gè)分析棧（文法符號(hào)棧）聯(lián)合進(jìn)行控制來(lái)實(shí)現(xiàn)自上而下分析技術(shù)節(jié)目錄第59頁(yè)/共91頁(yè)2023/1/1761

4.5.1預(yù)測(cè)分析程序工作過(guò)程預(yù)測(cè)分析表實(shí)際上是一個(gè)矩陣M[A,a]M[A，a]=A→αi當(dāng)A面臨a時(shí)所應(yīng)選用的候選式空(error)A不可能與a匹配出現(xiàn)語(yǔ)法錯(cuò)誤待匹配棧頂非終結(jié)符所面臨輸入符號(hào)

預(yù)測(cè)分析表說(shuō)明p76第60頁(yè)/共91頁(yè)2023/1/1762表達(dá)式文法的預(yù)測(cè)分析表p76M[E’，+]=E’→+TE’E’面臨+時(shí)選用E’→+TE’M[T’，)]=T’→εT’面臨）時(shí)選用T’→εM[F，*]=errorF面臨*時(shí)出現(xiàn)語(yǔ)法錯(cuò)誤請(qǐng)?jiān)嚱o出輸入串w=i*i+i的預(yù)測(cè)分析過(guò)程?第61頁(yè)/共91頁(yè)2023/1/1763分析棧的說(shuō)明p76分析棧用于存放分析過(guò)程中的文法符號(hào)topstack棧頂指針?lè)治鰲３跏蓟瘯r(shí)：棧底壓入一個(gè)‘#’底頂#Stoptop次棧底壓入文法開(kāi)始符S入棧操作push出棧操作poptop第62頁(yè)/共91頁(yè)2023/1/1764

預(yù)測(cè)分析器模型p77

輸入緩沖區(qū):…a…#

X┆#

?？偪刂瞥绦蝾A(yù)測(cè)分析表輸出所選用產(chǎn)生式序列查找第63頁(yè)/共91頁(yè)2023/1/1765總控程序執(zhí)行時(shí)可能動(dòng)作p77對(duì)于任何（X，a）X是棧頂符號(hào)a是面臨輸入符號(hào)X∈ＶT

且X＝a＝‘#’，分析成功結(jié)束，輸入串是一個(gè)合法句子(2)X∈ＶT

且X＝a≠‘#’，

X出棧，輸入指針指向下一輸入符號(hào)(3)X∈ＶN

，查分析表M[X，a]

若M[X，a]=X→αi，

X出棧，αi逆序入棧，輸入指針不動(dòng)若M[X，a]=空，則調(diào)用error程序，進(jìn)行錯(cuò)誤處理第64頁(yè)/共91頁(yè)2023/1/1766執(zhí)行例子：i*i+i分析過(guò)程

棧輸入緩沖區(qū)所用產(chǎn)生式0#E

i*i+i#E→TE'E'T入棧1#E'T

i*i+i#T→FT'2#E'T'F

i*i+i#F→i3#E'T'i

i*i+i#i出棧，a下移4#E'T'

*i+i#T'→*FT'5#E'T'F*

*i+i#*出棧，a下移6#E'T'F

i+i#F→i7#E'T'i

i+i#i出棧，a下移第65頁(yè)/共91頁(yè)2023/1/1767i*i+i分析

過(guò)程

續(xù)

棧輸入緩沖區(qū)所用產(chǎn)生式8#E'T'

+i#T'→ε9#E'

+i#E'→+TE'10#E'T+

+i#11#E'T

i#T→FT'12#E'T'F

i#F→i13#E'T'i

i#14#E'T'

#T'→ε15#E'

#E'→ε16#

#

#=#分析成功結(jié)束輸出的產(chǎn)生式序列形成了按最左推導(dǎo)生成的語(yǔ)法分析樹(shù)第66頁(yè)/共91頁(yè)2023/1/1768課堂練習(xí)一：i+i分析過(guò)程棧輸入緩沖區(qū)所用產(chǎn)生式BEGIN0#E

i+i#E→TE'1#E'T

i+i#T→FT' 2#E'T'F

i+i#F→i3#E'T'i

i+i# 4#E'T'

+i#T'→ε5#E'

+i#E'→+TE'6#E'T+

+i# 7#E'T

i#T→FT'

第67頁(yè)/共91頁(yè)2023/1/1769i+i分析過(guò)程續(xù)棧輸入緩沖區(qū)所用產(chǎn)生式8#E'T'F

i#F→i9#E'T'i

i#10#E'T'

#T'→ε11#E'

#E'→ε12#

##=#分析成功第68頁(yè)/共91頁(yè)2023/1/1770課堂練習(xí)二：i+i*i分析過(guò)程棧輸入緩沖區(qū)所用產(chǎn)生式0#E

i+i*i#E→TE'1#E'T

i+i*i# T→FT'2#E'T'F

i+i*i#F→i3#E'T'i

i+i*i# 4#E'T'

+i*i#T'→ε5#E'

+i*i#E'→+TE'6#E'T+

+i*i#7#E'T

i*i#T→FT'

第69頁(yè)/共91頁(yè)2023/1/1771i+i*i分析過(guò)程續(xù)棧輸入緩沖區(qū)所用產(chǎn)生式8#E'T'F

i*i#F→i9#E'T'i

i*i#10#E'T'

*i#T'→*FT'11#E'T'F*

*i#12#E'T'F

i#F→i13#E'T'i

i#14#E'T'

#T'→ε15#E'

#E'→ε16#

#分析成功結(jié)束第70頁(yè)/共91頁(yè)2023/1/1772總控程序?qū)崿F(xiàn)算法描述p77BEGINPUSH(STACK,’#’)；PUSH(STACK,開(kāi)始符號(hào));a=第一個(gè)輸入符號(hào)；

FLAG:=TRUE；

WHILEFLAGDOBEGINX=POP(STACK);IFX∈ＶTTHENIFX=aTHENa=下一個(gè)符號(hào){終結(jié)符匹配}ELSEERROR{與當(dāng)前輸入符號(hào)不匹配}

第71頁(yè)/共91頁(yè)2023/1/1773總控程序?qū)崿F(xiàn)算法描述p77（續(xù)）ELSEIFX=‘#’THENIFX=aFLAG:=FALSEELSEERRORX=a=‘#’

分析成功結(jié)束ELSEIFM[A，a]={X→X1X2…Xk}

把Xk…X2X1一一推進(jìn)STACK棧]ELSEERRORENDOFWHILESTOP{分析成功,過(guò)程完畢}END節(jié)目錄第72頁(yè)/共91頁(yè)2023/1/17744.5.2預(yù)測(cè)分析表的構(gòu)造p78設(shè)有文法G，預(yù)測(cè)分析表構(gòu)造過(guò)程：計(jì)算所有候選式α的首符集

FIRST（α）計(jì)算所有非終結(jié)符A的后繼符集

FOLLOW（A）構(gòu)造預(yù)測(cè)分析表

M節(jié)目錄第73頁(yè)/共91頁(yè)2023/1/1775FIRST(α)的計(jì)算FIRST(α)={a｜α==*>a…，a∈ＶT}若α==*>ε，則ε∈FIRST(α)計(jì)算文法符號(hào)X的FIRST（X）計(jì)算文法符號(hào)串α=X1X2…Xn的FIRST(α)第74頁(yè)/共91頁(yè)2023/1/1776FOLLOW(A)的計(jì)算FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，則#∈FOLLOW（A）第75頁(yè)/共91頁(yè)2023/1/1777預(yù)測(cè)分析表的構(gòu)造算法p79(4)把所有無(wú)定義的M[A,a]標(biāo)上“出錯(cuò)標(biāo)志”(1)對(duì)文法G的每個(gè)產(chǎn)生式A→α，執(zhí)行(2)和(3)(2)對(duì)每個(gè)終結(jié)符a∈FIRST(α)，把A→α

填入M[A,a](3)若ε∈FIRST(α)，則對(duì)任何b∈FOLLOW(A)

把A→α

填入M[A,b]第76頁(yè)/共91頁(yè)2023/1/1778預(yù)測(cè)分析表的構(gòu)造算法舉例E→TE’FIRST(TE’)={(,i}M[E,(]=E→TE’M[E,i]=E→TE’

E’→+TE’FIRST(+TE’)={+}M[E’,+]=E’→+TE’E’→εFOLLOW(E’)={),#}M[E’,)]=E’→εM[E’,#]=E’→εF→(E)|i

M[F,(]=F→(E)M[F,i]=F→i若文法G的分析表不含多重入口，則G是LL(1)文法第77頁(yè)/共91頁(yè)2023/1/1779預(yù)測(cè)分析法（狀態(tài)矩陣法）1)編寫(xiě)文法，消除二義性；2)消除左遞歸、提取左因子；3)求FIRST集合和FOLLOW集合4）檢查是不是LL(1)文法若不是LL(1),說(shuō)明文法的復(fù)雜性超過(guò)自上而下方法的分析能力5）按照LL(1)文法構(gòu)造預(yù)測(cè)分析表6）實(shí)現(xiàn)預(yù)測(cè)分析器小節(jié)目錄第78頁(yè)/共91頁(yè)2023/1/1780預(yù)測(cè)分析程序課堂綜合練習(xí)文法G為：S→aBc｜bABA→aAb｜bB→b｜ε1.非終結(jié)符的FIRST集FIRST(S)={a,b}FIRST(A)={a,b}FIRST(B)={b,ε}2.非終結(jié)符FOLLOW集FOLLOW(S)={#}FOLLOW(A)=FIRST(b)∪FIRST(B)-{ε}∪FOLLOW(S)={b,#}FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}問(wèn)題：構(gòu)造預(yù)測(cè)分析表，并分析符號(hào)串baabbb是否為該文法的句子？S→bABB==>εS→bAB第79頁(yè)/共91頁(yè)2023/1/1781預(yù)測(cè)分析程序課堂綜合練習(xí)(續(xù)）文法G為：S→aBc｜bABA→aAb｜bB→b｜εFOLLOW(B)={c,#}SABabc#S→aBcS→bABA→aAbA→bB→bB→εB→ε3.構(gòu)造預(yù)測(cè)分析表若分析表無(wú)多重入口，則G是LL(1)文法第80頁(yè)/共91頁(yè)2023/1/1782綜

合

練

習(xí)

續(xù)

符號(hào)棧輸入緩沖區(qū)所用產(chǎn)生式0#S baabbb#S→bAB1#BAbbaabbb#移進(jìn)b 2#BAaabbb#A→aAb3#BbAaaabbb#移進(jìn)a4#BbAabbb#A→aAb5#BbbAaabbb#移進(jìn)a6#BbbAbbb#A→b7#Bbbbbbb#移進(jìn)b8#Bbbbb#移進(jìn)b9#Bbb#移進(jìn)b10#B#B→ε11##分析成功結(jié)束

4.b

a

a

b

b

b

分

析

過(guò)

程節(jié)目錄第81頁(yè)/共91頁(yè)2023/1/17834.6LL(1)分析中的錯(cuò)誤處理p80語(yǔ)法錯(cuò)誤：棧頂終結(jié)符與當(dāng)前輸入符不匹配棧頂非終結(jié)符A面臨輸入符a，但分析表M中M[A,a]為空解決方法：彈出棧頂終結(jié)符利用“同步符號(hào)”進(jìn)行略過(guò)或恢復(fù):(1)FOLLOW(A)——略過(guò)輸入串中的符號(hào)

(2)FIRST(A)——根據(jù)A恢復(fù)語(yǔ)法分析第82頁(yè)/共91頁(yè)2023/1/1784加入同步符號(hào)的LL(1)分析表p80第83頁(yè)/共91頁(yè)2023/1/1785對(duì))i*+i的語(yǔ)法分析與錯(cuò)誤處理p81棧輸入緩沖區(qū)所用產(chǎn)生式0#E)i*+i#錯(cuò),跳過(guò))1#Ei*+i#i∈FIRST(E)E→TE'2#E'Ti*+i#T→FT' 3#E'T'Fi*+i#F→i4#E'T'ii*+i#i出棧 5#E'T'*+i#T'→*FT'6#E'T'F**+i#*出棧7#E'T'F+i#錯(cuò),synch彈出F8#E'T'+i#T'→ε9#E'+i#E'→+TE'10#E'T++i#i出棧 11#E'Ti#T→FT’12#E'T'Fi#F→i13#E'T'ii#i出棧14#E'T'#T'→ε15#E'#E'→ε16###=#分析成功章節(jié)目錄第84頁(yè)/共91頁(yè)2023/1/1786本章練習(xí)1.編譯過(guò)程中,語(yǔ)法分析器的任務(wù)是

.

①分析單詞是怎樣構(gòu)成的②分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的③分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的

④分析程序的結(jié)構(gòu)

A②和③B④C②③④D①②③④自上而下分析法自下而上分析法左遞歸回溯2.語(yǔ)法分析的常用方法是

和

.3.自上而下語(yǔ)法分析法會(huì)遇到的主要問(wèn)題有

和

.第85頁(yè)/共91頁(yè)2023/1/1787本章練習(xí)4.LL(1)分析法中,第一個(gè)L的含義是

,第二個(gè)L的含義是

,“1”的含義是

.從左到右掃描輸入串每次進(jìn)行最左推導(dǎo)對(duì)輸入串中向前查看1個(gè)符號(hào)5.一個(gè)文法G,若

,則稱(chēng)它是LL(1)文法.A.G中不含左遞歸.B.G無(wú)二義性

C.G的LL(1)分析表不含多重定義

D.G中產(chǎn)生式不含左公因子6.高級(jí)語(yǔ)言編譯程序常用的語(yǔ)法分析方法中,遞歸下降分析法屬于

分析方法.A.自左至右B.自上而下C.自下而上D.自右向左第86頁(yè)/共91頁(yè)2023/1/1788本章練習(xí)7.

下列文法是左遞歸文法，試消除其左遞歸。G[S]：

S→SaA|bBA→aB|cB→Bb|d

S→bBS’S’→aAS’|εA→aB|cB→dB’B’→bB’|ε解答:8.考慮文法G[S]:S→aSb|PP→bPc|bQcQ→Qa|a

該文法消除左遞歸、提取左公因子后是不是LL(1)文法？

第87頁(yè)/共91頁(yè)2023/1/1789本章練習(xí)9.有文法G[S]:S→BAA→BS|dB→aA|bS|c(1)證明文法G是LL(1)文法;(2)構(gòu)造LL(1)分析表;(3)寫(xiě)出句子adccd的分析過(guò)程.

章節(jié)目錄第88頁(yè)/共91頁(yè)2023/1/1790作業(yè)p81123章節(jié)目錄第89頁(yè)/共91頁(yè)2023/1/1791bMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F6IaLdPgSjVnYq!x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZq$+B3E6H9LcO