編譯原理復(fù)習(xí)題(考試)

1、編譯原理復(fù)習(xí)題一、是非題1計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。(×)3每個(gè)文法都能改寫為 LL(1) 文法。 (×)4算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ()5LR分析方法是自頂向下語法分析方法。 (×)6“ 用高級(jí)語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法。(× )7一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 ()8僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。 ( )9在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 (× )10對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存

2、分配策略。(×)11甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(× )12遞歸下降分析法是自頂向下分析方法。( )13產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 (×)14在 SLR(1)分析法的名稱中，S的含義是簡(jiǎn)單的。()15綜合屬性是用于 “ 自上而下 ” 傳遞信息。(× )16符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。 (×)17程序語言的語言處理程序是一種應(yīng)用軟件。 (×)18解釋程序適用于 COBOL 和 FORTRAN 語言。 (

3、×)19一個(gè) LL(l)文法一定是無二義的。 ()20正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ()21一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。 (×)22目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ()22逆波蘭法表示的表達(dá)式亦稱后綴式 。 ( )23如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。 ( )24數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。()25算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 (×)26編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。(× )27一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且

4、僅有一個(gè)唯一的終態(tài)。(×)28一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ( )29語法分析時(shí)必須先消除文法中的左遞歸 。 (×)30LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 ()31逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。 ( )32靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。 ()33進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。 ()34兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 ()35一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 (×)36設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L

5、(s)。(×)37確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。()38詞法分析作為單獨(dú)的一遍來處理較好。 (× )39構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 ()40規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 ()41同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖突。 (× )42LR分析技術(shù)無法適用二義文法。 (× )43樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 (×)44程序中的表達(dá)式語句在語義翻譯時(shí)不需要回填技術(shù)。 ()45對(duì)中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。 (× )46若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部

6、，則此右部一定是該句型的句柄。(×)47在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。(×)48削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。(×)49編譯程序與具體的機(jī)器有關(guān)，與具體的語言無關(guān)。(×)二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)1 一個(gè)編譯程序中，不僅包含詞法分析，( A )，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A語法分析 B文法分析C語言分析D解釋分析2 語法分析器則可以發(fā)現(xiàn)源程序中的( D )。A語義錯(cuò)誤   B語法和語義錯(cuò)誤C錯(cuò)誤并校正    D語法錯(cuò)誤3 解釋程

7、序處理語言時(shí) , 大多數(shù)采用的是( B )方法。A源程序命令被逐個(gè)直接解釋執(zhí)行B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行D以上方法都可以4 編譯程序是一種( B )。A匯編程序 B翻譯程序C解釋程序         D目標(biāo)程序5 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是( B )。A.短語文法     B正則文法C上下文有關(guān)文法 D上下文無關(guān)文法6 通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五

8、個(gè)部分，還應(yīng)包括( C )。A模擬執(zhí)行器             B解釋器      C表格處理和出錯(cuò)處理     D符號(hào)執(zhí)行器7 一個(gè)句型中的最左( B )稱為該句型的句柄。A短語         B簡(jiǎn)單短語       C素短語     

9、0;    D終結(jié)符號(hào) 8 文法 GE ：      ETE T      TFT F      Fa （ E ）該文法句型 E F (E T) 的簡(jiǎn)單短語是下列符號(hào)串中的( B )。 （ E T ）   E T      F    F (E T) A 和 B 和 C 和 D 9 詞法分析器用于識(shí)別( C )

10、。A句子      B句型         C單詞         D產(chǎn)生式 10 在自底向上的語法分析方法中，分析的關(guān)鍵是( A )。 A尋找句柄         B尋找句型       C消除遞歸       D選擇候選式 11 文法

11、G 產(chǎn)生的( D )的全體是該文法描述的語言。A句型 B終結(jié)符集 C非終結(jié)符集 D句子12 若文法 G 定義的語言是無限集，則文法必然是( A )。  A遞歸的   B前后文無關(guān)的C二義性的 D無二義性的13 四種形式語言文法中，1型文法又稱為( C )文法。A短語結(jié)構(gòu)文法       B前后文無關(guān)文法 C前后文有關(guān)文法     D正規(guī)文法 14 一個(gè)文法所描述的語言是( A )。A唯一的   B不唯一的C可能唯一，好可能不唯一   D都不對(duì)15 ( B )和代碼優(yōu)化部分不是

