語法分析——自下而上分析.ppt

1、第五章 語法分析,自下而上分析,5.1自下而上的語法分析,實(shí)現(xiàn)思想 從輸入符號(hào)串開始，從左到右進(jìn)行掃描，將輸入符號(hào)逐個(gè)移入一個(gè)棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)產(chǎn)生式的右部時(shí)，就用該產(chǎn)生式的左部非終結(jié)符代替，稱為歸約。重復(fù)這一過程，直到歸約到棧中只剩下文法的開始符號(hào)時(shí)，則分析成功， 稱為“移進(jìn)-歸約”方法。 從語法樹的角度看：從語法樹的樹葉開始，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)。是推導(dǎo)的逆過程。,自下而上分析的關(guān)鍵問題是尋找可歸約串。 對(duì)“可歸約串”概念的不同定義，就形成了 不同的自下而上的分析方法。 核心 在算符優(yōu)先分析法中： 用“最左素短語”來刻畫“可歸約串”， 在“規(guī)范歸約”

2、中： 則用“句柄”來刻畫“可歸約串”,規(guī)范歸約概念,有文法G，開始符號(hào)為S, 如果有 S=xy,則xy是文法G的句型，x,y是任意的符號(hào)串 如果有S=xAy, 且有 A=,則是句型xy相對(duì)于非終結(jié)符A的短語 如果有S=xAy, 且有A-,則是句型xy相對(duì)于A-的直接短語 位于一個(gè)句型最左邊的直接短語稱為句柄. 句型- 短語 - 直接短語 -句柄,注: 每次歸約的部分必須是稱之為句柄的字符串(最右推導(dǎo))。 關(guān)鍵的問題是如何識(shí)別句柄,例1：下述文法的另一個(gè)句型： E+T * F + i 其短語、直接短語、句柄分別是？,ET | E+T TF | T*F Fi | (E),短語有：i, T * F,

3、 E+T * F, E + T * F + i 直接短語有： i, T * F 句柄是：T * F,例2考慮文法： E T|E+T T F|T*F F i | (E) （5.2） 對(duì)于句型i*i+i 推導(dǎo) 解： EE+TT+TT*F+TF*F+Ti*F+Ti*i+F i*i+i 盡管有E +i+i 但是, i+i 并不是該句型的一個(gè)短語，因?yàn)椴淮嬖趶腅(文法開始符）到i*E的推導(dǎo)。但是，i, i*i,和i*i+ i 自身都是句型i*i+i 的短語。而且為為直接短語。,最左推導(dǎo)(Left-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符 與最右歸約對(duì)應(yīng) 最右推導(dǎo)(Right-m

4、ost Derive) 每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符 與最左歸約(規(guī)范歸約)對(duì)應(yīng)，得規(guī)范句型,規(guī)范歸約的定義：,假定是文法G的一個(gè)句子，如果序列： n, n-1, , 0 (=S)滿足如下條件，則 序列n, n-1, , 0是一個(gè)規(guī)范歸約: (1) n = 是給定的句子 (2) 0 =S 是文法的開始符號(hào) (3) 對(duì)任何i, 0in，i-1是從i經(jīng)把句柄替換為相應(yīng)文法產(chǎn)生式的左部符號(hào)而得到的。 規(guī)范歸約是最右推導(dǎo)的逆過程，規(guī)范歸約又稱為最左歸約。 最右推導(dǎo)又稱規(guī)范推導(dǎo)，又規(guī)范推導(dǎo)所得到的句型稱規(guī)范句型，規(guī)范推導(dǎo)的逆過程是規(guī)范歸約。 修剪語法樹方法描述自下而上的分析過程。書87頁。,

5、例3 設(shè)有文法G和輸入串$ G: SaABe $: abbcde A Abc|b B d 通過語法樹能使我們直觀的理解規(guī)范“歸約”、“句柄”等概念。,上圖中圖a是輸入串a(chǎn)bbcde的語法樹，一個(gè)句型的句柄是該句型語法樹中最左子樹的末端結(jié)的自左至右排列。則此子樹為A b其末端b為句型abbcde的句柄。將其剪掉（歸約）后如圖b，其最左子樹A Abc其末端結(jié)Abc為句型aAbcBe的最左子樹末端結(jié)故為句柄。圖c表明句型aAde的句柄為d。將其歸約句型aABe的最左子樹為其自身。即為其自身句柄。,分析器的四種動(dòng)作,1) 移進(jìn)：將下一輸入符號(hào)移入棧 2) 歸約：當(dāng)棧頂出現(xiàn)句柄，用產(chǎn)生式左側(cè)的非終結(jié)符替

