第五章語法——自下而上

1、第五章 語法分析 自下而上分析自下而上分析：從輸入串開始，逐步進(jìn)行“歸約”，直至歸 約到文法的開始符號(hào)。 5.1 自下而上分析基本問題n歸約 自下而上分析法是“移進(jìn)歸約”法。 模型：移進(jìn)歸約識(shí)別成功其他出錯(cuò)字符串：babAba#b#ba#A歸約5.1 自下而上分析基本問題1.輸入帶記錄待識(shí)別語句（單詞結(jié)束符#）2.讀頭自左向右掃描輸入串，初態(tài)指在最左單詞上，棧內(nèi)僅有#3.語法分析執(zhí)行動(dòng)作有：移進(jìn)讀入一單詞并壓入棧內(nèi)，讀頭下移一位歸約檢查棧頂若干符號(hào)是否為語法表中產(chǎn)生式右部，若是，用左部替換右部識(shí)別成功棧內(nèi)為文法開始符號(hào)，讀頭指向#否則，語法錯(cuò)誤programIdVar#語法分析程序分析表#輸入

2、串：下推棧，初態(tài)為#，字符“先進(jìn)后出”如：SaAcBeAAb|bBd分析：abbcdeSaAcBeAbdb5.1.2 規(guī)范規(guī)約簡述1.短語、直接短語、句柄n短語：已知文法GS，是文法G的一個(gè)句型，若S A且A，則稱是句型的相對于非終結(jié)符A的短語。n直接短語：若有SA且A，稱是句型的相對于規(guī)則A的直接短語。n句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。*例：G: E E+T | E-T | T T T*F | T/F | F F (E) | i 給出句型E+T*F+i的短語、直接短語和句柄。例： G： EE+T | T 句型E+T*F+i TT*F | F F(E) | i短語： E+T*F+

3、i， E+T*F， T*F，i直接短語： T*F，i句柄： T*F歸約方法：形成句柄則進(jìn)行歸約。abbcde AbaAbcde AbaAcde BdaAcBe SaAcBdS2.規(guī)范歸約： 假定是文法G的一個(gè)句子，稱序列n，n1， 0 是的一個(gè)規(guī)范歸約，則此序列滿足： （1）n （2）0為文法開始符，即0S （3）對任何i，0in， i1是從i經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部符號(hào)而得到的。 最左推導(dǎo)的逆過程最右歸約 最右推導(dǎo)的逆過程最左歸約 最右推導(dǎo)稱為規(guī)范推導(dǎo) 最左歸約稱為規(guī)范歸約SaAcBeAbdb5.2 算符優(yōu)先分析n直觀算符優(yōu)先法 對于文法，任何兩個(gè)相繼出現(xiàn)的終結(jié)符（ab或aQb），有下

4、列三種關(guān)系： a b a的優(yōu)先性等于b a b a的優(yōu)先性高于b a b a的優(yōu)先性低于b注意：這三個(gè)關(guān)系不同于數(shù)學(xué)中的“=”，“”，此處a b并不一定意味著b a，a b也不一定意味著 b a。5.2.1 算符優(yōu)先文法及優(yōu)先表的構(gòu)造1.算符文法(OG)：文法G，如果G中每條規(guī)則不能有形如ABC(A,B,CVN)的規(guī)則，則稱G為算符文法。2.設(shè)G是不含產(chǎn)生式的文法，對任何終結(jié)符a,bVT，A,B,CVN， (1)a bG中含有規(guī)則Aab或AaBb (2)a bG中含有規(guī)則AaB，而Bb或BCb (3)a bG中含有規(guī)則ABb，而Ba或BaCn若一個(gè)算符文法G 中任何終結(jié)符對(a,b)至多只滿足