12、每個(gè)編譯程序都必需的。A語法分析   B中間代碼生成C詞法分析       D目標(biāo)代碼生成 16( B )是兩類程序語言處理程序。 A高級(jí)語言程序和低級(jí)語言程序B解釋程序和編譯程序 C編譯程序和操作系統(tǒng)D系統(tǒng)程序和應(yīng)用程序 17 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的( D )的信息。A維數(shù) B類型       C維上下界         D各維的界差 18. 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，

13、它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組( D )。 A句子 B句型C單詞 D產(chǎn)生式19 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是( D )。A短語文法    B正則文法     C上下文有關(guān)文法D上下文無關(guān)文法20文法 G 所描述的語言是( C )的集合。 A文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串B文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串C由文法的開始符號(hào)推出的所有終極符串D由文法的開始符號(hào)推出的所有符號(hào)串21詞法分析器用于識(shí)別( C )。  A字符串  

14、 B語句C單詞 D標(biāo)識(shí)符22文法分為四種類型，即0型、1型、2型、3型。其中0型文法是( A )。A短語文法     B正則文法     C上下文有關(guān)文法 D上下文無關(guān)文法24( A )是一種典型的解釋型語言。  ABASIC BC CFORTRAN  DPASCAL25與編譯系統(tǒng)相比，解釋系統(tǒng)( D )。A比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度快 B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快C比較簡(jiǎn)單 , 可移植性差 , 執(zhí)行速度慢 D比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度慢 26用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的

15、程序叫( B )。 A源程序       B目標(biāo)程序      C連接程序 D解釋程序27詞法分析器用于識(shí)別( A )。   A字符串       B語句          C單詞        D標(biāo)識(shí)符 28編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后 , 到正式上機(jī)運(yùn)

16、行之前，一般要經(jīng)過( B )這幾步: (1) 編輯   (2) 編譯   (3) 連接   (4) 運(yùn)行 A(1)(2)(3)(4)     B(1)(2)(3)    C(1)(3)     D(1)(4)29把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由( B )完成的。A編譯器            B匯編器   &#

17、160;       C解釋器            D預(yù)處理器31詞法分析器的輸出結(jié)果是( C )。A單詞的種別編碼 B單詞在符號(hào)表中的位置C單詞的種別編碼和自身值 D單詞自身值32 正規(guī)式 M 1 和 M 2 等價(jià)是指( C )。  AM1和M2的狀態(tài)數(shù)相等BM1和M2的有向邊條數(shù)相等CM1和M2所識(shí)別的語言集相等DM1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 33 文法G：SxSx|y所識(shí)別的語言是( C )。Axyx&#

18、160; B(xyx)* C     Dx*yx* 34如果文法G是無二義的，則它的任何句子 ( A )。A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同C最左推導(dǎo)和最右推導(dǎo)必定相同   D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 35構(gòu)造編譯程序應(yīng)掌握( D )。A源程序   B目標(biāo)語言C編譯方法      D以上三項(xiàng)都是36四元式之間的聯(lián)系是通過( B )實(shí)現(xiàn)的。 A指示器      &#

19、160;  B臨時(shí)變量C符號(hào)表             D程序變量 37表達(dá)式(AB)(CD)的逆波蘭表示為( B )。AABCD BABCD      CABCD         DABCD 38. 優(yōu)化可生成( D )的目標(biāo)代碼。A運(yùn)行時(shí)間較短B占用存儲(chǔ)空間較小C運(yùn)行時(shí)間短但占用內(nèi)存空間大 D運(yùn)行時(shí)間短且占用存儲(chǔ)空間小39下列( C )優(yōu)化方法不是針對(duì)循

20、環(huán)優(yōu)化進(jìn)行的。A強(qiáng)度削弱     B刪除歸納變量     C刪除多余運(yùn)算   D代碼外提40編譯程序使用( B )區(qū)別標(biāo)識(shí)符的作用域。 A說明標(biāo)識(shí)符的過程或函數(shù)名B說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次C說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 D標(biāo)識(shí)符的行號(hào)41編譯程序絕大多數(shù)時(shí)間花在( D )上。A出錯(cuò)處理 B詞法分析 C目標(biāo)代碼生成 D表格管理42 編譯程序是對(duì)( D )。  A匯編程序的翻譯   B高級(jí)語言程序的解釋執(zhí)行C機(jī)器語言的執(zhí)行 D高級(jí)語言的翻譯 43 采用自上而下分析，必須( C )。A消除