6、換棧頂?shù)木浔?3) 接受：分析成功，是歸約的一種特殊情況 4) 出錯(cuò)：棧頂?shù)膬?nèi)容與輸入符號(hào)相悖，進(jìn)行出錯(cuò)處理 ？決定移進(jìn)和歸約的依據(jù)是什么,例4：對(duì)于文法（5.2）輸入串i1*i2+i3 的分析（規(guī)范歸約）步驟可表示如下： 步驟 符號(hào)棧 輸入串 動(dòng)作 0 # i1*i2+i3# 預(yù)備 #i1 *i2+i3# 讀入i1 #F *i2+i3# 歸約，F(xiàn)i #T *i2+i3 # 歸約，T F #T* i2+i3# 讀入 #T*i2 +i3# 讀入 #T*F +i3# 歸約，F(xiàn) i #T +i3# 歸約，T T*F #E +i3# 歸約，E T # E+ i3# 讀入 #E+i3 # 讀入 #E+F

7、 # 歸約, F i #E+T # 歸約, T F #E # 歸約，E E+T #E # 接受,5.2 算符優(yōu)先分析,算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號(hào)之間的關(guān)系來尋找可歸約串。 將句型中的終結(jié)符號(hào)當(dāng)作“算符”，借助于算符之間的優(yōu)先關(guān)系確定句柄。 顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào)a和b之間，只可能存在以下四種優(yōu)先關(guān)系：(1) a, b優(yōu)先性相同， 記作 a b。(2) a優(yōu)先性高于b， 記作 a b。(3) a優(yōu)先性低于b ， 記作 a b。(4) a與b不可能相鄰，即此符號(hào)串不是句型(出錯(cuò))。 如果以上四種關(guān)系中的任意兩種都不會(huì)同時(shí)成立，則可以根據(jù)終結(jié)符號(hào)之間

8、的歸約關(guān)系進(jìn)行語法分析。,1.算符文法.(P89):一個(gè)上下無關(guān)文法G,如果沒有P-,且沒有P-.QR.(P,Q,R屬于非終結(jié)符),則G是一個(gè)算符文法 2.算符優(yōu)先關(guān)系的定義(自底向上,可通過樹形結(jié)構(gòu)觀察) a b,G中有P-.ab.或P-.aQb. (在同一產(chǎn)生式中)a b,G中有P-.aR.的產(chǎn)生式,且R=b.或R=Qb. (注意ab相鄰)a b,G中有P-.Rb.的產(chǎn)生式,且R=.a或R=.aQ (注意ab相鄰),算符優(yōu)先文法的定義,例：EE+E | E*E | (E) | i 證明不是OPG文法。 因?yàn)椋篍E+E ， EE*E 則有 + * 又因?yàn)椋篍E*E, EE+E 則有 + *

9、所以不是算符優(yōu)先文法。,算符優(yōu)先文法 算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有 = , 中的一種成立,則G為一算符優(yōu)先文法。,算符優(yōu)先關(guān)系表的構(gòu)造,用表格形式來表示各終結(jié)符號(hào)的優(yōu)先關(guān)系，這種表稱為優(yōu)先表。 構(gòu)造優(yōu)先關(guān)系表的方法： 按照定義手工計(jì)算 使用算法,1、通過檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可以找出滿足a=b的終結(jié)符對(duì)。 2、為了找出所有滿足關(guān)系的終結(jié)符對(duì)，我們需要對(duì)G的每個(gè)非終結(jié)符P 構(gòu)造兩個(gè)集合FIRSTVT(P)和LASTVT(P): FIRSTVT(P)=a | P+a或P +Qa,aVT而 Q VN LASTVT(P)=a | P+a或P +aQ,

