編譯原理習(xí)題

1、作業(yè)一1 .已知文法GA,寫出它定義的語言描述如：GA:A f 0B|1CB- 1|1A|0BBC- 0|0A|1CC2. 給出生成下述語言的上下文無關(guān)文法：(1) a nbnambml n , m>=0(2) 1 n0m 1m0n| n , m>=03. 給出生成下述語言的三型文法：(1) anbmjn,m>=1 a nbmck|n,m,k>=0 4、文法 GE為：E- E+T|TTf T*F|FF-(E)|i試給出句型(E+F)*i的短語，簡(jiǎn)單(直接)短語，句柄。第3章練習(xí)題一、判斷題：1、編譯程序中的詞法分析程序以字符形式的源程序作為輸入，輸出的單詞符號(hào)常 采用二

2、元組的形式。2、正規(guī)式的運(yùn)算符“ |”讀作”或3、若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是等價(jià)的。4、用l代表字母，d代表數(shù)字，2=l,d,則正規(guī)式r=dd*定義了無符號(hào)整數(shù)單詞。5、一個(gè)確定的有窮自動(dòng)機(jī)DFA M的轉(zhuǎn)換函數(shù)f是一個(gè)從Kx 2到K的子集的映像。6、一個(gè)非確定的有窮自動(dòng)機(jī) NFA N的轉(zhuǎn)換函數(shù)f是一個(gè)從KxNiJK的映像。7、一張狀態(tài)轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。8、終態(tài)與非終態(tài)是可區(qū)別的。9、對(duì)任意一個(gè)右線性文法 G,都存在一個(gè) NFA M滿足L ( G) =L ( M)。10、對(duì)任意一個(gè)右線性文法 G都存在一個(gè) DFA M滿足L (M)

3、 =L (R)。二、構(gòu)造正規(guī)式1(0|1) *101相應(yīng)的DFA.練習(xí)題2一、判斷題：1、 空符號(hào)串的集合 £ = 6。2、 設(shè)A是符號(hào)串的集合，則 A0= e。3、 設(shè)G是一個(gè)文法，S是開始符號(hào)，如果 S => x且xC W則稱x是文法G網(wǎng)的句型。4、 在形式語言中，最右推導(dǎo)的逆過程也稱為規(guī)范歸約。5、 一個(gè)語言的文法是唯一的。6、 若一個(gè)語言是無窮集合，則定義該語言的文法一定是遞歸的。7、 一個(gè)句型中出現(xiàn)某個(gè)產(chǎn)生式的右部，則此右部一定是此句型的句柄。8、 每個(gè)直接短語都是某規(guī)則的右部。9、 用二義性文法定義的語言也是二義性的。10、 文法的二義性與語言的二義性是兩個(gè)不同的概

