編譯原理5.1自下而上語(yǔ)法分析

1、第五章第五章 語(yǔ)法分析語(yǔ)法分析自下而上分析自下而上分析本章內(nèi)容本章內(nèi)容l自下而上分析基本問題自下而上分析基本問題l直觀算符優(yōu)先分析法直觀算符優(yōu)先分析法l算符優(yōu)先分析算符優(yōu)先分析l LRLR分析法分析法自下而上分析法自下而上分析法從輸入串開始，逐步進(jìn)行從輸入串開始，逐步進(jìn)行“歸約歸約”，直至，直至歸約到文法的開始符號(hào)；歸約到文法的開始符號(hào)；一、自下而上分析基本問題一、自下而上分析基本問題1 1 、歸約、歸約利用棧，輸入符號(hào)移進(jìn)棧，當(dāng)棧頂形成利用棧，輸入符號(hào)移進(jìn)棧，當(dāng)棧頂形成P P的的候選式時(shí)，就歸約為它的左候選式時(shí)，就歸約為它的左P P符號(hào)符號(hào)例例5.1 5.1 文法文法G2:G2:S-aAcB

2、e A-bS-aAcBe A-bA-Ab B-dA-Ab B-d輸入串：輸入串：abbcdeabbcde自下而上法，即自下而上法，即“移進(jìn)移進(jìn)- -歸約歸約”法法最右推導(dǎo)：最右推導(dǎo)：a aa ab ba aA Aa aA Ab ba aA Aa aA Ac ca aA Ac cd da aA Ac cB Ba aA Ac cB Be eS S1 12 23 34 45 56 67 78 89 91010棧棧S S= aAc= aAcB Be e = aAc= aAcd de e =a=aAbAbcdecde= a b b c d e= a b b c d eS-aAcBeS-aAcBe輸入串：

3、輸入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-bSaAcBeAbdb分分 析析 樹樹最左歸約：最左歸約：= S= S= aAc= aAcB Be e= a= aA Acdecde= a= aA Abcdebcdea a b b b c d e b c d e S-aAcBeS-aAcBe輸入串：輸入串：abbcdeabbcdeA-AbA-AbB-dB-dA-bA-b2 2 規(guī)范歸約規(guī)范歸約短語(yǔ)短語(yǔ): :令令G G是一個(gè)文法，是一個(gè)文法，S S是文法的開始符是文法的開始符號(hào)，若號(hào)，若是文法是文法G G的一個(gè)句型，的一個(gè)句型，如果有如果有S AS A且且 A A ，則稱，則

4、稱是句型是句型相對(duì)于相對(duì)于非終結(jié)符非終結(jié)符A A的的短語(yǔ)。短語(yǔ)。句柄：句柄：一個(gè)句型的一個(gè)句型的最左直接短語(yǔ)最左直接短語(yǔ)稱為該句型稱為該句型的句柄。的句柄。直接短語(yǔ)：直接短語(yǔ)：如果有如果有A A ，則稱，則稱是句型是句型相對(duì)于規(guī)則相對(duì)于規(guī)則A A的的直接短語(yǔ)直接短語(yǔ)規(guī)范推導(dǎo)：規(guī)范推導(dǎo)：即即最右推導(dǎo)最右推導(dǎo)；規(guī)范句型：規(guī)范句型：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型；句型；規(guī)范歸約：規(guī)范歸約：是關(guān)于句型是關(guān)于句型的一個(gè)的一個(gè)最右推導(dǎo)最右推導(dǎo)的的逆過(guò)程，也稱逆過(guò)程，也稱最左歸約最左歸約。例例5.25.2 文法文法G G E T | E +T T F | T * F F i |