10、aVT而 Q VN 3、有了這兩個(gè)集合后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系的所有終結(jié)符對(duì)。 例如：假定有個(gè)產(chǎn)生式的一個(gè)候選式為 aP 那么，對(duì)任何bFISTVT(P),我們有ab.,構(gòu)造集合FIRSTVT(P)的算法。 （1）若有產(chǎn)生式Pa或P Qa,則aFIRSTVT(P) （2）若aFIRSTVT(Q)，且有產(chǎn)生式P Q 則aFIRSTVT(P),構(gòu)造文法G的優(yōu)先表算法： FOR 每一條產(chǎn)生式PX1X2Xn FOR i:=1 TO n-1 DO BEGIN IF Xi 和 Xi+1 均為終結(jié)符THEN 置 Xi=Xi+1 IF Ia END,算符優(yōu)先分析算法,通過比較終結(jié)符間的

11、優(yōu)先關(guān)系來實(shí)現(xiàn) 根據(jù)優(yōu)先分析的原理：語法分析程序的任務(wù)是：不斷移進(jìn)輸入符號(hào)，識(shí)別句柄并進(jìn)行歸約。 分析的方法：根據(jù)優(yōu)先性“高于”來識(shí)別句柄的頭，根據(jù)優(yōu)先性“低于”來識(shí)別句柄的尾。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。,1.不能識(shí)別只由一個(gè)非終結(jié)符組成的句柄。不能保證每次對(duì)句柄進(jìn)行歸約,在算符優(yōu)先分析過程中,每次歸約的符號(hào)串,是當(dāng)前句型的最左素短語. 2.素短語：至少含有一個(gè)終結(jié)符,且除自身外,不再包含任何其它更小的素短語。 3.最左素短語(leftmost prime phrase)：是指位于句型最左邊的那個(gè)素短語。,例5：下述文法的一個(gè)句型： T * F + i 其短語、素短語、最左素短語分別是

12、？,ET | E+T TF | T*F Fi | (E),短語有：i, T * F, T * F + i 素短語有： i, T * F 最左素短語是：T * F,我們把算符優(yōu)先文法句型（括在兩個(gè)#號(hào)之間）的一般形式寫成： #N1a1N2a2Nnan Nn+1# （5.4） 其中每個(gè)ai都是終結(jié)符，Ni是可有可無的非終結(jié)符。 一個(gè)算符優(yōu)先文法G的任何句型（5.4）的最左素短語是滿足如下條件的最左子串：NjajNia i+1, a j-1a i+1 根據(jù)這個(gè)最左素短語的定義我們可以構(gòu)造算符優(yōu)先分析算法。,最左素短語的特點(diǎn)：,算符優(yōu)先分析法小結(jié),優(yōu)點(diǎn) 簡單、效率高 能夠處理部分二義性文法 缺點(diǎn) 文法