21、左遞歸  B消除右遞歸C消除回溯  D提取公共左因子 44在規(guī)范歸約中，用( B )來刻畫可歸約串。A直接短語 B句柄C最左素短語   D素短語 45 若a為終結(jié)符，則A-> · a為( B ) 項(xiàng)目。A歸約   B移進(jìn)     C接受      D待約 46間接三元式表示法的優(yōu)點(diǎn)為( A )。 A采用間接碼表，便于優(yōu)化處理B節(jié)省存儲(chǔ)空間，不便于表的修改C便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理 47基本塊內(nèi)的優(yōu)化為( B

22、 )。A代碼外提，刪除歸納變量B刪除多余運(yùn)算，刪除無用賦值C強(qiáng)度削弱，代碼外提D循環(huán)展開，循環(huán)合并48. 在目標(biāo)代碼生成階段，符號(hào)表用( D )。A目標(biāo)代碼生成 B語義檢查C語法檢查 D地址分配49若項(xiàng)目集Ik含有A-> · ，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aFOLLOW(A)時(shí)，才采取“A-> · ”動(dòng)作的一定是( D )。ALALR文法    BLR(0)文法 CLR(1)文法DSLR(1)文法50堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守( D )原則。 A先請(qǐng)先放   B先請(qǐng)后放C后請(qǐng)先放  

23、0;D任意三、填空題1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有_表格處理_和 _出錯(cuò)處理_。 2編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。3產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。 4設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S->x( 其中 xVT*), 則稱 x是文法的一個(gè)_句子_。 5自頂向下的語法分析方法的基本思想是：從文法的_開始符號(hào)_開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)_，試圖推導(dǎo)出文法的_句子_，使之與給定的輸入串_匹配_。 6常用的參數(shù)傳遞方式有_傳

24、地址_，傳值和傳名。 7一個(gè)句型中的最左簡(jiǎn)單短語稱為該句型的_句柄_。 8對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 _語義規(guī)則_ 。9一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。10 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。11 掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_。 12 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。13語法分析是依據(jù)語言的_語法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進(jìn)行的。14語法分析器的輸入是_單詞符號(hào)串_，

25、其輸出是_語法單位_。15一個(gè)名字的屬性包括_類型_和_作用域_。16逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為_(a+b+c)*d-e_ 。 17語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。18計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 19掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。20自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。21一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。22后綴式abc-/所代表的表達(dá)式是_a/(b

26、-c)_。 23局部?jī)?yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。24詞法分析基于_正則_文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。 25語法分析基于_上下文無關(guān)_文法進(jìn)行，即識(shí)別的是該類文法的句子。語法分析的有效工具是_語法樹_。26分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是_最左素短語_，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是_句柄_。27語義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭_、_四無式表示_與_三元式表示_等。28按Chomsky分類法，文法按照_規(guī)則定義的形式_進(jìn)行分類。 29一個(gè)文法能用有窮多個(gè)規(guī)則描述無窮的符號(hào)串集合（語言）是因?yàn)槲姆ㄖ写嬖谟衉遞歸_定

27、義的規(guī)則。四、簡(jiǎn)答題111. 寫一文法，使其語言是偶正整數(shù)的集合,要求：    (1)允許0打頭；   (2) 不允許0打頭。解：(1)GS=(S,P,D,N,0,1,2,9,P,S) P: S->PD|D P->NP|N D->0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)GS=(S,P,R,D,N,Q ,0,1,2,9,P,S) P: S->PD|P0|D P->NR|N R->QR|Q D->2|4|6|8 N->1|2|3|4|5|6|7|8|9

28、Q->0|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. 寫出表達(dá)式(ab*c)/(ab)d的逆波蘭表示和三元式序列。逆波蘭表示： abc*ab/d三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)4. 已知文法 GS 為：   SdAB    AaA|a   BBb|   GS 產(chǎn)生的語言是什么？ 答：GS產(chǎn)生的語言是L(GS)=。5. 構(gòu)造正規(guī)式相應(yīng)的

