1、作業一1 .已知文法GA,寫出它定義的語言描述如：GA:A f 0B|1CB- 1|1A|0BBC- 0|0A|1CC2. 給出生成下述語言的上下文無關文法：(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的短語，簡單(直接)短語，句柄。第3章練習題一、判斷題：1、編譯程序中的詞法分析程序以字符形式的源程序作為輸入，輸出的單詞符號常 采用二

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

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

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

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

6、0)如果在推導過程中的任何一步a=>3,都是對口中的最右非終結符進行替換，則稱這種推導為()。A.直接推導 B.最右推導C.最左推導D.規范推導(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)設有文法 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) 一個句型最左邊的()稱為該句型的句柄。A.短語B.素短語C.直接短語D.規范短語(14)設有文法GS:E f E+T | E-T |TT f T*F |T/F|FF - (E) |i該文法白句型E+T*F的句柄是下列符號串()。A E B E+T C T*F D E+T*F （15）設有文法GT:T f T*F |FFf FAP | PP - （T） |a該文法白句型T*PA（T*F）的直接短語是下列符號串（）。A. P B. （T*F） C. T*F D. PA（T*F）（16）若一個文法滿足（），則稱該文法是二義文法。A.

8、文法的某一個句子存在兩棵（包括兩棵）以上的語法樹。B.文法的某一個句子，它有兩個（包括兩個）以上的最右（最左）推導。C.文法的某一個句子，它有兩個（包括兩個）以上的最右（最左）歸約。D.文法的某一個句子存在一棵（包括一棵）以上的語法樹。（17）在下列描述含+, *算術表達式的文法中，屬于二義性文法的是（）。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.上下文無關文法B. 正規文法C.上下文有關文法 B.無限制文法1、如下程序流圖（圖11.18）中，B3中的i ： =2是循環不變量，可以將其提到前置結點嗎 你還能舉出一些例子說明循環不變量外移的條件嗎？圖 11.182、2、對圖11.19的流圖：(1)求出流圖中各結點 n的必經結點集(2)求出流圖中的回邊；(3)求出流圖中的循環。圖 11.19L ®-D(n)；B8語法分析部分一、判斷題：1、LL (1)文法是無左遞歸、無二義性文法。2、無左遞歸的文法是 LL (1)文法。3、在高級語言編譯程序常用的語法分析方法中，預測分析法屬于自上而下的語法分析方 法。4、在高級語

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

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

12、T - > FT 'T? -> *FT? |£F >(E)|idFIRST(T?)=, FOLLOW(F)=.A. (, id ) B. *,e C. *,+,# D. +,),#6、自下而上語法分析法的原理是 .A.移進-推導法” B. 移進-歸約法” C .最左推導法” D.推導-歸約法”7、設有文法 G如果文法G中沒有形如A->BC 的規則，其中A, B, C為非終結符，則稱 文法G為.A.算符優先文法B. LL (1)文法C. LR (1)文法 D. 算符文法9、設有文法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、設有文法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)項目集規范族的項目類型可分為 .A.移進項目B.歸約項目C待約項目D.接受項目12、 LR0)分析器的核心部分是一張分析表，這張分析表包括兩部分，它們是A. LL(1)分析表B.分析動作表C狀態轉換表D.移進分析

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

15、操作。6、自下而上語法制導翻譯法的特點是在棧頂形成句柄，在歸約之前執行相應的語義動作。7、逆波蘭表達式ab+cd+*所代表的中綴形式的表達式是a+b*c+d.8、賦值語句A=A+B*CA(D/E)/F的逆波蘭表示是 AABCDE/A*F/+=9、表達式-(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)編譯程序的語義處理有兩個任務：一個是()，另一個是()。A.靜態語義審查B。審查語法結構C.執行真

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

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