編譯原理與技術(shù)練習(xí)題匯總

1、練習(xí) 1 1.1為什么高級(jí)程序語(yǔ)言需要編譯程序？1.2 解釋下列術(shù)語(yǔ)：源程序，目標(biāo)程序，翻譯程序，編譯程序，解釋程序1.3 簡(jiǎn)單敘述編譯程序的主要工作過程。1.4 編譯程序的典型體系結(jié)構(gòu)包括哪些構(gòu)件，主要關(guān)系如何，請(qǐng)用輔助圖示意。1.5 編譯程序的開發(fā)有哪些途徑？了解你熟悉的高級(jí)編程語(yǔ)言編譯程序的開發(fā)方式。1.6 運(yùn)用編譯技術(shù)的軟件開發(fā)和維護(hù)工具有許多類，簡(jiǎn)單敘述每一類的主要用途。1.7了解一個(gè)真實(shí)編譯系統(tǒng)的組成和基本功能。1.8 簡(jiǎn)單說明學(xué)習(xí)編譯程序的意義和作用。1.9 如果機(jī)器H上有兩個(gè)編譯：一個(gè)把語(yǔ)言A翻譯成語(yǔ)言B，另一個(gè)把B翻譯成C，那么可以把第一個(gè)編譯的輸出作為第二個(gè)編譯的輸入，結(jié)果

2、在同一類機(jī)器上得到從A到C的編譯。請(qǐng)用T形圖示意過程和結(jié)果。練習(xí) 22.1 詞法分析器的主要任務(wù)是什么？2.2 下列各種語(yǔ)言的輸入字母表是什么？(1) C(2) Pascal(3) Java(4) C#2.3 可以把詞法分析器寫成一個(gè)獨(dú)立運(yùn)行的程序，也可以把它寫成一個(gè)子程序，請(qǐng)比較各自的優(yōu)劣。2.4 用高級(jí)語(yǔ)言編寫一個(gè)對(duì)C#或Java程序的預(yù)處理程序，它的作用是每次調(diào)用時(shí)都把下一個(gè)完整的句子送到掃描緩沖區(qū)，去掉注釋和無用的空格、制表符、回車、換行。2.5 用高級(jí)語(yǔ)言實(shí)現(xiàn)圖2.5所示的Pascal語(yǔ)言數(shù)的狀態(tài)轉(zhuǎn)換圖。2.6 用高級(jí)語(yǔ)言編程實(shí)現(xiàn)圖2.6所示的小語(yǔ)言的詞法掃描器。2.7 用自然語(yǔ)言描

3、述下列正規(guī)式所表示的語(yǔ)言： (1) 0(0|1)*0(2) (e|0)1)*)*(3) (a|b)*a(a|b|e) (4) (A|B|.|Z)(a|b|.|z)* (5) (aa|b)*(a|bb)* (6) (0|1|.|9|A|B|C|D|E)+(t|T)2.8 為下列語(yǔ)言寫正規(guī)式(1) 所有以小寫字母a開頭和結(jié)尾的串。 (2) 所有以小寫字母a開頭或者結(jié)尾（或同時(shí)滿足這兩個(gè)條件）的串。(3) 所有表示偶數(shù)的串。(4) 所有不以0開始的數(shù)字串。(5) 能被5整除的10進(jìn)制數(shù)的集合。(6) 沒有出現(xiàn)重復(fù)數(shù)字的全體數(shù)字串。2.9 試構(gòu)造下列正規(guī)式的NFA，并且確定化，然后最小化。(1) (a

4、|b)*a(a|b)(2) (a|b)*a(a|b) *(3) ab(ba|ab)*(bb|aa)*ab(4) 00|(0|1)*|11(5) 1(0|1)*01(6) 1(1010*|1(010)*1*02.10 請(qǐng)分別使用下面的技術(shù)證明(a|b)*，(a*|b*)*以及(a|e)b*)*這三個(gè)正規(guī)式是等價(jià)的： (1) 僅用正規(guī)式的定義及其代數(shù)性質(zhì)；(2) 從正規(guī)式構(gòu)造的最小DFA的同構(gòu)來證明正規(guī)式的等價(jià)。2.11 構(gòu)造有限自動(dòng)機(jī)M，使得(1) L(M) = anbn | n ³ 1；(2) L(M) = anbncn | n ³ 1；(3) 它能識(shí)別S0, 1上0和1的

5、個(gè)數(shù)都是偶數(shù)的串；(4) 它能識(shí)別字母表0, 1上的串，但是串不含兩個(gè)連續(xù)的0和兩個(gè)連續(xù)的1；(5) 它能接受形如±dd*，±d*E和±dd的實(shí)數(shù)，其中d=0，1，2，3，4，5，6，7，8，9。(6) 它能識(shí)別a, b上不含子串a(chǎn)ba的所有串。2.12 分別將下列NFA確定化，并畫出最小化的DFA：(a)a10a,bb(b)a40a,ba123abbba(c)eabFAa,bBCDebbaSEee2.13 下面是URL的一個(gè)極其簡(jiǎn)化的擴(kuò)展正規(guī)式的描述： letter A-Za-zdigit 0-9letgit letter| digit letgit_hyphe