29、DFA : 1(1010 * | 1(010) * 1) * 0。解：1(1010 * | 1(010) * 1) * 0對(duì)應(yīng)的NFA為：6. 已知文法G(S) Sa|(T) TT，S|S 寫出句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。解：句型歸約規(guī)則 句柄 (a，a)，a)Saa(S，a)，a)TSS (T，a)，a)Saa(T，S)，a)TT，S T，S(S)，a) TSS(T)，a) SS(T) (T)(S，a) TSS(T，a) Saa(T，S) TT，S T，S(T) S(T) (T)S7. 寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。解：文法G(N)：NAB|BAA

30、C|DB1|3|5|7|9DB|2|4|6|8C0|D8. 設(shè)文法G(S)： S(L)|a S|a LL，S|S    (1) 消除左遞歸和回溯；   (2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW。解：(1) S(L)|aS' S'S| LSL' L'SL'| (2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S')，a,FOLLOW(S')#，)FIRST(L)(，aFOLLOW(L) ) FIRST(L')，F(xiàn)OLLOW(L' )9.

31、已知文法G(E) ET|ET TF|T *F F(E)|i (1)給出句型(T *Fi)的最右推導(dǎo)； (2)給出句型(T *Fi)的短語、素短語。解：(1) 最右推導(dǎo)： E=>T->F=>(E)->(ET)=>(EF)->(Ei)=>(Ti)=>(T*Fi)(2) 短語：(T*Fi)，T*Fi，T*F，i素短語：T*F,i 10. Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻譯成四元式序列。解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4)

32、 (j，15) (5) (，X，1，T1) (6) (：，T1，X) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15)11. 寫出下列表達(dá)式的三地址形式的中間表示。   (1) 5+6 *(a + b);    (2)for j:=1 to 10 do aj + j:=0。答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (

33、2)100: j:=1 101: if j>10 goto NEXT 102: i:=j+j 103: ai:=012. 設(shè)基本塊p由如下語句構(gòu)成：    T 0 : =3.14;    T 1 :=2*T 0 ;    T 2 :=R+r;    A:=T l *T 2 ；    B:=A;    T 3 :=2*T 0 ;    T 4 :=R+r;   &

34、#160;T 5 :=T 3 *T 4 ;    T 6 :=R-r ；    B:=T 5 *T 6 ；試給出基本塊p的 DAG 。解：基本塊p的DAG圖: 1234+-*T03.14T1,T36.28RrT2,T4T6A,T5B13. 寫出表達(dá)式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：（1）三元式：（，a，b）（，a，b）（/，）（*，b，c）（，a，）（，）（2）四元式：（，a，b，T1）（，a，b，T2）（/，T1，T2，T3）（*，b，c，T4）（，a，T4，T5）（，T3，T5，T6）14. 寫一個(gè)文

35、法使其語言為偶數(shù)集，且每個(gè)偶數(shù)不以0開頭。 解：文法G（S）：SAB|B|A0 AAD|C B2|4|6|8 C1|3|5|7|9|B D0|C15. 設(shè)文法 G （ S ）：    SS aF|aF| aF    F*aF|*a  （1）消除左遞歸和回溯； （2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合。解：（1） S->aFS'|aFS' S'->aFS'| F->*aF' F'->F| （2）FIRST（S）a，+ FOLLOW（S）FIRST（S&#

36、39;）+， FOLLOW（S'）FIRST（F）* FOLLoW（F）（+， FIRST（F'）*， FOLLOW（+，16. 簡(jiǎn)要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。17. 考慮文法 GS: S (T) | a+S | a T T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸：S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 18. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。

