自頂向下的語法分析-編譯原理-04-(一)

《編譯原理》

(PrinciplesofCompiling)主講：蔣宗禮2024/1/111正規(guī)式轉(zhuǎn)換成狀態(tài)轉(zhuǎn)移圖上次課主要內(nèi)容εaΦεar|sr,srrssrr*2024/1/112上次課主要內(nèi)容正規(guī)文法與狀態(tài)轉(zhuǎn)換圖ABaAaA→aBA→aA→εA2024/1/113上次課主要內(nèi)容狀態(tài)轉(zhuǎn)移圖的構(gòu)造開始12061-93x0-9,a-f40-9,a-f其它0-9其它50-70-7其它（DEC，值）（OCT，值）其它用狀態(tài)轉(zhuǎn)移圖描述單詞的識(shí)別——詞法分析2024/1/114上次課主要內(nèi)容用狀態(tài)轉(zhuǎn)移圖實(shí)現(xiàn)詞法分析器詞法分析器的自動(dòng)生成Lex程序從Lex程序到C語言描述的詞法分析器Lex源程序Lex.yy.cLex編譯器詞法分析器LLex.yy.cC編譯器2024/1/11588pin88+pin*d88+pin*d2024/1/116編譯程序總體結(jié)構(gòu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表格管理出錯(cuò)處理中間代碼目標(biāo)代碼語法單位單詞符號(hào)詞法分析器源程序2024/1/117第4章

自頂向下的語法分析語法分析(SyntaxAnalysis)文法的改造問題自頂向下(TopDown)的分析推導(dǎo)(Derivation)2024/1/1184.1語法分析的任務(wù)語法分析(SyntaxAnalysis)檢查掃描器輸出的單詞序列是否符合該語言的文法——組成句子，并分析組成此句子的語法成分完成語法分析的程序叫做(語法)分析器ParserSyntaxAnalyzer2024/1/1194.1語法分析的任務(wù)掃描器分析器語義處理單詞符號(hào)語法樹源程序輸入：Token序列輸出語法成分及組成表現(xiàn)形式：語法樹錯(cuò)誤報(bào)告出錯(cuò)處理:定位、續(xù)編譯2024/1/1110語法分析方法E→E+E|E-E|E*E|E/E|(E)|id

：id+id*idE+EEidEE*ididE+EEEid*ididE2024/1/1111語法分析方法自頂向下TopDown自底向上BottomUp文法產(chǎn)生語言自動(dòng)機(jī)識(shí)別語言遞歸子程序法預(yù)測分析法(LL(1))算符優(yōu)先分析法LR(0)、SLR(1)[LR(1)、LALR]歸約!推導(dǎo)/派生!2024/1/11124.2自頂向下分析面臨的問題

與CFG的改造一、自頂向下的分析從文法的開始符號(hào)出發(fā)，尋求所給的輸入符號(hào)串的最左推導(dǎo)從樹根S開始，構(gòu)造所給輸入符號(hào)串的語法樹例：G為：S→xAyA→**|*，輸入串：x**ySxAy

x**ySxAy**2024/1/1113二、重要概念回顧推導(dǎo):αＡβ

αγβ(依據(jù):Ａ→γ)最左(Left-most)推導(dǎo)——最左分析左句型最左推導(dǎo)對應(yīng)最右歸約

EE+Ea1+Ea1+E*Ea1+a2*Ea1+a2*a3

EE+EE+E*EE+E*a3E+a2*a3a1+a2*a3最右(Right-most)推導(dǎo)——最右分析規(guī)范推導(dǎo)、規(guī)范句型(右句型)最右推導(dǎo)對應(yīng)最左歸約(規(guī)范歸約)二義性(先天二義性語言、二義性文法)E→E+E|E-E|E*E|E/E|(E)|id2024/1/1114三、重要問題——虛假匹配

x*y發(fā)現(xiàn)不匹配,需要回退(回溯)SxAy*SxAy**SS→xAyA→**|*輸入串x**yS

xAy

x**y匹配成功

xAy2024/1/1115三、重要問題——回溯S

x**yS

xAyx**y發(fā)現(xiàn)不匹配,需要回退

xAyx*ySxAy*SxAy**x**y匹配成功2024/1/1116三、重要問題——二義性及其消除E→E+E|E-E|E*E|E/E|(E)|id對同一句子存在兩棵語法分析樹，哪個(gè)是對的？EE*EidEE+ididEE+EEEid*idid2024/1/1117三、重要問題——二義性及其消除二義性文法E→E+E|E-E|E*E|E/E|(E)|id非二義性文法E→E+T|E-T|TT→T*F|T/F|FF→(E)|id改造方法：引入語法變量，使文法含有更多的信息2024/1/1118三、重要問題——二義性及其消除再例：If語句S→ifEthenSS→ifEthenSelseSS→other設(shè)執(zhí)行下列語句前b=0,理解1：ifa≠0thenifa>0thenb=1elseb=-1當(dāng)a=1時(shí),執(zhí)行后b=1;當(dāng)a=-1時(shí)，執(zhí)行后b=-1理解1：ifa≠0thenifa>0thenb=1elseb=-1當(dāng)a=1時(shí),執(zhí)行后b=1;當(dāng)a=-1時(shí)，執(zhí)行后b=02024/1/1119一個(gè)句子有兩棵不同的語法樹

S S E E S S ifa≠0thenifa>0thenb=1elseb=-1 S S E E S S ifa≠0thenifa>0thenb=1elseb=-12024/1/1120三、重要問題——二義性及其消除1.重寫文法S→U|MU→ifEthenSU→ifEthenMelseUM→ifEthenMelseM|other2.設(shè)置一個(gè)規(guī)則——實(shí)現(xiàn)“就近”、“最長”匹配原則改造1改造2S→TS|CSC→ifEthenT→CSelseC—ConditionT—Else每個(gè)else與前面最近的沒有配對的then配對，即出現(xiàn)在then和else之間的語句必須是配對的2024/1/1121按照“改造1”構(gòu)造的語法樹

S U S M E E M Mifa≠0thenifa>0thenb=1elseb=-1M→ifEthenMelseM|other2024/1/1122按照“改造2”構(gòu)造的語法樹

S S

T(最長)

C C E E S SIfa≠0thenifa>0thenb=1elseb=-1S→TS|CSC→ifEthenT→CSelse2024/1/1123按照“改造2”構(gòu)造的語法樹

S T S(非最長)

C C E E S SIfa≠0thenifa>0thenb=1elseb=-1S→TS|CSC→ifEthenT→CSelse2024/1/1124三、重要問題——二義性及其消除

S S S T(最長) T(最長) S C C C CifEthenifEthenSelseifEthenSelseifEthenSS→TS|CSC→ifEthenT→CSelse2024/1/1125三、重要問題——左遞歸及其消除例：文法S→Say|*與它的句子*ayay*ayayS*不對！SSay

Sayay

Sayayay……

Sayay……ayay一個(gè)無限循環(huán)！2024/1/1126三、重要問題——左遞歸及其消除例簡單算術(shù)表達(dá)式的文法——左遞歸E→E+T|E-T|T|-ET→T*F|T/F|FF→F↑P|PP→(E)|id|const|FUN(L)FUN→abs|sin|cos|ln|log|exp|sqrtL→E|E,LVN＝{E,T,F,P,FUN,L｝VT＝{id,const,+,-,*,/,(,),\,abs,sin,cos,log,ln,exp,sqrt}S＝E2024/1/1127三、重要問題——左遞歸及其消除無法根據(jù)左遞歸文法進(jìn)行自頂向下的分析

Aa1a2……ai……an直接左遞歸A

Aα 當(dāng)前變量 輸入指針 (棧頂、最左變量)間接左遞歸

A

+Aα左遞歸的消除方法將A→Aα|β替換為A→βA′和A′→αA′｜ε2024/1/1128例：表達(dá)式文法直接左遞歸的消除E→E+T｜TT→T*F｜FF→(E)｜idE→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜id2024/1/1129例：間接左遞歸的消除S→Ac|c A→Bb|b B→Sa|a將B的定義代入A產(chǎn)生式得：A→Sab|ab|b將A的定義代入S產(chǎn)生式得:S→Sabc|abc|bc|c消除直接左遞歸： S→abcS’|bcS’|cS’

S’→abcS’|ε刪除“多余的”產(chǎn)生式：A→Sab|ab|b和B→Sa|a結(jié)果： S→abcS’|bcS’|cS’

S’→abcS’|ε

2024/1/1130消除左遞歸的一般方法對產(chǎn)生式組A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

用如下產(chǎn)生式組替換A

β1B|β2B

|…|βm

BB

α1B|α2B

|…|αnB|ε其中：B為新變量，相當(dāng)于A’消除左遞歸的算法見P70的算法為非終結(jié)符編號(hào)，再采用代入法將間接左遞歸變?yōu)橹苯幼筮f歸，消除直接左遞歸2024/1/1131三、重要問題——提取左因子例：if語句的原始文法S→ifEthenS|ifEthenSelseS|other遇到if時(shí)難以判斷用哪一個(gè)產(chǎn)生式進(jìn)行匹配（推導(dǎo)）存在左因子ifEthenS2024/1/1132三、重要問題——提取左因子提取作因子ifEthenSS→ifEthenSS’|otherS'→ε|elseS另一種寫法S→TS|CS|otherC→ifEthenT

→CSelse2024/1/1133三、重要問題——提取左因子將形如A→αβ1|αβ2|…|αβm|γ1|γ2|…|γp的規(guī)則改寫為A→αA'|γ1|γ2|…|γp和A'→β1|β2|…|βm結(jié)果：S→ifEthenSS’|otherS'→ε|elseS2024/1/1134《編譯原理》

(PrinciplesofCompiling)主講：蔣宗禮2024/1/1135上次課主要內(nèi)容兩類不同的語法分析方法自頂向下的分析推導(dǎo)（派生）：自頂向下構(gòu)造語法分析樹自底向上的分析歸約：自地向上構(gòu)造語法分析樹待處理的問題虛假匹配與回溯二義性文法2024/1/1136上次課主要內(nèi)容消除左遞歸將產(chǎn)生式組 A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

變換成 A

β1B|β2B

|…|βm

B B

α1B|α2B

|…|αnB|ε2024/1/1137上次課主要內(nèi)容提取公共左因子將產(chǎn)生式組 A→αβ1|αβ2|…|αβm|γ1|γ2|…|γp 改寫為

A→αA'|γ1|γ2|…|γp和A'→β1|β2|…|βm2024/1/1138四、CFG的使用限制沒有一種方法能夠有效地分析所有CFG(上下文無關(guān)文法)存在無法處理的CFG每種方法能夠處理一部分CFG每種方法都有適用范圍2024/1/1139五、常用文法與分析方法LL文法和LR文法都是CFG的子集無二義性可用不同的文法來描述同一語言對于不同的文法，可用不同的分析方法LL文法──遞歸下降分析法、預(yù)測分析法多用于編譯的手工實(shí)現(xiàn)LR文法──LR分析法多用于編譯的自動(dòng)生成2024/1/11404.3自頂向下的分析方法回顧基本思想尋找輸入符號(hào)串的最左推導(dǎo)試圖根據(jù)當(dāng)前輸入單詞確定使用哪個(gè)產(chǎn)生式基本過程從S出發(fā)，構(gòu)造輸入符號(hào)串(Token)的最左推導(dǎo)從根開始，按與最左推導(dǎo)相對應(yīng)的順序，構(gòu)造輸入符號(hào)串(Token)的語法分析樹2024/1/1141例符號(hào)串id+id*id的分析E→TE’E’→+TE’｜εT→FT’T’→*FT’｜εF→(E)｜idE→E+T｜TT→T*F｜FF→(E)｜id按照最左推導(dǎo)過程，構(gòu)造語法樹2024/1/1142id+id*id的最左推導(dǎo)

與語法樹的生成ＥＴＥ’ＦＴ’Ｔ＋Ｅ’idεＦＴ’idεＦ＊Ｔ’idε1、E→TE’2、T→FT'3、F→id4、T'→ε5、E'→+TE’6、T→FT’7、F→id8、T'→*FT’9、F→id10、T'→ε11、E'→εE→TE’E’→+TE’｜εT→FT’T’→*FT’｜εF→(E)｜id2024/1/1143id+id*id的最左推導(dǎo)再現(xiàn)ETE’ E→TE’FT’E’ T→FT’

idT’E’ F→id

idE’

T’→ε

id+TE’ E’→+TE’id+FT’E’ T→FT’

id+idT’E’ F→id

id+id*FT’E’ T’→*FT’id+id*idT’E’ F→id

id+id*idE’

T’→ε

id+id*id

E’→εE→TE’E’→+TE’｜εT→FT’T’→*FT’｜εF→(E)｜id分析真的就總是這么順利？2024/1/1144候選式的確定與回溯(Backtracking)給定文法S→cAd

A→ab|e?句子ced是該文法定義語言的句子ec A dS當(dāng)需要用A派生時(shí)，可以根據(jù)輸入符號(hào)e唯一的確定A的候選式2024/1/1145候選式的確定與回溯(Backtracking)給定文法S→cAd

A→ab|e?句子cad是該文法定義語言的句子

c A dSba出現(xiàn)一次虛假的匹配，并且立即發(fā)現(xiàn)cad不是合法句子2024/1/1146候選式的確定與回溯(Backtracking)給定文法S→cAd

A→ab|a?句子cad是該文法定義語言的句子c A dSbaac A dS當(dāng)需要用A派生時(shí)，無法根據(jù)輸入符號(hào)a唯一的確定A的候選式2024/1/1147候選式的確定與回溯(Backtracking)給定文法S→cABd

A→ab|ε

B→a?句子cad是該文法定義語言的句子bacAB dScAB dSaε當(dāng)需要用A派生時(shí)，因?yàn)锳→ε使得無法根據(jù)輸入符號(hào)a唯一的確定A的候選式2024/1/1148候選式的確定與回溯(Backtracking)給定文法S→cABd

