自下而上的語(yǔ)法分析5.1自下而上的語(yǔ)法分析概述

從葉結(jié)點(diǎn)出發(fā)，步步向上歸約。若能歸約到根結(jié)點(diǎn)，說(shuō)明輸入串是文法的一個(gè)句子，否則輸入串存在語(yǔ)法錯(cuò)誤。比較：從文法的開(kāi)始符號(hào)出發(fā)進(jìn)行推導(dǎo)，最終推出確定的輸入串（由單詞種別構(gòu)成的源程序）。

第2頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

㈠概述實(shí)質(zhì)上是一種移進(jìn)歸約法，設(shè)置一個(gè)棧，將輸入串符號(hào)逐個(gè)移進(jìn)棧內(nèi)，一旦發(fā)現(xiàn)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，立即將棧頂這一部分符號(hào)替換（歸約）成該產(chǎn)生式的左部符號(hào)。第3頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

例給定文法Ｇ：S→aAcBeA→b|AbB→d輸入串a(chǎn)bbcde第4頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

移進(jìn)歸約過(guò)程如下所示

第5頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

因最終歸約到根結(jié)點(diǎn)，輸入串a(chǎn)bbcde是文法的一個(gè)句子。第6頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

㈡問(wèn)題從第④步到第⑤步有二種選擇，可將b歸約成A，棧頂成aAA；也可將Ab歸成A，棧頂成aA，顯然后者是正確的，故需精確定義可歸約串。第7頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

㈢句柄和規(guī)范歸約①短語(yǔ)②直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）第8頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

③句柄句型aAbcde中存在三個(gè)短語(yǔ)，它們是Ab、d和aAbcde，其中Ab和d是直接短語(yǔ)，句柄是Ab。不能因?yàn)榇嬖谝?guī)則A→b，就斷定b是這個(gè)句型的一個(gè)短語(yǔ)，b不是句柄，甚至連短語(yǔ)都不是。第9頁(yè),共58頁(yè)，2024年2月25日，星期天5.1自下而上的語(yǔ)法分析概述

④規(guī)范歸約（最左歸約）⑤規(guī)范句型⑥規(guī)范推導(dǎo)⑦圖解法第10頁(yè),共58頁(yè)，2024年2月25日，星期天5.2算符優(yōu)先文法1.算符文法比較簡(jiǎn)單，適合手工構(gòu)造，特別適合算術(shù)表達(dá)式的語(yǔ)法分析2.算符優(yōu)先分析法的優(yōu)先關(guān)系P106第11頁(yè),共58頁(yè)，2024年2月25日，星期天5.2算符優(yōu)先文法3.算符優(yōu)先文法的定義P107第12頁(yè),共58頁(yè)，2024年2月25日，星期天5.2算符優(yōu)先文法4.FIRSTVT集合定義P109LASTVT集合定義P109第13頁(yè),共58頁(yè)，2024年2月25日，星期天5.2算符優(yōu)先文法構(gòu)造集合的規(guī)則第14頁(yè),共58頁(yè)，2024年2月25日，星期天5.2算符優(yōu)先文法5.構(gòu)造算符優(yōu)先文法分析表第15頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理LR分析法適用范圍廣泛，適合自動(dòng)生成，目前大多數(shù)編譯程序的語(yǔ)法分析器都采用這種分析法第16頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理㈠前綴—字的任意首部㈡活前綴—規(guī)范句型的一個(gè)前綴，不包含句柄后的任何符號(hào)?；罹褪瞧溆也刻砑右恍┙K結(jié)符后，就構(gòu)成一個(gè)規(guī)范句型㈢LR分析法的基本思想把每個(gè)句柄的識(shí)別（產(chǎn)生式右部符號(hào)串）過(guò)程劃分為若干狀態(tài)，每個(gè)狀態(tài)只識(shí)別句柄的一個(gè)符號(hào)，若干個(gè)符號(hào)就可識(shí)別句柄左端的一部分符號(hào)。識(shí)別了句柄這一部分就相當(dāng)于識(shí)別了當(dāng)前規(guī)范句型的左起部分，既規(guī)范句型的活前綴。第17頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理對(duì)于文法G，可以構(gòu)造一個(gè)有限自動(dòng)機(jī)DFA，用它去識(shí)別給定文法的所有規(guī)范句型的活前綴，然后把這個(gè)DFA轉(zhuǎn)換成LR分析表。因此，首先構(gòu)造一個(gè)識(shí)別文法G所有活前綴的NFA，這個(gè)NFA的每個(gè)狀態(tài)是下面定義的一個(gè)“項(xiàng)目”第18頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理㈣LR(0)項(xiàng)目（簡(jiǎn)稱項(xiàng)目）文法G的LR（0）項(xiàng)目定義為：在文法G每個(gè)產(chǎn)生式右部的某個(gè)位置添加一個(gè)園點(diǎn)“.”。如A→XYZ包含四個(gè)項(xiàng)目A→.XYZ A→X.YZA→XY.Z A→XYZ.特例，A→ε的項(xiàng)目為A→.。第19頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理例文法0.