6、n letgit | _letgit_hyphen_string letgit_hyphen | letgit_hyphen letgit_hyphen_stringlabel letter (letgit_hyphen_string? letgit)？ URL (label.)*label (1) 請(qǐng)將這個(gè)URL的擴(kuò)展正規(guī)改寫成只含字母表A, B, 0, 1, _, .上符號(hào)的正規(guī)式； (2) 構(gòu)造出識(shí)別（1）更簡(jiǎn)化的URL串的有限自動(dòng)機(jī)。2.14 用某種高級(jí)語(yǔ)言實(shí)現(xiàn)(1) 將正規(guī)式轉(zhuǎn)換成NFA的算法；(2) 將NFA確定化的算法；(3) 將DFA最小化的算法。2.15 描述下列語(yǔ)言詞法記號(hào)

7、的正規(guī)表達(dá)式：(1) 描述C浮點(diǎn)數(shù)的正規(guī)表達(dá)式。(2) 描述Java表達(dá)式的正規(guī)表達(dá)式。2.16 Pascal語(yǔ)言的注釋允許兩種不同的形式：花括弧對(duì).，以及括弧星號(hào)對(duì)(*.*)。(1) 構(gòu)造一個(gè)識(shí)別這兩種注釋形式的DFA；(2) 用Lex的符號(hào)構(gòu)造它的一個(gè)正規(guī)式。2.17 寫一個(gè)Lex輸入源程序，它將產(chǎn)生一個(gè)把C語(yǔ)言程序中（注釋除外）的保留字全部大寫。練習(xí) 33.1對(duì)于文法G3.26EE T | E+T | E-TT F | T*F | T/FF (E) | i 證明(i+T)*i是它的一個(gè)句型。3.2 給定文法G3.27SS aAcB | BdS B aScA | cAB | b A BaB

