大學(xué)編譯原理課程復(fù)習(xí)試題及答案

-.z.編譯原理復(fù)習(xí)材料選擇題1.文法S→0S|S1|0的語(yǔ)言是()。A.{0mB.{0mC.{0m1nD.{0m1n2.描述程序語(yǔ)言所采用的Ⅲ型文法是()。A.短語(yǔ)文法B.正規(guī)文法C.上下文無(wú)關(guān)文法D.上下文有關(guān)文法3.狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)的簡(jiǎn)單方法是使每個(gè)狀態(tài)結(jié)對(duì)應(yīng)()。A.一個(gè)終結(jié)符B.一個(gè)非終結(jié)符C.一段小程序D.一個(gè)函數(shù)4.標(biāo)準(zhǔn)歸約的關(guān)鍵問(wèn)題是尋找()。A.最左素短語(yǔ)B.句柄C.直接短語(yǔ)D.短語(yǔ)5.一個(gè)算符文法的任何產(chǎn)生式的右部都不含有兩個(gè)相繼的()。A.終結(jié)符B.非終結(jié)符C.終結(jié)符和非終結(jié)符D.空字6.算符優(yōu)先分析法的關(guān)鍵在于規(guī)定()。A.算符優(yōu)先順序和結(jié)合性質(zhì)B.算符優(yōu)先順序C.結(jié)合性質(zhì)D.終結(jié)符和非終結(jié)符之間關(guān)系7.優(yōu)先函數(shù)的優(yōu)點(diǎn)是()。A.形象直觀B.便于進(jìn)展比擬運(yùn)算C.語(yǔ)法分析速度快D.語(yǔ)法分析方法簡(jiǎn)單8.文法符號(hào)的屬性通常分為()兩類。A.共用屬性和私有屬性B.固有屬性和可變屬性C.語(yǔ)法屬性和語(yǔ)義屬性D.綜合屬性和繼承屬性9.在程序流圖中，組成循環(huán)的結(jié)點(diǎn)序列應(yīng)滿足()A.它們是強(qiáng)連通的B.它們中間有唯一的入口結(jié)點(diǎn)C.它們中間有一條回邊D.它們是強(qiáng)連通的且有唯一的入口結(jié)點(diǎn)10.在利用存放器R生成T1:=C/B的目標(biāo)代碼同時(shí),還應(yīng)記錄信息()。A.C/B在T1中B.T1在C/B中C.R含有T1,T1在R中D.R含有C/B,C/B在R中1.D 2.B 3.C 4.B 5.B6.A 7.B 8.D 9.D 10.C1.編譯方式與解釋方式的根本區(qū)別在于()A.是否生成目標(biāo)代碼B.是否生成中間代碼C.是否生成匯編代碼D.是否生成優(yōu)化代碼2.編譯程序生成的目標(biāo)程序()A.一定是機(jī)器語(yǔ)言的程序B.不一定是機(jī)器語(yǔ)言的程序C.一定不是機(jī)器語(yǔ)言的程序D.一定是匯編語(yǔ)言的程序3.設(shè)字母表∑={0,1,*,y},則∑上的正規(guī)式ε所對(duì)應(yīng)的正規(guī)集為()A.εB.{ε0,1,*,y}C.{ε}D.Φ4.*假設(shè)G是一個(gè)文法，S是文法的開場(chǎng)符號(hào)，如果S===>*,則稱*是()A.短語(yǔ)B.句柄C.句子D.句型5.一個(gè)算符文法的任何產(chǎn)生式的右部都不含有兩個(gè)相繼的()A.終結(jié)符B.非終結(jié)符C.終結(jié)符和非終結(jié)符D.ε字6.設(shè)有文法G[A]：A→A*|Ay|Aa|Ac|a|b|c，以下哪些是該文法的句子()(1)aby (2)aycy* (3)aaa (4)bc*yA.(1)(2)(3)B.(1)(2)(4)C.(2)(3)(4)D.全部7.ＬＲ分析器的核心局部是()A.帶先進(jìn)后出存貯器的DFAB.一張動(dòng)作表C.一張GOTO表D.一張分析表8.在程序流圖中，組成循環(huán)的結(jié)點(diǎn)序列應(yīng)滿足()A.它們是強(qiáng)連通的且有唯一的入口結(jié)點(diǎn)B.它們中間有唯一的入口結(jié)點(diǎn)C.它們中間有一條回邊D.它們是強(qiáng)連通的9.表達(dá)式a≤b＋c∧a＞d∨a＋b≠e的后綴式式為()。A.abc≤ad＋＞∧ab＋e≠∨B.ab≤c＋∧da＞ab＋e≠∨C.abc＋≤ad＞∧ab＋e≠∨D.abc＋≤ad＞ab＋∧e≠∨10.程序根本塊是指()A.一個(gè)子程序B.一個(gè)僅有一個(gè)入口和一個(gè)出口的語(yǔ)句C.一個(gè)沒(méi)有嵌套的程序段D.一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口1.A 2.B 3.C 4.D 5.B6.C 7.D 8.A 9.C 10.D1.BNF是一種用于()的工具。A.描述句型B.描述句子C.描述語(yǔ)言D.描述文法2.設(shè)字母表∑={0,1,*,y},則∑上的正規(guī)式ε所對(duì)應(yīng)的正規(guī)集為()A.εB.{ε}C.{ε0,1,*,y}D.Φ3.標(biāo)準(zhǔn)推導(dǎo)也稱為()A.最右推導(dǎo)B.最左推導(dǎo)C.一般推導(dǎo)D.自左向右推導(dǎo)4.在標(biāo)準(zhǔn)歸約中,任何可歸約串的出現(xiàn)必在()A.棧的內(nèi)部B.棧頂C.剩余的輸入串中D.在先進(jìn)后出棧中5.一個(gè)算符文法的任何產(chǎn)生式的右部都不含有兩個(gè)相繼的()A.終結(jié)符B.非終結(jié)符C.終結(jié)符和非終結(jié)符D.ε字6.ＬＲ分析器的核心局部是()A.一張分析表B.一張動(dòng)作表C.一張GOTO表D.帶先進(jìn)后出存貯器的DFA7.算符優(yōu)先分析的關(guān)鍵問(wèn)題是尋找()。A.句柄B.最左素短語(yǔ)C.短語(yǔ)D.直接短語(yǔ)8.四元式之間的聯(lián)系是通過(guò)()A.指示器B.臨時(shí)變量C.四元式的編號(hào)D.中間運(yùn)算結(jié)果9.表達(dá)式a≤b＋c∧a＞d∨a＋b≠e的逆波蘭式為()。A.abc＋≤ad＞∧ab＋e≠∨B.ab≤c＋∧da＞ab＋e≠∨C.abc≤ad＋＞∧ab＋e≠∨D.abc＋≤ad＞ab＋∧e≠∨10.代碼外提時(shí)要求該不變運(yùn)算所在的結(jié)點(diǎn)是循環(huán)的()。A.*個(gè)出口的必經(jīng)結(jié)點(diǎn)B.至少是一個(gè)入口的必經(jīng)結(jié)點(diǎn)C.入口的必經(jīng)結(jié)點(diǎn)D.所有出口的必經(jīng)結(jié)點(diǎn)1.D 2.B 3.A 4.B 5.B6.A 7.B 8.B 9.A 10.D填空題1.一個(gè)狀態(tài)轉(zhuǎn)換圖可用于一定的字符串。2.設(shè)∑＝｛a,b,c｝，則∑*中最短的符號(hào)串為。3.假設(shè)由文法的開場(chǎng)符號(hào)可以推導(dǎo)出串α，且，則α為原文法的一個(gè)句子。4.假設(shè)文法的*非終結(jié)符P滿足，稱文法含有左遞歸。5.表達(dá)式-(a+b)/(c*d)-e的逆波蘭式為______________________________。6.后序遍歷一棵表達(dá)式樹，可得到它的。7.中間代碼是一種面向語(yǔ)法，易于翻譯成的代碼。8.四元式序列中各四元式出現(xiàn)的順序與是一致的。9.假設(shè)每個(gè)程序?qū)?yīng)一個(gè)流圖，則流圖中的結(jié)點(diǎn)對(duì)應(yīng)一個(gè)。10.假設(shè)從流圖首結(jié)點(diǎn)出發(fā),到達(dá)nj的任一通路必須經(jīng)過(guò)ni，則稱的必經(jīng)結(jié)點(diǎn)。1. 識(shí)別或承受2. ε3. α?VT*4. Ｐ==＋＞Ｐα5. ab+cd*/e-6. 逆波蘭式7. 目標(biāo)代碼8. 運(yùn)算順序9. 根本塊10. ni為nj1.一個(gè)非確定的有限自動(dòng)機(jī)可以表示為一個(gè)元式。2.假設(shè)文法的*非終結(jié)符P滿足，稱文法含有左遞歸。3.設(shè)∑＝｛1,2,3｝，則∑*中最短的符號(hào)串為。4.用∑+表示∑上所有的集合。5.三地址代碼的一般形式為。6.遞歸下降法對(duì)每個(gè)構(gòu)造一個(gè)相應(yīng)的子程序。7.在算符優(yōu)先分析中，用作為可歸約串。8.在形式語(yǔ)言中，最推導(dǎo)被稱為標(biāo)準(zhǔn)推導(dǎo)。9.語(yǔ)法樹中，一個(gè)結(jié)點(diǎn)的屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的屬性確定。10.如果循環(huán)中對(duì)變量I只有唯一的形如I=I±C的賦值，則稱I為循環(huán)中的變量。1.2.五Ｐ==＋＞Ｐα3.ε4.長(zhǎng)度不為0的串5.*:=yopz6.非終結(jié)符7.最左素短語(yǔ)8.右9.繼承10.根本歸納1.終態(tài)與非終態(tài)的區(qū)別在于。2.用∑+表示∑上所有的集合。3.一個(gè)狀態(tài)轉(zhuǎn)換圖可用于一定的字符串。4.用于詞法分析的掃描緩沖區(qū)可將兩個(gè)半?yún)^(qū)使用。5.一個(gè)句型的稱為該句型的句柄。6.遞歸下降法對(duì)每個(gè)構(gòu)造一個(gè)相應(yīng)的子程序。7.算符優(yōu)先法尤其適用于的分析。8.標(biāo)準(zhǔn)歸約的關(guān)鍵在于如何確定。9.文法符號(hào)的屬性值可自底向上應(yīng)用語(yǔ)義規(guī)則計(jì)算出來(lái)。10.DAG代表。1.終態(tài)可承受空串2.長(zhǎng)度不為0的串3.識(shí)別4.互補(bǔ)5.最左簡(jiǎn)單短語(yǔ)6.非終結(jié)符7.表達(dá)式8.句柄9.綜合10.有向無(wú)環(huán)圖判斷題1.假設(shè)一個(gè)文法是遞歸的，則由它產(chǎn)生的語(yǔ)言的句子個(gè)數(shù)是有限的。〔〕2.用于詞法分析的掃描緩沖區(qū)可將兩個(gè)半?yún)^(qū)重疊使用?！病?.一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶有后進(jìn)先出存儲(chǔ)器的DFA?！病?.符號(hào)表的每一項(xiàng)一般包含入口欄和信息欄兩大局部?！病?.DAG是對(duì)循環(huán)進(jìn)展優(yōu)化的有效工具?！病?.代碼外提時(shí)要求該不變運(yùn)算所在的結(jié)點(diǎn)是循環(huán)的*個(gè)出口的必經(jīng)結(jié)點(diǎn)?！病?. ×無(wú)限2. ×互補(bǔ)3. √4. ×名字5. ×根本塊6. ×所有1.描述程序語(yǔ)言所采用的Ⅲ型文法是上下文無(wú)關(guān)文法。〔〕2.狀態(tài)轉(zhuǎn)換圖實(shí)現(xiàn)的簡(jiǎn)單方法是使每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)非終結(jié)符〔〕3.欲構(gòu)造行之有效的自下而上分析器，則必須去除文法中含有的左遞歸。〔〕4.在標(biāo)準(zhǔn)歸約中,任何可歸約串的出現(xiàn)必在棧的內(nèi)部?！病?.循環(huán)優(yōu)化中的強(qiáng)度削弱主要是指將循環(huán)中的乘法變成加法?！病?.符號(hào)表的信息欄中的內(nèi)容稱為關(guān)鍵字?！病?.×正規(guī)文法2.×一段小程序3.×自上而下4.×棧頂5.×遞歸加法6.×名字1.設(shè)α是*句型的一個(gè)子串，假設(shè)它能被一次直接歸約為一個(gè)非終結(jié)符，則α是該句型的一個(gè)直接短語(yǔ)。〔〕2.語(yǔ)法分析過(guò)程可用一棵樹表示出來(lái),這棵樹叫做語(yǔ)法樹?！病?.欲構(gòu)造行之有效的自下而上分析器，則必須去除文法中含有的左遞歸?！病?.四元式作為中間語(yǔ)言，用于翻譯除表達(dá)式外的其他語(yǔ)句代碼?！病?.循環(huán)優(yōu)化中的強(qiáng)度削弱主要是指將循環(huán)中的乘法變成加法?！病?.流圖中有向邊a→b為回邊的條件是aDOMb。〔〕1.×要求這個(gè)非終結(jié)符取代α后，原句型還可繼續(xù)向開場(chǎng)符方向歸約。2.×分析樹3.×自上而下4.×各種5.×遞歸加法6.×bDOMa簡(jiǎn)答題1.簡(jiǎn)述正規(guī)式與有限自動(dòng)機(jī)的關(guān)系。2.文法G:S→iSeS|iS|i該文法是否具有二義性？請(qǐng)根據(jù)句子iiiei構(gòu)造語(yǔ)法樹予以說(shuō)明。3.何謂遞歸下降分析法？應(yīng)用此種分析法的文法應(yīng)滿足什么條件？4．簡(jiǎn)述代碼優(yōu)化所依據(jù)的原則與優(yōu)化的級(jí)別，并列舉三種常用的優(yōu)化技術(shù)。1.正規(guī)式用來(lái)描述正規(guī)集，而有限自動(dòng)機(jī)用來(lái)識(shí)別正規(guī)集，在正規(guī)集的意義上它們存在等價(jià)關(guān)系。即：對(duì)每一個(gè)正規(guī)式所代表的正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)M，使得L(M)=L(G)，M所能識(shí)別的字的全體恰為這個(gè)正規(guī)文法G的語(yǔ)言集合；對(duì)每一個(gè)有限自動(dòng)機(jī)M，都存在一個(gè)可以用正規(guī)式表示的正規(guī)文法G，使得L(G)=L(M)，這個(gè)正規(guī)文法G的語(yǔ)言集合中的任一個(gè)字可以由M識(shí)別。2.對(duì)于句子iiiei，該文法具有兩棵不同的語(yǔ)法樹與之對(duì)應(yīng)，故為二義性文法。SS//\\/\iSeSiS/\|//\\iSiiSeS|||Iii3.當(dāng)文法滿足LL(1)條件時(shí)，可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序。它由一組遞歸過(guò)程〔函數(shù)〕組成，每個(gè)過(guò)程〔函數(shù)〕對(duì)應(yīng)文法的一個(gè)非終極符，這樣的分析程序稱為遞歸下降分析器。利用這種分析程序進(jìn)展語(yǔ)法分析的方法稱為遞歸下降分析法。4.代碼優(yōu)化所依據(jù)的原則是：等價(jià)原則、有效原則和合算原則。代碼優(yōu)化所依據(jù)的級(jí)別是：局部?jī)?yōu)化、循環(huán)優(yōu)化與全局優(yōu)化。常用的代碼優(yōu)化技術(shù)有：刪除公共子表達(dá)式、刪除無(wú)用賦值、合并量、代碼外提、強(qiáng)度削弱、刪除歸納變量等。1.什么是編譯器的前端和后端，通常兩者之間用什么作為接口？2.簡(jiǎn)述NFA和DFA的聯(lián)系與區(qū)別。3.語(yǔ)法分析方法如何分類？它們面對(duì)的主要問(wèn)題是什么？4.何謂中間語(yǔ)言？簡(jiǎn)述它的作用。1.前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些局部組成，通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可包括在前端?！?分〕后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些局部，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等?！?分〕通常，前端和后端以中間語(yǔ)言作為接口〔1分〕2.聯(lián)系：NFA和DFA都是有限自動(dòng)機(jī)，都用于接收、識(shí)別一定的字符串。NFA是DFA的推廣，DFA是NFA的特例?！?分〕區(qū)別：NFA多值函數(shù)，DFA是單值函數(shù)。NFA可以有多個(gè)初態(tài)，DFA只有一個(gè)初態(tài)。NFA的每條弧允許用∑*上的一個(gè)字作標(biāo)記，DFA的每條弧只允許用∑上的一個(gè)字符作標(biāo)記。〔3分〕3.按照語(yǔ)法分析樹的建立方法，可以把語(yǔ)法分析方法分為兩類：自上而下分析法與自下而上分析法?！?分〕自上而下分析法面對(duì)的主要問(wèn)題是：如何消除文法的左遞歸，以及在由文法的開場(chǎng)符出發(fā)推導(dǎo)句子的過(guò)程中如何防止回溯?！?分〕自下而上分析法面對(duì)的主要問(wèn)題是：在由輸入串出發(fā)向文法的開場(chǎng)符歸約的過(guò)程中，如何確定可歸約子串〔句柄或最左素短語(yǔ)〕。〔1分〕4.中間語(yǔ)言是一種面向語(yǔ)法，復(fù)雜性介于用高級(jí)語(yǔ)言書寫的源程序和用機(jī)器語(yǔ)言表示的目標(biāo)程序之間，是一種易于翻譯成目標(biāo)代碼的代碼形式?！?分〕中間語(yǔ)言的作用在于：利用它作為中間環(huán)節(jié)，不僅可以較快地實(shí)現(xiàn)源程序翻譯過(guò)程，而且可在此根底上應(yīng)用優(yōu)化方法，將源程序翻譯成為運(yùn)行時(shí)間短、占用內(nèi)存少的目標(biāo)程序。〔2分〕1.何謂上下文無(wú)關(guān)文法"它是由哪幾局部組成的"2.簡(jiǎn)述NFA和DFA的聯(lián)系與區(qū)別。3.語(yǔ)法分析方法如何分類？它們面對(duì)的主要問(wèn)題是什么？4.何謂中間語(yǔ)言？簡(jiǎn)述它的作用。1.上下文無(wú)關(guān)文法是這樣一種文法，它所定義的語(yǔ)法范疇〔或語(yǔ)法單位〕是完全獨(dú)立于這種范疇所處的環(huán)境的?！?分〕上下文無(wú)關(guān)文法由四局部所組成：一組終極符號(hào)，一組非終極符號(hào)，一個(gè)開場(chǎng)符號(hào)以及一組產(chǎn)生式?！?分〕2.聯(lián)系：NFA和DFA都是有限自動(dòng)機(jī)，都用于接收、識(shí)別一定的字符串。NFA是DFA的推廣，DFA是NFA的特例?！?分〕區(qū)別：NFA多值函數(shù)，DFA是單值函數(shù)。NFA可以有多個(gè)初態(tài)，DFA只有一個(gè)初態(tài)。NFA的每條弧允許用∑*上的一個(gè)字作標(biāo)記，DFA的每條弧只允許用∑上的一個(gè)字符作標(biāo)記。〔3分〕3.按照語(yǔ)法分析樹的建立方法，可以把語(yǔ)法分析方法分為兩類：自上而下分析法與自下而上分析法。〔2分〕自上而下分析法面對(duì)的主要問(wèn)題是：如何消除文法的左遞歸，以及在由文法的開場(chǎng)符出發(fā)推導(dǎo)句子的過(guò)程中如何防止回溯。〔2分〕自下而上分析法面對(duì)的主要問(wèn)題是：在由輸入串出發(fā)向文法的開場(chǎng)符歸約的過(guò)程中，如何確定可歸約子串〔句柄或最左素短語(yǔ)〕。〔1分〕4.中間語(yǔ)言是一種面向語(yǔ)法，復(fù)雜性介于用高級(jí)語(yǔ)言書寫的源程序和用機(jī)器語(yǔ)言表示的目標(biāo)程序之間，是一種易于翻譯成目標(biāo)代碼的代碼形式。〔3分〕中間語(yǔ)言的作用在于：利用它作為中間環(huán)節(jié)，不僅可以較快地實(shí)現(xiàn)源程序翻譯過(guò)程，而且可在此根底上應(yīng)用優(yōu)化方法，將源程序翻譯成為運(yùn)行時(shí)間短、占用內(nèi)存少的目標(biāo)程序。〔2分〕綜合題1.構(gòu)造一個(gè)DFA，它承受Σ={a，b}上所有包含ab的字符串。2.對(duì)文法G〔S〕：S→〔L〕|aS|aL→L,S|S1

