編譯原理復(fù)習(xí)題(考試)(編輯修改稿)
2025-09-01 15:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 分配申請(qǐng)和釋放存儲(chǔ)空間遵守( D )原則。 A．先請(qǐng)先放 B．先請(qǐng)后放 C．后請(qǐng)先放 D．任意三、填空題1．編譯程序的工作過(guò)程一般可以劃分為詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有__表格處理___和 ___出錯(cuò)處理__。 2．編譯方式與解釋方式的根本區(qū)別在于__是否生成目標(biāo)代碼___。3．產(chǎn)生式是用于定義___語(yǔ)法成分__的一種書(shū)寫(xiě)規(guī)則。 4．設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx( 其中 x∈VT*), 則稱(chēng) x是文法的一個(gè)__句子___。 5．自頂向下的語(yǔ)法分析方法的基本思想是：從文法的__開(kāi)始符號(hào)____開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行__直接推導(dǎo)____，試圖推導(dǎo)出文法的__句子____，使之與給定的輸入串___匹配___。 6．常用的參數(shù)傳遞方式有___傳地址__，傳值和傳名。 7．一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的___句柄__。 8．對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為 __語(yǔ)義規(guī)則___ 。9．一個(gè)典型的編譯程序中，不僅包括__詞法分析___、__語(yǔ)法分析___、__中間代碼生成___、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。10． 從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)_執(zhí)行性___語(yǔ)句和__說(shuō)明性___語(yǔ)句兩大類(lèi)。11． 掃描器的任務(wù)是從__源程序___中識(shí)別出一個(gè)個(gè)___單詞符號(hào)__。 12． 產(chǎn)生式是用于定義__語(yǔ)法范疇___的一種書(shū)寫(xiě)規(guī)則。13．語(yǔ)法分析是依據(jù)語(yǔ)言的__語(yǔ)法___規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的__語(yǔ)義___規(guī)進(jìn)行的。14．語(yǔ)法分析器的輸入是__單詞符號(hào)串___，其輸出是__語(yǔ)法單位___。15．一個(gè)名字的屬性包括__類(lèi)型___和__作用域___。16．逆波蘭式 ab+c+ d*e 所表達(dá)的表達(dá)式為_(kāi)_(a+b+c)*de___ 。 17．語(yǔ)法分析最常用的兩類(lèi)方法是__自上而下___和__自下而上___分析法。18．計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：___解釋__和__編譯___。 19．掃描器是__詞法分析器___，它接受輸入的__源程序___，對(duì)源程序進(jìn)行___詞法分析__并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。20．自上而下分析法采用___移進(jìn)__、歸約、錯(cuò)誤處理、___接受__等四種操作。21．一個(gè)LR分析器包括兩部分：一個(gè)總控程序和___一張分析表__。22．后綴式abc/所代表的表達(dá)式是___a/(bc)__。 23．局部?jī)?yōu)化是在__基本塊___范圍內(nèi)進(jìn)行的一種優(yōu)化。24．詞法分析基于__正則___文法進(jìn)行，即識(shí)別的單詞是該類(lèi)文法的句子。 25．語(yǔ)法分析基于__上下文無(wú)關(guān)___文法進(jìn)行，即識(shí)別的是該類(lèi)文法的句子。語(yǔ)法分析的有效工具是__語(yǔ)法樹(shù)___。26．分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是__最左素短語(yǔ)___，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是___句柄__。27．語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有__逆波蘭___、___四無(wú)式表示__與___三元式表示__等。28．按Chomsky分類(lèi)法，文法按照___規(guī)則定義的形式__進(jìn)行分類(lèi)。 29．一個(gè)文法能用有窮多個(gè)規(guī)則描述無(wú)窮的符號(hào)串集合（語(yǔ)言）是因?yàn)槲姆ㄖ写嬖谟衉__遞歸__定義的規(guī)則。四、簡(jiǎn)答題111. 寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合,要求： (1)允許0打頭；(2) 不允許0打頭。解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) P: SPD|D PNP|N D0|2|4|6|8 N0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) P: SPD|P0|D PNR|N RQR|Q D2|4|6|8 N1|2|3|4|5|6|7|8|9 Q0|1|2|3|4|5|6|7|8|9 2. 構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101 解1(0|1)*101對(duì)應(yīng)的NFA為 3. 寫(xiě)出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示和三元式序列。逆波蘭表示： abc*＋ab＋/d－三元式序列：① (*，b，c) ② (＋，a，①)③ (＋，a，b)④ (/，②，③)⑤ (－，④，d)4. 已知文法 G[S] 為：S→dAB A→aA|aB→Bb|εG[S] 產(chǎn)生的語(yǔ)言是什么？ 答：G[S]產(chǎn)生的語(yǔ)言是L(G[S])={}。5. 構(gòu)造正規(guī)式相應(yīng)的 DFA : 1(1010 * | 1(010) * 1) * 0。解：1(1010 * | 1(010) * 1) * 0對(duì)應(yīng)的NFA為：6. 已知文法G(S) S→a|∧|(T) T→T，S|S 寫(xiě)出句子((a，a)，a)的規(guī)范歸約過(guò)程及每一步的句柄。解：句型 歸約規(guī)則 句柄 ((a，a)，a) S→a a((S，a)，a) T→S S ((T，a)，a) S→a a((T，S)，a) T→T，S T，S((S)，a) T→S S((T)，a) S→S(T) (T)(S，a) T→S S(T，a) S→a a(T，S) T→T，S T，S(T) S→(T) (T)S 7. 寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。解：文法G(N)：N→AB|BA→AC|DB→1|3|5|7|9D→B|2|4|6|8C→0|D8. 設(shè)文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左遞歸和回溯；(2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW。解：(1) S→(L)|aS39。 S39。→S|ε L→SL39。 L39?！鶶L39。|ε (2) FIRST)S)＝{(，a} FOLLOW(S)＝{，，)} FIRST(S39。)＝{，a,ε} FOLLOW(S39。)＝{，，)}FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L39。)＝{，ε} FOLLOW(L39?！常絳 )}9. 已知文法G(E) E→T|E＋T T→F|T *F F→(E)|i (1)給出句型(T *F＋i)的最右推導(dǎo)； (2)給出句型(T *F＋i)的短語(yǔ)、素短語(yǔ)。解：(1) 最右推導(dǎo)： E=TF=(E)(E＋T)=(E＋F)(E＋i)=(T＋i)=(T*F＋i)(2) 短語(yǔ)：(T*F＋i)，T*F＋i，T*F，i素短語(yǔ)：T*F,i 10. While a＞0 ∨ b＜0 do Begin X：＝X＋1； if a＞0 then a：＝a－1 else b：＝b＋1 End； 翻譯成四元式序列。解：
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1