8、 | aBc | a 試檢驗(yàn)下列符號(hào)串中哪些是G3.27 S中的句子。(1) aacb (2) aabacbadcd (3) aacbccb (4) aacabcbcccaacdca (5) aacabcbcccaacbca3.3 考慮文法G3.28S S (L) | aL L, S | S(1) 指出該文法的終結(jié)符號(hào)及非終結(jié)符號(hào)。(2) 給出下列各句子的語(yǔ)法分析樹：    (a,a) (a,(a, a) (a, (a, a), (a, a) (3) 分別構(gòu)造(b)中各句子的一個(gè)最左推導(dǎo)和最右推導(dǎo)。3.4 考慮文法G3.29S S aSbS | bSaS |(1) 討論句子

9、abab的最左推導(dǎo)，說明該文法是二義性的。(2) 對(duì)于句子abab構(gòu)造兩個(gè)相應(yīng)的最右推導(dǎo)。 (3) 對(duì)于句子abab構(gòu)造兩棵相應(yīng)的分析樹。 (4) 此文法所產(chǎn)生的語(yǔ)言是什么？3.5 文法G3.30S為： S Ac | aB A ab B bc 寫出L(G3.30)的全部元素。 3.6 試描述由下列文法GS所產(chǎn)生的語(yǔ)言。 (1) S 10S0 | aA AbA | a (2) S SS | 1A0 A1A0 | (3) S 1A | B0 A1A | C BB0 | C C1C0 | (4) S bAdc AAS | a (5) S aSS Sa(6) A 0B | 1CB 1 | 1A | 0

10、BBC 0 | 0A | 1CC3.7 設(shè)已給文法G3.31=(VN,VT,P,S)，其中： VN = S VT = a1,a2,an, , , P = Sai| i=1,2,nS S, S SS, S SS，試指出此文法所產(chǎn)生的語(yǔ)言。3.8 已知文法G3.32=(A,B,C,a,b,c,A,P)，其中P由以下產(chǎn)生式組成：A ®abc A ®aBbcBb ®bB Bc ®CbccbC ®Cb aC ®aaBaC ®aa 問：此文法表式的語(yǔ)言是什么？3.9 已知文法 G3.33 P:P aPQR |abR RQ QR bQ b

11、b bR bc cR cc 證明 aaabbbccc 是該文法的一個(gè)句子。3.10 構(gòu)造一個(gè)文法，使其產(chǎn)生的語(yǔ)言是由算符+, *, (, ) 和運(yùn)算對(duì)象a構(gòu)成的算術(shù)表達(dá)式的集合。3.12 已知語(yǔ)言L=anbbn| n1, 寫出產(chǎn)生語(yǔ)言L的文法。3.13 寫一文法，使其語(yǔ)言是偶正整數(shù)的集合。 要求：(1) 允許0打頭。 (2) 不允許0打頭。3.14 文法G3.34 S為： S Ac|aB, A ab B bc 該文法是否為二義的？為什么？（提示：找一個(gè)句子，使之有兩棵不同的分析樹。） 3.15 證明下述文法G3.35表達(dá)式是二義的： 表達(dá)式 a | (表達(dá)式) |表達(dá)式運(yùn)算符表達(dá)式 運(yùn)算符 +

12、 | - | * | / 3.16 下面的文法產(chǎn)生a的個(gè)數(shù)和b的個(gè)數(shù)相等的非空a、b串 S aB | bAB bS | aBB | b A aS | bAA | a 其中非終結(jié)符B推出b比a的個(gè)數(shù)多1個(gè)的串，A則反之。(1) 證明該文法是二義的。 (2) 修改上述文法，不增加非終結(jié)符，使之成為非二義文法，并產(chǎn)生同樣的語(yǔ)言。 3.17 考慮文法G3.36R RR '|' R | RR | R* | (R) | a | b 其中R '|' R表示R或R；RR表示R與R的連接；R*表示R的閉包。(1) 證明此文法生成å=a, b上的除了Æ和的所有正

13、規(guī)表達(dá)式。 (2) 試說明此文法是二義性的。(3) 構(gòu)造一個(gè)等價(jià)的無二義性文法，該文法給出*、連接和|等運(yùn)算符號(hào)的優(yōu)先級(jí)和結(jié)合規(guī)則。3.18 給出產(chǎn)生下述語(yǔ)言的上下文無關(guān)文法：(1) an bn am bm | n, m0。(2) 1n 0m1m 0n | n, m0。(3) wcwT | wa, b*，其中wT是w的逆。(4) w | wa,b+，且w中a的個(gè)數(shù)恰好比b多1 。(4) w | wa,b+，且|a|b|2|a| 。(5) w | w是不以0開始的奇數(shù)集 。3.19 設(shè)G=(VN,VT,P,S)為CFG，1,2,n為V上的符號(hào)串，試證明： 若 12n 則存在V上的符號(hào)串1,2，,

14、n，使=12n，且有 aii (i=1,2,n)。3.20 設(shè)G=(VN,VT,P,S)為CFG，和都是V上的符號(hào)串，且 ，試證明：(1) 當(dāng)?shù)氖追?hào)為終結(jié)符號(hào)時(shí)，的首符號(hào)也必為終結(jié)符號(hào)；(2) 當(dāng)?shù)氖追?hào)為非終結(jié)符號(hào)時(shí)，則的首符號(hào)也必為非終結(jié)符號(hào)。3.21 寫出下列語(yǔ)言的3型文法：(a) an | n0(b) anbm | n, m1 (c) anbmck | n, m, k1 3.22 已知文法G3.37 S：S dABA aA|aB |Bb 給出相應(yīng)的正規(guī)式和等價(jià)的正規(guī)文法。3.23給出下列文法GA消除左遞歸后的等價(jià)文法：(1) A BaC | CbBB Ac | cC Bb | b (

15、2) A B a | A a | cB B b | A b | d(3) S SA | A A SB | B | (S) | ( ) B S | (4) S AS | b A SA | a (5) S (T) | a | T S | T, S 練習(xí) 44.1證明：含有左遞歸的文法不是LL(1)文法。4.2 對(duì)于文法G4.11SS uBDz B Bv | w D EF E y | eF x | e(1) 計(jì)算文法G4.11各非終結(jié)符的FIRST集和FOLLOW集，以及各產(chǎn)生式的SELLECT集。(2) 判斷該文法是否是LL(1)文法。(3) 若不是LL(1)文法，則修改此文法 , 使其成為能產(chǎn)生

16、相同語(yǔ)言的 LL(1) 文法。4.3 已知布爾表達(dá)式文法G4.12bexpr bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | (bexpr) | true | false 改寫文法G4.12為擴(kuò)充的巴克斯范式，并為每個(gè)非終結(jié)符構(gòu)造遞歸下降分析子程序。4.4已知用EBNF表示的文法G4.13A A B B X A X (a | b) a | b 試用類 C 或類 PASCAL 語(yǔ)言寫出其遞歸下降子程序。4.5 已知文法G4.14SS (L) | a L L, S | S (1

17、) 消除文法G4.14的左遞歸，并為每個(gè)非終結(jié)符構(gòu)造不帶回溯的遞歸子程序。(2) 經(jīng)改寫后的文法是否是LL(1)文法？給出它的預(yù)測(cè)分析表。(3) 給出輸入串 (a, a)$ 的分析過程，并說明該符號(hào)串是否為文法G4.14的句子。4.6 對(duì)于文法G4.15RR R ' | ' T | T T TF | F F F* | C C (R) | a | b(1) 消除文法的左遞歸。(2) 計(jì)算文法G4.15各非終結(jié)符的FIRST集和FOLLOW集。(3) 構(gòu)造LL(1)分析表。4.7 已知文法G4.16A A aABe | a B Bb | d(1) 判斷該文法是否為L(zhǎng)L(1) 文法。