5、（E）的一個(gè)句型的一個(gè)句型 i i1 1* *i i2 2+i+i3 3語(yǔ)語(yǔ) 法法 樹樹TFEEFF+T*iiiTTFEEFF+T*i1i2i3T i i1 ,1 ,i i2 ,2 ,i i3 , 3 , i i1 1* *i i2 , 2 , i i1 1* *i i2 2+i+i3 3i i1 ,1 ,i i2 ,2 ,i i3 3 i i1 1 l短語(yǔ)短語(yǔ): :l直接短語(yǔ)直接短語(yǔ): :l句柄句柄: : 3 3 符號(hào)棧的使用符號(hào)棧的使用規(guī)范歸約用來(lái)作語(yǔ)法分析需要解決的規(guī)范歸約用來(lái)作語(yǔ)法分析需要解決的問題：?jiǎn)栴}：如何在句型中找出句柄如何在句型中找出句柄? ?在相同的右部有不止一個(gè)產(chǎn)生式時(shí)在相

6、同的右部有不止一個(gè)產(chǎn)生式時(shí), ,選哪一個(gè)選哪一個(gè)? ?實(shí)現(xiàn)移進(jìn)實(shí)現(xiàn)移進(jìn)- -歸約分析的一個(gè)方便途徑是用一個(gè)棧和一個(gè)輸歸約分析的一個(gè)方便途徑是用一個(gè)棧和一個(gè)輸 入緩沖區(qū)入緩沖區(qū), ,用用# #表示棧底和輸入的結(jié)束表示棧底和輸入的結(jié)束棧棧輸輸 入入#w# 分析程序的動(dòng)作分析程序的動(dòng)作l移進(jìn)移進(jìn): : 下一輸入符號(hào)移進(jìn)棧頂下一輸入符號(hào)移進(jìn)棧頂l歸約歸約: : 把句柄按產(chǎn)生式的左部進(jìn)行歸約把句柄按產(chǎn)生式的左部進(jìn)行歸約l接收接收: : 分析程序報(bào)告成功分析程序報(bào)告成功l出錯(cuò)出錯(cuò): : 發(fā)現(xiàn)了一個(gè)語(yǔ)法錯(cuò)發(fā)現(xiàn)了一個(gè)語(yǔ)法錯(cuò), ,調(diào)用出錯(cuò)處理程序調(diào)用出錯(cuò)處理程序注意注意: : 可歸約的串在棧頂可歸約的串在棧頂,

7、 ,不會(huì)在內(nèi)部不會(huì)在內(nèi)部二二 直觀算符優(yōu)先分析法直觀算符優(yōu)先分析法 1 1 定義定義: : 任二個(gè)相繼出現(xiàn)的終結(jié)符任二個(gè)相繼出現(xiàn)的終結(jié)符a a與與b(b(可能中間有可能中間有V VNN), ),可能有以可能有以下優(yōu)先關(guān)系下優(yōu)先關(guān)系: :a b a的優(yōu)先性的優(yōu)先性低于低于ba b a的優(yōu)先性的優(yōu)先性等于等于ba b a的優(yōu)先性的優(yōu)先性高于高于b2 例例5.3 文法文法G:E E + E | E * E | EE | ( E ) | i的終結(jié)符的優(yōu)先關(guān)系見下表。的終結(jié)符的優(yōu)先關(guān)系見下表。 + * i （ ） # + * i（ ） #優(yōu)優(yōu) 先先 表表E E E+E | E E+E | E* *E |

8、 EE |( E )| iE | EE |( E )| i3 3 使用如上分析表，構(gòu)造分析算法（直觀算符使用如上分析表，構(gòu)造分析算法（直觀算符優(yōu)先分析法）優(yōu)先分析法）記號(hào)使用說(shuō)明：記號(hào)使用說(shuō)明： #：語(yǔ)句括號(hào)（棧底：語(yǔ)句括號(hào)（棧底 w后）后）：現(xiàn)行棧頂符：現(xiàn)行棧頂符 a：剛讀入字符：剛讀入字符OPTR：運(yùn)算符棧：運(yùn)算符棧OPND：操作符棧：操作符棧分析算法步驟：分析算法步驟：下一個(gè)輸入符號(hào)讀至下一個(gè)輸入符號(hào)讀至a a中；中；若若a a為為i i，則，則aOPNDaOPND，轉(zhuǎn)第一步；，轉(zhuǎn)第一步；若若 a a，則調(diào)用關(guān)于，則調(diào)用關(guān)于的處理程序（語(yǔ)義程序），處理子的處理程序（語(yǔ)義程序），處理子表達(dá)

