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

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

2、a,(S,S) (a,(a,S) (a,(a,a) (a,(a,a),(a,a)S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S) (a,(S,S) (a,(L),S) (a,(L,S),S) (a,(S,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)造下列各句子的一個(gè)最右推導(dǎo)：(a,a)S (L) (L,S) (L,a) (S,a) (a,a)(a,(a，a)S (L)

3、(L,S) (L,(L) (L,(L,S) (L,(L,a)    (L,(S,a) (L,(a,a) (S,(a,a) (a,(a,a)(a，(a，a)，(a，a)  S (L) (L,S) (L,(L) (L,(L,S) (L,(L,(L)(L,(L,(L,S) (L,(L,(L,a) (L,(L,(S,a)(L,(L,(a,a) (L,(S,(a,a) (L,(L),(a,a)(L,(L,S),(a,a) (L,(L,a),(a,a) (L,(S,a),(a,a)(L,(a,a),(a,a) (S,(a,a),(a,a) (a,(a,a),(a,a

4、)(5)這個(gè)文法生成的語言是什么？L(GS) = (1,2,.,n)或a其中i(1in)，即L(GS)是一個(gè)以a為原子的純表，但不包括空表。2.2 考慮文法GS SaSbS|bSaS|(1)試說明此文法是二義性的?？梢詮膶?duì)于句子abab有兩個(gè)不同的最左推導(dǎo)來說明。 S aSbS abS abaSbS ababS abab    S aSbS abSaSbS abaSbS ababS abab    所以此文法是二義性的。(2)對(duì)于句子abab構(gòu)造兩個(gè)不同的最右推導(dǎo)。 S aSbS aSbaSbS aSbaSb aSbab abab   

5、; S aSbS aSb abSaSb abSab abab(3)對(duì)于句子abab構(gòu)造兩棵不同的分析樹。 (一)   (二)    (4)此文法所產(chǎn)生的語言是什么？此文法產(chǎn)生的語言是：所有a的個(gè)數(shù)與b的個(gè)數(shù)相等的由a和b組成的字符串。2.4 已知文法GS的產(chǎn)生式如下：S (L)|a L L,S|S屬于L(GS)的句子是 A ，(a,a)是L(GS)的句子，這個(gè)句子的最左推導(dǎo)是 B ，最右推導(dǎo)是 C ，分析樹是 D ，句柄是 E 。A： a   a,a   (L)   (L,a)B,C： S (L) (L,

6、S) (L,a) (S,a) (a,a)      S (L) (L,S) (S,S) (S,a) (a,a)      S (L) (L,S) (S,S) (a,S) (a,a)D：  E： (a,a)   a,a   (a)   a解答： A： B： C： D： E：3.1  有限狀態(tài)自動(dòng)機(jī)可用五元組（VT，Q，q0，Qf）來描述,設(shè)有一有限狀態(tài)自動(dòng)機(jī)M的定義如下：         VT=0,

7、1，Q=q0,q1,q2，Qf=q2，的定義為：（q0，0）=q1     （q1，0）=q2（q2，1）=q2     （q2，0）=q2    M是一個(gè) A 有限狀態(tài)自動(dòng)機(jī)，它所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖為 B ,它所能接受的語言可以用正則表達(dá)式表示為 C 。其含義為 D 。 A:  歧義的   非歧義的   確定的   非確定的B:C： (0|1)*   00(0|1)* 

8、;  (0|1)*00   0(0|1)*0D：由0和1所組成的符號(hào)串的集合；   以0為頭符號(hào)和尾符號(hào)、由0和1所組成的符號(hào)串的集合；   以兩個(gè)0結(jié)束的，由0和1所組成的符號(hào)串的集合；   以兩個(gè)0開始的，由0和1所組成的符號(hào)串的集合。答案 A:   B:   C:   D:  3.2  (1)有窮自動(dòng)機(jī)接受的語言是正則語言。（）(2)若r1和r2是上的正規(guī)式，則r1|r2也是。（）

9、(3)設(shè)M是一個(gè)NFA，并且L(M)x,y,z，則M的狀態(tài)數(shù)至少為4個(gè)。(4)令a,b，則上所有以b為首的字構(gòu)成的正規(guī)集的正規(guī)式為b*(a|b)*。(5)對(duì)任何一個(gè)NFA M，都存在一個(gè)DFA M'，使得L(M')=L(M)。（）(6)對(duì)一個(gè)右線性文法G，必存在一個(gè)左線性文法G'，使得L(G)=L(G')，反之亦然。（） 答案 (1)  T    (2)  T   (3)  F    (4)  F   

10、(5)  T 3.3 描述下列各正規(guī)表達(dá)式所表示的語言。(1) 0(0|1)*0(2) (|0)1*)*(3) (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組成的所有符號(hào)串(2) |0,1*即由0和1組成的所有符號(hào)串。(3) 由0和1組成的符號(hào)串，且從右邊開始數(shù)第3位為0。(4) 含3個(gè)1的由0和1組成的所有符號(hào)串。

11、0; |0,1+，且中含有3個(gè)1 (5) |0,1*,中含0和1的數(shù)目為偶數(shù)。 4.10 已知文法GS，其產(chǎn)生式如下：S(L)|a      LL,S|S 文法GS的算符優(yōu)先關(guān)系由下表給出。建立與下表相應(yīng)的算符優(yōu)先函數(shù)并用算符優(yōu)先分析法分析句子(a,(a,a)。文法GS的算符優(yōu)先關(guān)系表： 解：對(duì)每個(gè)終結(jié)符或建立符號(hào)f與g，把f(和g)分成一組。根據(jù)GS的算符優(yōu)先關(guān)系表，畫出如下的有向圖:優(yōu)先函數(shù)如下： 用算符優(yōu)先分析法分析句子(a,(a,a) 4.19 (1) 存在有左遞歸規(guī)則的文法是LL(1)的。    

12、0;      (2) 任何算符優(yōu)先文法的句型中不會(huì)有兩個(gè)相鄰的非終結(jié)符號(hào)。 (3) 算符優(yōu)先文法中任何兩個(gè)相鄰的終結(jié)符號(hào)之間至少滿足三種 關(guān)系(·，·，)之一。     (4) 任何LL(1)文法都是無二義性的。        (5) 每一個(gè)SLR(1)文法也都是LR(1)文法。        (6) 存在一種算法，能判定任何上下文無關(guān)文法是否是LL(1)的。   (7) 任

13、何一個(gè)LL(1)文法都是一個(gè)LR(1)文法，反之亦然。       (8)' LR(1)'括號(hào)中的1是指，在選用產(chǎn)生式A進(jìn)行分析，看當(dāng)前讀入符號(hào)是否在FIRST()中。答案：(1)× (2) (3)× (4) (5) (6) (7)× (8)× 4.20 在編譯程序中，語法分析分為自頂向下分析和自底向上分析兩類。_A_和LL(1)分析法屬于自頂向下分析；_B_和LR分析法屬于自底向上分析。自頂向下分析試圖為輸入符號(hào)串構(gòu)造一個(gè)_C_；自底向上分析試圖為輸入符號(hào)串構(gòu)造一個(gè)_D_。采用自頂向下分析方法時(shí)，

14、要求文法中不含有_E_。A、B：深度分析法寬度優(yōu)先分析法算符優(yōu)先分析法預(yù)測遞歸分析法C、D：語法樹有向無環(huán)圖最左推導(dǎo)最右推導(dǎo)E：右遞歸左遞歸直接右遞歸直接左遞歸A： B： C： D： E： 4.21 自底向上語法分析采用_A_分析法，常用的是自底向上語法分析有算符優(yōu)先分析法和LR分析法。LR分析是尋找右句型的 _B_；而算符優(yōu)先分析是尋找右句型的_C_。LR分析法中分析能力最強(qiáng)的是_D_；分析能力最弱的是_E_。A：遞歸回溯枚舉移進(jìn)規(guī)約B、C：短語素短語最左素短語句柄D、E：SLR(1)LR(0)LR(1)LALR(1)A： B： C： D： E：5.5 用S的綜合屬性val給出在下面的文法中

15、的S產(chǎn)生的二進(jìn)制數(shù)的值（例如，對(duì)于輸入 101.101，S.val=5.625）：        SL.L|L  LLB|B B0|1 （1）試用各有關(guān)綜合屬性決定S.val。 （2）試用一個(gè)語法制導(dǎo)定義來決定S.val,在這個(gè)定義中僅有B的綜合屬性，設(shè)為c，它給出由B 生成的位對(duì)于最后的數(shù)值的貢獻(xiàn)。例如，在101.101中的第一位和最后一位對(duì)于值5.625的貢獻(xiàn)分別為4和0.125。解答：(1)用綜合屬性決定s.val的語法制導(dǎo)定義：產(chǎn)生式語義規(guī)則    S -&

16、gt; L S.val:=L.val;     S -> L1.L2 S.val:=L1.val+L2.val*L2.p;     L -> B L.val:=B.val;    L.p:=2-1;     L -> L1B L.val:=L1.val*2+B.val; L.p:=L.p*2-1;    B -> 0 B.val:=0;     B -> 1

17、 B.val:=1; 注：L.p表示恢復(fù)L.val的因子。(2)分析：設(shè)B.c是B的綜合屬性，是B產(chǎn)生的位對(duì)最終值的貢獻(xiàn)。要求出B.c，必須求出B產(chǎn)生位的權(quán)，設(shè)B.i。B.i的求法請參看下面的圖示：另外，設(shè)L.fi為繼承因子，L.fs為綜合因子，語法制導(dǎo)定義如下：產(chǎn)生式語義規(guī)則     S -> L L.i:=1; L.fi:=2; L.fs:=1; S.val:=L.val;     S -> L1.L2 L1.i=1; L1.fi=2; L1.fs:=1; L2.i=2-1; L2.fi=

18、1; L2.fs:=2-1;S.val:=L1.val+L2.val;     L -> B L.s:=L.i; B.i:=L.s; L.val:=B.c;     L -> L1B L1.i:=L.i*L1.fi; L.s:=L1.s*L1.fs;B.i:=L.s;L.val:=L1.val+B.c;     B -> 0 B.c:=0;    B -> 1 B.c:=B.i; 5.15描述文法符號(hào)語義的屬性有兩種，一種稱為( A

19、 ),另一種稱為( B )。( A )值的計(jì)算依賴于分析樹中它的( C )的屬性值；( B )的值的計(jì)算依賴于分析樹中它的( D )的屬性值。 A,B: L-屬性 R-屬性 綜合屬性 繼承屬性 C,D: 父結(jié)點(diǎn) 子結(jié)點(diǎn) 兄弟結(jié)點(diǎn) 父結(jié)點(diǎn)與子結(jié)點(diǎn) 父結(jié)點(diǎn)與兄弟結(jié)點(diǎn) 解答: A    B    C   D 5.16(1) 語法制導(dǎo)定義中某文法符號(hào)的一個(gè)屬性，既可以是綜合屬性，又可以是繼承屬性。(2) 只使用綜合屬性的語法制導(dǎo)定義稱為S-屬性定義。(3) 把L-屬性定義變換成翻譯模式，在構(gòu)造翻譯程序的過程中前進(jìn)了一大步。

20、(4)一個(gè)特定的翻譯模式既適于自頂向下分析，又適于自底向上分析。(5) 用于自頂向下分析的翻譯模式，其基礎(chǔ)文法中不能含有左遞歸。(6) 在基礎(chǔ)文法中增加標(biāo)記非終結(jié)符不會(huì)導(dǎo)致新的語法分析沖突。解答:(1) FALSE   (2) TRUE   (3) TRUE   (4) FALSE   (5) TRUE   (6) FALSE6.7  (1) 對(duì)于允許遞歸調(diào)用的程序語言，程序運(yùn)行時(shí)的存儲(chǔ)分配策略不能采用靜態(tài)的存儲(chǔ)分配策略。（ ） (2) 若一個(gè)程序語言的任何變量的存儲(chǔ)空間大小

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

22、TRUE)   6.8 運(yùn)行時(shí)的存儲(chǔ)分配策略分(  A  )和(  B  )兩類。(  B  )又分(  C  )和(  D  )。一個(gè)語言中不同種類的變量根據(jù)定義域和生存期的不同往往采用不同的存儲(chǔ)分配策略，C語言中的靜態(tài)變量往往采用(  A  )，而自動(dòng)(out)類變量往往采用(  C  )。使用mallac中申請的內(nèi)存單元采用(  D  )。A,B,C,D: 棧式分配    最佳分配

23、    堆式分配 靜態(tài)分配   隨機(jī)分配     動(dòng)態(tài)分配 解答： A:      B:      C:      D:  7.2 翻譯算術(shù)表達(dá)式一（ab）*（cd）（abc）為  (1)四元式，  (2)三元式   (3)間接三元式解答：(1)四元式序列為：  op arg1 arg2 result (1)+abt1

24、(2)+cd  t2(3)*t1t2t3(4)uminust3t4(5)+abt5(6)+t5ct6(7)+t4t6t7(2)三元式序列為：  op arg1 arg2 (1)+ab(2)+cd(3)*(1)(2)(4)uminus(3)(5)+ab(6)+(5)c(7)+(4)(6)(3)間接三元式表示：  statement     op arg1 arg2 (1)(11)(11)+ab(2)(12)(12)+cd(3)(13)(13)*(11)(12)(4)(14)(14)uminus(13)(5)(11)(15)+(11)c(6)(15

25、)(16)+(14)(15)(7)(16)        9.1 試構(gòu)造下面的程序的流圖，并找出其中所有回邊及循環(huán)。          read P          x := 1          c := P * P      

26、;    if c < 100 goto L1          B := P * P          x := x + 1          B := B + x          write x&#

27、160;         halt      L1: B:= 10          x := x + 2          B := B + x          write B          if B < 100 goto L2          halt      L2: x := x + 1          goto L1解：程序的流圖如下9.2 對(duì)本題中所示的流圖，