5、下述三個(gè)關(guān)系之一： a b ，a b ，a b 則稱G是一個(gè)算符優(yōu)先文法(OPG)。如： EE+E | E*E | (E)| i 為算符文法，但不是算符優(yōu)先文法。 EE+E EE*E + * EE*E EE+E + *n注意：算符優(yōu)先文法中允許a b，b a同時(shí)存在，但不允許a b ，a b ，a b三種中任何兩種同時(shí)存在。例： G： EE+T | T TT*F | F FPF | P P(E) | i3.算符優(yōu)先關(guān)系的構(gòu)造 FIRSTVT(P)=a | Pa或P Qa，aVT，QVN LASTVT(P)=a | Pa或P aQ，aVT，QVN三種關(guān)系的計(jì)算： 關(guān)系：由產(chǎn)生式右部決定，形如ab

6、或aQb如：SaAcBe，Ab，AAb，Bd，BAb 有 a c c e 關(guān)系：求出每個(gè)符號(hào)的FIRSTVT，對于形如AaB就有a FIRSTVT(B)如上例：FIRSTVT(S)=a,FIRSTVT(A)=b, FIRSTVT(B)=b,d 關(guān)系：求出每個(gè)符號(hào)的LASTVT，對于形如ABb就有LASTVT(B) b如上例：LASTVT(S)=e，LASTVT(A)=b， LASTVT(B)=b,dG： S#S# Sif Eb then E else E EE+T | T TT*F | F F i EbbFIRSTVT(S)=#FIRSTVT(S)=ifFIRSTVT(E)=+,*,iFIRS

7、TVT(T)=*,iFIRSTVT(F)=iFIRSTVT(Eb)=bLASTVT(S)=#LASTVT(S)=else, +,*,iLASTVT(E)=+,*,iLASTVT(T)=*,iLASTVT(F)=iLASTVT(Eb)=bnFIRSTVT(P)算法： (1)若有Pa或PQa，則aFIRSTVT(P)； (2)若有PQ且aFIRSTVT(Q)，則aFIRSTVT(P)。nLASTVT(P)算法： (1)若有Pa或PaQ，則aLASTVT(P)； (2)若有PQ且aLASTVT(Q)，則aLASTVT(P)。5.2.1 算符優(yōu)先文法及優(yōu)先表的構(gòu)造例： G： E#E# EE+T | T

8、 TT*F | F FPF | P P(E) | i5.2.2 算符優(yōu)先分析算法n素短語：是一個(gè)短語，它至少含有一個(gè)終結(jié)符，且除自身之外不包含其它的素短語。n最左素短語：處于句型最左邊的素短語。（從語法樹看）n例：G: E E+T | T T T*F | F F PF | P P (E) | i 給出句型P*P+i的短語、素短語和最左素短語。2.句型的一般形式： #N1a1N2a2NnanNn+1# 其中Ni為非終結(jié)符或，ai為終結(jié)符。3.一個(gè)算法優(yōu)先文法G的任何句型的最左素短語是滿足如下條件的最左子串NjajNiaiNi+1：aj-1 ajaj aj+1,ai-1 aiai ai+14. 算

9、符優(yōu)先算法k=1; Sk=#; / S為下推棧 do把下一個(gè)輸入符號(hào)讀入Sym中； if(SkVT) j=k; else j=k-1; while(Sj Sym) / 素短語歸約可能為若干次 do / 找素短語的頭 Q=Sj; if(Sj-1VT) j=j-1; else j=j-2; while(Sj Q); 把Sj+1Sk歸約為某個(gè)N; k=j+1; Sk=N; / while if( sj Sym | sj=Sym )k=k+1; Sk=Sym; / 移進(jìn) else error(); while(Sym=#)n算符優(yōu)先算法根據(jù)運(yùn)算符優(yōu)先關(guān)系決定最左素短語。n只需知道把最左素短語歸約為某一