18、 (2) 寫出輸入串a(chǎn)ade$ 的分析過程。練習(xí) 55.1 設(shè)文法G5.10E為E E+T | E-T | TT T*F | T/F | FF FP | PP (E) | i求以下句型的短語(yǔ)、直接短語(yǔ)、素短語(yǔ)、句柄和最左素短語(yǔ)：（1）E-T/F+i（2）E+F/T-Pi（3）T*(T-i)+P（4）(i+i)/i-i5.2 根據(jù)下列優(yōu)先關(guān)系矩陣計(jì)算其優(yōu)先函數(shù)，并說明優(yōu)先函數(shù)是否存在。SABabcSABabc5.3 對(duì)于文法G5.11SS (R) | a | b R TT S; T | S（1）計(jì)算G5.11 S的FIRSTTV和LASTTV；（2）構(gòu)造G5.11 S的優(yōu)先關(guān)系表，并說明G5.1

19、1 S是否為算符優(yōu)先文法；（3）計(jì)算G5.11 S的優(yōu)先函數(shù)。5.4 對(duì)于文法G5.12 SS S;G | GG G(T) | HH a | (S)T T+S | S（1）構(gòu)造G5.12 S的算符優(yōu)先關(guān)系表，并判斷G5.12 S是否為算符優(yōu)先文法；（2）給出句型a(T+S);H;S的短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)；（3）分別給出(a+a)和a;(a+a)的分析過程，并說明它們是否為G5.12 S的句子；（4）給出（3）中輸入串的最右推導(dǎo)，分別說明它們是否為G5.12 S的句子；（5）從（3）和（4）說明算符優(yōu)先分析的優(yōu)缺點(diǎn)。5.5 對(duì)于文法G5.13PP LAd | cdL cA a

20、P | P | a請(qǐng)證明它不存在優(yōu)先函數(shù)。5.6 給定文法G5.14 SS AS | bA SA | a（1）構(gòu)造它的LR(0)的項(xiàng)集；（2）構(gòu)造識(shí)別該文法所有活前綴的DFA；（3）這個(gè)文法是SLR(1)嗎？若是，構(gòu)造出它的SLR(1)分析表。5.7 給定文法G5.15SS AS | eA aA | b（1）構(gòu)造它的LR(1)文法；（2）構(gòu)造識(shí)別該文法所有活前綴的DFA；（3）構(gòu)造出它的SR(1)分析表；（4）給出字符串a(chǎn)bab$的分析過程。5.8 若有定義二進(jìn)制數(shù)的文法G5.16DD L . L | LL LB | BB 0 | 1 （1） 通過構(gòu)造該文法的無沖突的分析表來說明它是哪類LR文

21、法;（2） 給出輸入串101.010的分析過程。5.9 給定文法G5.17SS L = R| RL *R | idR L（1）構(gòu)造它的LR(0)的項(xiàng)集；（2）構(gòu)造它的LR(0)項(xiàng)集規(guī)范族；（3）構(gòu)造識(shí)別該文法所有活前綴的DFA；（4）該文法是SLR(1)、LR(1)以及LALAR(1)？構(gòu)造相應(yīng)的分析表。5.10 對(duì)于文法G5.18SS AA Ab | bBaB aAc | aAb | a（1）證明它是SLR(1)文法，但不是LR(0)文法；（2）證明所有SLR(1)文法都是LR(1)文法。5.11 證明文法G5.19MM NN Qa | bQc | dc | bdaQ D是LALR(1)文法

22、，但不是SLR(1)文法。5.12 證明文法G5.20SS aAa | aBb | bAb | bBaA cB c是LR(1)文法，但不是LALR(1)文法。5.13 對(duì)于文法G5.21SS AaAb | BbBa A eB e（1）證明它是LL(1)文法，但不是SLR(1)文法；（2）證明所有LL(1)文法都是LR(1)文法。5.14 對(duì)于下列各個(gè)文法，判斷它是哪類最簡(jiǎn)單的LR文法，并構(gòu)造相應(yīng)的分析表。（1）A AA + | AA* | a （2）S ABA aBa | eB bAb | e（3）S D; B | BD d | eB B; a | a| e（4）S D; B | BD d |

23、 eB B; a | a| e（5）S (SR | aR . SR | )（6）S UTa | TbT S | Sc | dU US | e5.15 命題演算的文法G5.22B B B and B | B or B | not B | (B) | true | false | b是二義性文法。（1）為句子b and b or true構(gòu)造兩個(gè)不同的最右推導(dǎo)，以此說明該文法是二義的。（2）為它寫一個(gè)等價(jià)的非二義性文法。（3）給出無二義性規(guī)則，構(gòu)造出LR(0)分析表，并給出句子b and b or true的分析過程。練習(xí) 66.1 符號(hào)表的作用有哪些？6.2 符號(hào)表的表項(xiàng)通常包括哪些屬性，主要描