A→ba|ε

B→a?句子cad是該文法定義語言的句子cAB dSaε當(dāng)需要用A派生時(shí),雖然有A→ε,仍然可以根據(jù)輸入符號(hào)a唯一的確定A的候選式2024/1/1149候選式的確定與回溯(Backtracking)句子cad的分析對給定文法S→cAd

A→ab|a,分析需要回溯對給定文法S→cAd

A→ab|e

,分析不需要回溯對給定文法S→cABd

A→ab|ε

B→a，分析需要回溯對給定文法S→cABd

A→ba|ε

B→a，分析不需要回溯2024/1/1150候選式的確定與回溯(Backtracking)當(dāng)要進(jìn)行某個(gè)語法變量的推導(dǎo)時(shí)，希望能夠根據(jù)當(dāng)前符號(hào)確定候選式如果有幾個(gè)候選式左端第一個(gè)符號(hào)相同，則分析程序無法根據(jù)當(dāng)前輸入符號(hào)選擇產(chǎn)生式一個(gè)候選式可空，另一個(gè)候選式的首符號(hào)可以跟在這個(gè)語法變量后面希望：尋找一類文法，可以方便地根據(jù)當(dāng)前輸入符號(hào)確定正確的候選式2024/1/11514.3.1FIRST和FOLLOW集A→α1|α2|…|αi|…|αn對于