9、式表達(dá)式 : : E E（1 1）EE（2 2） ；然后重新進(jìn)入第；然后重新進(jìn)入第3 3步；（其中，步；（其中， E E（1 1） 、E E（2 2）分分別為別為OPNDOPND棧的次棧頂和棧頂）棧的次棧頂和棧頂）aOPTROPND#E （1） E （2）E（3）=若若 a a，則，則若若=(=(,a=),a=),則逐出則逐出OPTROPTR棧頂?shù)臈ｍ數(shù)?,(,放棄放棄a a中中的的 ),),轉(zhuǎn)第轉(zhuǎn)第 1 1步步; ;若若=a=#,a=#,分析成功結(jié)束；分析成功結(jié)束；若若 a a，aOPTRaOPTR棧，轉(zhuǎn)第棧，轉(zhuǎn)第1 1步；步；與與a a不存在優(yōu)先關(guān)系，則輸入串錯(cuò)誤，調(diào)出錯(cuò)處理不存在優(yōu)先關(guān)系

10、，則輸入串錯(cuò)誤，調(diào)出錯(cuò)處理)OPTROPND#(E （1） E （2）a#成功！成功！2 例例5.4 由文法由文法G: E E + E | E * E | EE | ( E ) | i的終結(jié)符的優(yōu)先關(guān)系表及上述分析算法的終結(jié)符的優(yōu)先關(guān)系表及上述分析算法分析算術(shù)表達(dá)式分析算術(shù)表達(dá)式 i1 + i2 i1 + i2 * * i3 # i3 # 的過(guò)程。的過(guò)程。OPTROPTROPNDOPND分析過(guò)程分析過(guò)程 OPND OPND棧為空，棧為空， # -OPTR# -OPTR棧棧 i1-OPND i1-OPND # + # OPTR+-OPTR i2-OPND i2-OPND# #+ +i1 i1i2

11、i2i3i3* *t te e輸入串輸入串 : :i1 + i2 i1 + i2 * * i3 # i3 # + +OPTR-OPTR i3-OPND i3-OPND * * # # ， * *彈出彈出OPTROPTR棧棧； i2 i2 * * i3 = t -OPND i3 = t -OPND + # + # ， +彈出彈出OPTROPTR棧棧； t + i1 = e -OPNDt + i1 = e -OPND # =# # =# ， 分析成功；分析成功； e e 為整個(gè)表達(dá)式的結(jié)為整個(gè)表達(dá)式的結(jié)果果a a1 1 算符優(yōu)先文法算符優(yōu)先文法定義一定義一 如果一個(gè)文法的任何產(chǎn)生式右部都不含兩個(gè)相

12、如果一個(gè)文法的任何產(chǎn)生式右部都不含兩個(gè)相繼（并列）的非終結(jié)符，即不含有如下形式的產(chǎn)繼（并列）的非終結(jié)符，即不含有如下形式的產(chǎn)生式右部：生式右部：QRQR則我們稱該文法為則我們稱該文法為算符文法算符文法(OG)(OG)。三三 算符優(yōu)先分析算符優(yōu)先分析定義二定義二 假定假定G G是一個(gè)不含是一個(gè)不含-產(chǎn)生式的算符文法。對(duì)于任何一產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符對(duì)終結(jié)符a a、b b，我們說(shuō)：，我們說(shuō)：la ba b， 當(dāng)且僅當(dāng)文法當(dāng)且僅當(dāng)文法G G中含有形如中含有形如P-ab P-ab 或或P-P-aQbaQb的產(chǎn)生式；的產(chǎn)生式； （如：（如：（E E），則（），則（ ）la ba b， 當(dāng)且