13、書寫限制大 占用內(nèi)存空間大 不規(guī)范、存在查不到的語法錯(cuò)誤,第五章 語法分析-自下而上分析,例5.1考慮下面文法： 1。 EE+T|T 2. T T*F|F 3. F PF|P 4. P (E)|i 構(gòu)造優(yōu)先關(guān)系表 解： 根據(jù)產(chǎn)生式4 我們有(=), 從產(chǎn)生式1，2 的+T和T*我們有+,同理可得：。 由產(chǎn)生式P (E)和E E+T T+T T*F+T F*F+T PF*F+T iF*F+T 我們可以得到 ( +, ( *, ( , ( i .總之，我們可以按定義得到對(duì)于文法G的任何終結(jié)符對(duì)（a,b)的，至多只有一種優(yōu)先關(guān)系。從而得到下面的優(yōu)先表：,例題與習(xí)題解答,第五章 語法分析-自下而上分析

14、,優(yōu)先關(guān)系表 + * i ( ) # + * i ( ) # ,第五章 語法分析-自下而上分析,例5.2 對(duì)下列文法G: S#S# P S|i S D(R) D i R R; P|P 求出每個(gè)非終結(jié)符的FIRSTVT集和LASTVT集，并構(gòu)造算符優(yōu)先關(guān)系矩陣。 文法G每個(gè)非終結(jié)符的FIRSTVT集合 FIRSTVT(S)= # FIRSTVT(P) =i, ( FIRSTVT(S)= (, i FIRSTVT(D) =i FIRSTVT(R) =;, (, i 文法G的每個(gè)非終結(jié)符的LASTVT集合 LASTVT(S) = # LASTVT(P) = i , ) LASTVT(S) = ) L

15、ASTVT(D) = i LASTVT(R) =;, ) ,i 優(yōu)先關(guān)系矩陣 （ ） ； i # ( ; # =,第五章 語法分析-自下而上分析,例5.3已知文法GS為算符優(yōu)先文法，其規(guī)則為： SSaF|F F FbP|P P c|d 求優(yōu)先關(guān)系矩陣 解：每個(gè)非終結(jié)符的FISRVT集合 FIRSTVT(S) = c, d, a,b FIRSTVT(F) = b, c, d FIRSTVT(P) =c , d 每個(gè)非終結(jié)符的LASTVT集合 LASTVT(S)= a, b, c, d LASTVT(F) = b, c, d LASTVT(P) = c, d 因?yàn)镾SaF 則LASTVT(S)a且

16、aa, ba, ca, da 且ab且bb, cb, db 且bc, bd,第五章 語法分析-自下而上分析,優(yōu)先關(guān)系矩陣： a b c d a d ,第五章 語法分析-自下而上分析,優(yōu)先函數(shù) 在實(shí)際實(shí)現(xiàn)算符優(yōu)先分析算法時(shí)，一般不用優(yōu)先表而是用兩個(gè)優(yōu)先函數(shù)f 和g。我們把每個(gè)終結(jié)符號(hào)與兩個(gè)自然數(shù)f()和g() 相對(duì)應(yīng)，使得 若1g(2) 函數(shù)f 稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。 構(gòu)造優(yōu)先函數(shù)的方法應(yīng)在必須掌握之列。 如果優(yōu)先函數(shù)存在，那么，從優(yōu)先表構(gòu)造優(yōu)先函數(shù)的一個(gè)簡單方法是： （1）對(duì)于每個(gè)終結(jié)符a(包括#）令其對(duì)應(yīng)兩個(gè)符號(hào)fa和ga , 畫一張以所有符號(hào)fa和ga為結(jié)點(diǎn)的方向圖，如果a

17、=b,那么，就從fa畫一箭弧至gb;如果a=b 則畫一條從gb到fa的箭弧。,第五章 語法分析-自下而上分析,(2) 對(duì)于每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)所能到達(dá)結(jié)點(diǎn)（包括出發(fā)結(jié)點(diǎn)自身在內(nèi)）的個(gè)數(shù)。賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b). (3)檢查構(gòu)造出來的函數(shù)f 和g，看它們同原來的關(guān)系表是否有矛盾。如果沒矛盾，則f 和g就是所要的優(yōu)先函數(shù)。如果有矛盾，那么，就不存在優(yōu)先函數(shù)。 例題5。5 就是構(gòu)造優(yōu)先函數(shù)的例子，望同學(xué)們好好研究一下。 5。2。4 算符優(yōu)先分析中的出錯(cuò)處理,LR分析法,LR分析概述 LR(0)分析 SLR(1)分析 LR(1)分析 LALR(1)分析 二

18、義性文法在LR分析中的應(yīng)用,復(fù)習(xí)：移進(jìn)-歸約分析,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn),2） #a bbcde# 移進(jìn),4） #aA bcde# 移進(jìn),6） #aA cde# 移進(jìn),7） #aAc de# 移進(jìn),9） #aAcB e# 移進(jìn),11） #S # 接受,分析符號(hào)串a(chǎn)bbcde是否GS的句子,對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-規(guī)約分析過程,在步驟3中，用Ab歸約 在步驟5中，用AAb歸約 問題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式歸約？,3） #ab bcde# 歸