S'→E1.

E→aA2.

A→cA3.

A→d4.

E→d第20頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理這個(gè)文法的項(xiàng)目有1S'→.E 2S'→E.3E→.aA 4E→a.A 5E→aA.6A→.cA 7A→c.A 8A→cA.9A→.d 10A→d.11E→.d 12E→d.第21頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理㈤構(gòu)造識(shí)別活前綴的NFA①將每個(gè)項(xiàng)目視為識(shí)別活前綴NFA的一個(gè)狀態(tài)。②規(guī)定狀態(tài)S'→.S為NFA的唯一初態(tài)，狀態(tài)S'→S.為NFA的唯一接受態(tài)（S為原文法開(kāi)始符號(hào)，S'為拓廣文法開(kāi)始符號(hào)）。第22頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理③因在每個(gè)狀態(tài)都可識(shí)別出一個(gè)活前綴（初態(tài)可識(shí)別出活前綴ε），故NFA的每個(gè)狀態(tài)都是終態(tài)，終態(tài)又稱為活前綴識(shí)別態(tài)。④如果狀態(tài)i和狀態(tài)j源自于同一產(chǎn)生式，而且狀態(tài)i和狀態(tài)j的園點(diǎn)位置相差一個(gè)文法符號(hào)，例狀態(tài)i為

i:X→X1……Xi-1.XiXi+1……Xn

狀態(tài)j為

j:X→X1……Xi-1Xi.Xi+1……Xn那么狀態(tài)i和j之間存在一條弧，標(biāo)記為Xi，表示在狀態(tài)i讀入Xi進(jìn)入狀態(tài)j。第23頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理⑤若狀態(tài)i園點(diǎn)之后的符號(hào)為非終結(jié)符（例i:X→α.Aβ），那么從狀態(tài)i畫(huà)一條ε弧到所有k:A→.γ狀態(tài),表示只有看到了從A推出的全部符號(hào):狀態(tài)i:X→α.Aβ才可經(jīng)A弧進(jìn)入狀態(tài)j:X→αA.β。第24頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理接上例，構(gòu)造識(shí)別文法活前綴的NFA，如下所示：

其中1稱為初態(tài)（含有S'→.E的項(xiàng)目），狀態(tài)2、8、10、5和12稱為句柄識(shí)別態(tài)（含有形如A→γ.的項(xiàng)目），其中2又稱為接受態(tài)（含有S'→E.的項(xiàng)目）。