13、僅當(dāng)當(dāng)且僅當(dāng)G G中含有形如中含有形如P-aRP-aR的產(chǎn)生式，的產(chǎn)生式，而而R b R b 或或 R QbR Qb；la ba b， 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G G中含有形如中含有形如P-RbP-Rb的產(chǎn)生式，的產(chǎn)生式，而而R a R a 或或 R aQR aQ。 定義三定義三 如果一個(gè)算符文法如果一個(gè)算符文法G G中的任何終結(jié)符對(duì)（中的任何終結(jié)符對(duì)（a a，b b）至多只滿足下述三種關(guān)系之一：至多只滿足下述三種關(guān)系之一：a ba b，a ba b，a ba b則稱則稱G G是一個(gè)是一個(gè)算符優(yōu)先文法算符優(yōu)先文法(OPG)(OPG)。Ch5 語(yǔ)法分析5.2 算符優(yōu)先分析法5.2.2 算符優(yōu)先分析與分析

14、器例5.4設(shè)文法G(P)：PaQQbR(討論若為討論若為Rb？) Ra考察G(P)中的終結(jié)符a、b的優(yōu)先關(guān)系：據(jù)定義中的，因存在PaQ且Q=bR, 所以a b ；據(jù)定義中的 ，因存在bR且=a, 所以b a ；b與b, a與a不存在優(yōu)先關(guān)系。所以G(P)是算符優(yōu)先文法。abba構(gòu)造優(yōu)先關(guān)系表，就是要找出所有構(gòu)造優(yōu)先關(guān)系表，就是要找出所有V VT T對(duì)之間的三種關(guān)系對(duì)之間的三種關(guān)系，而對(duì)于，而對(duì)于 可以直接檢查所有的可以直接檢查所有的G G中中P P來(lái)得到。而來(lái)得到。而 ， 關(guān)系關(guān)系不易檢查，故要定義二個(gè)集合。不易檢查，故要定義二個(gè)集合。FIRSTVT(P)=a|P aFIRSTVT(P)=a|

15、P a或或P QaP Qa，aVaVT T 而而QVQVN N LASTVT(P)=a|P aLASTVT(P)=a|P a或或P aQP aQ，aVaVT T 而而QVQVN N 如該二集合成功，檢查如該二集合成功，檢查P P，就可確定滿足，就可確定滿足 ， 的（的（a a，b b）對(duì)。）對(duì)。這是因?yàn)?，假定有個(gè)產(chǎn)生式候選式：這是因?yàn)椋俣ㄓ袀€(gè)產(chǎn)生式候選式： aPaP，那么對(duì)任何，那么對(duì)任何 bFIRSTVT(P),bFIRSTVT(P),有有a ba b； PbPb，那么對(duì)任何，那么對(duì)任何 aLASTVT(P)aLASTVT(P)，有，有a ba b；2 2 從算符優(yōu)先文法構(gòu)造優(yōu)先關(guān)系表從算