24、述的內(nèi)容是什么？6.3 符號(hào)表組織的數(shù)據(jù)結(jié)構(gòu)有哪些種？每種組織結(jié)構(gòu)選取的主要依據(jù)是什么？6.4程序塊是程序語(yǔ)言的主要構(gòu)造元素，它允許以嵌套的方式確定局部聲明。大多數(shù)語(yǔ)言規(guī)定，程序塊結(jié)構(gòu)的聲明作用域使最近嵌套規(guī)則，請(qǐng)按照這個(gè)規(guī)則寫出下列聲明的作用域。main()/* 開始?jí)KB0 */int a = 0;int b =0; /* 開始?jí)KB1 */int b = 1; /* 開始?jí)KB2 */int a = 2; /* 結(jié)束塊B2 */ /* 開始?jí)KB3 */int b = 3; /* 結(jié)束塊B3*/ /* 結(jié)束塊B1*/6.5C語(yǔ)言中規(guī)定變量標(biāo)識(shí)符可以定義為：extern、ertern static

25、、auto、local static和register，請(qǐng)對(duì)這5種變量分別說明其作用域。6.6 設(shè)散列表為HT13，哈希函數(shù)定義為hash(key)=key%13（整數(shù)除法取余運(yùn)算），用鏈地址法解決沖突對(duì)下列關(guān)鍵碼12，23，45，57，20，3，31，15，56，78造表。練習(xí) 77.1 請(qǐng)考慮過程和活動(dòng)記錄的聯(lián)系和區(qū)別。7.2 請(qǐng)解釋下列概念：生存期，過程的活動(dòng)，活動(dòng)樹，活動(dòng)記錄。 7.3有哪些常見的參數(shù)傳輸方式，請(qǐng)分析和比較它們各自的特點(diǎn)。7.4對(duì)你熟悉的高級(jí)程序語(yǔ)言（如C、Pascal、C+、Java或C#），了解它們的參數(shù)傳輸機(jī)制。7.5執(zhí)行下面Pascal程序的輸出a結(jié)果分別是什么

26、，如果參數(shù)的傳遞機(jī)制是：（1）引用調(diào)用方式；（2）值結(jié)果調(diào)用方式；program copyout (input, output);var a: integer;procedure unsafe （var x: integer）;begin x := 2; a := 0 end;begina := 1; unsafe (a); writeln (a)end7.6 執(zhí)行下面程序時(shí)打印的a分別是什么，若參數(shù)的傳遞機(jī)制是：（1）按值調(diào)用方式；（2）引用調(diào)用方式；（3）值結(jié)果調(diào)用方式；（4）換名調(diào)用方式。procedure p(x, y, z);beginy := y +1; z := zx;end p

27、;begina := 2;b := 3;p(a+b, a, a);print a;end;7.7 設(shè)計(jì)存儲(chǔ)分配時(shí)要考慮哪些主要因素？常見的存儲(chǔ)分配策略有哪些？簡(jiǎn)單說明在什么情況下使用哪種存儲(chǔ)分配策略。7.8C+語(yǔ)言中關(guān)于變量的存儲(chǔ)類型符有4個(gè)：auto、register、static和extern，請(qǐng)說明每個(gè)說明符所表示的存儲(chǔ)方式。7.9為下面FORTRAN程序的運(yùn)行時(shí)環(huán)境構(gòu)造出一個(gè)可能的組織結(jié)構(gòu)，要保證對(duì)AVE的調(diào)用時(shí)存在的一個(gè)存儲(chǔ)器指針（參考7.4節(jié)）。REAL A(SIZE), AVEINTEGER N, I10READ *, NIF (N .LE. 0 .OR. N .GT. SIZE

28、) GOTO 99READ *, (A(I), I=1, N)PRINT *, AVE = , AVE(A, N)GOTO 1099CONTINUEENDREAL FUNCTION AVE (B, N)INTEGER I, NREAL B(N), SUMSUM = 0.0DO 20 I=1, N20SUM = SUM+B(I)AVE = SUM/NEND7.10考慮C語(yǔ)言中的下列過程：void f ( char c, char s10, double r) int * x; int y 5; .（1）使用標(biāo)準(zhǔn)C參數(shù)傳遞約定，利用7.5.1所描述的活動(dòng)記錄結(jié)構(gòu)判斷以下的fp的偏移：c，s7和y2

29、（假設(shè)數(shù)據(jù)大小為：整型2個(gè)字節(jié)，字符1個(gè)字節(jié)，雙精度8個(gè)字節(jié)，地址4個(gè)字節(jié)）（2）假設(shè)所有的參數(shù)都是按值傳遞（包括數(shù)組），重做（1）；（3）假設(shè)所有的參數(shù)都是引用傳遞（包括數(shù)組），重做（1）。7.11為下面C程序的運(yùn)行時(shí)環(huán)境構(gòu)造出一個(gè)可能的組織結(jié)構(gòu)（參考7.5.1節(jié)）。(1)在進(jìn)入函數(shù)f中的塊A之后；(2)在進(jìn)入函數(shù)g中的塊B之后。int a10;char *s = hello;int f ( int i, int b )int j = 1; A: int i = j;char c = bi;. return 0;void g (char *s)char c = s0;B: int a5; .