19、約(Ab),5） #aAb cde# 歸約(AAb),4） #aA bcde# 移進(jìn),6） #aA cde# 移進(jìn),分析：已分析過的部分在棧中的前綴不同，而且移進(jìn)和歸約后棧中的狀態(tài)會(huì)發(fā)生變化 我們引入一個(gè)新的狀態(tài)棧來表示符號(hào)棧中的符號(hào)目前狀態(tài) 用LR分析表來表示不同狀態(tài)下對(duì)于各輸入符號(hào)應(yīng)采取的動(dòng)作,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9

20、,11） #S # 接受 01 acc,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移進(jìn)，并將狀態(tài)i進(jìn)棧 ri:用第i個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)，根據(jù)GOTO表將相應(yīng)狀態(tài)入棧,S8,S9,問題： 對(duì)于一個(gè)文法，狀態(tài)集

21、是如何確定的？ LR分析表是如何得到的？,可歸前綴與活前綴,文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d4,S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,每次歸約句型的前部分依次為：ab2aAb3aAcd4aAcBe1,規(guī)范句型的這種前部分符號(hào)串稱為可歸前綴 我們把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為活前綴,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe,活前綴（Viable Prefixes）,viable:adj capable of growin

22、g and developing capable of being put into practice : workable 定義： S A 是文法G中的一個(gè)規(guī)范推導(dǎo)，如果符號(hào)串是的前綴，則稱是G的一個(gè)活前綴。,LR分析需要構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī) 我們可以把文法的終結(jié)符和非終結(jié)符都看成有窮自動(dòng)機(jī)的輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)?？闯梢炎R(shí)別過了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識(shí)別到可歸前綴時(shí)，相當(dāng)于在棧中形成句柄，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S

23、6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,11） #S # 接受 01 acc,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸

24、入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,對(duì)輸入

25、串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,

26、動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn)

27、 023 S5,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde

28、# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb)

29、 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5）

30、#aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約

