版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、1第五章 語法分析自下而上分析 5.1 自下而上分析基本問題5.2 算符優(yōu)先分析5.3 LR分析法5.4 語法分析器的自動產生工具YACC(略)25.1 自下而上分析基本問題一、歸約1.“移進規(guī)約”的思想: 用一個寄存符號的先進后出棧,把輸入符號一個一個地移進棧里,當棧頂形成某個產生式的一個候選式時,即把棧頂的這一部分替換成(歸約為)該產生式的左部符號。3舉例:已知文法G為(1)SaAcBe (2)Ab (3)AAb (4)Bd 及輸入串abbcde歸約過程如下:eBcAa進9BcAa歸8dcAa進7cAa進6bAa進4Aa歸5Aa歸3ba進2S歸10a進1動作:步驟:5.1 自下而上分析基本
2、問題42.自下而上分析的關鍵:“可歸約串”如何精確定義?“可歸約串”的不同定義,形成了不同的自下而上的分析方法。從上例的步驟()可發(fā)現(xiàn)5.1 自下而上分析基本問題“算符優(yōu)先分析”中:“最左素短語”“可歸約串”“規(guī)范歸約分析”中:“句柄”“可歸約串”例:5.自下而上分析的中心問題: 怎樣判斷棧頂的符號串的可歸約性以及如何歸約。5.1 自下而上分析基本問題各種自下而上分析法的共同特點: 邊輸入單詞符號(移進符號棧),邊歸約。即:在從左到右移進輸入串的過程中,一旦發(fā)現(xiàn)棧頂呈現(xiàn)可歸約串就立即進行歸約。6二.規(guī)范歸約簡述5.1 自下而上分析基本問題(1)短語:若且,則稱是句型相對于 非終結符的短語。*
3、+(2)直接短語:若,則稱是句型相對于規(guī)則 的直接短語。(3)句柄:一個句型的最左直接短語成為該句型的句柄。.定義:令是一個文法,是的開始符號, 假定是文法的一個句型, 即 *75.1 自下而上分析基本問題規(guī)范規(guī)約中的概念短語:直接短語:句柄:是句型的短語僅當 S A 且A S.A.A =最左直接短語8例1:EE+T | TTT*F | FF(E) | i i1*i2+i3短語:直接短語:句柄: i1,i2,i3,i1*i2,i1*i2+i3 i1,i2,i3i19練習:EE+T | TTT*F | FF(E) | i E+T*F+i 短語:直接短語:句柄: E+T*F+i, E+T*F, T
4、*F, i T*F, i T*FEETETTFFi+*10例2:利用句柄對句子進行歸約5.1 自下而上分析基本問題句型歸約規(guī)則aAbcdeaAcdeaAcBeS對文法(1)SaAcBe; (2)Ab; (3)AAb; (4)Bd 的句子abbcde進行歸約。 abbcde(2)Ab(3)AAb(4)Bd(1)SaAcBe112.規(guī)范歸約規(guī)范歸約是關于的一個最右推導的逆過程.5.1 自下而上分析基本問題例: S aAcBe aAcde aAbcde abbcde (1) (2) (3) (4)(1)定義:設是文法G的一個句子,我們稱序列n, n-1,0 是的一個規(guī)范歸約,若此序列滿足:n=;0=
5、S,S為文法開始符號;對任何i,0in, i-1是經把i的句柄替換為相應產生式的左部符號而得到的.12(2)規(guī)范推導:即最右推導.5.1 自下而上分析基本問題 規(guī)范句型:由規(guī)范推導所得到的句型,稱為規(guī)范句型. 若文法G是無二義的,則規(guī)范推導(最右推導)的逆過程必是規(guī)范歸約(最左歸約)。(3)規(guī)范歸約的實質:在移進過程中,當發(fā)現(xiàn)棧頂呈現(xiàn)句柄時, 就用相應產生式的左部符號進行替換。2.規(guī)范歸約規(guī)范歸約的中心問題:如何尋找或確定一個句型的句柄。給出了尋找句柄的不同算法就給出了不同的規(guī)范歸約方法。13三、符號棧的使用1.與LL(1)方法區(qū)別:符號棧輸入串開始#W#分析成功#S#符號棧輸入串開始#SW#
6、分析成功#LL(1)分析:5.1 自下而上分析基本問題142.舉例:規(guī)范歸約(課本88頁例5.3) 語法分析對符號棧的使用有四類操作:5.1 自下而上分析基本問題“移進”指把輸入串的一個符號移進棧.“歸約”指發(fā)現(xiàn)棧頂呈可規(guī)約串,并用適當的相應符號去 替換這個串.“接受”指宣布最終分析成功.“出錯處理” 指發(fā)現(xiàn)棧頂的內容與輸入串相悖,分析工 作無法正常進行,此時需調用出錯處理程序.15例2:有文法:E-E+T|TT-T*F|FF-(E)|i對輸入串 i1+i2*i3 的規(guī)范規(guī)約過程:16 動作 棧 輸入緩沖區(qū)1) 準備 # i1+i2*i3#2) 移進 #i1 +i2*i3#3) 歸約 Fi #
7、F +i2*i3#4) 歸約 TF #T +i2*i3# 5) 歸約 ET #E +i2*i3#6) 移進 #E+ i2*i3#7) 移進 #E+i2 *i3#8) 歸約 Fi #E+F *i3#9) 歸約 TF #E+T *i3# 10) 移進 #E+T* i3#11) 移進 #E+T*i3 #12) 歸約 Fi #E+T*F #13) 歸約 TT*F #E+T #14) 歸約 EE+T #E # 15) 接受所得的結果是:用產生式序列表示語法分析樹E-E+T|TT-T*F|FF-(E)|ii1 + i2 * i3FTEFTFTE175.2 算符優(yōu)先分析算符優(yōu)先分析: 不是一種規(guī)范歸約法,是
8、一種自下而上的語法分析法,關鍵在于規(guī)定算符(即終結符)之間的優(yōu)先順序和結合性質,借助這種優(yōu)先關系尋找“可歸約串”進行歸約。特點:有利于表達式分析,宜于手工實現(xiàn)。18一、算符優(yōu)先文法及優(yōu)先表構造1.算符優(yōu)先文法算符文法:一個文法,如果它的任一產生式的右部都不含 兩個相繼(并列)的非終結符,即不含如下形 式的產生式右部:則我們稱該文法為算符文法。5.2 算符優(yōu)先分析19算符優(yōu)先文法:如果一個算符文法G中的任何終結符對(a,b) 至多只滿足下述三關系之一: a b,a b,a b 則稱G是一個算符優(yōu)先文法。 假定是一個不含-產生式的算符文法。對于任何一對終結符a、b,我們說: a b當且僅當 文法G
9、中含有形如 Pab或aQb的產生式;5.2 算符優(yōu)先分析+ (2) a b當且僅當 G中含有形如 PaR 的產生式, 而Rb或R Qb;+ (3) a b當且僅當 G中含有形如 PRb的產生式, 而R a或R aQ 。+ + FIRSTVT(R)LASTVT(R)20按定義,我們用以下兩條規(guī)則構造集合FIRSTVT(P):(1)若有產生式Pa或PQa, 則aFIRSTVT(P);(2)若aFIRSTVT(Q), 且有產生式PQ, 則aFIRSTVT(P)。返回 5.2 算符優(yōu)先分析構造集合FIRSTVT(P):構造集合LASTVT(P):按定義,我們用以下兩條規(guī)則構造集合LASTVT(P):(
10、1)若有產生式Pa或PaQ, 則aLASTVT(P);(2)若aLASTVT(Q), 且有產生式PQ, 則aLASTVT(P)。215.2 算符優(yōu)先分析文法G:(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|iFIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 22(1)a b:找出滿足“ ”的所有終結符對。(借助于FIRSTVT(P)和LAST
11、VT(P)實現(xiàn))5.2 算符優(yōu)先分析2.構造優(yōu)先表(3)構造出優(yōu)先表(2)ab,ab:找出滿足“”和“”的所有終結符對。ab: 有形如aP的候選,且bFIRSTVT(P);ab: 有形如Pb的候選,且aLASTVT(P)。23另:“”是作為語句的起始和結束標記,認為存在候選式: #開始符號#(1)#=#(2)#5.2 算符優(yōu)先分析24例:優(yōu)先關系和優(yōu)先表考慮文法G:(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i5.2 算符優(yōu)先分析FIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(
12、,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 25按定義,我們可得文法G終結符對的優(yōu)先關系表,如下所示:+*i()#+*i()# (1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i26返回按定義,我們可得文法G終結符對的優(yōu)先關系表,如下所示:+*i()#+*i()#對于G的任何終結對(a,b),至多只有一種關系成立。 因此,G是一個算符優(yōu)先文法。27二、算符優(yōu)先分析算法1.最左素短語 素短語:是指這樣的一個短語,它至少含有一個終結符,并且, 除它自身之外不再含任何更小的素短
13、語。 最左素短語:指處于句型最左邊的那個素短語。5.2 算符優(yōu)先分析28練習:EE+T | TTT*F | FF(E) | i 練習:(1)EE+T|T(2)TT*F|F(3)FPF|P(4)P(E)|i29一個算符優(yōu)先文法G的任何句型的最左素短語是滿足 如下條件的最左子串:NjajNiaiNi+15.2 算符優(yōu)先分析aj-1 ajaj aj+1, ,ai-1 aiai ai+1句型的一般形式:#N1a1N2a2 aj-1 NjajNiaiNi+1ai+1 NnanNn+1#N1a1N2a2 aj-1 ai+1 NnanNn+1#302.算法 過程:讀入一個輸入符號a, 然后比較棧頂終結符a。
14、Si存放“文法符號”的分析棧始終指向VT符號始終指向棧頂存放“輸入符號”的字符變量用于存放待比較的終結符號:j5.2 算符優(yōu)先分析31K:=1; SK:=#; REPEAT 把下一個輸入符號讀進a中; IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sja DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把 Sj+1Sk歸約為某個N; k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sja THEN BEGIN k:=k+1; Sk:=a END EL
15、SE ERROR;UNTIL a=#aj-1 aj aj+1,ai-1 ai ai+1Sj Q Sk=Q a32REPEATQ:=S j;IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q使得Q不斷向左移,指向新終結符使得j指向VT左符號Sj與右符號Q之間還可能滿足:Sj Q 不可能出現(xiàn),若成立則前面已經歸約過了;Sj Q 此時,符合“最左素短語” 定義,一直repeat;S j與Q無優(yōu)先關系不可能出現(xiàn), 若成立則前面已經報告“Error”5.2 算符優(yōu)先分析335.2 算符優(yōu)先分析+*i()#+*i()#步驟分析棧剩余輸入串動作 1 # i+i*ii #
16、 2 #i +i*ii # 移進 #*R=RS A a B a=*R=RbFirst( a)b, a71(2)GO(I,X) = CLOSURE(J)AX, a IAX, a J72例:(0)SS(1)SBB (2)BaB(3)BbLR(1)項目集規(guī)范族:I0:SS, # S BB , B aB, B b,#a/ba/bI1:SS , #I2:S BB ,# B aB, B b,#I3: Ba B,a/b B aB, B b,a/ba/bI4: B b , a/bI5:S BB ,#I6: Ba B,# B aB, B b,#I7: B b , #I8: Ba B ,a/bI9: Ba B ,
17、#73狀態(tài)ACTIONGOTOab#SB012345678974練習:若有文法GS:SS;M|MMMbD|DDD(S)|(1)證明GS是SLR文法,并構造它的分析表;(2)給出GS的LR(1)項目集規(guī)范族中的I0。75五、LALR分析表的構造同心集的合并:76同心集的合并 不會產生新的移進-歸約沖突 但會產生新的歸約-歸約沖突A , aB , bA , bB , aA , a/bB , b/b77五、LALR分析表的構造1、SLRLR(1)LALR(1)之間的關系LALR(1)一種折衷的方法對于同一個文法,LALR分析表永遠具有相同數目的狀態(tài)5.3 L分析法782、同義集合并 (1)同心集:若
18、兩個LR(1)項目集,除去搜索符外,這兩 個集合相同,則稱它們是同心集 (2)引出的問題 A.同心集合并不會產生“移進歸約”沖突 證明:(反證)假設合并后才存在“移進歸約”沖突,則:對當前輸入符號a,項目A ,a要求歸約 項目Ba ,b要求移進既然兩項目處于合并后的一個集合中,則:合并前,必c、d,使得A ,a與Ba ,b 已同處于某一集合中。即合并前,已有LR(1)項目集 存在“移進歸約”沖突故同心集合并不會產生“移進歸約”沖突 B.同心集合并會產生“歸約歸約”沖突5.3 L分析法79例:考慮文法(0)SS(1)SaAd|bBd|aBe|bAe(2)Ac(3)Bc項目集:Ac ,d,Bc ,e Ac ,e,Bc ,d(合并)Ac ,d/e,Bc ,d/e問題:面臨a=d/e時,采用哪一個歸約?5.3 L分析法803、構造LALR(1)分析表的步驟:(1)文法拓廣:
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 校友合租宿舍合同范本
- 校園食品安全衛(wèi)生檢查協(xié)議
- 人力資源復印機租賃合同
- 家庭陽臺植物擺放租賃合同
- 煙草種植園藥品研發(fā)合同
- 戶外瑜伽活動微站租賃合約
- 遠程醫(yī)療服務協(xié)議
- 旅行社導購員聘用合同
- 旅游項目開發(fā)審批指南
- 農業(yè)機械傷害死亡賠償
- 醫(yī)院會計實務操作培訓課件
- 《江蘇省建筑業(yè)10項新技術(2021)》
- 高中化學實驗員招聘考試試卷及評分標準
- ()國民經濟行業(yè)分類(2019修改版-)
- 氣體檢測報警儀的檢定校準
- 六年級上冊數學課件-6.1 認識百分數丨蘇教版 (共18張PPT)
- 河北省地圖介紹模板
- 全國職業(yè)英語技能大賽選拔賽職場應用樣題
- 設備安全運行檢查評分表
- 倉庫收貨臺賬
- 木結構設計規(guī)范
評論
0/150
提交評論