37、解： w a b + c d e 10 - / + 8 + * +19. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (A<C B<D) if (A 1) C=C+1;else while (A D)A=A+2;。解：該語句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)ACBD、A1和AD，并且關(guān)系運(yùn)算符優(yōu)先級(jí)高)：100 (j<,A,C,102) 101 (j,_,_,113) 102 (j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 10

38、7 (j,_,_,112) 108 (j,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100)11320. 已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。證明：由文法GS：SaSb|Sb|b，對(duì)句子aabbbb對(duì)應(yīng)的兩棵語法樹為： 因此，文法GS為二義文法。21. 文法 GS 為： S->Ac|aB A->ab B->bc 寫出 L(GS) 的全部元素。解：S=>Ac=>abc 或S=>aB=>abc 所以L(GS)=abc22.

39、構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的DFA。解：先構(gòu)造NFA：確定化： 重新命名，令A(yù)B為B、AC為C、ABY為D得： 所以，可得DFA為： 23. 文法 S->a|(T) T->T,S|S 對(duì) (a,(a,a) 和 (a,a),(a),a) 的最左推導(dǎo)。解： 對(duì)(a,(a,a)的最左推導(dǎo)為： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T) =>(a,(T,S) =>(a,(S,S) =>(a,(a,S) =>(a,(a,a) 對(duì)(a,a),(a),a) 的最左推導(dǎo)為： S=>(T) =

40、>(T,S) =>(S,S) =>(T),S) =>(T,S),S) =>(T,S,S),S) =>(S,S,S),S) =>(T),S,S),S) =>(T,S),S,S),S) =>(S,S),S,S),S) =>(a,S),S,S),S) =>(a,a),S,S),S) =>(a,a),S),S) =>(a,a),(T),S) =>(a,a),(S),S) =>(a,a),(a),S) =>(a,a),(a),a)24. 文法： S->MH|a H->LSo| K->dML|

41、 L->eHf M->K|bLM 判斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1) 分析表。解：各符號(hào)的FIRST集和FOLLOW集為： 預(yù)測(cè)分析表為：由于預(yù)測(cè)分析表中無多重入口，所以可判定文法是LL(1)的。25敘述由下列正規(guī)式描述的語言(a)0(0|1)*0(b)(|0)1*)*(c)(0|1)*0(0|1)(0|1)(d)0*10*10*10*(e)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*解：(a)以0開頭、以0結(jié)尾的所有0和1的串。(b)由0和1組成的串，包括空串。(c)倒數(shù)第3個(gè)字符為0，由0和1組成的串。(d)含有3個(gè)

42、1的所有0和1的串。(e)由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有0和1的串。26已知文法GS：S(L)|aLL,S|S為句子(a,(a,a)構(gòu)造最左推導(dǎo)和最右推導(dǎo)。解：句子(a,(a,a)的最左推導(dǎo)為：S=>(L)=>(L,S) =>(S,S)=>(a,S) =>(a,(L)=>(a,(L,S) =(a,(S,S)=>(a,(a,S)=>(a,(a,a)句子(a,(a,a)的最右推導(dǎo)為：S=>(L)=>(L,S) =>(l,(L)=>(L,(L,S)=>(L,(L,a)=>(L,(S,a)=>(L,(a,a)=(

43、S,(a,a)=(a,(a,a)五.計(jì)算題1構(gòu)造下述文法 GS 的自動(dòng)機(jī)： S->A0 A->A0|S1|0 該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。解：由于該文法的產(chǎn)生式S->A0，A->A0|S1中沒有字符集VT的輸入，所以不是確定的自動(dòng)機(jī)。 要將其他確定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把S?A0代入產(chǎn)生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S->A0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動(dòng)機(jī)為： 由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA，下面將它確定化：下表由子集法將N

44、FA轉(zhuǎn)換為DFA: 由上表可知DFA為：2對(duì)下面的文法 G ： E->TE' E'->+E| T->FT' T' ->T| F-> PF' F'-> *F'| P->(E)|a|b| (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。 (2) 證明這個(gè)方法是 LL(1) 的。 (3) 構(gòu)造它的預(yù)測(cè)分析表。 解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b

45、,; FIRST(E')=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T')=FIRST(T)=(,a,b,; FIRST(F)=FIRST(P)=(,a,b,; FIRST(F')=FIRST(P)=*,; FIRST(P)=(,a,b,; FOLLOW集合有： FOLLOW(E)=),#; FOLLOW(E')=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E')FOLLOW(E)=+,),#;/不包含 FOLLOW(T')=FOLLOW(T)=FIRST(E')FOLLOW

46、(E)=+,),#; FOLLOW(F)=FIRST(T')FOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F')=FOLLOW(F)=FIRST(T')FOLLOW(T)=(,a,b,+,),#; FOLLOW(P)=FIRST(F')FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)證明這個(gè)方法是LL(1)的。 各產(chǎn)生式的SELECT集合有： SELECT(E->TE')=FIRST(T)=(,a,b,; SELECT(E'->+E)=+; SELECT(E'->)=FOLLOW(E/)=),# SELECT(T->FT')=FIRST(F)=(,a,b,; SELECT(T'->T)=FIRST(T)=(,a,b,; SELECT(T'-&