31、(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #a

32、AcB e# 移進(jìn) 02357 S9,11） #S # 接受 01 acc,對(duì)輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,如何構(gòu)造識(shí)別活前綴的有限自動(dòng)機(jī),已經(jīng)有了活前綴如何構(gòu)造有限自動(dòng)機(jī)? 活前綴及其可歸前綴的一般計(jì)算方法,文法GS：S S0

33、S aAcBe1A b2A Ab3B d4,句子abbcde的可歸前綴如下：S0ab1aAb3aAcd4aAcBe1,構(gòu)造識(shí)別其活前綴及可歸前綴的有限自動(dòng)機(jī)如下：,1,0,4,3,8,7,13,12,10,18,2,5,9,14,6,17,15,16,11,10,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,1,*,句子識(shí)別態(tài),i,句柄識(shí)別態(tài),1,0,4,3,8,7,13,12,10,18,2,5,9,14,6,17,15,16,11,10,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,X,加上開始狀態(tài)X,確定化,X,1,3,2,4,6,8,5,9,S,a,

34、b,A,b,c,B,e,d,7,*,識(shí)別活前綴的確定的有限自動(dòng)機(jī),活前綴及其可歸前綴的一般計(jì)算方法,定義：文法G，AVN, LC(A)= | S A, V*, VT * 規(guī)范推導(dǎo)中在非終結(jié)符A左邊所有可能出現(xiàn)的符號(hào)串的集合 推論：若文法G中有產(chǎn)生式BA，則有LC(A) LC(B),文法GS：S S0S aAcBe1A b2A Ab3B d4,由前面的定義與推論我們知： LC(S) = LC(S) = LC(S) *LC(A) = LC(S) *a LC(A) * LC(B) = LC(S) *aAc,化簡為： S = S = SA = Sa+A B = SaAc,求解方程組可得： S = S

35、= A = a+A B = aAc,A = a|A,A = a*=a,這樣我們求出了每個(gè)非終結(jié)符在規(guī)范推導(dǎo)中用該非終結(jié)符的右部替換該非終結(jié)符之前，它的左部可能出現(xiàn)的所有前綴，也就是在規(guī)范歸約過程中用句柄歸約成該非終結(jié)符之前不包括句柄的活前綴。,不包括句柄的活前綴 + 句柄 = ？,可歸前綴？,令 LR(0)C(A) = LC(A)* ,文法G的可歸前綴有： LR(0)C(S S) = S*S = S LR(0)C(S aAcBe) = S*aAcBe = aAcBe LR(0)C(A b) = A*b = ab LR(0)C(A Ab) = A*Ab = aAb LR(0)C(B d) = B

36、*d = aAcd,總結(jié)：如何構(gòu)造識(shí)別文法活前綴的有限自動(dòng)機(jī)？,1、根據(jù)文法算出其可歸前綴2、根據(jù)可歸前綴，構(gòu)造識(shí)別文法活前綴的不確定有限自動(dòng)機(jī)3、確定化，從而構(gòu)造出識(shí)別文法活前綴的確定的有限自動(dòng)機(jī),LR分析器的構(gòu)造,1、構(gòu)造識(shí)別文法活前綴的確定有限自動(dòng)機(jī)2、根據(jù)該自動(dòng)機(jī)構(gòu)造相應(yīng)的分析表(ACTION表、GOTO表),總控程序,Action/Goto表,輸入符號(hào)串,輸出,狀態(tài)與符號(hào)棧,這種方法構(gòu)造識(shí)別可歸前綴的有限自動(dòng)機(jī)從理論的角度講是比較嚴(yán)格的，但實(shí)現(xiàn)起來卻很復(fù)雜 是否存在一種比較實(shí)用的方法？,由文法的產(chǎn)生式直接構(gòu)造識(shí)別活前綴和可歸前綴的有限自動(dòng)機(jī) 項(xiàng)目（item）：在每個(gè)產(chǎn)生式的右部適當(dāng)位

37、置添加一個(gè)圓點(diǎn)構(gòu)成項(xiàng)目 例如：產(chǎn)生式S aAcBe對(duì)應(yīng)有6個(gè)項(xiàng)目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 有限自動(dòng)機(jī)的每一個(gè)狀態(tài)由一個(gè)項(xiàng)目構(gòu)成,項(xiàng)目圓點(diǎn)的左部表示分析過程的某個(gè)時(shí)刻用該產(chǎn)生式歸約時(shí)句柄已識(shí)別的部分，圓點(diǎn)右部表示待識(shí)別的部分。 構(gòu)造識(shí)別活前綴的NFA：1、把文法的所有產(chǎn)生式的項(xiàng)目都引出，每個(gè)項(xiàng)目都為NFA的一個(gè)狀態(tài)2、確定初態(tài)、句柄識(shí)別態(tài)、句子識(shí)別態(tài)3、確定狀態(tài)之間的轉(zhuǎn)換關(guān)系*若項(xiàng)目i為 X X1X2.Xi-1 Xi.Xn項(xiàng)目j為 X X1X2.Xi-1 Xi Xi+1.Xn則從狀態(tài)i到狀態(tài)j

38、連一條標(biāo)記為Xi的箭弧*若i為X A，k為A ，則從狀態(tài)i畫標(biāo)記為 的箭弧到狀態(tài)k,文法G：S EE T + E E TT int * T T int T (E),文法的項(xiàng)目有：1、 S E2、 S E 3、 E T + E4、 E T + E5、 E T + E6、 E T + E 7、 E T8、 E T 9、T int * T10、T int * T11、T int * T12、T int * T ,13、 T int 14、 T int 15、 T (E) 16、 T ( E)17、 T (E )18、 T (E) ,NFA for Viable Prefixes of the Exa

39、mple,T . (E),T (.E),T (E.),T (E).,(,E,),S E.,E . T+E,E T.+E,E T+.E,E T+E.,S . E,E . T,E T.,T int.,T .int,T .int * T,T int * T.,T int *.T,T int.* T,e,e,e,e,E,e,T,e,e,e,E,+,e,int,int,*,T,e,e,e,e,e,T,e,NFA for Viable Prefixes in Detail (1),S . E,NFA for Viable Prefixes in Detail (2),S . E,NFA for Viabl

40、e Prefixes in Detail (3),S E.,E . T+E,S . E,E . T,e,E,e,NFA for Viable Prefixes in Detail (4),T . (E),S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,E,e,e,e,T,NFA for Viable Prefixes in Detail (5),T . (E),S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,E,e,e,e,e,e,e,T,NFA for Viable Prefixe

41、s in Detail (6),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,E,e,e,e,e,e,e,T,NFA for Viable Prefixes in Detail (7),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,T (E.),E,NFA for Viable Prefixes in Detail (8),T . (E),T (.E),(,S E.,E .

42、 T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),NFA for Viable Prefixes in Detail (9),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,NFA for Viable Prefixes in Detail (10),T . (E)

43、,T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,NFA for Viable Prefixes in Detail (11),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E

44、 T+E.,E,T int.,int,NFA for Viable Prefixes in Detail (12),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,T int.* T,int,T int *.T,*,NFA for Viable Prefixes in Detail (13),T . (E),T (.E),(,S E.,E . T+

45、E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,T int.* T,int,T int *.T,*,根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把項(xiàng)目分為以下幾種： 移進(jìn)項(xiàng)目，形如 A a 待約項(xiàng)目，形如 A B 歸約項(xiàng)目，形如 A 接受項(xiàng)目，形如 S S ,Translation to the DFA,S . E E . T E .T + E T .(E) T .int * T T .int,S E

46、.,E T. E T. + E,T int. * T T int.,T (. E) E .T E .T + E T .(E) T .int * T T .int,E T + E.,E T + . E E .T E .T + E T .(E) T .int * T T .int,T int * .T T .(E) T .int * T T .int,T int * T.,T (E.),T (E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,T,項(xiàng)目集,構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族 NFA確定化為D

47、FA的工作量較大，我們考慮直接構(gòu)造出項(xiàng)目集作為DFA的狀態(tài)，就可直接構(gòu)造DFA 通過閉包函數(shù)(CLOSURE)來求DFA一個(gè)狀態(tài)的項(xiàng)目集,如果I是文法G的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：a)I的項(xiàng)目都在CLOSURE(I)中b)若A B屬于CLOSURE(I)，則每一形如B 的項(xiàng)目也屬于CLOSURE(I)c)重復(fù)b)直到CLOSURE(I)不再擴(kuò)大 定義轉(zhuǎn)換函數(shù)如下：GOTO（I，X）= CLOSURE（J）其中：I為包含某一項(xiàng)目集的狀態(tài)，X為一文法符號(hào) J=任何形如AX 的項(xiàng)目| A X 屬于I,圓點(diǎn)不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核，唯一的例外是S S。因此用GOT