10、非終結(jié)符，不需知道其為何物。n算符優(yōu)先算法中的歸約是非規(guī)范歸約。n例：已知文法G，用算符優(yōu)先算法分析 if b then i else i #G: S#S# Sif Eb then E else E EE+T | T TT*F | F Fi Ebb5.2.3 優(yōu)先函數(shù)nf(a)棧內(nèi)優(yōu)先函數(shù)ng(a)比較優(yōu)先函數(shù)（棧外（源程序）運(yùn)算符的優(yōu)先函數(shù)）na,bVT 若a b，則f(a) g(b)優(yōu)先關(guān)系數(shù)學(xué)運(yùn)算關(guān)系n幾點(diǎn)說明： 優(yōu)先函數(shù)優(yōu)先關(guān)系表。 有些優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)。 若存在一對優(yōu)先函數(shù)f，g，則存在無窮多對優(yōu)先函數(shù)。 f(a)=f(a)+c g(a)=g(a)+c優(yōu)先函數(shù)算法n用關(guān)系圖法

11、構(gòu)造優(yōu)先函數(shù)對aVT(包括#)用下標(biāo)fa，ga為結(jié)點(diǎn)名畫出2n個(gè)結(jié)點(diǎn)；a,bVT ，若a b或a b，則從fa畫一箭弧到gb；若a b或 a b，則從gb畫一箭弧到fa；給每個(gè)結(jié)點(diǎn)賦一個(gè)數(shù)值，此數(shù)等于從該結(jié)點(diǎn)出發(fā)到所能到達(dá)結(jié)點(diǎn)（包括出發(fā)結(jié)點(diǎn)自身在內(nèi)）的個(gè)數(shù)，賦給fa的數(shù)值作為f(a)的值，賦給gb的數(shù)值作為g(b)的值；檢查所構(gòu)造出的函數(shù)f和g，看它同原來的優(yōu)先關(guān)系表是否矛盾，若沒有矛盾，則f和g就是所要的優(yōu)先函數(shù)；若有矛盾，則不存在優(yōu)先函數(shù)。n例：已知文法G： S#S# S*A A* | 0A1求文法所有非終結(jié)符的FIRSTVT和LASTVT構(gòu)造優(yōu)先關(guān)系表如果可能，構(gòu)造優(yōu)先函數(shù)nFIRSTV

12、T(S)=# LASTVT(S)=# FIRSTVT(S)=* LASTVT(S)=*,1 FIRSTVT(A)=*,0 LASTVT(A)=*,1f0f1f*fg0g1g*g優(yōu)先關(guān)系表優(yōu)先函數(shù)關(guān)系圖S#S#S*AA* | 0A15.2.4 算法優(yōu)先分析中的出錯(cuò)處理n出錯(cuò)情況： (1)棧頂終結(jié)符與下一個(gè)輸入符間不存在任何優(yōu)先關(guān)系； (2)找到某一“句柄”（素短語），但不存在任一產(chǎn)生式的右部與它匹配。n對第(1)種錯(cuò)誤處理方法為：改變、插入或刪除符號(hào)。n對第(2)種錯(cuò)誤處理方法為：打印錯(cuò)誤信息（找到類似的產(chǎn)生式右部）。5.3 LR分析法nLR(0)nSLR(1)nLR(1)nLALR(1)5.3

13、.1 LR分析器1.組成 總控程序不依賴于文法 分析表依賴于文法 分析棧 狀態(tài)棧 文法符號(hào)棧2.模型ai#總控程序分析表輸入串：狀態(tài)棧Action表Goto表#S1x1 Smxm符號(hào)棧5.3.1 LR分析器3.分析表 Action表ActionSj,ai= Sk(移進(jìn)) rk(歸約) accept 出錯(cuò)Goto表GotoSj,Ai=k分析表 ActionS,a規(guī)定了棧頂狀態(tài)為S時(shí)遇到輸入符號(hào)a應(yīng)執(zhí)行的動(dòng)作：(1)移進(jìn)：把S,a的下一狀態(tài)S=GotoS,a和輸入符號(hào)a推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。(2)規(guī)約：用產(chǎn)生式A進(jìn)行歸約。若|=r，歸約動(dòng)作為A，則去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r變

14、成棧頂狀態(tài)，然后把Sm-r,A的下一狀態(tài)S=GotoSm-r,A和文法符號(hào)A推進(jìn)棧。(3)接受accetpt：宣布分析成功，停止分析器的工作。(4)報(bào)錯(cuò)：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。5.3.2 LR(0)項(xiàng)目集族與LR(0)分析表的構(gòu)造一、前綴、活前綴、可歸前綴1.前綴：符號(hào)串的任意部首。 abc：，a，ab，abc2.活前綴：文法G的句型，存在規(guī)范推導(dǎo)SA，則的前綴稱為的活前綴。3.可歸前綴： SA則稱為可歸前綴。 含有句柄的活前綴稱為可歸前綴。*RR二、LR(0)項(xiàng)目集1.LR(0)項(xiàng)目：文法G的每條規(guī)則右部的任意位置加上一圓點(diǎn)構(gòu)成的式子。 AXYZ AXYZ AXYZ AXYZ

15、 AXYZ AX1X2Xi-1Xi Xi+1Xn對應(yīng)四個(gè)項(xiàng)目已在棧內(nèi)符號(hào)尚未進(jìn)棧符號(hào)A 只有一個(gè)項(xiàng)目A2.識(shí)別文法活前綴的NFA(1)拓廣文法 SS 對文法的開始符S加入規(guī)則SS例：已知文法G： SE E aA|bB A cA|d B cB|d(2)給出文法的所有LR(0)項(xiàng)目。 凡圓點(diǎn)在串的最右邊的項(xiàng)目稱為終止項(xiàng)目(歸約項(xiàng)目)(3)設(shè)項(xiàng)目i為XX1X2Xi-1 XiXn ，項(xiàng)目j為XX1X2Xi Xi+1Xn ，則從項(xiàng)目i畫一條弧至項(xiàng)目j。(4)對于項(xiàng)目i為A B (BVN)，則從i畫一弧射向B的項(xiàng)目。 Xi例：已知文法G： SE E aA|bB A cA|d B cB|d 1. SE 2.

16、 SE 3. EaA 4. EaA 5. EaA6. AcA 7. AcA 8. AcA9. Ad 10. Ad11.EbB 12.EbB 13.EbB14. BcB 15.BcB 16. BcB17. Bd 18. Bd例：已知文法G： SE E aA|bB A cA|d B cB|d 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad11.EbB 12.EbB 13.EbB 14. BcB 15.BcB16. BcB 17. Bd 18. Bd131124126717958101813141516acAAEb

17、BBcdd三、LR(0)項(xiàng)目集規(guī)范族的構(gòu)造算法nLR(0)項(xiàng)目集規(guī)范族：構(gòu)成識(shí)別一個(gè)文法活前綴的DFA的項(xiàng)目集（狀態(tài)）的全體。n算法：(1)拓廣文法GS：增加SS G(2)設(shè)I0是拓廣文法G的一個(gè)狀態(tài)項(xiàng)目集，定義和構(gòu)造I的閉包c(diǎn)losure(I)。 a) I中項(xiàng)目closure(I) b) 若A B (BVN)，則規(guī)定B對應(yīng)的項(xiàng)目B closure(I)。 c) 重復(fù)b)直至closure(I)不再增加為止。(3)狀態(tài)轉(zhuǎn)換函數(shù)Go(Ik,x)=closure(Ij) Ij=A x | A x Ik n如： S Aa|Bb A Cb|d C De|e Bd Df I=S Aa， S Bb clo