16、符優(yōu)先文法構(gòu)造優(yōu)先關(guān)系表構(gòu)造該二個(gè)集合的算法，對(duì)每一構(gòu)造該二個(gè)集合的算法，對(duì)每一 V VNN的的FIRSTVT(P) FIRSTVT(P) 、LASTVT(PLASTVT(P）使用每個(gè)使用每個(gè)V VNN的的FIRSTVT(P) FIRSTVT(P) 、LASTVT(PLASTVT(P），檢），檢查每一個(gè)產(chǎn)生式，找出所有（查每一個(gè)產(chǎn)生式，找出所有（a a，b b）的關(guān)）的關(guān)系，就完成了構(gòu)造優(yōu)先關(guān)系表。系，就完成了構(gòu)造優(yōu)先關(guān)系表。因此，問題歸結(jié)為：因此，問題歸結(jié)為：3 3 構(gòu)造集合構(gòu)造集合FIRSTVT(P)FIRSTVT(P)的算法的算法 P-a P-a或或P-Qa,P-Qa,則則aFIRSTV

17、T(P)aFIRSTVT(P)；若若aFIRSTVT(Q),aFIRSTVT(Q),且有產(chǎn)生式且有產(chǎn)生式P-QP-Q，則，則aFIRSTVT(P)aFIRSTVT(P)4 4 構(gòu)造集合構(gòu)造集合LASTSTVT(P)LASTSTVT(P)的算法的算法 P-a P-a 或或 P-aQ,P-aQ,則則aLASTVT(P)aLASTVT(P)；若若aLASTVT(Q),aLASTVT(Q),且有產(chǎn)生式且有產(chǎn)生式P-QP-Q，則，則aLASTVT(P)aLASTVT(P)firstVT(E)=#firstVT(E)=+,*, ( , i )firstVT(T)=*, ( , i )firstVT(F)=

18、, ( , i )firstVT(P)= ( , i )lastVT(E)=#lastVT(E)=+,*, ) , i lastVT(T)=*, ) , i lastVT(F)= ) , i lastVT(P)= i , ) 例：文法為例：文法為 E#E# TF EE+T FPF FP ET P（E ） TT*F Pi求求firstVTfirstVT和和lastVTlastVT集集方法：方法：(1)(1)建立一個(gè)建立一個(gè)布爾數(shù)組布爾數(shù)組FmFm，nn(m(m為非終結(jié)為非終結(jié)符個(gè)數(shù)，符個(gè)數(shù)，n n為終結(jié)符個(gè)數(shù)為終結(jié)符個(gè)數(shù)) )和和 一個(gè)后進(jìn)先出一個(gè)后進(jìn)先出棧棧STACKSTACK。(2)(2)將

19、所有的將所有的非終結(jié)符非終結(jié)符排序，用排序，用i iA A表示非終結(jié)符表示非終結(jié)符A A的的序號(hào)，再將所有的終結(jié)符排序，用序號(hào)，再將所有的終結(jié)符排序，用j ja a表示終結(jié)表示終結(jié)符符a a的序號(hào)。的序號(hào)。(3) (3) 要使數(shù)組要使數(shù)組每一個(gè)每一個(gè)元素最終取值滿足：元素最終取值滿足：FiFiA A，j ja a 的值為真，當(dāng)且僅當(dāng)?shù)闹禐檎妫?dāng)且僅當(dāng)aFIRSTVT(A)aFIRSTVT(A)lFIRSTVT(P)FIRSTVT(P)的自動(dòng)構(gòu)造的自動(dòng)構(gòu)造步驟如下：步驟如下： (1) 按規(guī)則按規(guī)則對(duì)每個(gè)數(shù)組元素賦初值。對(duì)每個(gè)數(shù)組元素賦初值。 若若FiA，ja的值為真，則將（的值為真，則將（A,a

20、）推入棧中，直至對(duì)所）推入棧中，直至對(duì)所有數(shù)組元素的初值都按此處理完。有數(shù)組元素的初值都按此處理完。 (2) 將棧頂項(xiàng)彈出，設(shè)為（將棧頂項(xiàng)彈出，設(shè)為（B，a），再用規(guī)則），再用規(guī)則檢查所有產(chǎn)檢查所有產(chǎn)生式，若有形為生式，若有形為AB的產(chǎn)生式，而的產(chǎn)生式，而FiA，ja的值為假的值為假，則令其變?yōu)檎妫覍ⅲ?，則令其變?yōu)檎妫覍ⅲˋ，a）推進(jìn)棧，如此重復(fù)直到棧）推進(jìn)棧，如此重復(fù)直到棧彈空為止。彈空為止。對(duì)對(duì)FIRSTVT集的集的構(gòu)造算法規(guī)則：構(gòu)造算法規(guī)則： 若有產(chǎn)生式若有產(chǎn)生式Aa或或A ABaBa，則，則a aFIRSTVT(A)，其中，其中A、B為非為非終結(jié)符，終結(jié)符，a為終結(jié)符為終結(jié)符 若若