第25頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理第26頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理㈥構(gòu)造識(shí)別活前綴的DFA其中0是初態(tài)，1為接受態(tài)，3、4、6和7是句柄識(shí)別態(tài)。第27頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理第28頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理㈦項(xiàng)目分類凡是圓點(diǎn)在最右端的項(xiàng)目稱為歸約項(xiàng)目，A→α.對(duì)文法開(kāi)始符號(hào)S'的歸約項(xiàng)目稱為接受項(xiàng)目形如A→α.aβ的項(xiàng)目稱為移進(jìn)項(xiàng)目，a為終結(jié)符形如A→α.Bβ的項(xiàng)目稱為待約項(xiàng)目，B為非終結(jié)符第29頁(yè),共58頁(yè)，2024年2月25日，星期天5.3LR分析法的基本原理㈧LR(0)項(xiàng)目集規(guī)范族（簡(jiǎn)稱項(xiàng)目集規(guī)范族）識(shí)別一個(gè)文法活前綴的DFA的項(xiàng)目集（狀態(tài)）的全體㈨活前綴識(shí)別工作原理輸入串a(chǎn)cd第30頁(yè),共58頁(yè)，2024年2月25日，星期天5.4項(xiàng)目集規(guī)范族的構(gòu)造㈠文法拓廣引進(jìn)產(chǎn)生式S'→S㈡項(xiàng)目集I的閉包（CLOSURE(I)）P132㈢狀態(tài)轉(zhuǎn)換函數(shù)（GO(I,X)）P132㈣項(xiàng)目集規(guī)范族構(gòu)造算法C={I0};//項(xiàng)目集的集合If(GO(Ii,XK)<>{}&&GO(Ii,XK)!∈C){j++;Ij=GO(Ii,XK);C=C∪Ij};第31頁(yè),共58頁(yè)，2024年2月25日，星期天5.4項(xiàng)目集規(guī)范族的構(gòu)造第32頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造㈠預(yù)備工作①引入產(chǎn)生式S'→S，將文法拓廣成G'。②對(duì)G'的產(chǎn)生式進(jìn)行編號(hào)。③構(gòu)造文法G'的狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)和項(xiàng)目集規(guī)范族C。第33頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造㈡構(gòu)造法設(shè)項(xiàng)目集規(guī)范族C={I0、I1、……In}，將I0、I1、……In視為分析表狀態(tài)0、1、……n。LR(0)分析表存放在二維數(shù)組M中，第一維為狀態(tài)，第二維為文法符號(hào)。①若移進(jìn)項(xiàng)目A→α.aβ∈Ii且GO(Ii,a)=Ij，其中a∈VT，則置M[i][a]=sj（s表示移進(jìn)）。第34頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造②若歸約項(xiàng)目A→α.∈Ii，對(duì)于任何a∈VT∪{#}，置M[i][a]=rk（k是產(chǎn)生式A→α的編號(hào)，r表示歸約）。③若接受項(xiàng)目S'→S.∈Ii，則置M[i]['#']=Acc（Acc表示接受）。④若待約項(xiàng)目A→α.Bβ∈Ii且GO(Ii,B)=Ij，其中B∈VN，則置M[i][B]=j。⑤分析表中的空白表示出錯(cuò)。第35頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造規(guī)則②若歸約項(xiàng)目A→α.∈Ii，對(duì)于任何a∈VT∪{#}，置M[i][a]=rk（k是產(chǎn)生式A→α的編號(hào)，r表示歸約）。某一個(gè)狀態(tài)若含有歸約項(xiàng)目，則在該狀態(tài)下應(yīng)執(zhí)行歸約操作，該規(guī)則簡(jiǎn)單處理為遇到任何符號(hào)都執(zhí)行歸約，而不考慮有些終結(jié)符出錯(cuò)的問(wèn)題，這就是LR（0）分析法中0的含義，0表示沒(méi)有任何展望。1表示有展望，向前看一個(gè)輸入符號(hào)第36頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造例已知文法GE→aA|dA→cA|d 構(gòu)造它的LR(0)分析表。第37頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造解：①預(yù)備工作1）引入產(chǎn)生式S'→E，將文法G拓廣成G'。2）產(chǎn)生式編號(hào)如下：0.S'→E1.E→aA2.E→d3.A→cA4.A→d3）構(gòu)造上述文法的狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)和項(xiàng)目集規(guī)范族。第38頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造②構(gòu)造分析表（過(guò)程，手工完成）第39頁(yè),共58頁(yè)，2024年2月25日，星期天5.5LR(0)分析表的構(gòu)造總結(jié)若文法的項(xiàng)目集規(guī)范族中的每個(gè)項(xiàng)目集不存在以下情況：1.既含有移進(jìn)項(xiàng)目又含有歸約項(xiàng)目2.含有多個(gè)歸約項(xiàng)目則稱該文法是一個(gè)LR（0）文法即LR（0）文法的項(xiàng)目集規(guī)范族的任何一個(gè)項(xiàng)目集都不包含沖突項(xiàng)目，僅當(dāng)一個(gè)文法是LR（0）文法時(shí)，才能構(gòu)造出不含沖突的LR（0）分析表第40頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造㈠SLR(1)分析法的引出例簡(jiǎn)單算術(shù)表達(dá)式文法G'：0.

