編譯原理和技術(shù)期末考試復(fù)習(xí)題

1、2.1考慮文法GS,其產(chǎn)生式如下：Sf (L)|aL-L, S|S(1)試指出此文法的終結(jié)符號、非終結(jié)符號。終結(jié)符號為：(,),a,非終結(jié)符號為：S,L開始符號為：S(2)給出下列各句子的分析樹：(a,(a,a),(a,a)(a,a)(a,(a,a)SS一 (a,(L,S) (a,(L,S)力(a,(S,S),S)(3)構(gòu)造下列各句子的一個最左推導(dǎo)：(a,a)S (L) FL,S)="(S,S) fa,S) (a,a) (a,(a,a)S (L) (L,S) (S,S) (a,S) (a,(L)(a,(S,S) (a,(a,S) (a,(a,a)(a,(a,a),(a,a)S =(L

2、) =(L,S)=(S,S) fa,S) =(a,(L)(a,(S,S)=(a,(L),S)=(a,(L,S),S)(a,(a,S),S) (a,(a,a),S) (a,(a,a),(L)=(a,(a,a),(L,S)一. (a,(a,a),(S,S)=(a,(a,a),(a,S)(a，(a，a),(a，a)(4)構(gòu)造下列各句子的一個最右推導(dǎo):(a,a)S =(L)L,S) , a)S =(L) =>(L,S) >(L,(S,a) (a , (a , a) , (a ,S 4(L) 4(L,S)ML,a) =(S,a) 與(a,a)，l,(L) =；(L,(a,a) a)=(L,(

3、L)=HL,(L,S) f (S,(a,a)一 (L,(L,a)(a,(a,a)0(L,(L,S)0(L,(L,(L)fL,(L,(L,S) =(L,(L,(a,a) 與(L,(L,S),(a,a) 與(L,(a,a),(a,a),(L,(L,(L,a)=(L,(S,(a,a)=(L,(L,(S,a)=(L,(L),(a,a)(L,(L,a),(a,a):：(S,(a,a),(a,a)=>(L,(S,a),(a,a)(a,(a,a),(a,a)(5)這個文法生成的語言是什么?L(GS) = ( a i, a 2,，a n)或 a其中ai(iwiwn),即L(GS)是一個以a為原子的純表，

4、但不包括空表。.2考慮文法GSSf aSbS|bSaS| £1)試說明此文法是二義性的。可以從對于句子 abab有兩個不同的最左推導(dǎo)來說明。S 二、aSbS i'abS Y'abaSbS 一'ababS "ababS -aSbS ' abSaSbS abaSbS - ababS abab 所以此文法是二義性的。(2)對于句子abab構(gòu)造兩個不同的最右推導(dǎo)。S aSbS ' aSbaSbS aSbaSb ' aSbab ababS 4aSbS =%Sb 與abSaSb ?abSab =abab(二)(3)對于句子abab構(gòu)造兩棵

5、不同的分析樹。(一)(4)此文法所產(chǎn)生的語言是什么？此文法產(chǎn)生的語言是：所有a的個數(shù)與b的個數(shù)相等的由a和b組成的字符串。2.4 已知文法 GS的產(chǎn)生式如下：S 一 (L)|aL - L,S|S屬于L(GS)的句子是A_, (a,a)是L(GS)的句子，這個句子的最左推導(dǎo)是 B,最右推導(dǎo) 是C ,分析樹是D ,句柄是E 。A： a a,a (L)(L,a)B,C: S =(L) W(L,S)='(L,a) t (S,a)今(a,a) S =、(L) 今(L,S) =>(S,S)今(S,a) =-(a,a) S -L) =ML,S) ，S,S)，a,S) =>(a,a)D:E

6、：(a,a) a,a (a) a解答：A： B : C : D : E :M的定義如下:3.1 有限狀態(tài)自動機可用五元組(VT, Q 8 , qo, Q)來描述，設(shè)有一有限狀態(tài)自動機VT=0,1 , Q=qo,q i,q 2, 6 (qo, 0) =qi 8 (q2, 1) =q2Q=q2, 8的定義為:8 (qi, 0) =q26 ( q2, 0) =q2它所對應(yīng)的狀態(tài)轉(zhuǎn)換圖為B,它所能接受的語言可以用正則表達式M是一個A有限狀態(tài)自動機, 表示為C 。其含義為D 。A:歧義的非歧義的確定的 非確定的B:0J0,1牲E囤電TI示升械毒，譚承絳止?fàn)畋P.C:(0|1) *00(0|1) *(0|1

7、) *000(0|1) *0D:由0和1所組成的符號串的集合；以0為頭符號和尾符號、由 0和1所組成的符號串的集合;以兩個0結(jié)束的，由0和1所組成的符號串的集合；以兩個0開始的，由0和1所組成的符號串的集合。答案 A: B: C: D:3.2 (1)有窮自動機接受的語言是正則語言。()(2)若ri和2是2上的正規(guī)式，則ri|r 2也是。()設(shè)M是一個NFA并且L(M) =x,y,z,則M的狀態(tài)數(shù)至少為 4個。(4)令2=a,b,則2上所有以b為首的字構(gòu)成的正規(guī)集的正規(guī)式為b*(a|b) *。對任何一個 NFA M 都存在一個 DFA M',使得L(M'尸L(M)。()(6)對一

8、個右線性文法 G,必存在一個左線性文法G',使得L(G尸L(G'),反之亦然。()答案(1) T (2) T (3) F (4) F (5) T3.3 描述下列各正規(guī)表達式所表示的語言。0(0|1) *0(2)( & |0)1 *) *(0|1) *0(0|1)(0|1)(4) 0*10*10*10*(5) (00|11) *(01|10)(00|11)*(01|10)(00|11)*)*答案(1) 以0開頭并且以0結(jié)尾的，由0和1組成的所有符號串(2) a | a C 0,1 *即由0和1組成的所有符號串。(3) 由0和1組成的符號串，且從右邊開始數(shù)第3位為0。(4)

9、 含3個1的由0和1組成的所有符號串。 a | a C 0,1+ ,且口中含有3個1 (5) a | a C 0,1 *, a中含0和1的數(shù)目為偶數(shù)。4.10已知文法 GS,其產(chǎn)生式如下：S-(L)|aLfL,S|S文法GS的算符優(yōu)先關(guān)系由下表給出。建立與下表相應(yīng)的算符優(yōu)先函數(shù)并用算符優(yōu)先分析法分析句子(a,(a,a)。文法GS的算符優(yōu)先關(guān)系表：3()4$a< )> >< < -< ) > >>1< »< « >>$< < 解：對每個終結(jié)符或$建立符號f與g,把f (和g)分成一組。根

10、據(jù)GS的算符優(yōu)先關(guān)系表，畫出如下的有向圖：a(1$f20220g33010用算符優(yōu)先分析法分析句子(a,(a,a)棧侑A動作$(a, (a, a)$初始a. (a, a)U睡$(a.a.a)$移進$(N羽為(a, a)$睡a,旬)$移進$(N. (a,日)$(N, (N,a)$歸約$(N. (N.日)$移進i(N. (Ni. a)$移進r$W (N.N)5歸約$(N. (N和M (N)$ 當(dāng)史豹 醴$<N, N)$歸豹悔曲約W)$移進$歸的，接受4.19 (1)存在有左遞歸規(guī)則的文法是LL(1)的。(2)任何算符優(yōu)先文法的句型中不會有兩個相鄰的非終結(jié)符號。(3)算符優(yōu)先文法中任何兩個相鄰

11、的終結(jié)符號之間至少滿足三種關(guān)系(V, - >,三)之)中。寬度優(yōu)先分析法預(yù)測遞歸分析法有向無環(huán)圖最右推導(dǎo)左遞歸直接右遞歸直接左遞歸(4)任彳sj LL(1)文法都是無二義性的。(5)每一個SLR(1)文法也都是LR(1)文法。(6)存在一種算法，能判定任何上下文無關(guān)文法是否是LL(1)的。(7)任何一個LL(1)文法都是一個LR(1)文法，反之亦然。(8)'LR(1)' 括號中的1是指，在選用產(chǎn)生式 2進行分析，看當(dāng)前讀入符號是否在FIRST(答案：(1) X (2) , (3) X (4) , (5) , (6) , (7) X (8) X4.20在編譯程序中，語法分析

12、分為自頂向下分析和自底向上分析兩類。_A_和LL(1)分析法屬于自頂向下分析； _B_和LR分析法屬于自底向上分析。 自頂向下分析試圖為輸入符號 串構(gòu)造一個_C_;自底向上分析試圖為輸入符號串構(gòu)造一個 _D_。采用自頂向下分析方法 時，要求文法中不含有 _E_OA B:深度分析法算符優(yōu)先分析法C D:語法樹最左推導(dǎo)E:右遞歸A: B: C: D: E:4.21自底向上語法分析采用 _A_分析法，常用的是自底向上語法分析有算符優(yōu)先分析法和 LR分析法。LR分析是尋找右句型的 _B_ ;而算符優(yōu)先分析是尋找右句型的_C_O LR分析法中分析能力最強的是 _D_;分析能力最弱的是_E_O遞歸回溯枚舉

13、移進規(guī)約B、C:短語素短語D E: SLR(1) LR(0)A:最左素短語句柄 LR(1) LALR(1)A: B: C: D: E :5.5用S的綜合屬性val給出在下面的文法中的S產(chǎn)生的二進制數(shù)的值(例如，對于輸入 101.101 , S.val=5.625 )：Sf L.L|LL-LB|BB- 0|1(1)試用各有關(guān)綜合屬性決定S.val。(2)試用一個語法制導(dǎo)定義來決定S.val,在這個定義中僅有 B的綜合屬性，設(shè)為 c,它給出由B生成的位對于最后的數(shù)值的貢獻。例如，在 101.101中的第一位和最后一位對于值 5.625的貢獻分別為 4和0.125。解答：(1)用綜合屬性決定 s.v

14、al的語法制導(dǎo)定義：產(chǎn)供語義規(guī)則S -> LS.val:=L.val;S -> L 1.L2S.val:=L 1.val+L 2.val*L 2.p;L -> BL.val:=B.val;L.p:=2 -1;,15B -> 1B.val:=1;L -> L iBL.val:=L i.val*2+B.val; L.p:=L.p*2B -> 0B.val:=0;注：L.p表示恢復(fù)L.val的因子。B2Bi Bl i«lBl c=lLl i=4 LiLl s=4Bl Bl iW | Bu c=1BZ c=01B 七 1=2B泉 c=0Li. i=lU-5

15、=lE, Ba. i=4 g cMLl. i=2 JLi. s=2 zBa Bs. i=2-1Bs. c=2-1(2)分析：設(shè)B.c是B的綜合屬性，是 B產(chǎn)生的位對最終值的貢獻。要求出 產(chǎn)生位的權(quán)，設(shè) B.i。B.i的求法請參看下面的圖示：B.c ,必須求出B另外，設(shè)L.fi為繼承因子,1產(chǎn)生式語義規(guī)則S -> LL.i:=1; L.fi:=2; L.fs:=1; S.val:=L.val;1S -> L 1.L2Li.i=1; L 1.fi=2; L 1.fs:=1;L2.i=2 -1; L 2.fi=1; L 2.fs:=2 -1 ;S.val:=L 1.val+L 2.val

16、;1L -> BL.s:=L.i; B.i:=L.s; L.val:=B.c;L.fs為綜合因子，語法制導(dǎo)定義如下:rL-> L iBL1.i:=L.i*L1.fi; L.s:=L 1.s*L 1.fs;B.i:=L.s;L.val:=L1.val+B.c;B -> 0B.c:=0;1B -> 1B.c:=B.i;5.15 描述文法符號語義的屬性有兩種，一種稱為(A ),另一種稱為(B ) 。( A )值的計算依賴于分析樹中它的(C )的屬性值；(B)的值的計算依賴于分析樹中它的 (D)的屬性值。A,B:L-屬性R-屬性綜合屬性繼承屬性C,D:父結(jié)點子結(jié)點兄弟結(jié)點父結(jié)點

17、與子結(jié)點父結(jié)點與兄弟結(jié)點解答:A B C D5.16 (1)語法制導(dǎo)定義中某文法符號的一個屬性，既可以是綜合屬性，又可以是繼承屬性。(2)只使用綜合屬性的語法制導(dǎo)定義稱為S-屬性定義。(3)把L-屬性定義變換成翻譯模式，在構(gòu)造翻譯程序的過程中前進了一大步。(4) 一個特定的翻譯模式既適于自頂向下分析，又適于自底向上分析。(5)用于自頂向下分析的翻譯模式，其基礎(chǔ)文法中不能含有左遞歸。(6)在基礎(chǔ)文法中增加標(biāo)記非終結(jié)符不會導(dǎo)致新的語法分析沖突。解答：(1) FALSE (2) TRUE (3) TRUE (4) FALSE TRUE (6) FALSE6.7 (1)對于允許遞歸調(diào)用的程序語言，程序

18、運行時的存儲分配策略不能采用靜態(tài)的存儲分配策略。()(2)若一個程序語言的任何變量的存儲空間大小和相互位置都能在編譯時確定，則可采用靜態(tài)分配策略。()(3)在不含嵌套過程的詞法作用域中，若一個過程中有對名字 a的非局部引用，則a必須在任何過程(或函數(shù))外被說明。 ()(4)在允許嵌套的詞法作用域的語言中，過程不能作為參數(shù)，原因時不能建立其運行環(huán)境的存取鏈。()(5)在堆式存儲分配中，一個堆中存活的活動記錄不一定是鄰接的。()(6)如果源程序正文中過程 p直接嵌入在過程 q中，那么，p的一個活動記錄中的存取鏈接 指向q的最近的活動記錄。()解答：(1)(TRUE) (2)(FALSE) (3)(

19、TRUE) (4)(FALSE) (5)(TRUE) (6)(TRUE)6.8 運行時的存儲分配策略分( A )和(B )兩類。(B )又分(C )和(D )。一個語言中不同種類的變量根據(jù)定義域和生存期的不同往往采用不同的存儲分配策略，C語言中的靜態(tài)變量往往采用(A )，而自動(out)類變量往往采用(C )。使用mallac中申請的內(nèi)存單元采用 (D )。A,B,C,D:棧式分配最佳分配堆式分配靜態(tài)分配隨機分配動態(tài)分配7.2 翻譯算術(shù)表達式一(a+ b) * (c+d) + ( a+b+c)為(1)四元式，(2)三元式(3)間接三元式解答：(1)四元式序列為：oparg1arg2result

20、(1)+abt1(2)+cdt2(3)*t1t2t3(4)uminust3t4(5)+abt5(6)+t5ct6(7)+t4t6t7(2)三元式序列為:oparg1arg2(1)+ab(2)+cd(3)*(1)(2)(4)uminus(3)(5)+ab(6)+(5)c(7)+(4)(6)(3)間接三兀式表布:statementoparg1arg2(1)(11)(11)+ab(2)(12)(12)+cd 1(13)f(13)*(11):(12)(14)(14)uminus(13)(5)(11)(15)+(11)c(6)(15)(16)+(14)1(15)(16)9.1 試構(gòu)造下面的程序的流圖，并找出其中所有回邊及循環(huán)。 read Px := 1 c := P * P if c < 100 goto L1 B := P * P x := x + 1 B := B + x write x haltL1: B:= 10 x := x + 2 B