30、 main () int x = 1; x = f (x, a); g (s); return 0;7.12使用訪問鏈（參考7.5.2節(jié)）分別畫出下面Pascal程序執(zhí)行到（1） 第1次調(diào)用r之后的運(yùn)行時(shí)棧的內(nèi)容；（2） 第2次調(diào)用r之后的運(yùn)行時(shí)棧的內(nèi)容；program pascal1;procedure p;var x: integer;procedure q;procedure r;beginx := 2;.if . then p;end; r beginr;end; q beginq;end; p begin pascal1 p;end.7.13使用顯示表display重做練習(xí)7.12。

31、7.14對(duì)下面的Pascal程序，分別畫出程序執(zhí)行到點(diǎn)（1）和（2）時(shí)刻的運(yùn)行時(shí)棧的內(nèi)容。program pascal2 (input, output);var i: integer; d: integer;procedure a ( k: real );var p: char;procedure b;var c: char;begin.(1).end: bprocedure c;var t: real;begin.(2).end: cbegin.b;c;.end; abegin pascal2 .a (d);.end. 7.15使用顯示表display重做練習(xí)7.14。7.16實(shí)現(xiàn)棧式動(dòng)態(tài)存

32、儲(chǔ)管理的一個(gè)問題是，如何分配空閑塊。請(qǐng)考慮有幾種空閑塊的分配策略，并比較每個(gè)策略的優(yōu)缺點(diǎn)。7.17了解面向?qū)ο笳Z(yǔ)言（如面向?qū)ο驪ascal、C+、C#、Java）是如何實(shí)現(xiàn)垃圾搜集任務(wù)的。7.18存儲(chǔ)緊縮有時(shí)也稱為“單空間復(fù)制”，以區(qū)別雙空間復(fù)制，請(qǐng)指出兩者的相同之處和差異。7.19為以下的C+類畫出對(duì)象的存儲(chǔ)器框架和虛擬函數(shù)表（參考7.6.3節(jié)）：class A public:int a;virtual void f();virtual void g(); ;class B: public A public:int b;virtual void f();void h();；class C:

33、public B public:int c;virtual void g(); 練習(xí) 88.1 語(yǔ)義分析的基本任務(wù)是什么？請(qǐng)簡(jiǎn)單說明它們可以在編譯的哪些階段或者由編譯的哪些模塊完成？8.2 考慮下列無符號(hào)數(shù)的簡(jiǎn)單語(yǔ)法：number ® digit number | digitdigit ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9寫出計(jì)算number整數(shù)值的屬性規(guī)則。8.3根據(jù)下列文法，給出求十進(jìn)制浮點(diǎn)數(shù)的值的語(yǔ)義規(guī)則（提示：用屬性count表示小數(shù)點(diǎn)后的數(shù)字?jǐn)?shù)目）：num ® num.numnum ® num digi

34、t | digitdigit ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 98.4考慮下面的簡(jiǎn)單的Pascal風(fēng)格的聲明：decl ® var-list：typevar-list ® var-list，id | idtype ® integer | real（1）為它設(shè)計(jì)一個(gè)計(jì)算變量類型的屬性文法；（2）為每個(gè)產(chǎn)生式對(duì)應(yīng)的屬性文法劃一個(gè)依賴圖；（3）為聲明a, b, c: real畫出屬性依賴圖。8.5修改例8.4中的文法G8.3，使之只用綜合屬性就可以計(jì)算based-num的值。8.6考慮下列屬性文法：文法規(guī)則語(yǔ)義規(guī)則S

35、 ® ABCB.u := S.uA.u := B.v + C.vS.v := A.vA ® aA.v := 2*A.uB ® bB.vl := B.uC ® cC.v := 1(1) 構(gòu)造出串a(chǎn)bc的分析樹及其屬性依賴圖，并給出計(jì)算這些屬性的一個(gè)正確順序；(2) 假設(shè)S.u在屬性求值之前的值是3，那么S.v在屬性求值之后的值是什么？(3) 如果語(yǔ)義規(guī)則修改如下，問題（2）的結(jié)果如何？文法規(guī)則語(yǔ)義規(guī)則S ® ABCB.u := S.uC.u := A.vA.u := B.v + C.vS.v := A.vA ® aA.v := 2*A.

36、uB ® bB.vl := B.uC ® cC.v := C.u - 28.7設(shè)計(jì)有向圖的一個(gè)拓?fù)渑判蛩惴ǎ⒂酶呒?jí)程序語(yǔ)言實(shí)現(xiàn)。8.8一個(gè)包含了綜合屬性和繼承屬性的屬性文法中，如果綜合屬性依賴于繼承屬性（以及其它綜合屬性），但是繼承屬性不依賴任何綜合屬性，那么，用一趟混合的后序遍歷和前序遍歷就可以計(jì)算所有的屬性值。請(qǐng)用高級(jí)語(yǔ)言或偽代碼設(shè)計(jì)這個(gè)算法。8.9例8.11中的三個(gè)屬性isFloat、etype和val的語(yǔ)義規(guī)則如表8.8所示，它們需要遍歷分析樹或語(yǔ)法樹兩次才能計(jì)算出來。第一遍后序遍歷計(jì)算出綜合屬性isFloat的值，第二遍用混合的前序遍歷和后序遍歷計(jì)算出繼承屬性e