S'→E 1.

E→E+T 2.

E→T 3.

T→T*F4.

T→F5.

F→(E) 6.

F→i 第41頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造它的項(xiàng)目集規(guī)范族如下圖所示：第42頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造項(xiàng)目集規(guī)范族共有12個(gè)狀態(tài)（I0-I11），根據(jù)項(xiàng)目集規(guī)范族構(gòu)造LR(0)分析表，如下：第43頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造因M[2]['*']=s7r2、M[9]['*']=s7r1，分析表含多重定義，故上述分析表不是LR(0)分析表。第44頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造㈡SLR(1)分析法的基本思想假定I是項(xiàng)目集規(guī)范族的一個(gè)項(xiàng)目集I={X→α.bβ，A→α.，B→α.}若follow(A)∩follow(B)={}、follow(A)∩={}、follow(B)∩={}，則SLR(1)分析法處理如下：第45頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造

①若當(dāng)前輸入符號(hào)t.code和b相等，則移進(jìn)輸入符號(hào)。②若當(dāng)前輸入符號(hào)t.code∈follow(A)，則用產(chǎn)生式A→α進(jìn)行歸約。③若當(dāng)前輸入符號(hào)t.code∈follow(B)，則用產(chǎn)生式B→α進(jìn)行歸約。④此外報(bào)錯(cuò)。第46頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造㈢構(gòu)造法SLR(1)分析表的構(gòu)造是在LR(0)分析表基礎(chǔ)上進(jìn)行的，只要對(duì)LR(0)分析表的構(gòu)造方法稍加修改，就可獲得SLR(1)分析表的構(gòu)造方法，修改部分如下所述：第47頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造㈠預(yù)備工作①引入產(chǎn)生式②產(chǎn)生式編號(hào)③構(gòu)造狀態(tài)轉(zhuǎn)換函數(shù)和項(xiàng)目集規(guī)范族④計(jì)算非終結(jié)符的follow集。㈡構(gòu)造法①②若歸約項(xiàng)目A→α.∈Ii，對(duì)于任何a∈follow(A)，置M[i][a]=rk（k是產(chǎn)生式A→α的編號(hào)，r表示歸約）。③④⑤第48頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造接上例，構(gòu)造G的SLR(1)分析表。解：①預(yù)備工作1）文法拓廣（同上）2）產(chǎn)生式編號(hào)（同上）3）構(gòu)造狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)和項(xiàng)目集規(guī)范族（同上）4）計(jì)算非終結(jié)符的follow集folow(S')={#}、folow(E)={#,+,)}、folow(T)={#,+,),*}、folow(F)={#,+,),*}第49頁(yè),共58頁(yè)，2024年2月25日，星期天5.6SLR(1)分析表的構(gòu)造②構(gòu)造分析表第50頁(yè),共58頁(yè)，2024年2月25日，星期天5.7LR語(yǔ)法分析器的控制程序㈠數(shù)據(jù)結(jié)構(gòu)①LR分析表②狀態(tài)棧③符號(hào)棧④產(chǎn)生式右部符號(hào)串長(zhǎng)度㈡手工模擬控制程序計(jì)算第51頁(yè),共58頁(yè)，2024年2月25日，星期天5.7LR語(yǔ)法分析器的控制程序㈢算法描述分析表用二維數(shù)組M存儲(chǔ)，棧頂狀態(tài)用Stop表示，當(dāng)前輸入符號(hào)用t.code表示，控制程序的算法歸納如下：第52頁(yè),共58頁(yè)，2024年2月25日，星期天5.7LR語(yǔ)法分析器的控制程序①移進(jìn)若M[Stop][t.code]=sj，說(shuō)明句柄尚未形成，應(yīng)執(zhí)行移進(jìn)操作。s表示移進(jìn)，j為狀態(tài)號(hào)，將j移入狀態(tài)棧，將t.code移入符號(hào)棧，j成為新的棧頂狀態(tài)Stop。讀下一個(gè)單詞。第53頁(yè),共58頁(yè)，2024年2月25日，