18、sure(I)=S Aa， S Bb ，B d， A Cb， A d， C De， C e， D f 例：(1) SE (2) EaA (3) EbB (4) AcA (5) Ad (6) B cB (7) Bd構(gòu)造該文法可識(shí)別活前綴的DFA。SEEaAEbBI0EaAAcAAdI2AcAAcAAdI6AcAI7EaAI4AdI5SEI1EbBBcBBdI3BcBBcBBdI10BcBI11EbBI9BdI8abEcAdcBdccABddnSS “接受”態(tài)nA B (BVN) 待約項(xiàng)目nA x (xVT) 移進(jìn)項(xiàng)目nA 歸約項(xiàng)目n在同一項(xiàng)目集中后繼符號(hào)相同則后繼狀態(tài)相同。n在不同項(xiàng)目集中和前面

19、對應(yīng)相同項(xiàng)目的后繼狀態(tài)相同。四、LR(0)分析表的構(gòu)造設(shè)LR(0)項(xiàng)目集規(guī)范族為C=I0,I1,In SS稱為初態(tài) (1)若項(xiàng)目AxIk ，GoIk,x=Ij 若xVT，置ActionIk,x=Sj 若xVN，置GotoIk,x=j(2)若項(xiàng)目SSIk ，則置ActionIk,#=acc(3)若項(xiàng)目AIk ，則a VT (包括#)，置ActionIk,a=rj (j指第j條產(chǎn)生式)例：(1) SE (2) EaA (3) EbB (4) AcA (5) Ad (6) B cB (7) Bd構(gòu)造LR(0)分析表。SEEaAEbBI0EaAAcAAdI2AcAAcAAdI6AcAI7EaAI4Ad

