《編譯原理和技術(shù)》部分課后試題解答

慮文法 GS,其產(chǎn)生式如下 : S(L)|a LL ， S|S (1) 試指出此文法的終結(jié)符號、非終結(jié)符號。 終結(jié)符號為： (,),a, 非終結(jié)符號為： S,L 開始符號為： S (2)給出下列各句子的分析樹： (a,a) (a,(a,a) (a,(a,a),(a,a) (3)構(gòu)造下列各句子的一個最左推導(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) (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)造下列各句子的一個最右推導(dǎo)： (a,a) S (L) (L,S) (L,a) (S,a) (a,a) (a,(a ， a) S (L) (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) (5)這個文法生成的語言是什么？ L(GS) = ( 1, 2,., n)或 a 其中 i(1in) ，即 L(GS)是一個以 a 為原子的純表，但不包括空表。 慮文法 GS S (1)試說明此文法是二義性的?？梢詮膶τ诰渥?S 以此文法是二義性的。 (2)對于句子 S 3)對于句子 (一 ) (二 ) (4)此文法所產(chǎn)生的語言是什么？ 此文法產(chǎn)生的語言是：所有 b 的個數(shù)相等的由 a 和 知文法 GS的產(chǎn)生式如下： S (L)|a L 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) (L,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： 有限狀態(tài)自動機可用五元組（ Q， ， 描述 ,設(shè)有一有限狀態(tài)自動機 M 的定義如下： 0,1， Q=q0,q1, 的定義為： （ 0） = （ ） = （ 1） = （ ） = 是一個 A 有限狀態(tài)自動機，它所對應(yīng)的狀態(tài)轉(zhuǎn)換圖為 B ,它所能接受的語言可以用正則表達式表示為 C 。其含義為 D 。 A: 歧義的 非歧義的 確定的 非確定的 B: C： (0|1) * 00(0|1) * (0|1) *00 0(0|1) *0 D： 由 0 和 1 所組成的符號串的集合； 以 0 為頭符號和尾符號、由 0 和 1 所組成的符號串的集合； 以兩個 0結(jié)束的，由 0 和 1所組成的符號串的集合； 以兩個 0開始的，由 0 和 1所組成的符號串的集合。 答案 A: B: C: D: (1)有窮自動機接受的語言是正則語言。（） (2)若 上的正規(guī)式，則 r1|） (3)設(shè) M 是一個 且 L(M) x,y,z，則 M 的狀態(tài)數(shù)至少為 4個。 (4)令 a,b，則 上所有以 b 為首的字構(gòu)成的正規(guī)集的正規(guī)式為 b*(a|b)*。 (5)對任何一個 ，都存在一個 ，使得 L(M)=L(M)。（） (6)對一個右線性文法 G，必存在一個左線性文法 G，使得L(G)=L(G)，反之亦然。（） 答案 (1) T (2) T (3) F (4) F (5)T 述下列各正規(guī)表達式所表示的語言。 (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 組成的所有符號串(2) | 0,1*即由 0 和 1 組成的所有符號串。 (3) 由 0 和 1 組成的符號串，且從右邊開始數(shù)第 3 位為 0。 (4) 含 3 個 1 的由 0 和 1 組成的所有符號串。 | 0,1+，且 中含有 3 個 1 (5) | 0,1*, 中含 0 和 1 的數(shù)目為偶數(shù)。 知文法 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)系表： 解： 對每個終結(jié)符或建立符號 f 與 g，把 f(和 g)分成一組。 根據(jù) GS的算符優(yōu)先關(guān)系表，畫出如下的有向圖 : 優(yōu)先函數(shù)如下： 用算符優(yōu)先分析法分析句子 (a,(a,a) 1) 存在有左遞歸規(guī)則的文法是 )的。 (2) 任何算符優(yōu)先文法的句型中不會有兩個相鄰的非終結(jié)符號。 (3) 算符優(yōu)先文法中任何兩個相鄰的終結(jié)符號之間至少滿足三種 關(guān)系( ， ， )之一。 (4) 任何 )文法都是無二義性的。 (5) 每一個 )文法也都是 )文法。 (6) 存在一種算法 ，能判定任何上下文無關(guān)文法是否是 )的。 (7) 任何一個 )文法都是一個 )文法，反之亦然。 (8) )括號中的 1 是指，在選用產(chǎn)生式 A 進行分析，看當(dāng)前讀入符號是否在 ) 中。 答案： (1) (2) (3) (4) (5) (6) (7) (8) 編譯程序中，語法分析分為自頂向下分析和自底向上分析兩類。 _L(1)分析法屬于自頂向下分析； _R 分析法屬 于自底向上分析。自頂向下分 析試圖為輸入符號串構(gòu)造一個 _底向上分析試圖為輸入符號串構(gòu)造一個 _用自頂向下分析方法時，要求文法中不含有 _ A、 B： 深度分析法 寬度優(yōu)先分析法 算符優(yōu)先分析法 預(yù)測遞歸分析法 C、 D： 語法樹 有向無環(huán)圖 最左推導(dǎo) 最右推導(dǎo) E： 右遞歸 左遞歸 直接右遞歸 直接左遞歸 A： B： C： D： E： 底向上語法分析采用 _用的是自 底向上語法分析有算符優(yōu)先分析法和 析法。 _算符優(yōu)先分析是尋找右句型的 _析法中分析能力最強的是 _析能力最弱的是 _ A： 遞歸 回溯 枚舉 移進規(guī)約 B、 C： 短語 素短語 最左素短語 句柄 D、 E： ) ) ) ) A： B： C： D： E： 產(chǎn)生的二進制數(shù)的值（例如，對于輸入 S L B0|1 （ 1）試用各有關(guān)綜合屬性決定 （ 2）試用一個語法制導(dǎo)定義來決定 這個定義中僅有 B 的綜合屬性，設(shè)為 c，它給出由 B 生成的位對于最后的數(shù)值的貢獻。例如，在 的第一位和最后一位對于值 貢獻分別為 解答： (1)用綜合屬性決定 語法制導(dǎo)定 義： 產(chǎn)生式 語義規(guī)則 S - L S - L - B 2 L - + B - 0 0; B - 1 1; 注： (2)分析：設(shè) B 的綜合屬性，是 求出 須求出 B 產(chǎn)生位的權(quán)，設(shè) 另外，設(shè) 繼承因子， 綜合因子，語法制導(dǎo)定義如下： 產(chǎn)生式 語義規(guī)則 S - L 1; 2; 1; S - ; ; 1; ; 2 L - B L - B - 0 0; B - 1 種稱為 ( A ),另一種稱為( B )。 ( A )值的計算依賴于分析樹中它的 ( C )的屬性值； ( B )的值的計算依賴于 分析樹中它的 ( D )的屬性值。 A,B: 綜合屬性 繼承屬性 C,D: 父結(jié)點 子結(jié)點 兄弟結(jié)點 父結(jié)點與子結(jié)點 父結(jié)點與兄弟結(jié)點 解答 : A B C D ) 語法制導(dǎo)定義中某文法符號的一個屬性，既可以是綜合屬性，又可以是繼承屬性。 (2) 只使用綜合屬性的語法制導(dǎo)定義稱為 (3) 把 構(gòu)造翻譯程序的過程中前進了一大步。 (4)一個特定的翻譯模式既適于自頂向下分析 ，又適于自底向上分析。 (5) 用于自頂向下分析的翻譯模式，其基礎(chǔ)文法中不能含有左遞歸。 (6) 在基礎(chǔ)文法中增加標(biāo)記非終結(jié)符不會導(dǎo)致新的語法分析沖突。 解答 :(1) (2) (3) (4) (5) (6) (1) 對于允許遞歸調(diào)用的程序語言，程序運行時的存儲分配策略不能采用靜態(tài)的存儲分配策略。（ ） (2) 若一個程序語言的任何變量的存儲空間大小和相互位置都能在編譯時確定，則可采用靜態(tài)分配策略。（ ） (3) 在不含嵌套過程的詞法作用域中，若一個過程中有對名字 函數(shù)）外被說明。（ ） (4) 在允許嵌套的詞法作用域的語言中，過程不能作為參數(shù)，原因時不能建立其運行環(huán)境的存取鏈。（ ） (5) 在堆式存儲分配中，一個堆中存活的活動記錄不一定是鄰接的。（ ） (6) 如果源程序正文中過程 p 直接嵌入在過程 q 中，那么， p 的一個活動記錄中的存取鏈接指向 q 的最近的活動記錄。（ ） 解答： (1)(2)(3)(4)( (5)( (6)( 行時的存儲分配策略分 ( A )和 ( B )兩類。 ( B )又分 ( C )和 ( D )。一個語言中不同種類的變量根據(jù)定義域和生存期的不同往往采用不同的存儲分配策略， C 語言中的靜態(tài)變量往往采用 ( A )，而自動 (變量往往采用 ( C )。使用申請的內(nèi)存單元采用 ( D )。 A,B,C,D: 棧式分配 最佳分配 堆式分配 靜態(tài)分配 隨機分配 動態(tài)分配 解答： A: B: C: D: 譯算術(shù)表達式一（ a b） *（ c d）（ a b c）為 (1)四元式， (2)三元式 (3)間接三元式 解答： (1)四元式序列為： (1) + a b 2) + c d 3) * t1 t2 4) 5) + a b 6) + t5 c 7) + t4 t6 2)三元式序列為： (1) + a b (2) + c d (3) * (1) (2) (4) 3) (5) + a b (6) + (5) c (7) + (4) (6) (3)間接三元式表示： (1) (11) (11) + a b (2) (12) (12) + c d (3) (13) (13) * (11) (12) (4) (14) (14) 13) (5) (11) (15) + (11) c (6) (15) (16) + (14)