編譯原理-第二三章總結(jié)

編譯技術(shù)命題指導(dǎo)意A（1）[2分編譯程序絕大多數(shù)時(shí)間花在 [2] )[3]編譯程序前三個(gè)階段完成的工作是 （2）[2分 將編譯程序分成若干個(gè)“遍”是為 [3]編譯器從邏輯上可以分為7個(gè)階段，其中，可以作為一個(gè)后端遍的是 （3）[5分什么是前端 [5分什么是后端 [5分什么是前端？什么是后端 [5分2.12.2B（1）[2分[1]詞法分析程序的輸出結(jié)果是（[2]詞法分析器用于識(shí) [3]掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ) A．字符 （2）[2分 答案：記號(hào)名屬性值 答案：記號(hào)名屬性（3）[2分下面文法 ）和正規(guī)表達(dá)式a*b描述的語(yǔ)言相同S→ab|S→b|S→a|S→a|[2]最多包含兩個(gè)a的{a,b}上的語(yǔ)言 C.D.[3]與(a|b)*等價(jià)的正規(guī)式是（2.3.1,2.3.2C（1）NFADFA[2分有如圖所示的有窮自動(dòng)機(jī)，與之等價(jià)的正規(guī)式為 (0|1)Ａ，B，C選項(xiàng)都不正確[2]NFADFA模型說(shuō)法錯(cuò)誤的是（[3]DFA模型，說(shuō)法錯(cuò)誤的是（εDDFA可以有多個(gè)接受狀態(tài)（2）NFA[10分NFAM=({A，B，C}，{0，1}，，{A}，{C})(A，0)={C} (A，1)={A，B} (B，1)={C} 01ACBCCC 1 0NFA1(0|1)*101。（ε|ab**ababbab 或者0 （3）NFADFA10分DFA。II1(0|1)*101DFA。NFA：ABB、ACC、ABYD[3]NFADFA[10分[1]NFA=（{x,y,z},{0,1},M,{x},{z}M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=φ,M(z,1)={y},區(qū)分P2由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C所以FC等價(jià)。由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,D，E不等價(jià)（見(jiàn)下步BC，F(xiàn)可以區(qū)分。P21={C,F},P22={B}。P1:A，E0D0DA，E可以區(qū)分，P11={A,E},P12={D}。綜上所述，DFAP={{A}，{B}，{D}，{E}，{C，F(xiàn)}}[2]DFAa a ab--ab01220--112a-- {0,1}a {0,1}b=所以：{0,1}｛0｝｛2｝a0-- a第二章2.4,2.5詞法分析器的;第二章習(xí)D[1]寫(xiě)出能產(chǎn)生字母表{x,y}上的不含兩個(gè)相鄰的x,且不含兩個(gè)相鄰的ｙ的全體符號(hào)串的有x1 2y處于/**/之間的串構(gòu)成注解，注解中間沒(méi)有*/DFA的狀態(tài)轉(zhuǎn)* L={w|w(0,1)+w110，試構(gòu)造接受該語(yǔ)言的確定有限狀態(tài)自動(dòng)機(jī)。（2）Lex的功能[2分[1]Lex是從基于正規(guī)式的描述來(lái)構(gòu) Lex程序包含三部分： 答案：翻譯規(guī)則由Lex建立 答案：詞 語(yǔ)第三章3.1E（1）上下文無(wú)關(guān)文法定義[2分 [2]文法分為四種類(lèi)型，即0型、1型、2型、3型。其中2型文法是 [3]文法分為四種類(lèi)型，即0型、1型、2型、3型。其中0型文法 （2）最左推導(dǎo)、最右推導(dǎo)[5分(a,(a,a)(((a,a),^,(a)),a)的最左推導(dǎo)。S=>(T)=>(T,S)=>(S,S)=>(a,(T))=>(a,(T,S))=>(a,(a,S))對(duì)(((a,a),^,(a)),a)S=>(T)=>(T,S)=>(S,S)=>(((T),S,S),S)=>(((T,S),S,S),S)=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),^,(T)),S)=>(((a,a),^,(S)),S)E→RP|PP→(E)|iR→RP+|RP*ERPR(E)R(RP)R(Ri)R(P+i)R(i+i)RP*(i+i)P+i*(i+i)[3]S->aSbS|bSaS（a）abab（b）為abab構(gòu)造對(duì)應(yīng)的最右推導(dǎo)。（3）分析樹(shù)[5分[1]S->aSbS|bSaS為ababE（2）a、bab串（含空串（1）ETF(E)(E+T)(E+F)(E+i)(T+i)A→aAb|ab（2）aabbb的最左推導(dǎo)，并給出其語(yǔ)法分析樹(shù)。

（2）s（4）二義性概念[2分如果文法G是無(wú)二義的，則它的任何句子 [2]如果一個(gè)文法G是無(wú)二義性文法，對(duì)于任何一個(gè)句子，該句子 D.僅存在一個(gè)最左推導(dǎo)和一個(gè)最右推導(dǎo)[3]若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是 第三章3.2F（1）消除左遞歸[2分一個(gè)文法是左遞歸的，如果它有非終結(jié)符A，對(duì)某個(gè)串a(chǎn)，存在推導(dǎo) 由形式為A->Aa的產(chǎn)生式引起的左遞歸稱(chēng)為 （2）提取左因子[2分 elsestmt->ifexprthenstmtelse|ifexprthen|提取左因子后的文法成 答案：stmt->ifexprthenstmtoptional_else_part| optional_else_part->else（3）形式語(yǔ)言鳥(niǎo)瞰[2分[1]Chomsky把文法分為4種類(lèi)型，其中描述能力最強(qiáng)的是 A0B.1C.2D3[2]文法分為四種類(lèi)型，即0型、1型、2型、3型。其中1型文法是 [3]文法分為四種類(lèi)型，即0型、1型、2型、3型。其中3型文法是 第三章3.3G（1）LL(1)文法概念[2分3在下面的各種編譯方法中，屬于自頂向下的語(yǔ)法分析算法的是 LL(1)LR(K)SLRDLALR(1)分析方法[2]LL(1)分析法的名字中，第二個(gè)“L”的含義是 [3]LL(1)分析法的名字中，第一個(gè)“L”的含義是 （2）構(gòu)造預(yù)測(cè)分析表（FIRST、FOLLOW集）[10分[1]S→S＋aF|aF|＋aFFIRSTFollow集合。 FIRST（S'）＝｛+，ε｝FOLLOW（S'）＝｛＃｝ FIRST（F'）＝｛*，ε｝FOLLOW（+，＃｝[2]H->LSo|εK->dML|εGLL(1)LL(1)分析表。FIRSTFOLLOWSA由于預(yù)測(cè)分析表中無(wú)多重，所以可判定文法是LL(1)的FIRSTFOLLOW集合。S→S*aA|aA|*aAA→+aA|+aS→*aAS’|aAS’S’→*aAS’|*a+#SS→A（3）用預(yù)測(cè)分析表對(duì)輸入串進(jìn)行分析的過(guò)程[5分[1]LL(1)[2]i+*()#-/EGεTSF步 分析 i i / F[3]a$(),#STF有輸入符號(hào)串(a,(a))#步 分析 剩余字 所用產(chǎn)生 a a , a 第三章3.4H（1）歸約概念[2分若a為終結(jié)符，則A->α·aβ 項(xiàng)目[2]移近-歸約分析為輸入串構(gòu)造分析樹(shù)是從 [3]在每一步歸約中，一個(gè)子串和某個(gè)產(chǎn)生式的（）匹配，然后用該產(chǎn)生式的（）符號(hào)（2）句柄概念[2分在規(guī)范歸約中，用 [2]下面說(shuō)法正確的是 [3]面說(shuō)法錯(cuò)誤的是 第三章3.5LRI（1）活前綴概念[2分A.在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 )的DFA狀態(tài) B.前綴 C.活前綴 D.LR(0)項(xiàng)目下列語(yǔ)句描述錯(cuò)誤的是A的A12的右部子串已出現(xiàn)在棧頂，期待從輸入串中看到2A的右部A的右部頂（2）SLR分析表[20分SLREE+ FE FTT FT EEE|EE*|aSLR(1)LR(1)SLR(2)SLR分析表‘‘#r(1)SLR文法。(2)SLR（3）LR分析表[20分[1]SABA|BaB|LR[2]SAS|AaA|LR構(gòu)造其LR（1）I0 TS, SAS, S, AaA, Ab, $/a/b TS I2 Ab, I3 SAS, SAS, S, AaA, Ab, I4 AaA, AaA, $/a/bAb, $/a/bI Ab I SAS I7 AaA, AaA, Ab, I8 AaA, I9 AaA, 觀察上面的項(xiàng)目規(guī)范集可以發(fā)現(xiàn)，在項(xiàng)集0和3中，歸約項(xiàng)都是在 符號(hào)'$'時(shí)才發(fā)生，和移進(jìn)符號(hào)不同。所以，該文法是LR文法。LRab$SA0131236348567989LR分析表答案：LR（4）LALR分析表[20分[1]LALRS S’ SEE+ EE+ ET(E)| T(E TLALRLALR分析表分析輸入串“i=*i#”的過(guò)程答案：(1)LALR分析表(2)“i=*i#LALRSdBb|Ba|cb|AABcAAc|LALRabcd$SBA0123123456789（5）SLR分析器對(duì)輸入串進(jìn)行分析的格局變化和相應(yīng)動(dòng)作[5分AaAd|aAb|SLR分析表，給出輸入串“ab#SLRSLRSLL|LLLB|BB0|1SLR101.110的分析過(guò)程。[3]考慮以下的文法G（EE→(L)|aL→L,E|E給出輸入串((a)a(aa))的SLR分析程序的動(dòng)作。（6）LR分析器對(duì)輸入串進(jìn)行分析的格局變化和相應(yīng)動(dòng)作[5分LRababLR分析過(guò)程（按步驟給出狀態(tài)棧，符號(hào)，輸入串的變化過(guò)程）[2]給定文法SABA|BaB|LRabab的分析過(guò)程。SS(S)SLR給出(())LR分析過(guò)程。第三章3.7J（1）Yacc的相關(guān)概念[2分A.B.翻譯規(guī)則C.支持例程D.定 lexlexA①③B①④C②③D②④第四章4.1K（1）[2分] ②R-屬性③綜合屬性④繼承屬A.B.C.D.②④[3]AXY的繼承屬性Y.y，可能正確的語(yǔ)義規(guī)則是A.A.a:f(X B.Y.y:f(C.Y.y:f(X D.A.a:f(Y（2）S屬性定義的概念[填空題2分[1]S屬性是僅僅使用 對(duì)于S屬性定義，分析樹(shù)中各結(jié)點(diǎn)屬性的計(jì)算是 答案：S屬性定義（3）[2分注釋分析樹(shù)的概念 注釋分析樹(shù)中計(jì)算各結(jié)點(diǎn)屬性值的過(guò)程稱(chēng) 第四章4.2SL（1）S屬性定義的自下而上計(jì)算、棧操作[填空題2分] [2]S屬性定義的計(jì)算中，拓展后分子棧的每個(gè)棧元素由 答案：狀態(tài)域 [3]SAXYA.a:fX.x,Y.y規(guī)約成A之前，stack[top-1].Val中存放 第四章4.3LM（1）L屬性定義的概念[2分[1]L屬性定義的說(shuō)法正確的是SL變量類(lèi)型的語(yǔ)法制導(dǎo)定義不是一個(gè)L屬性定LL屬性定義中只包含繼承屬性[2]在L屬性定義中，如果產(chǎn)生式AX1X2,Xn的每條語(yǔ)義規(guī)則計(jì)算的是Xj(1jn的繼承屬性，則他依賴于①A②AXjX1X2,Xj1④XjXj1Xj2,XnABCD②③[3]LAX1X2,Xn的每條語(yǔ)義規(guī)則計(jì)算短的可以是①A②AXj(1jn的繼承屬Xj(1jn的綜合屬ABC①③D①④（2）[10分PDD；D|id：T|procid；D；SidnidP D D Dproc DLL,idL1|:TTinteger|real建立一個(gè)翻譯模式,答案：D L, {L.type=L: {L.type=T T 0表示整型1表示實(shí)型[3]S(L（a（a，a）2,5,7.S' S'( ') L L1 ',' L 第四章4.4LN（1）L屬性定義的自上而下分析中各種屬性與參數(shù)、返回值的映射關(guān)系[2分[1]設(shè)計(jì)翻譯方案時(shí)，必須保證動(dòng)作在屬性時(shí)其值已經(jīng)可用，在只有屬性時(shí)，[2]L屬性定義的自上而下分析中設(shè)計(jì)翻譯方案時(shí)，若包含繼承屬性則產(chǎn)生式右部符號(hào)的[3]L屬性定義的自上而下分析中設(shè)計(jì)翻譯方案時(shí)，若包含繼承屬性則左部非終結(jié)符的（2）L屬性定義的自下而上計(jì)算中輔助非終結(jié)符引入的目的[2分[1]L屬性定義的自下而上計(jì)算中的標(biāo)記非終結(jié)符說(shuō)法正確的是使L使LL屬性定義的綜合屬性計(jì)算只出現(xiàn)在產(chǎn)生式左端[2]L屬性定義的自下而上計(jì)算中引入標(biāo)記非終結(jié)符引入的目的錯(cuò)誤的是[3]L屬性定義的自下而上計(jì)算中處理繼承屬性時(shí)需要引入A.標(biāo)記非終結(jié)符B.標(biāo)記終結(jié)符C.綜合屬性DL屬性第六章6.1,6.2局部、全局分O（1）[2分]A.B.局部數(shù)據(jù)安排不存在對(duì)齊問(wèn)C.局部數(shù)據(jù)的數(shù)據(jù)安排與目標(biāo)機(jī)器的尋址限制無(wú)D.襯墊區(qū)是一定會(huì)出現(xiàn)的[3]局部數(shù)據(jù)在安排時(shí)，襯墊區(qū)是因?yàn)椋ǎ﹩?wèn)題而引起的無(wú)用空A.B.C.D.空間（2）[5分]答案：返回值，參數(shù)，控制鏈，鏈，保存的機(jī)器狀態(tài)，局部數(shù)據(jù)，臨時(shí)數(shù)（3）[5分]結(jié)點(diǎn)abab的活動(dòng)；結(jié)點(diǎn)abab的生存期。ababab的左邊，當(dāng)且僅ab的生存期。（4）[2分把控制棧中的信息到包括過(guò)程活動(dòng)所需的所有局部信息，這種類(lèi)型的棧稱(chēng) （5）[2分 （6）懸空的概念[填空題2分 只要空間可以回收，就有可能出 第六章6.3P（1）[2分[1]下列說(shuō)法錯(cuò)誤的是display表記錄了A.過(guò)程的數(shù)據(jù)B.過(guò)程的嵌套層次C.過(guò)程的返回地址D.過(guò)程的地址display表，則說(shuō)明A.B.C.D.有遞歸、無(wú)嵌套（2）[5分 nppnx的過(guò)程x答 np<nx的情x肯定就在p被調(diào)用過(guò)程的鏈必須指向調(diào)用過(guò)程的活動(dòng)記錄的鏈npnxp和x的嵌套深度分別為1，2，…，nx1的過(guò)程肯定相追蹤鏈np（nx–1）次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過(guò)程的活動(dòng)記錄所到達(dá)的鏈就是x的活動(dòng)記錄中的鏈應(yīng)該指向的那個(gè)簡(jiǎn)述活動(dòng)記錄和鏈的主要作用，以及鏈的指向答：活動(dòng)記錄用于提供活動(dòng)所需的環(huán)境，鏈用于非本地?cái)?shù)據(jù)。鏈的指向有兩種：非顯示表指向直接外層的活動(dòng)記錄，顯示表指向同層次新活動(dòng)記錄。（AB、C、D、E均是過(guò)程分別A、B、C、D、E的嵌套深度試根據(jù)鏈中的內(nèi)容畫(huà)出過(guò)程的嵌套關(guān)系樹(shù)。答案：(1)A、B、C、D、E的嵌套深度分別為： （3）[5分]答案：深，