37、type與綜合屬性val的值。（1）請(qǐng)用高級(jí)語(yǔ)言或偽代碼設(shè)計(jì)這個(gè)算法；（2）描述5/2/2.0屬性的計(jì)算過程。8.10請(qǐng)按照例8.14中的語(yǔ)義規(guī)則，畫出float x, y的帶屬性的分析樹以及依賴關(guān)系圖。8.11考慮文法S ® ( L ) | aL ® L, S | S（1）寫一個(gè)打印括號(hào)對(duì)數(shù)的屬性文法；（2）寫一個(gè)翻譯模式，它輸出每個(gè)a的嵌套深度。例如，對(duì)于輸入串(a, (a, a)的輸出是1，2，2。（3）寫一個(gè)翻譯模式，它打印出每個(gè)a在句子中的位置。例如，對(duì)于輸入串(a, (a, a)的結(jié)果是2，5，7。8.12下列文法由S符號(hào)開始產(chǎn)生一個(gè)二進(jìn)制數(shù)，令綜合屬性val給

38、出該數(shù)的值：S ® L.L | LL ® LB | BL ® 0 | 1請(qǐng)?jiān)O(shè)計(jì)求S.val的屬性文法。其中B的唯一綜合屬性c給出由B產(chǎn)生的二進(jìn)位的結(jié)果值。例如，輸入101.101時(shí)，S.val是5.625，其中第一個(gè)二進(jìn)位的值是4，最后一個(gè)二進(jìn)位的值是0.125。8.13考慮下列類似于C語(yǔ)言包含賦值語(yǔ)句的表達(dá)式的文法S ® EE ® E := E | E + E | (E) | id即b := c表示把c的值賦給b的賦值表達(dá)式，而a:= ( b:= c)表示c的值賦給b后再賦給a。試構(gòu)造語(yǔ)義規(guī)則，檢查表達(dá)式的左部是一個(gè)左值。提示：同非終結(jié)符E的

39、繼承屬性side表示生成的表達(dá)式出現(xiàn)在賦值運(yùn)算符的左邊還是右邊。8.14請(qǐng)根據(jù)例8.5的屬性文法，（1）把語(yǔ)義規(guī)則翻譯成LR屬性求值器的棧操作代碼（參考例8.12）；（2）建立對(duì)應(yīng)的翻譯模式；（3）消除基礎(chǔ)文法的左遞歸，對(duì)新增的符號(hào)增加綜合屬性和繼承屬性，編寫無左遞歸的翻譯模式;（4）編寫它的遞歸下降屬性求值器。8.15為下列類型寫出類型表達(dá)式（1）指向?qū)崝?shù)的指針數(shù)組，下標(biāo)范圍從1到100；（2）二維數(shù)組，行的下標(biāo)從1到10，列的下標(biāo)從10到10；（3）一個(gè)函數(shù)，它的定義域是從整型到整型指針的函數(shù)，值域是一個(gè)實(shí)型和字符組成的記錄。8.16對(duì)下面C語(yǔ)言的聲明：typedef struct int

40、 a,b: CELL, *PCELL;CELL foo100;PCELL bar(x, y) int;CELL y;.試為類型foo和函數(shù)bar寫出類型表達(dá)式。8.17下列是一個(gè)包含文字串表的文法，其中符號(hào)的含義和圖8.15中的一樣。只是增加了類型list，它表示一個(gè)元素表，表中類型由of 后面的類型T確定。試設(shè)計(jì)一個(gè)翻譯模式/語(yǔ)義規(guī)則，確定表達(dá)式(E)和(L)的類型。P ® D; ED ® D; D | id:T T ® list of T | char | integerE ® (L) | literal | num | idE ® E;

41、L | E8.18修改表8.15的語(yǔ)義規(guī)則，使之可以處理（1）有值語(yǔ)句。賦值語(yǔ)句的值是賦值號(hào):=右邊表達(dá)式的值；條件語(yǔ)句和循環(huán)語(yǔ)句的值是語(yǔ)句體的值；順序語(yǔ)句的值是該序列中最后一個(gè)語(yǔ)句的值；（2）布爾表達(dá)式。增加邏輯運(yùn)算符and、or和not以及關(guān)系運(yùn)算符、<、=、>和，并且增加相應(yīng)的翻譯規(guī)則，給出這些表達(dá)式的類型。練習(xí) 99.1把下列表達(dá)式變換成后綴式：（1）23ab（2）a*b + 2*c*d（3）(x := x +3) *4（4）(x := y := 2) + 3*(x := 4)9.2把下列表達(dá)式變換成后綴式：（1）(not A and B) or (C or not D)（