20、I5SEI1EbBBcBBdI3BcBBcBBdI10BcBI11EbBI9BdI8abEcAdcBdccABdd對bccd#進(jìn)行分析： 狀態(tài)棧 符號(hào)棧 輸入串1 0 # bccd#2 03 #b ccd#3 0310 #bc cd#4 0310 10 #bcc d#5 0310 10 8 #bccd #6 0310 10 11 #bccB #7 0310 11 #bcB #8 039 #bB #9 01 #E # accnLR(0)文法 一文法若其LR(0)的分析表無沖突，則稱文法為LR(0)文法。nLR(0)項(xiàng)目集相容性 無移進(jìn)項(xiàng)目、歸約項(xiàng)目并存 無歸約項(xiàng)目并存5.3.3 SLR分析表的構(gòu)

21、造n問題的提出real ，i i(0) SS (1) SrD(2) DD,i (3) Di (0) SS (1) SrD(2) DD,i (3) Di I1SSSrDSSI0SrDDD,iDiI2SrDDD,iI3DiI4DD,iI5DD,iI6SrDi，iLR(0)分析表產(chǎn)生移進(jìn)歸約沖突(0) SS (1) SrD(2) DD,i (3) Di LR(0)分析表產(chǎn)生移進(jìn)規(guī)約沖突n解決辦法：考察當(dāng)用句柄rD歸約成S時(shí)，S的后跟符號(hào)集FOLLOW(S)。若FOLLOW(S)不包含當(dāng)前所有移進(jìn)項(xiàng)目的移進(jìn)符號(hào)集合，則這種移進(jìn)歸約沖突可解決 。nFOLLOW(S)=#，移進(jìn)符號(hào)只有，則在狀態(tài)3中當(dāng)遇到

22、，時(shí)做“移進(jìn)”，遇到時(shí)做歸約。(0) SS (1) SrD(2) DD,i (3) Di LR(0)分析表分析表變成n假定一個(gè)LR(0)規(guī)范族中包含項(xiàng)目集(狀態(tài))I：I=Xb， A， B，即在該項(xiàng)目集中包含移進(jìn)歸約沖突和歸約歸約沖突，解決沖突的辦法為： 考察FOLLOW(A)和FOLLOW(B),若這兩個(gè)集合不相交且均不包含b，那么當(dāng)狀態(tài)I面臨輸入符a時(shí)，可采用如下決策執(zhí)行動(dòng)作： (1)若a=b，則移進(jìn)； (2)若aFOLLOW(A)，則用A歸約； (3)若aFOLLOW(B)，則用B歸約。推廣至一般：n假定LR(0)規(guī)范族的某一個(gè)項(xiàng)目集I含有m個(gè)移進(jìn)項(xiàng)目：A1a11， A2a22， Amam