21、aFIRSTVT(B)且有產(chǎn)生式且有產(chǎn)生式AB， 則有則有a aFIRSTVT(A)例如對(duì)例例如對(duì)例3表達(dá)式文法求每個(gè)非終結(jié)符的表達(dá)式文法求每個(gè)非終結(jié)符的FIRSTVT（B）棧棧STACK的初值的初值為：為：（6） （P，i)（5） （P，( )（4） （F，)（3） （T，*)（2） （E，+)（1） （E，#)由產(chǎn)生式由產(chǎn)生式FP，TF，ET棧頂（棧頂（6）的內(nèi)容逐）的內(nèi)容逐次改變?yōu)椋海ù胃淖優(yōu)椋海‵,i)， （T,i) ，（，（E,i)E#E# EE+TETTT*F TFFPF FPFPP（E ）Pi 棧頂（棧頂（5 5）為）為（P P，( () )，同樣由產(chǎn)生式：同樣由產(chǎn)生式：FPFP

22、，TFTF，ETET當(dāng)前棧頂（當(dāng)前棧頂（5 5）的變化依次為：（）的變化依次為：（F,( )F,( )， （T,( ) T,( ) ，（，（E,( )E,( ) 當(dāng)棧頂（當(dāng)棧頂（4 4）為）為（F F，），），由產(chǎn)生式由產(chǎn)生式TFTF，ETET當(dāng)前棧頂（當(dāng)前棧頂（4 4）的變化依次為：（）的變化依次為：（T, )T, )， （E,) E,) ，（，（E, )E, ) 當(dāng)棧頂（當(dāng)棧頂（3 3）為）為（T,T,* *），），由產(chǎn)生式由產(chǎn)生式ETET，棧頂（，棧頂（3 3）變?yōu)椋ǎ┳優(yōu)椋‥ E，* *），），以下逐次彈出棧頂元素后，都再無(wú)進(jìn)棧項(xiàng)，直至棧空以下逐次彈出棧頂元素后，都再無(wú)進(jìn)棧項(xiàng)，直至?？?/p>

23、（6） （P，i)（5） （P，( )（4） （F，)（3） （T，*)（2） （E，+)（1） （E，#)由算法可知，凡在棧中出現(xiàn)過(guò)的非終結(jié)符和終結(jié)符對(duì)，由算法可知，凡在棧中出現(xiàn)過(guò)的非終結(jié)符和終結(jié)符對(duì)，在相應(yīng)數(shù)組元素的布爾值為真，在表的數(shù)組中在相應(yīng)數(shù)組元素的布爾值為真，在表的數(shù)組中“1”表示表示+ +* *i i( () )# #EE1 1E E1 11 11 11 11 1T T1 11 11 11 1F F1 11 11 1P P1 11 1布爾數(shù)組的值布爾數(shù)組的值 由數(shù)組布爾元素值知文法中每個(gè)非終結(jié)符的由數(shù)組布爾元素值知文法中每個(gè)非終結(jié)符的FIRSTVT(A)集合為：集合為：FIRST