42、2）(A or B) and (C or not D and E)（3）if (x+y) *z = 0 then (a+b) *c else (a*b) +b（4）aai = b j+29.3請(qǐng)把do S while E和for (V = E1; E2; E3) S形式的循環(huán)語(yǔ)句寫成后綴式。9.4如果允許處理過程遞歸，還需要改變表9.7的翻譯模式。在產(chǎn)生式D ® proc id; N D1; S的S之前，執(zhí)行語(yǔ)義動(dòng)作把id插入其直接外圍過程的符號(hào)表。請(qǐng)通過引入非終結(jié)符R及其e產(chǎn)生式，修改表9.7的語(yǔ)義動(dòng)作，使它能夠處理遞歸過程調(diào)用。9.5請(qǐng)根據(jù)表9.7的語(yǔ)義動(dòng)作，補(bǔ)充圖9.4中符號(hào)表

43、的構(gòu)造過程，畫出符號(hào)表以及tblptr和offset：（1）當(dāng)編譯掃描完quicksort的局部變量說明var k, v: integer；時(shí)；（2）當(dāng)編譯掃描完partition的聲明、在局部變量說明var i, j: integer；之前；（3）當(dāng)編譯掃描完partition的整個(gè)過程時(shí)。9.6把下列表達(dá)式翻譯成三地址代碼：（1）x := y*(- a + b)（2）i := (j+k)*(10+m)9.7一般而言，程序設(shè)計(jì)語(yǔ)言都把算術(shù)表達(dá)式中不同類型的運(yùn)算數(shù)進(jìn)行轉(zhuǎn)換，通常的規(guī)則是把整數(shù)轉(zhuǎn)換成實(shí)數(shù)，然后進(jìn)行運(yùn)算。為了區(qū)別不同類型的運(yùn)算，可以在運(yùn)算符前加上類型，如實(shí)數(shù)加法的符號(hào)是real+，

44、整數(shù)乘法的符號(hào)是int*。（1）請(qǐng)利用單目轉(zhuǎn)換符inttoreal以及表示類型的運(yùn)算符，修改表9.9文法中加法表達(dá)式翻譯規(guī)則，插入必要的類型轉(zhuǎn)換。（提示：參考圖9.6和表7.16，使用E的屬性type和place）（2）把下列程序段的執(zhí)行語(yǔ)句翻譯成三地址代碼：float x, y;int a, b;x := y + a*b9.8用9.3節(jié)所給的翻譯模式，把下列賦值語(yǔ)句翻譯成三地址代碼：（1）ai+j := ai+aj*10（2）Ai, j := Bi, j + CAk, 1 + Di+19.9按照表9.11翻譯模式把下列布爾表達(dá)式翻譯成三地址碼（假設(shè)語(yǔ)句起始標(biāo)號(hào)是10）：（1）a<b o

45、r c<d and e<f（2）a¹b and not c or d>c9.10按照表9.12翻譯模式把9.9題目中的布爾表達(dá)式翻譯成三地址碼。9.11利用回填技術(shù)把9.9題目中的布爾表達(dá)式翻譯成四元式，假設(shè)語(yǔ)句起始標(biāo)號(hào)是10，真值出口是100，假值出口是200。9.12根據(jù)9.4.2節(jié)的翻譯規(guī)則，把下列語(yǔ)句翻譯成抽象的三地址代碼：（1）while a < b doif c < d then x := y + z; else x:= y - z;（2）while a < b and c > d do if a = 1 then c := c

46、+ 1 elsewhile a <= d do begin d := d*2; c := c - d end;9.13利用回填技術(shù)，分別把題目9.12中的語(yǔ)句翻譯成四元式的形式。9.14C語(yǔ)言中的for語(yǔ)句的一般形式是for (E1; E2; E3) S含義如下：E1;while (E2) do beginS;E3;end;試構(gòu)造一個(gè)把C語(yǔ)言for 語(yǔ)句翻譯成三地址碼的翻譯模式。9.15給出描述下面語(yǔ)句的翻譯模式repeat S until E;練習(xí) 1010.1一個(gè)編譯程序的代碼生成工作需要考慮哪些因素？10.2 利用語(yǔ)法制導(dǎo)的翻譯技術(shù)把下列程序段翻譯成目標(biāo)代碼：(1) x := (a

47、+b)*c - a(2) a > b and cd or e < f10.2 請(qǐng)把以下程序劃分為基本塊并作出其程序流圖。read CA := 0B:= 1L1: A := A + Bif B ³C gogo L2B := B + 1goto L1L2: write A10.3請(qǐng)把以下程序劃分為基本塊并作出其程序流圖。i := mj := na := u1L1:i := i + 1j := j 1if i > j goto L2a := u2L2: i := u3goto L110.4 對(duì)下列中間代碼序列(1)T1 := B CT2 := A*T1T3 := D + 1T4 := E FT5 := T3*T4W := T2/T5W是基本塊出口的活躍變量(2)T1 := A + BT2 := T1 CT3 := T2 *T1