(整理完)編譯原理網(wǎng)上作業(yè)題參考答案20121101.doc

《(整理完)編譯原理網(wǎng)上作業(yè)題參考答案20121101.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院編譯原理作業(yè)題參考答案第一章編譯概述多項(xiàng)選擇題：1.編譯程序各階段的工作都涉及到（BC）。（﹡﹡）A.語(yǔ)法分析B.表格管理C.出錯(cuò)處理D.語(yǔ)義分析E.詞法分析2.編譯程序工作時(shí)，通常有（ABCE）階段。?（﹡）A.詞法分析B.語(yǔ)法分析C.中間代碼生成D.語(yǔ)義檢查E.目標(biāo)代碼生成填空題：1．解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)程序）。（﹡）2．編譯過(guò)程通?？煞譃?個(gè)階段，分別是（詞法分析）、（語(yǔ)法分析）、（中間代碼生成）、（代碼優(yōu)化）和（目標(biāo)代碼）生成。（﹡）3．編譯程序工作過(guò)程中，第

2、一段輸入是（源程序），最后階段的輸出為（目標(biāo)代碼生成）程序。（﹡）4．編譯程序是指將（高級(jí)語(yǔ)言編寫的）程序翻譯成（目標(biāo)語(yǔ)言）程序的程序。（﹡）綜合題：1.畫出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。（﹡﹡﹡）解答：編譯程序的總體結(jié)構(gòu)如下圖所示：詞法分析程序：輸入源程序，進(jìn)行詞法分析，輸出單詞符號(hào)。語(yǔ)法分析程序：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則（方法規(guī)則）把單詞符號(hào)串分解成各類語(yǔ)法單位，并判斷輸入串是否構(gòu)成語(yǔ)法上正確的“程序”。中間代碼生成程序：按照語(yǔ)義規(guī)則把語(yǔ)法分析程序歸約（或推導(dǎo)）出的語(yǔ)法單位翻譯成一

3、定形式的中間代碼，比如說(shuō)四元式。優(yōu)化程序：對(duì)中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成程序：把中間代碼翻譯成目標(biāo)語(yǔ)言程序。表格管理模塊保存一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展情況。編譯程序各階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需信息多數(shù)都需從表格中獲取，整個(gè)編譯過(guò)程中都在不斷地和表格打交道。出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。此外，編譯的各個(gè)階段都可能出現(xiàn)錯(cuò)誤。出錯(cuò)處理程序?qū)Πl(fā)現(xiàn)的錯(cuò)誤都及時(shí)進(jìn)行處理。第二章文法和語(yǔ)言的基本知識(shí)多項(xiàng)選擇題：1.ABC2.ACE3.BCD4.AC5.BC?填空題：1

4、．文法中的終結(jié)符和非終結(jié)符的交集是（空集）。詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定是（終結(jié)符），它一定只出現(xiàn)在產(chǎn)生式的（右）部。（﹡）2．最左推導(dǎo)是指每次都對(duì)句型中的（最左）非終結(jié)符進(jìn)行擴(kuò)展。（﹡）3．在語(yǔ)法分析中，最常見(jiàn)的兩種方法一定是（自上而上）分析法，另一是（自下而上）分析法。（﹡）4．采用（自上而下）語(yǔ)法分析時(shí)，必須消除文法的左遞歸。（﹡）5．（語(yǔ)法）樹(shù)代表推導(dǎo)過(guò)程，（分析）樹(shù)代表歸約過(guò)程。（﹡）6．自下而上分析法采用（移進(jìn)）、歸約、錯(cuò)誤處理、（接受）等四種操作。（﹡﹡）7．Chomsky把文法分為（4）

5、種類型，編譯器構(gòu)造中采用（2型）和（3型）文法，它們分別產(chǎn)生（上下文無(wú)關(guān)語(yǔ)言）和（正規(guī)語(yǔ)言）語(yǔ)言，并分別用（下推自動(dòng)機(jī)）和（有限）自動(dòng)機(jī)識(shí)別所產(chǎn)生的語(yǔ)言。（﹡﹡）判斷題：?1．正確2．錯(cuò)誤3．錯(cuò)誤4．錯(cuò)誤5．錯(cuò)誤6．錯(cuò)誤7．正確8．正確9．錯(cuò)誤簡(jiǎn)答題1句柄：（﹡）解答：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。2．素短語(yǔ)：（﹡﹡）解答：至少含有一個(gè)終結(jié)符的素短語(yǔ)，并且除它自身之外不再含任何更小的素短語(yǔ)。3．語(yǔ)法樹(shù)：（﹡﹡）解答：滿足下面4個(gè)條件的樹(shù)稱之為文法G[S]的一棵語(yǔ)法樹(shù)?！　、倜恳唤K結(jié)均有一標(biāo)記，此標(biāo)記為V

6、N∪VT中的一個(gè)符號(hào)；　?、跇?shù)的根結(jié)點(diǎn)以文法G[S]的開(kāi)始符S標(biāo)記；　　③若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號(hào)；　?、苋粢粋€(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2,…,Xk，則A→X1,X2,…,Xk，必然是G的一個(gè)產(chǎn)生式。4．歸約：（﹡﹡）解答：我們稱αγβ直接歸約出αAβ，僅當(dāng)A→γ是一個(gè)產(chǎn)生式，且α、β∈(VN∪VT)*。歸約過(guò)程就是從輸入串開(kāi)始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開(kāi)始符。5．推導(dǎo)：（﹡﹡）解答：我們稱α

7、Aβ直接推出αγβ，即αAβTαγβ，僅當(dāng)A→γ是一個(gè)產(chǎn)生式，且α、β∈(VN∪VT)*。如果α1α2…αn，則我們稱這個(gè)序列是從α1至α2的一個(gè)推導(dǎo)。若存在一個(gè)從α1αn的推導(dǎo)，則稱α1可推導(dǎo)出αn。推導(dǎo)是歸約的逆過(guò)程。問(wèn)答題1．給出上下文無(wú)關(guān)文法的定義。（﹡﹡）解答：　　一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式（VT,VN,S,P），其中：　　●VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)；　　●VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VT∩VN=Φ；　　●S是一個(gè)非終結(jié)符號(hào)，稱為開(kāi)始符號(hào)；　　●P是一個(gè)

8、產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2.文法G[S]：　　　　　　　S→aSPQ

9、abQ　　　　　　　QP→PQ　　　　　　　bP→bb　　　　　　　bQ→bc　　　　　　　cQ→cc　　?。?）它是Chomsky哪一型文法？　　?。?）它生成的語(yǔ)言是什么？（﹡﹡﹡）解答：　?。?/p>