24、VT(E)FIRSTVT(E)+，*，(，iFIRSTVT(T)*，(，iFIRSTVT(F) ，(，i FIRSTVT(P)(，i5 5 構(gòu)造優(yōu)先表方法構(gòu)造優(yōu)先表方法 對(duì)形如對(duì)形如 P-abP-ab和形如和形如P-aQbP-aQb，有，有a ba b；對(duì)形如對(duì)形如 P-aRP-aR，而，而bFIRSTVT(R)bFIRSTVT(R)，有，有a ba b；對(duì)形如對(duì)形如 P-RbP-Rb，而，而aLASTVT(R)aLASTVT(R)，有，有a ba b；對(duì)文法開始符號(hào)對(duì)文法開始符號(hào)S，有，有# FIRSTVT(S)，LASTVT(S) #， 且對(duì)且對(duì) #S#，有，有# #。Ch5 語(yǔ)法分析5.

25、2 算符優(yōu)先分析法5.2.2 算符優(yōu)先分析與分析器算法5.3 構(gòu)造文法G的優(yōu)先關(guān)系表輸入：文法G及G的FIRSTVT(G)和LASTVT(G)輸出：文法G的優(yōu)先關(guān)系表方法：for G中的每條規(guī)則P12n 置相鄰的兩個(gè)終結(jié)符i和i+1(或只隔一個(gè)非終結(jié)符)為“ ”，即i i+1； if iT而i+1N 則 for FIRSTVT(Xi+1)中的每個(gè)a置i a； if iN而i+1T 則 for LASTVT(i)中的每個(gè)a置a i+1。P aR 且 FIRSTVT(R)P Ra 且 LASTVT(R)上例的算符優(yōu)先關(guān)系表 +*i()#+*i(#a； 比較符號(hào)棧頂項(xiàng) b(bVT)與a的優(yōu)先級(jí)；若

26、ba或 b= a轉(zhuǎn) ；若 b a轉(zhuǎn) ； 否則 error; a入棧( p+)轉(zhuǎn) ； /還沒形成最左素短語(yǔ)，移進(jìn) 在棧中尋找滿足bn+1bnbn-1 b1a的bn，即尋找最左素短語(yǔ)的頭； 將 bn bn-1 b1及有關(guān)的非終結(jié)符歸約到，入棧；若棧中為S與a“”，則end，否則(a)=棧頂轉(zhuǎn) ；Ch5 語(yǔ)法分析5.2 算符優(yōu)先分析法5.2.3 算符優(yōu)先分析法理論探討例5.9設(shè)有文法G(Z) 和輸入串b (aa)bZ bMbM (LaL Ma)文法G(Z)的優(yōu)先關(guān)系表ba()#ba()#Ch5 語(yǔ)法分析5.2 算符優(yōu)先分析法5.2.3 算符優(yōu)先分析法理論探討步驟符號(hào)棧優(yōu)先關(guān)系 (a)輸入字符串動(dòng)作1

27、b (aa)b初始化(aa)baa)ba)b)b)bb=23456789101112bb(b(ab(Mb(Mab(Ma)b(LbMbMbZb(aaa)bbbb進(jìn)棧( 進(jìn)棧a 進(jìn)棧用Ma歸約a 進(jìn)棧) 進(jìn)棧用LMa)歸約用M(L歸約b進(jìn)棧用ZbMb歸約分析成功，結(jié)束7 7 優(yōu)先函數(shù)優(yōu)先函數(shù) l定義：定義： 我們把每個(gè)終結(jié)符我們把每個(gè)終結(jié)符與兩個(gè)自然數(shù)與兩個(gè)自然數(shù)f( f() ) 和和g(g() )相對(duì)相對(duì)應(yīng)，使得：應(yīng)，使得： 若若1 1 2 2，則，則f( f(1 1)g()g()g(2 2) )函數(shù)函數(shù) f f 稱為稱為入棧優(yōu)先函數(shù)入棧優(yōu)先函數(shù)，g g 稱為稱為比較優(yōu)先函數(shù)比較優(yōu)先函數(shù)。Ch5 語(yǔ)法分析5.2 算符優(yōu)先分析法5.2.4 優(yōu)先函數(shù)表的構(gòu)造為什么引入優(yōu)先函數(shù)表對(duì)給定文法G，若其終結(jié)符個(gè)數(shù)=n，則G的優(yōu)先關(guān)系表的大小 = (n+1)2 ;引入優(yōu)先