




已閱讀5頁,還剩3頁未讀, 繼續(xù)免費閱讀
版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
第四章 詞法分析p72 1.構造正規(guī)式1(0|1)*101相應的dfa. 答案 先構造nfa 確定化 0 1 x a a a ab ab ac ab ac a aby aby ac ab 重新命名,令ab為b、ac為c、aby為d 0 1 x a a a b b c b c a d d c b dfa: 3.將下圖確定化:答案 0 1 s vq qu vq vz qu qu v quz vz z z v z quz vz quz z z z 重新命名,令vq為a、qu為b、vz為c、v為d、quz為e、z為f。 0 1 s a b a c b b d e c f f d f e c e f f f dfa: 4.把下圖最小化:答案 初始分劃得0:終態(tài)組0,非終態(tài)組1,2,3,4,5 對非終態(tài)組進行審查: 1,2,3,4,5a 0,1,3,5 而0,1,3,5既不屬于0,也不屬于1,2,3,4,5 4 a 0,所以得新分劃 1:0,4,1,2,3,5 對1,2,3,5進行審查: 1,5 b 4 2,3 b 1,2,3,5,故得新分劃 2:0,4,1, 5,2,3 1, 5 a 1, 5 2,3 a 1,3,故狀態(tài)2和狀態(tài)3不等價,得新分劃 3:0,2,3,4,1, 5 這是最后分劃了最小dfa: 5.構造一個dfa,它接收=0,1上所有滿足如下條件的字符串:每個1都有0直接跟在右邊。并給出該語言的正規(guī)式和正規(guī)文法。 答案 按題意相應的正規(guī)表達式是0*(0 | 10)*0*或0*( 100*)*0* 構造相應的dfa,首先構造nfa為 用子集法確定化 i i0 i1 s 0 1 x,0,1,3,y 0,1,3,y 2 1,3,y 0,1,3,y 0,1,3,y 1,3,y 1,3,y 2 2 / 2 1 2 3 4 2 2 4 4 3 3 3 dfa:可最小化,終態(tài)組為1,2,4,非終態(tài)組為3,1,2,40 1,2,4,1,2,41 3,所以1,2,4為等價狀態(tài),可合并。 8給出下列文法所對應的正規(guī)式: s-0a|1b a-1s|1 b-0s|0 答案 解方程組s的解: s=0a|1b a=1s|1 b=0s|0 將a、b產(chǎn)生式的右部代入s中 s=01s|01|10s|10=(01|10)s|(01|10) 所以:s= (01|10)*(01|10) 第五章 自頂向下優(yōu)先分析法p991. 文法 s-a|(t) t-t,s|s (1) 對(a,(a,a)和(a,a),(a),a)的最左推導。 (2)對文法g改寫,然后對每個非終結(jié)符寫出不帶回溯的遞歸子程序。 (3)經(jīng)改寫后的文法是否為ll(1)的?給出它的預測分析表。 (4)給出輸入串(a,a)#的分析過程,并說明該串是否為g的句子。 答案 (1) 對(a,(a,a)的最左推導為: s=(t) =(t,s) =(s,s) =(a,s) =(a,(t) =(a,(t,s) =(a,(s,s) =(a,(a,s) =(a,(a,a) 對(a,a),(a),a) 的最左推導為: s=(t) =(t,s) =(s,s) =(t),s) =(t,s),s) =(t,s,s),s) =(s,s,s),s) =(t),s,s),s) =(t,s),s,s),s) =(s,s),s,s),s) =(a,s),s,s),s) =(a,a),s,s),s) =(a,a),s),s) =(a,a),(t),s) =(a,a),(s),s) =(a,a),(a),s) =(a,a),(a),a) (3)改寫文法為: 0) s-a 1) s- 2) s-( t ) 3) t-s n2 4) n2-, s n2 5) n2- first follow s a ( # , ) t a ( ) n2 , ) 對左部為n2的產(chǎn)生式可知: first (-, s n2)=, first (-)= follow (n2)=) , )= 所以文法是ll(1)的。 預測分析表 a ( ) , # s -a - -( t ) t -s n2 -s n2 -s n2 n2 - -, s n2 也可由預測分析表中無多重入口判定文法是ll(1)的。 (4)對輸入串(a,a)#的分析過程為: 步驟 狀態(tài)棧 當前字符 剩余輸入串 操作 1 #s ( a,a)# s-(t) 2 #)t( ( a,a)# 匹配 3 #)t a ,a)# t-sn2 4 #)n2s a ,a)# s-a 5 #)n2a a ,a)# 匹配 6 #)n2 , a)# n2-,sn2 7 #)n2s, , a)# 匹配 8 #)n2s a )# s-a 9 #)n2a a )# 匹配 10 #)n2 ) # n2- 11 #) ) # 匹配 12 # # 可見輸入串(a,a)#是文法的句子。 3文法: s-mh|a h-lso| k-dml| l-ehf m-k|blm 判斷g是否為ll(1)文法,如果是,構造ll(1)分析表。 答案 源文法g展開為: 0) s-m h 1) s-a 2) h-l s o 3) h- 4) k-d m l 5) k- 6) l-e h f 7) m-k 8) m-b l m first follow s a,d,b,e #,o m d, ,b e,#,o h ,e #,f,o l e a,d,b,e,o,# k d, e,#,o 預測分析表 a o d e f b # s -a -mh -mh -mh -mh -mh m -k -k -k -blm -k h - -lso - - l -ehf k - -dml - - 由預測分析表中無多重入口判定文法是ll(1)的。 第六章 自底向上優(yōu)先分析法p1161、已知文法gs為: sa|(t) tt,s|s (1)計算gs的firstvt和lastvt。 (2)構造gs的算符優(yōu)先關系表并說明gs是否未算符優(yōu)先文法。 (3)計算gs的優(yōu)先函數(shù)。 (4)給出輸入串(a,a)#和(a,(a,a)#的算符優(yōu)先分析過程。 答案 (1) firstvt和lastvt firstvt lastvt s a、( a、) t ,、a、( ,、a、) (2) 算符優(yōu)先關系 a ( ) , # a ( ) , # (3) 對應的算符優(yōu)先函數(shù)為: a ( ) , # s 2 1 2 2 2 1 t 3 3 1 1 3 1 (4) 句子(a,a)#分析過程如下: 步驟 棧 優(yōu)先關系 當前符號 剩余輸入串 移進或歸約 1 # #( ( a,a)# 移進 2 #( (a a ,a)# 移進 3 #(a a, , a)# 歸約 4 #(f (, , a)# 移進 5 #(f, ,a a )# 移進 6 #(f,a a) ) # 歸約 7 #(f,f ,) ) # 歸約 8 #(f () ) # 移進 9 #(f) )# # 歸約 10 #f # # 接受 句子(a, (a, a)分析過程如下: 步驟 棧 優(yōu)先關系 當前符號 剩余輸入串 移進或歸約 1 # #( ( a,(a,a)# 移進 2 #( (a a , (a,a)# 移進 3 #(a a, , (a,a)# 歸約 4 #(f (, , (a,a)# 移進 5 #(f, ,( ( a,a)# 移進 6 #(f,( (a a ,a)# 移進 7 #(f,(a a, , a)# 歸約 8 #(f,(f (, , a)# 移進 9 #(f,(f, ,a a )# 移進 10 #(f,(f,a a) ) )# 歸約 11 #(f,(f,f ,) ) )# 歸約 12 #(f,(f () ) )# 移進 13 #(f,(f) ) ) # 歸約 14 #(f,f ,) ) # 歸約 15 #(f () ) # 移進 16 #(f) )# # 歸約 17 #f # # 接受 第七章 lr分析法p1521、已知文法 a-aad| aab| 判斷該文法是否slr(1)文法,若是構造相應分析表,并對輸入串a(chǎn)b#給出分析過程。 答案 (1)拓廣文法 (0)s-a (1) a-aad (2)a- aab (3)a- (1)構造識別活前綴的dfa follow(a)=d,b,# 對于狀態(tài)i0:follow(a)a= 對于狀態(tài)i1:follow(a)a= 因為,在dfa中無沖突的現(xiàn)象,所以該文法是slr(1)文法。 (3)slr(1)分析表 狀態(tài) action goto a b d # a 0 s2 r3 r3 r3 1 1 acc 2 s2 r3 r3 r3 3 3 s5 s4 4 r1 r1
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年濰坊市精神衛(wèi)生中心招聘考試真題
- 觀唐山大地震有感300字(8篇)
- 消化系統(tǒng)疾病護理常規(guī)
- 藍莓果實品質(zhì)評價及果酒釀制研究
- 初中數(shù)學拓展學習:《不等式解法》專題課程
- 耕地破碎化對糧食生產(chǎn)碳排放強度的影響研究
- 以堅持為主題的演講稿演講稿類作文8篇
- 2025至2030中國工作流自動化與軟件優(yōu)化行業(yè)發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報告
- 組蛋白去乙?;敢种苿┲С衷i肝細胞的體外長期傳代培養(yǎng)
- 2025至2030中國導染劑行業(yè)競爭力剖析與銷售策略分析報告
- 2024年春季學期中國文學基礎#期末綜合試卷-國開(XJ)-參考資料
- 文藝復興經(jīng)典名著選讀智慧樹知到期末考試答案章節(jié)答案2024年北京大學
- 一年級下-科學-非紙筆測試
- 用S7200編寫搖臂鉆床PLC程序梯形圖
- 2024年造價工程師-水運工程造價工程師筆試參考題庫含答案
- 2023年北京朝陽初二(下)期末物理試卷及答案
- 2024年北京化學工業(yè)集團有限責任公司招聘筆試參考題庫附帶答案詳解
- 項目工程實體質(zhì)量(路基、路面工程)檢查表
- 圖文高中英語語法if條件句If - Clauses
- 中國網(wǎng)民權益保護調(diào)查報告
- 2022年四川省成考(專升本)經(jīng)濟學考試真題含解析
評論
0/150
提交評論