23、m，同時(shí)含有n個(gè)歸約項(xiàng)目 B1， B2， Bn，若a1,a2, ,am，F(xiàn)OLLOW(B1), FOLLOW(Bn)兩兩不相交，則隱含在I中的動(dòng)作沖突可通過檢查當(dāng)前輸入符a屬上述n+1個(gè)集合中的哪一個(gè)得到解決，方法為： (1)若a是某個(gè)ai (i=1,m) ，則移進(jìn)； (2)若aFOLLOW(Bi) i=1,n ，則用Bi歸約； (3)此外，報(bào)錯(cuò)。二、SLR(1)分析表的構(gòu)造方法1.把G拓廣為G，對G構(gòu)造LR(0)項(xiàng)目集C和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)。2.設(shè)C=I0,I1,In，令SS的Ik的下標(biāo)k為初態(tài)。 (a)若項(xiàng)目Aa屬于Ik，且GoIk,a=Ij，a為終結(jié)符，則置Actionk,a

24、為Sj； (b)若項(xiàng)目A屬于Ik，則對任何終結(jié)符a(包括) ，aFOLLOW(A)，置Actionk,a為rj ，j為產(chǎn)生式A在文法中的編號(hào)； (c)若項(xiàng)目SS屬于Ik，則置Actionk,#為acc； (d)若GoIk,A=Ij，則置Gotok,A=j； (e)凡不能用上述規(guī)則填入信息的空白格，均置“出錯(cuò)信息”。n按上述方法構(gòu)造的含有Action和Goto兩部分的分析表，若每個(gè)入口不含多重定義（沖突），則該文法稱為SLR(1)文法。(0) SS (1) SrD(2) DD,i (3) Di I1SSSrDSSI0SrDDD,iDiI2SrDDD,iI3DiI4DD,iI5DD,iI6SrDi

25、，iSLR(1)分析表FOLLOW(D)=， ,# FOLLOW(S)= # 5.3.4 規(guī)范LR分析表的構(gòu)造 LR(1)分析表n問題的提出文法G：(0) SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae I0I1SSSaAdSbAcSaecSbedSSSaAdSaec AeI2SaAdI4SbASbAcSbed AeI3Saec AeI5eSbAcI6ASbed AeI7eSaAddI8SaeccI9SbAccI10SbeddI11anI5:Saec ,Ae FOLLOW(A)=c,dc 該文法不是SLR(1)文法nI7:Sbed ,Ae FOLLO

26、W(A)=c,ddLR(0)SLR(1)LR(1)項(xiàng)目集不相容相關(guān)集合相交二、LR(1)項(xiàng)目集的構(gòu)造1.項(xiàng)目I的閉包c(diǎn)losure(I) (1)I的任何項(xiàng)目都屬于closure(I)； (2)若AB,a closure(I)， B為一產(chǎn)生式，則對bFIRST(a)， B,b closure(I)； (3)重復(fù)(2)，直至不產(chǎn)生新項(xiàng)目為止。 二、LR(1)項(xiàng)目集的構(gòu)造2.轉(zhuǎn)換函數(shù)的構(gòu)造 Go(I,x)=closure(J) J=任何形如Ax,a的項(xiàng)目 | Ax,aI 最初項(xiàng)目集C= SS,# 。n文法G的LR(1)項(xiàng)目集族C的構(gòu)造算法：Begin C:=closure(SS,# ); Repeat for C中每個(gè)項(xiàng)目集I和G的每個(gè)符號(hào)x， do if Go(I,x)非空且不屬于C，Then 把Go(I,x)加入C中 Until C不再增大End例：文法G：(0) SS (1) SBB (2) BaB (3) BbaI1SS，#SBB，#BaB，a/bBb，a/bSS,#SBB,#BaB,# Bb,#I2SaBaB,a/bBaB,a/b Bb,a/bI3SBB,#bI5BI0I4Bb,a/bbaBaB,#BaB,# Bb,#I6Bb,#B