48、O（I，X）轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)所含項(xiàng)目集的核 使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X)構(gòu)造文法G的LR(0)的項(xiàng)目集規(guī)范族，步驟如下： a)置項(xiàng)目S S為初態(tài)集的核，然后對(duì)核求閉包CLOSURE（S S）得到初態(tài)的項(xiàng)目集b)對(duì)初態(tài)集或其它所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)GOTO(I，X)= CLOSURE(J)求出新狀態(tài)J的項(xiàng)目集c)重復(fù)b)直到不出現(xiàn)新的項(xiàng)目集為止,S . E E . T E .T + E T .(E) T .int * T T .int,S E .,E T. E T. + E,T int. * T T int.,T (. E) E .T E .T +

49、 E T .(E) T .int * T T .int,E T + E.,E T + . E E .T E .T + E T .(E) T .int * T T .int,T int * .T T .(E) T .int * T T .int,T int * T.,T (E.),T (E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,T,總結(jié)：構(gòu)造識(shí)別文法活前綴DFA的三種方法,一、根據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造NFA再確定化為DFA 二、求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的NFA再確定化為DFA 三、使用閉包函數(shù)

50、（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X)構(gòu)造文法G的LR(0)的項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識(shí)別活前綴的DFA,LR（0）項(xiàng)目集規(guī)范族的項(xiàng)目類型分為如下四種： 1）移進(jìn)項(xiàng)目 A a 2）待約項(xiàng)目 A B 3）歸約項(xiàng)目 A 4）接受項(xiàng)目 S S 一個(gè)項(xiàng)目集可能包含多種項(xiàng)目 a) 移進(jìn)和歸約項(xiàng)目同時(shí)存在。移進(jìn)-歸約沖突 b) 歸約和歸約項(xiàng)目同時(shí)存在。歸約-歸約沖突 LR(0)文法：若其LR(0)項(xiàng)目集規(guī)范族不存在移進(jìn)-歸約沖突或歸約-歸約沖突，稱為LR(0)文法。,LR(0)分析表的構(gòu)造,LR(0)分析表相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DAF的狀態(tài)轉(zhuǎn)換矩陣 LR(0)分