、消除左遞歸和回朔；2、構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；3、構(gòu)造預(yù)測(cè)分析表。3.給出文法G〔P〕P→bQbQ→cRQ→aR→Qad該文法是不是算符優(yōu)先文法，請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之。4.〔1〕有如下三地址碼：read(n)i:=1fen:=1L1:ifi<=ngotoL2GotoL3L2:t1:=fen*ifen:=t1i:=i+1gotoL1L3:write(fen)將該代碼段劃分為根本塊；并構(gòu)造相應(yīng)的程序流圖?！?〕對(duì)以下四元式序列生成目標(biāo)代碼：A:=B*CD:=E+FG:=A+DH:=G*2其中，H在根本塊出口之后是活潑變量，R0和R1是可用存放器。1．構(gòu)造一個(gè)DFA，它承受Σ={a，b}上所有包含ab的字符串。2．對(duì)文法G〔S〕：S→〔L〕|aS|aL→L,S|S1、消除左遞歸和回朔；2、構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；3、構(gòu)造預(yù)測(cè)分析表。答：3．給出文法G〔P〕P→bQbQ→cRQ→aR→Qad該文法是不是算符優(yōu)先文法，請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之。答：對(duì)于文法G，計(jì)算它的每個(gè)非終結(jié)符的FIRSTVT和LASTVT集合：4．〔1〕有如下三地址碼：read(n)i:=1fen:=1L1:ifi<=ngotoL2GotoL3L2:t1:=fen*ifen:=t1i:=i+1gotoL1L3:write(fen)將該代碼段劃分為根本塊；并構(gòu)造相應(yīng)的程序流圖?！?〕對(duì)以下四元式序列生成目標(biāo)代碼：A:=B*CD:=E+FG:=A+DH:=G*2其中，H在根本塊出口之后是活潑變量，R0和R1是可用存放器。解：1.構(gòu)造一個(gè)最簡(jiǎn)的DFA，它承受Σ={a，b}上所有滿足如下條件的字符串：所有b都有a直接跟在后面。得分2.設(shè)有文法G(*)，該文法產(chǎn)生式為： *→b|&|(Y) Y→Y；*|*其中*為文法開場(chǎng)符號(hào)，b&；()為終結(jié)符號(hào)(1)消除左遞歸和回朔(2)計(jì)算每個(gè)非終結(jié)符號(hào)的FIRST集和FOLLOW集(3)構(gòu)造它的預(yù)測(cè)分析表3.設(shè)文法G〔S〕：S→SiA|AA→A+B|BB→〕A*|〔1、構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；2、構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)4.對(duì)以下程序(1)READB(2)J:=1(3)A:=I+2(4)E:=I*J(5)D:=A+E(6)B:=D+B(7)IfJ>60goto(10)(8)J:=J+1(9)goto(3)(10)WRITEB(11)halt(1)劃分根本塊，畫出流圖(2)對(duì)其中循環(huán)進(jìn)展優(yōu)化，畫出優(yōu)化后流圖1．構(gòu)造一個(gè)最簡(jiǎn)的DFA，它承受Σ={a，b}上所有滿足如下條件的字符串：所有b都有a直接跟在后面。答：(1)由以上正規(guī)式構(gòu)造相應(yīng)的NFAM'(4分)(2)用子集法對(duì)M'進(jìn)展確定化，得到DFAM(4分)IIa=ε_(tái)CLOSURE(J)Ib=ε_(tái)CLOSURE(J){*,1,y}{1,y}{2}{1,y}{1,y}{1,y}{2}{2}--狀態(tài)ab01211122--(3)把DFAM’進(jìn)展化簡(jiǎn)(4分)①把M狀態(tài)集分為兩組:終態(tài)結(jié)點(diǎn){0，1}；非終態(tài)結(jié)點(diǎn){2}②考察{0，1}，因?yàn)?，{0，1}a={1}包含于{0,1}；{0，1}b={2}包含于{2}；所以，{0，1}不可再分所以，最終把M分割為{0，1}，{2}。狀態(tài)1代替狀態(tài)0，把引向狀態(tài)0的箭弧都引向狀態(tài)1，把0消去，得到一個(gè)DFAM’’2．設(shè)有文法G(*)，該文法產(chǎn)生式為： *→b|&|(Y) Y→Y；*|*其中*為文法開場(chǎng)符號(hào)，b&；()為終結(jié)符號(hào)(1)消除左遞歸(2)計(jì)算每個(gè)非終結(jié)符號(hào)的FIRST集和FOLLOW集(3)構(gòu)造它的預(yù)測(cè)分析表答：(1)消除左遞歸(4分)*→b|&|(Y) Y→*Y’ Y’→；*Y’|ε(2)計(jì)算每個(gè)非終結(jié)符號(hào)的FIRST集和FOLLOW集(4分)FIRST(*)={b,&,(};FIRST(Y)={b,&,(};FIRST(Y’)={；,ε};FOLLOW(T)={)};FOLLOW(Y’)={)};FOLLOW(*)={#,；}};(3)構(gòu)造它的預(yù)測(cè)分析表(4分)b&()；#**→b*→&*→(Y)YY→*Y’Y→*Y’Y→*Y’Y’Y’→εY’→,*Y’3．設(shè)文法G〔S〕：S→SiA|AA→A+B|BB→〕A*|〔1、構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；2、構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)答：〔4分〕〔4分〕〔4分〕〔4分〕〔4分〕〔4分〕4．對(duì)以下程序(1)READB(2)J:=1(3)A:=I+2(4)E:=I*J(5)