




已閱讀5頁(yè),還剩5頁(yè)未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
一、簡(jiǎn)答題(每題4分,共24分)1、 構(gòu)造一個(gè)文法G,使得:L(G)=(m )m|m0 解答: GS: s- ()|(S)2、 構(gòu)造一個(gè)正規(guī)式,它接受S=0,1上符合以下規(guī)則的字符串: 串內(nèi)有且只有2個(gè)1的0、1字符串全體。解答: 0*10*10*3、 消除文法GS中的直接左遞歸和回溯 S (L) | aS | aL L,S | S解答: S (L) | aSS S | L S LL,S L | 4、 文法GS是喬姆斯基幾型文法? S ABS | AB AB BA A 0 B 1解答:1型文法/上下文有關(guān)文法5、按Thmopson算法構(gòu)造與正則表達(dá)式 (1*|0) * 等價(jià)的NFA。解答:略6、設(shè)計(jì)一個(gè)狀態(tài)轉(zhuǎn)換圖,其描述的語(yǔ)言規(guī)則為:如果以a開(kāi)頭,則其后是由a、b組成的任意符號(hào)串;如果以b開(kāi)頭,則其后是至少包含一個(gè)a的由a、b組成的任意符號(hào)串。解答:略二、(本題10分)對(duì)于文法GE:EET+|T TTF* | F FF | a (1) 給出句子FF*的最左推導(dǎo)和語(yǔ)法樹(shù); (2) 給出句子FF*的短語(yǔ)、直接短語(yǔ)和句柄。解答: (1) 2分: 句子FF*的最左推導(dǎo) 2分: 句子FF*的語(yǔ)法樹(shù) E=T=TF*=FF*=FF*=FF* (2) 3分:句子FF*的短語(yǔ) FF*、FF*、F、F、F 2分:句子FF*的直接短語(yǔ) F、F 1分:句子FF*的句柄 F三、(本題15分)構(gòu)造與下列NFA等價(jià)的最小化DFA。解答:(1)10分:構(gòu)造與NFA等價(jià)的DFA(2)5分:對(duì)DFA最小化 首先,將所有的狀態(tài)集合分成子集: k1=0,1,2,4 k2=3,5四、(本題15分)對(duì)下列文法GS:s eT | RTT DR | R dR | D a | bd (1) 寫出文法GS每個(gè)非終結(jié)符的FIRST集和FOLLOW集; (2) 判斷文法GS是否LL(1)文法(注:必須給出判斷過(guò)程,否則不得分); (3) 寫出文法文法GS的預(yù)測(cè)分析表。解答:(1)8分:每個(gè)First集合和FOLLOW集合各1分FIRST集FOLLOW集s eT | RT e a, b, d, #T DR | a, b #R dR | d a,b,#D a | bd a bD,# (2) 2分: 判斷文法GS是LL(1)文法。 對(duì)于產(chǎn)生式s eT | RT:FIRST(eT)FIRST(RT)- =ea,b,d= FIRST(eT)FOLLOW(S)=e#= 對(duì)于產(chǎn)生式T DR | : FIRST(DR)FOLLOW(T)=a,b#= 對(duì)于產(chǎn)生式R dR | : FIRST(dR)FOLLOW(R)=da,b,#= 對(duì)于產(chǎn)生式D a | bd: FIRST(a)FIRST(bd)=ab= 所以,對(duì)于文法GS是LL(1)文法。 (3) 5分:文法GS的預(yù)測(cè)分析表。五、(本題18分)已知文法GS:S r D D D ,i | i(1) 畫出識(shí)別文法活前綴的完整DFA,并判斷該文法是否LR(0)文法(必須說(shuō)明判斷依據(jù));(2) 構(gòu)造該文法的SLR(1)分析表,并判斷該文法是否SLR(1)文法(必須說(shuō)明判斷依據(jù))。解答:(1) 8分:畫出識(shí)別文法活前綴的完整DFA 文法拓展并對(duì)產(chǎn)生式編號(hào): (0)S S (1)S r D (2)D D ,i (3)D i (2) 2分:判斷該文法不是LR(0)文法 對(duì)于狀態(tài)3,項(xiàng)目集中存在“移進(jìn)-規(guī)約”沖突,所以該文法不是LR(0)文法。 (3) 6分:構(gòu)造該文法的SLR(1)分析表狀態(tài)ACTIONGOTOr ,i#SD0S211acc2S433S5r14r3r35S66r2r2 (4) 2分:判斷文法是SLR(1)分析表 回答1: 因?yàn)镾LR(1)分析表不存在沖突,所以文法是SLR(1)分析表。 回答2: 對(duì)于狀態(tài)3, FOLLOW(S),=(#),=,“移進(jìn)-規(guī)約”沖突可以用 SLR(1)方法解決,所以文法是SLR(1)分析表。六、(本題8分)文法GE的LR分析表如下圖所示:(1) E E+T (2) E T (3) T T*F(4) T F (5) F (E) (6) F i 寫出對(duì)輸入串 i * i + i的LR分析過(guò)程 (即狀態(tài),符號(hào),輸入串的變化過(guò)程)。解答: 七、(本題10分)寫出下列語(yǔ)句的四元式序列if(yz & (cn) while(ab) x=x+y*a; else m=m+n;解答:1 (j, y, z, 3)2 (j , -,-, 13)3 (j,m,n, 7)6 (j,-,-, 13)7 (j,a,b, 9) 8 (j,-,-,13/16
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 某湖泊黑臭水體成因及治理工程設(shè)計(jì)方案
- 智能音響市場(chǎng)分析及營(yíng)銷方案設(shè)計(jì)
- 圖書館管理員業(yè)務(wù)知識(shí)培訓(xùn)方案
- 股東公司分紅方案新增協(xié)議書
- 地下室頂板堆載布置及回頂方案
- 公路工程安全隱患排查治理計(jì)劃方案
- 中學(xué)安全隱患排查方案
- 樹(shù)葉健康校園活動(dòng)方案
- 樹(shù)木認(rèn)知活動(dòng)方案
- 校內(nèi)開(kāi)展講座活動(dòng)方案
- 天然氣計(jì)量與標(biāo)準(zhǔn)化-洞察分析
- 《護(hù)理不良事件》課件
- 無(wú)創(chuàng)眶周抗衰規(guī)范
- 花崗巖路面鋪設(shè)工藝流程
- 鋼結(jié)構(gòu)廠房水電安裝施工設(shè)計(jì)方案
- 國(guó)開(kāi)《演講與口才》形考任務(wù)1-4答案
- 2021年華南理工大學(xué)軟件工程專業(yè)《計(jì)算機(jī)組成原理》科目期末試卷B(有答案)
- 自適應(yīng)前照燈控制系統(tǒng)
- 歌曲《wake》中英文歌詞對(duì)照
- 2024-2025年咖啡師制作基礎(chǔ)知識(shí)試題庫(kù)與答案
- 清水混凝土涂料施工工藝簡(jiǎn)介
評(píng)論
0/150
提交評(píng)論