51、析表的構(gòu)造算法 書上p130, 倒數(shù)4行， A 改為 A a LR(0)分析器的工作過程,令包含S S 的項(xiàng)目集Ik的下標(biāo)k為分析器的初態(tài) LR(0)分析表的ACTION和GOTO表的構(gòu)造步驟如下： a) 若項(xiàng)目A a屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij ，當(dāng)a為終結(jié)符時(shí)，則置ACTIONk,a為Sjb) 若項(xiàng)目A 屬于Ik ，則對(duì)a為任何終結(jié)符或#，置ACTIONk,a = rj ，j為產(chǎn)生式在文法G中的編號(hào)c) 若GO(Ik,A)= Ij ，則置GOTOk,A=j，其中A為非終結(jié)符，j為某一狀態(tài)號(hào)d) 若項(xiàng)目SS 屬于Ik ，則置ACTIONk,# = acce) 其它填上“報(bào)錯(cuò)標(biāo)

52、志”,S . E E . T E .T + E T .(E) T .int * T T .int,S E .,E T. E T. + E,T int. * T T int.,T (. E) E .T E .T + E T .(E) T .int * T T .int,E T + E.,E T + . E E .T E .T + E T .(E) T .int * T T .int,T int * .T T .(E) T .int * T T .int,T int * T.,T (E.),T (E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,1,2,3

53、,4,5,6,7,8,9,10,11,SLR(1)分析,大多數(shù)適用的程序設(shè)計(jì)語言的文法不能滿足LR(0)文法的條件，即其規(guī)范族中會(huì)有含有沖突的項(xiàng)目集（狀態(tài)） 如果解決這種沖突？ 直覺：對(duì)于有沖突的狀態(tài)，向前查看一個(gè)符號(hào)，以確定采用的動(dòng)作,文法G：(0) S S(1) S rD (2) D D,i(3) D i,I0:S SS rD,I2: S rDD D,iD i,I3: S rD D D ,i,I4: D i ,I5: D D,i,I1: S S ,I6: D D,i ,S,r,i,D,i,LR(0)分析表,I3: S rD D D ,i,向前查看一個(gè)符號(hào)，看其是否是S的后跟符號(hào)（FOLLOW(S)）,若否則移進(jìn)，是則歸約。,SLR(1)分析表,一個(gè)LR(0)規(guī)范族中含有如下的項(xiàng)目集（狀態(tài)）II = X b , A , B 若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = 狀態(tài)I面臨某輸入符號(hào)a1) 若a=b，則移進(jìn)2) 若aFOLLOW(A), 則用產(chǎn)生式 A 進(jìn)行歸約3) 若aFOLLOW(B), 則用產(chǎn)生式 B 進(jìn)行歸約4) 此外，報(bào)錯(cuò) 若一個(gè)文法的LR(0)分析表