α∈(VT∪VN)*定義:α的首符號(hào)集FIRST(α)={a|α

*a…，a∈VT*}對于

A∈VN定義A的后續(xù)符號(hào)集：

FOLLOW(A)={a|S

*…Aa…，a∈VT}2024/1/1152求FIRST(X)的算法1)對

x∈VT，F(xiàn)IRST(x)={x}；2)對

X∈VN，取FIRST(X)的初值：

FIRST(X)={a|X→a…∈P} X→εP{a|X→a…∈P}∪{ε} X→ε∈P2024/1/11533)對

X∈VN，重復(fù)如下過程，直到所有FIRST集不變?nèi)鬤→Y…∈P，且Y∈VN，則FIRST(X)=FIRST(X)∪(FIRST(Y)-{ε})；若X→Y1…Yn∈P，且Y1...Yi-1

*ε，則對k=1到i:FIRST(X)=FIRST(X)∪(FIRST(Yk)-{ε})；若Y1...Yn

*ε，則FIRST(X)=FIRST(X)∪{ε}2024/1/1154例表達(dá)式文法的語法符號(hào)的FIRST集FIRST(F)={(,id}FIRST(T)=FIRST(F)={(,id}FIRST(E)=FIRST(T)={(,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(()={(}FIRST())={)}FIRST(id)={id}E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|id2024/1/1155求FIRST(α)的算法令α=X1…Xn初值FIRST(α)=FIRST(X1)-{ε};k=1;循環(huán)whileε∈FIRST(Xk)&k<ndoFIRST(α)=FIRST(α)∪(FIRST(Xk+1)-{ε})；K=k+1;結(jié)束處理ifk=n&ε∈FIRST(Xn)thenFIRST(α)=FIRST(α)∪{ε}2024/1/1156求FOLLOW(A)的算法令#為句子的結(jié)束符，對于所有非終結(jié)符,重復(fù)進(jìn)行以下計(jì)算1)將#加入到FOLLOW(S)2)若A→αBβ，則FOLLOW(B)=FOLLOW(B)∪(FIRST(β)–{ε})3)如果A→αB或A→αBβ，且β

*ε，A≠B，則FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)2024/1/1157例表達(dá)式文法的語法變量的FOLLOW集FOLLOW(E)={#,)}E→TE'

E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idFIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST'(α)=FIRST(α)–{ε}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)=FIRST'

(E’)∪FOLLOW(E)∪FOLLOW(E')={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)=FIRST'(T')∪FOLLOW(T)∪FOLLOW(T')={*,+,),#}2024/1/1158自頂向下分析中希望文法滿足的條件希望：從左到右掃描輸入串，尋找它的一個(gè)最左推導(dǎo)，每次有唯一的產(chǎn)生式可用對于G的每個(gè)非終結(jié)符A的任何兩個(gè)不同的候選式A→α|β1)FIRST(α)∩FIRST(β)=φ2)如果β

*ε，則FIRST(α)∩FOLLOW(A)=φ2’)如果α

*ε，則FIRST(β)∩FOLLOW(A)=φ——文法Ｇ是LL(1)的充要條件2024/1/11594.3.2LL(1)文法對G的任意變量A，A→α1|α2|…|αn是所有A產(chǎn)生式，如果它們滿足下列條件，則稱G是LL(1)文法，F(xiàn)IRST(αi)∩FIRST(αj)=Φi≠j且當(dāng)ε∈FIRST(αj)時(shí)，F(xiàn)OLLOW(A)∩FIRST(αi)=ΦLL(1)文法是自頂向下方法能夠處理的一類文法第一個(gè)L表示從左向右掃描輸入符號(hào)串第二個(gè)L表示生成最左推導(dǎo)1表示讀入一個(gè)符號(hào)可確定下一步推導(dǎo)LListhenotationoftheparsingstrategy:theinputstringisscannedinaleft-to-rightmannerandtheparsergeneratesaleftmostderivation2024/1/1160表達(dá)式文法是LL(1)文法E→TE'E'→+TE'｜ε

T→FT'T'→*FT'｜ε

F→(E)｜id考察E':+不在FOLLOW(E')={),#}T':*不在FOLLOW(T')={+,),#}F:(和id不同為什么只考慮所列的三條？2024/1/1161此文法不滿足LL(1)文法的條件，不能保證分析的每一步是確定的，這就是非LL(1)文法的不確定性例對文法S→cAdA→ab|a

輸入cad的分析FIRST(ab)={a}FIRST(a)={a}SdcAbaSdcAa2024/1/1162例對文法S→cABdA→ab|εB→a輸入cad的分析FOLLOW(A)={a}FIRST(ab)={a}bacAB dScAB dSaε此文法不滿足LL(1)文法的條件，不能保證分析的每一步是確定的，這就是非LL(1)文法的不確定性2024/1/1163不確定性的解決方法1)采用回溯算法過于復(fù)雜2）改寫文法將非LL(1)文法改寫為等價(jià)的LL(1)文法并非總有效3）無法改寫時(shí)增加其它的判別因素文法過于復(fù)雜，無法用自頂向下方法處理2024/1/11644.4預(yù)測分析器（LL(1)分析器）

a1a2……ai……an#

輸入緩沖區(qū)棧X…S#控制程序預(yù)測分析表M輸出的產(chǎn)生式序列2024/1/11654.4預(yù)測分析器（LL(1)分析器）系統(tǒng)維持一個(gè)分析表和一個(gè)分析棧，根據(jù)當(dāng)前掃描到的符號(hào)，選擇當(dāng)前語法變量（處于棧頂）的候選式進(jìn)行推導(dǎo)——希望找到相應(yīng)的輸入符號(hào)串的最左推導(dǎo)組成一個(gè)通用的控制算法一個(gè)分析棧，#為棧底符號(hào)一個(gè)輸入緩沖區(qū)，#為輸入串結(jié)束符一個(gè)統(tǒng)一形式的分析表M不同語言使用內(nèi)容不同的分析表2024/1/1166FOLLOW(E')={),#}FOLLOW(T')={+,),#}FIRST(TE')={(,id}FIRST(+TE')={+}FIRST(FT')={(,id}FIRST(*FT')={*}FIRST((E))={(} FIRST(id)={id}E→TE' E'

→+TE'

|ε T→FT'

T'

→*FT'

|ε F→(E)|id考慮簡單算術(shù)表達(dá)式文法的實(shí)現(xiàn)2024/1/1167表達(dá)式文法的預(yù)測分析表語法變量終極符號(hào)id+*()#EE'TT'FFOLLOW(E')={),#};FOLLOW(T')={+,),#};FIRST(TE')={(,id};FIRST(id)={id}FIRST(+TE')={+};FIRST(FT')={(,id};FIRST(*FT')={*};FIRST((E))={(}E→TE'E'

→+TE'

|εT→FT'T'

→*FT'

|εF→(E)|id→TE'→TE'→+TE'→ε→ε→ε→ε→ε→FT'→FT'→*FT'→id→(E)2024/1/1168《編譯原理》

(PrinciplesofCompiling)主講：蔣宗禮2024/1/1169上次課主要內(nèi)容自頂向下的分析方法基本思想分析的關(guān)鍵點(diǎn)輸入指針棧的處理：需要棧、變量和終極符進(jìn)棧問題希望根據(jù)當(dāng)前變量（最左變量）唯一地確定候選式2024/1/1170上次課主要內(nèi)容對文法的要求A→α1|α2|…|αnFIRST(α)={a|α

*a…，a∈VT}A→α1|α2|…|αn|εFIRST(α)={a|α

*a…，a∈VT}∪{ε}

FOLLOW(A)={a|S

*…Aa…，a∈VT}2024/1/1171上次課主要內(nèi)容求FIRST(α)的算法

x∈VT

∪

VN，求FIRST(X)X→a…∈P

X→ε∈PX→Y…∈P求FIRST(α)α=X1…Xn2024/1/1172上次課主要內(nèi)容求FOLLOW(A)的算法FOLLOW(S)={#}

A→αBβ，

FOLLOW(B)=FOLLOW(B)∪(FIRST(β)–{ε})A→αB，A≠B

FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)A→αBβ，β

*ε，A≠B，

FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)2024/1/1173上次課主要內(nèi)容LL(1)文法A→α1|α2|…|αn是所有A產(chǎn)生式FIRST(αi)∩FIRST(αj)=Φi≠j且當(dāng)ε∈FIRST(αj)時(shí)，F(xiàn)OLLOW(A)∩FIRST(αi)=Φ關(guān)于εFIRST有時(shí)會(huì)含ε，那么，F(xiàn)OLLOW呢？2024/1/1174上次課主要內(nèi)容——LL(1)分析器

a1a2……ai……an#

輸入緩沖區(qū)棧X…S#控制程序預(yù)測分析表M輸出的產(chǎn)生式序列2024/1/1175上次課主要內(nèi)容——預(yù)測分析表FOLLOW(E')={),#};FOLLOW(T')={+,),#};FIRST(TE')={(,id};FIRST(id)={id}FIRST(+TE')={+};FIRST(FT')={(,id};FIRST(*FT')={*};FIRST((E))={(}E→TE'E'

→+TE'

|εT→FT'T'

→*FT'

|εF→(E)|id2024/1/1176表達(dá)式文法的預(yù)測分析表語法變量終極符號(hào)id+*()#EE'TT'F→TE'→TE'→+TE'→ε→ε→ε→ε→ε→FT'→FT'→*FT'→id→(E)2024/1/1177執(zhí)行過程舉例：分析id+id*id

（在黑板上同時(shí)畫出語法樹）輸入緩沖區(qū)棧輸出id+id*id#E#id+id*id#TE'#E→TE'id+id*id#FT'E'#T→FT'id+id*id#idT'E'#F→id+id*id#T'E'#+id*id#E'#T'→ε+id*id#+TE'#E'→+TE'2024/1/1178id*id#TE'#id*id#FT'E'#T→FT'id*id#idT'E'#F→id*id#T'E'#*id#*FT'E'#T'→*FT'id#FT'E'#id#idT'E'#F→id#T'E'##E'#T'→ε##E'→ε輸出的產(chǎn)生式序列對應(yīng)最左推導(dǎo)的過程，同時(shí)可以看成相應(yīng)的分析樹+id*id#+TE'#

（接上頁）棧頂為變量：按分析表執(zhí)行推導(dǎo)棧頂為終極符：匹配2024/1/1179系統(tǒng)的執(zhí)行與特點(diǎn)初始化：輸入指針指向輸入串的第一個(gè)字符，分析棧中存放棧底符號(hào)#和文法的開始符號(hào)S根據(jù)棧頂符號(hào)A和讀入的符號(hào)a，查看分析表M,以決定相應(yīng)的動(dòng)作優(yōu)點(diǎn)1.效率高2.便于維護(hù)、自動(dòng)生成關(guān)鍵——分析表M的構(gòu)造2024/1/1180預(yù)測分析表（LL(1)分析表）構(gòu)造算法1.對于每一產(chǎn)生式A→α，執(zhí)行2.和3.；2.對于FIRST(α)中的每一終結(jié)符a,將A→α填入M[A,a]；3.如果ε屬于FIRST(α)，則對FOLLOW(A)中的每個(gè)符號(hào)b，將A→α填入M[A,b]；若ε屬于FIRST(α)，且#在FOLLOW(A)，則將A→α填入M[A,#]；4.將所有無定義的M[A,b]標(biāo)上錯(cuò)誤標(biāo)志2024/1/1181LL(1)通用控制算法P77X為當(dāng)前棧頂符號(hào);a為當(dāng)前輸入符號(hào)；repeat

ifX∈VT∪{#}then ifX=athen {ifX≠#then{將X彈出,且前移輸入指針}}

elseerror else ifM[X,a]=Y1Y2…Yk

then {將X彈出;依次將Yk…Y2Y1壓入棧； 輸出產(chǎn)生式X→Y1Y2…Yk

} elseerroruntilX=#2024/1/1182預(yù)測分析法——總結(jié)1.構(gòu)造文法2.改造文法：消除二義性、消除左遞歸、提取左因子3.求每個(gè)候選式的FIRST集和變量的FOLLOW集4.檢查是不是LL(1)文法若不是LL(1),說明文法的復(fù)雜性超過LL(1)分析方法的分析能力，需要附加新的“信息”5.構(gòu)造預(yù)測分析表6.實(shí)現(xiàn)預(yù)測分析器2024/1/1183出錯(cuò)處理問題對語法變量A，如果M[A,a]無定義，并且a屬于FOLLOW(A)，則增加M[A,a]為“同步點(diǎn)”(synch)詳見教材P80,關(guān)鍵是同步記號(hào)的選擇2024/1/1184一個(gè)設(shè)想對應(yīng)每個(gè)變量設(shè)置一個(gè)處理子程序：procedureAA→X1X2…Xk

…Xn當(dāng)遇到Xk是終極符號(hào)時(shí)直接進(jìn)行匹配當(dāng)遇到Xk是語法變量時(shí)就調(diào)用Xk對應(yīng)的處理子程序要求處理子程序是可以遞歸調(diào)用的E→TE'

E'

→+TE’|εT→FT'

T'→*FT’|εF→(E)|id2024/1/11854.5語法圖例4-9：表達(dá)式文法的描述+TE’ETE’E’E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id2024/1/1186語法圖化簡規(guī)則YXYZYXZX

左因子提取右因子提取A→YX|YZA→Y(X|Z)A→YX|ZXA→(Y|Z)X2024/1/1187語法圖化簡規(guī)則YXZX

X→YX|ZX→Y*Z2024/1/1188語法圖的化簡+TE’+TTEE’→+TE’|εE→TE’E→T(+T)*2024/1/1189簡化的語法圖+TE＊ＦＴidＥＦ

（）E→T(+T)*T→F(*F)*F→(E)|id2024/1/1190構(gòu)造語法圖語法圖是非常有用的設(shè)計(jì)工具語法圖和詞法分析器的狀態(tài)轉(zhuǎn)換圖不同每個(gè)非終結(jié)符對應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖，邊上標(biāo)記語法符號(hào)如果標(biāo)記的是終極符號(hào)，且與下一個(gè)輸入符號(hào)相同，表示匹配成功如果標(biāo)記的是非終結(jié)符A，則調(diào)用A對應(yīng)的過程2024/1/1191構(gòu)造語法圖對文法的每個(gè)非終結(jié)符A，構(gòu)造語法圖創(chuàng)建一個(gè)開始狀態(tài)和一個(gè)終止?fàn)顟B(tài)（返回狀態(tài)）；對每個(gè)產(chǎn)生式A→X1X2…Xn，創(chuàng)建一條從開始狀態(tài)到終止?fàn)顟B(tài)的路徑，邊上的標(biāo)記依次為X1，X2，…

，Xn。2024/1/11924.6遞歸子程序法對應(yīng)每一個(gè)語法變量設(shè)置一個(gè)遞歸處理子程序，按照語法圖，進(jìn)行相應(yīng)的處理開始時(shí)，分析器的輸入指針指向輸入符號(hào)串的第一個(gè)符號(hào)在處理過程中如果遇到標(biāo)記是終結(jié)符a，就與當(dāng)前輸入符號(hào)進(jìn)行匹配，并將輸入指針向右移動(dòng)一個(gè)字符如果遇到標(biāo)記是非終結(jié)符A，則調(diào)用A所對應(yīng)的遞歸處理程序此過程直到處理結(jié)束。2024/1/1193例簡單算術(shù)表達(dá)式的分析器E的子程序(E→T(+T)*)procedureE;beginT; Ｔ的過程調(diào)用

whilelookhead='+'dobegin 當(dāng)前符號(hào)等于＋時(shí)

match(‘+’); 處理終結(jié)符＋

T Ｔ的過程調(diào)用

endend; lookhead：當(dāng)前符號(hào)2024/1/1194T的子程序(T→F(*F)*)procedureT;beginF; F的過程調(diào)用

whilelookhead