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