4、念。11、 任何正規(guī)文法都是上下文無關(guān)文法。12、 正規(guī)文法對(duì)規(guī)則的限制比上下文無關(guān)文法對(duì)規(guī)則的限制要多一些。二、選擇題(從各題的 4個(gè)答案中選出一個(gè)或多個(gè)正確的答案寫在橫線上)(1) 一般程序設(shè)計(jì)語言的描述都涉及()3個(gè)方面。A 語法B 語用C 語義D 基本符號(hào)的確定(2)為了使編譯程序能對(duì)程序設(shè)計(jì)語言進(jìn)行正確的翻譯，必須采用()方法定義程序設(shè)計(jì)語言。A 非形式化B 自然語言描述問題號(hào)體系相結(jié)合(3)設(shè)x是符號(hào)串的哥運(yùn)算 x0=(A 1 B x C£ D *(4)設(shè)A是符號(hào)串的集合，則 A=(A A IA2U, U AnU,B A 0U Al A2U, U AnU, _+C S U

5、 AD A 0U A+(5)字母表中的元素可以是(A字母B字母和數(shù)字 C 數(shù)字D字母、數(shù)字和其他符號(hào)(6)文法用來描述語言的語法結(jié)構(gòu)，它由如下 開始符號(hào)。A文法終結(jié)符集合B文法規(guī)則的集合C文法非終結(jié)符集合D字母數(shù)字串(7)在規(guī)則中，符號(hào)T (:二)表示(A 恒等于 B 等于 C 取決于 DC 形式化 D自然語言和符4個(gè)部分組成：()和文法)° 定義為)°(8)在規(guī)則中，符號(hào)“ | ”表示(A與 B 或C 非D 定引導(dǎo)開關(guān)參數(shù)(9)設(shè)文法GE的規(guī)則如下：ZA1|A0|Aa|Ac|a|b|c ,該文法的句子是下列符號(hào)串()A ab0 B a0c01 C aaa D bc10(1

6、0)如果在推導(dǎo)過程中的任何一步a=>3,都是對(duì)口中的最右非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為()。A.直接推導(dǎo) B.最右推導(dǎo)C.最左推導(dǎo)D.規(guī)范推導(dǎo)(11)描述語百L=ambn|n 噎mm> 1的文法為(A. Sf ABbB.SfABbZ aA|aAfaA|aBf bB|bBfaBb|bC. S fSb |AD.SfaAbZ aAb |ab Af Ab|aAb| e(12)設(shè)有文法 GS= (S, B b, SfbB|b ,BfbS, S),該文法描述的語言是 ()。A. L(GS)=bn|n > 0B. L(GS)=b2n |n > 0C. L(GS)=b2n+1|n &

7、gt;0D. L(GS)= b 2n+1|n > 1(13) 一個(gè)句型最左邊的()稱為該句型的句柄。A.短語B.素短語C.直接短語D.規(guī)范短語(14)設(shè)有文法GS:E f E+T | E-T |TT f T*F |T/F|FF - (E) |i該文法白句型E+T*F的句柄是下列符號(hào)串()。A E B E+T C T*F D E+T*F （15）設(shè)有文法GT:T f T*F |FFf FAP | PP - （T） |a該文法白句型T*PA（T*F）的直接短語是下列符號(hào)串（）。A. P B. （T*F） C. T*F D. PA（T*F）（16）若一個(gè)文法滿足（），則稱該文法是二義文法。A.

8、文法的某一個(gè)句子存在兩棵（包括兩棵）以上的語法樹。B.文法的某一個(gè)句子，它有兩個(gè)（包括兩個(gè)）以上的最右（最左）推導(dǎo)。C.文法的某一個(gè)句子，它有兩個(gè)（包括兩個(gè)）以上的最右（最左）歸約。D.文法的某一個(gè)句子存在一棵（包括一棵）以上的語法樹。（17）在下列描述含+, *算術(shù)表達(dá)式的文法中，屬于二義性文法的是（）。A.E- E+E|E*E|(E)|iB.E fEAE|(E)|iAf+ |*C. E - E+T |TD.Ef EAE|TT f T*F | FTf TBF|FF-(E)|IF-(E)|iAf +B- *（18）喬姆斯基把文法分成 4種類型，即0型、1型、2型和3型。2型文法也稱為（3型文法

9、也稱為（）。A.上下文無關(guān)文法B. 正規(guī)文法C.上下文有關(guān)文法 B.無限制文法1、如下程序流圖（圖11.18）中，B3中的i ： =2是循環(huán)不變量，可以將其提到前置結(jié)點(diǎn)嗎 你還能舉出一些例子說明循環(huán)不變量外移的條件嗎？圖 11.182、2、對(duì)圖11.19的流圖：(1)求出流圖中各結(jié)點(diǎn) n的必經(jīng)結(jié)點(diǎn)集(2)求出流圖中的回邊；(3)求出流圖中的循環(huán)。圖 11.19L ®-D(n)；B8語法分析部分一、判斷題：1、LL (1)文法是無左遞歸、無二義性文法。2、無左遞歸的文法是 LL (1)文法。3、在高級(jí)語言編譯程序常用的語法分析方法中，預(yù)測(cè)分析法屬于自上而下的語法分析方 法。4、在高級(jí)語

10、言編譯程序常用的語法分析方法中，算符優(yōu)先分析法屬于自上而下的語法分析方法。5、算符優(yōu)先分析法是一種規(guī)范規(guī)約分析法。6、算符優(yōu)先分析法是最適合于分析算術(shù)表達(dá)式。7、設(shè)有一個(gè)LR (0)項(xiàng)目集I=X-> a .B 3 ,A-> ” .,該項(xiàng)目集含有“移進(jìn)一歸約"沖突。8、LR分析法是一種規(guī)范規(guī)約分析法。9、設(shè)有一個(gè)LR (1)項(xiàng)目集I=X-> a .b 3 , " ,A-> " . , a ,該項(xiàng)目集含有“移進(jìn)一歸約"沖突。10、 SLR (1)文法是二義性文法。二、選擇題(從四個(gè)答案中選擇一個(gè)或多個(gè)正確答案寫在橫線上)1、編譯程序中

11、語法分析常用的方法 .A.自上而下分析法B.自下而上分析法C.自左向右分析法 D.自右向左分析法2、編譯程序的語法分析器接受以 為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。A. 表達(dá)式 B. 字符串C.單詞D. 語句3、在高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于 分析法。A.自左向右分析法 B.自上而下分析法C.自下而上分析法 D.自右向左分析法4、遞歸分析法和預(yù)測(cè)分析法要求描述的文法是 。A. 正規(guī)文法 B. LR (1)文法C. LL (1)文法 D.右線性文法5、設(shè)有文法GE:E - >TE'E ' - > +TE' | £

12、T - > FT 'T? -> *FT? |£F >(E)|idFIRST(T?)=, FOLLOW(F)=.A. (, id ) B. *,e C. *,+,# D. +,),#6、自下而上語法分析法的原理是 .A.移進(jìn)-推導(dǎo)法” B. 移進(jìn)-歸約法” C .最左推導(dǎo)法” D.推導(dǎo)-歸約法”7、設(shè)有文法 G如果文法G中沒有形如A->BC 的規(guī)則，其中A, B, C為非終結(jié)符，則稱 文法G為.A.算符優(yōu)先文法B. LL (1)文法C. LR (1)文法 D. 算符文法9、設(shè)有文法GE:E->E+T|TT->T*F|FF->(E)|a句

13、型T+T*F+a的素短語是.A. a B. T*F C.T D.T+T*F10、設(shè)有文法GS:S->a| A |(T)T->T,S|S其中 FIRSTVT(T)=, LASTVT(T)=.A. a ,(,) B. a ,(,A )C. a ,(,?,?) D. a ,(,?,?, A)E. $, F. $,aG.a, ?.? H. ,?, ) ,a, A11、 LR (0)項(xiàng)目集規(guī)范族的項(xiàng)目類型可分為 .A.移進(jìn)項(xiàng)目B.歸約項(xiàng)目C待約項(xiàng)目D.接受項(xiàng)目12、 LR0)分析器的核心部分是一張分析表，這張分析表包括兩部分，它們是A. LL(1)分析表B.分析動(dòng)作表C狀態(tài)轉(zhuǎn)換表D.移進(jìn)分析

14、表13、 設(shè)有LR (0)項(xiàng)目集I=X-> a. b 3 , A-> ” .,B-> a .,該項(xiàng)目集含有沖突項(xiàng)目，它們是 .A、“移進(jìn)一歸約”沖突 B. “移進(jìn)一接受”沖突C “移進(jìn)一待約”沖突D. “歸約一歸約”沖突第五章自測(cè)練習(xí)題判斷題：1、對(duì)任何一個(gè)編譯程序來說，產(chǎn)生中間代碼是不可缺少的一部分。2、目前多數(shù)編譯程序進(jìn)行語義分析的方法采用語法制導(dǎo)翻譯法，這是因?yàn)檎Z法制導(dǎo)翻譯法是一種形式化系統(tǒng)。3、一個(gè)屬性文法包括一個(gè)上下文無關(guān)文法和一系列規(guī)則。4、文法符號(hào)的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性。5、自下而上語法制導(dǎo)翻譯法的特點(diǎn)是語法分析棧與語義分析棧不需同時(shí)

15、操作。6、自下而上語法制導(dǎo)翻譯法的特點(diǎn)是在棧頂形成句柄，在歸約之前執(zhí)行相應(yīng)的語義動(dòng)作。7、逆波蘭表達(dá)式ab+cd+*所代表的中綴形式的表達(dá)式是a+b*c+d.8、賦值語句A=A+B*CA(D/E)/F的逆波蘭表示是 AABCDE/A*F/+=9、表達(dá)式-(a+b)*(c+d)-(a+b+c)的四兀式表不'是：(1) (T1=a+b)(2) (T2=-T1)(3) (T3=c+d)(4) (T4=T2*T3)(5) (T5=a+b)(6) (T6=T5+c)(T7=T4-T6)選擇題：(1)編譯程序的語義處理有兩個(gè)任務(wù)：一個(gè)是()，另一個(gè)是()。A.靜態(tài)語義審查B。審查語法結(jié)構(gòu)C.執(zhí)行真

16、正的翻譯D。審查語義結(jié)構(gòu)(2)在編譯程序中安排中間代碼生成的目的是()。A .便于進(jìn)行存儲(chǔ)空間的組織B. 利于目標(biāo)代碼優(yōu)化C. 利于提高目標(biāo)代碼的質(zhì)量D. 利于編譯程序的移植(3)編譯過程中比較常見的中間語言有()。A .逆波蘭式 B。三元式C.四元式 D。樹形表示(4)中綴表達(dá)式-a+b*(-c+d)的逆波蘭表式是()。A . abcd+* +Bo abcd+8+C. abcd+*+D。abcd+*+(5)后綴式iiii-/A的中綴表達(dá)式是A. IA(i/(I-I)Bo (I-I)/IAiC. |A(|-|)/iDo (I-I)Ai/i自測(cè)練習(xí)題4選擇題：(1)在編譯過程中符號(hào)表的主要作用是

17、()。A.幫助錯(cuò)誤處理B.輔助語法錯(cuò)誤檢查C.輔助上下文語義正確性檢查D.輔助目標(biāo)代碼生成(2)符號(hào)表的查找一般可以使用()A.順序查找 B.折半查找C.雜湊查找D.排序查找(3)編譯程序中安排優(yōu)化的目的是為得到()的目標(biāo)代碼。A.結(jié)構(gòu)清晰 B.較短 C.高效率D.使用存儲(chǔ)空間最小(4)根據(jù)所涉及程序的范圍，優(yōu)化可分為()。A .局部?jī)?yōu)化B.函數(shù)優(yōu)化C.全局優(yōu)化D.循環(huán)優(yōu)化(5)局部?jī)?yōu)化是局限與一個(gè)()范圍內(nèi)的優(yōu)化。A.循環(huán) B.函數(shù) C.基本塊D.整個(gè)程序(6)所謂基本塊是指程序中一個(gè)順序執(zhí)行的語句序列，其中只有()。A. 一個(gè)子程序B. 一個(gè)人口語句和多個(gè)出口語句C. 一個(gè)出口語句和多個(gè)入口語句D. 一個(gè)入口語句和一個(gè)出口語句(7)在編譯程