編譯原理復(fù)習(xí)題集

1、編譯原理復(fù)習(xí)題集1名詞解釋短語(yǔ)：令G是一個(gè)文法。S劃文法的開(kāi)始符號(hào)，假定是文法G的一個(gè)句型，如果有SA且AB，則稱(chēng)是句型相對(duì)非終結(jié)符A的短語(yǔ)。 設(shè)GZ是給定文法, w=xuyV+，為該文法的句型,如果滿(mǎn)足下面兩個(gè)條件: Z xUy； U u； 則稱(chēng)句型xuy 中的子串u是句型xuy的短語(yǔ)。句柄：設(shè)GZ是給定文法, w=xuyV+，為該文法的句型,如果滿(mǎn)足下面兩個(gè)條件: Z xUy； U Þ u； 則稱(chēng)句型xuy 中的子串u是句型xuy的簡(jiǎn)單短語(yǔ)（或直接短語(yǔ)）。一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的句柄。文法上下文無(wú)關(guān)文法LL（1）文法：若文法的任何兩個(gè)產(chǎn)生式A ® a | b

2、都滿(mǎn)足下面兩個(gè)條件：（1）FIRST(a ) Ç FIRST(b ) = f；（2）若b Þ* e ，那么FIRST(a ) Ç FOLLOW( A ) = f。 我們把滿(mǎn)足這兩個(gè)條件的文法叫做LL(1)文法，其中的第一個(gè)L代表從左向右掃描輸入，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒(méi)有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。LR（1）文法語(yǔ)法分析：按文法產(chǎn)生式識(shí)別輸入的符號(hào)是否為一個(gè)句子的分析過(guò)程。無(wú)環(huán)路有向圖(DAG)：如果有向圖中任一通路都不是環(huán)路，則稱(chēng)廬有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱(chēng)

3、DAG。后綴式：一種把運(yùn)算量寫(xiě)在前面，把算符寫(xiě)在后面的表示表達(dá)式的方法。語(yǔ)法制導(dǎo)翻譯：在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的方法叫做語(yǔ)法制導(dǎo)翻譯。遍：指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。局部?jī)?yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼。詞法分析：詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語(yǔ)法分析程序。語(yǔ)義分析源語(yǔ)言源程序目標(biāo)語(yǔ)言中間語(yǔ)言（中間表示）2簡(jiǎn)答題(1

4、) 編譯程序和高級(jí)語(yǔ)言有什么區(qū)別? 用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫(xiě)的程序，必須先送入計(jì)算機(jī)，經(jīng)過(guò)轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的目標(biāo)程序（這個(gè)過(guò)程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過(guò)程的程序叫編譯程序。匯編程序是指沒(méi)有編譯過(guò)的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn)換過(guò)的叫目標(biāo)程序，也就是機(jī)器語(yǔ)言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來(lái)將匯編語(yǔ)言編寫(xiě)的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語(yǔ)言程序的一個(gè)語(yǔ)句，先解釋成為一組機(jī)器語(yǔ)言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語(yǔ)句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人

5、和計(jì)算機(jī)的"對(duì)話(huà)"，隨時(shí)可以修改高級(jí)語(yǔ)言的程序。BASIC語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)⒓?jí)語(yǔ)言編寫(xiě)的程序，一次就會(huì)部翻譯成機(jī)器語(yǔ)言表示的程序，而且過(guò)程進(jìn)行很快，在過(guò)程中，不能進(jìn)行人機(jī)對(duì)話(huà)修改。FORTRAN語(yǔ)言就是編譯型高級(jí)語(yǔ)言。(2) 編譯程序的工作分為那幾個(gè)階段? 詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序進(jìn)行的分析(稱(chēng)為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱(chēng)為對(duì)源程序進(jìn)行綜合(稱(chēng)為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。(3) 簡(jiǎn)述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開(kāi)始，逐步進(jìn)行“歸約”，

6、直至歸約到文法的開(kāi)始符號(hào)；或者說(shuō)從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”，直到根節(jié)點(diǎn)。(4) 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？ 答：目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。 應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪(fǎng)問(wèn)內(nèi)存次數(shù)；   (3)如何充分利用指僅系統(tǒng)的的特點(diǎn)。(5) 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？答：優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。分為三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。 (6

7、) 簡(jiǎn)述代碼優(yōu)化的目的和意義。3敘述下面的正規(guī)式描述的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA的狀態(tài)轉(zhuǎn)換圖。( 1 | 01 )* 0*解答：該正規(guī)式描述的語(yǔ)言是，所有不含子串001的0和1的串。最小化：A和C的后繼狀態(tài)是相同的，所以可以將其合并4Pascal語(yǔ)言無(wú)符號(hào)數(shù)的正規(guī)定義如下：num ® digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示數(shù)字，用狀態(tài)轉(zhuǎn)換圖表示接受無(wú)符號(hào)數(shù)的確定有限自動(dòng)機(jī)。解答：5畫(huà)出Pascal中實(shí)數(shù)(不帶正負(fù)號(hào)，可帶指數(shù)部分)的狀態(tài)轉(zhuǎn)換圖。 6用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)*aa的確定的有限自動(dòng)機(jī)。答案 狀態(tài)轉(zhuǎn)換圖見(jiàn)圖1.

8、8。a102startaabbb圖1.8 接收(a | b)* aa的DFA分析 和上一題不同的是，現(xiàn)在是直接構(gòu)造DFA。我們?nèi)匀粓?jiān)持這一點(diǎn)，大家既要會(huì)按教材上的算法從NFA的確定化得到DFA，也要會(huì)手工直接構(gòu)造DFA。我們通過(guò)本題和下一題來(lái)說(shuō)明，手工直接構(gòu)造DFA也并不困難。該正規(guī)式表示的語(yǔ)言是，字母表S= a, b上最后兩個(gè)字符都是a的串的集合。抓住這個(gè)特點(diǎn)，我們首先畫(huà)出構(gòu)造過(guò)程中的第一步，見(jiàn)圖1.9。它表明最簡(jiǎn)單的句子是aa。然后，因?yàn)樵诘谝粋€(gè)a前可以有若干個(gè)b，因此狀態(tài)0有到自身的b轉(zhuǎn)換。在最后兩個(gè)字符都是a的串的末尾添加若干個(gè)a，能夠保持串的這個(gè)性質(zhì)，因此狀態(tài)2有到自身的a轉(zhuǎn)換。這樣

9、我們有圖1.10。102starsaa圖1.9 構(gòu)造過(guò)程中的第一步102startaaab圖1.10 構(gòu)造過(guò)程中的第二步最后，在狀態(tài)1和狀態(tài)2碰到b時(shí)，前面剛讀過(guò)的a，不管連續(xù)有多少個(gè)，都不可能作為句子結(jié)尾的那兩個(gè)字符a，因此狀態(tài)1和狀態(tài)2的b轉(zhuǎn)換回到狀態(tài)0。所有狀態(tài)的a轉(zhuǎn)換和b轉(zhuǎn)換都已給出，這就得到最后結(jié)果。7處于/* 和 */之間的串構(gòu)成注解，注解中間沒(méi)有*/。畫(huà)出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。答案 見(jiàn)圖1.3。標(biāo)記為others的邊是指字符集中未被別的邊指定的任意其它字符。分析 這個(gè)DFA的狀態(tài)數(shù)及含義并不難確定，見(jiàn)下面的五個(gè)狀態(tài)說(shuō)明。狀態(tài)1：注釋開(kāi)始狀態(tài)。狀態(tài)2：進(jìn)入注釋體前的中間

10、狀態(tài)。狀態(tài)3：表明目前正在注釋體中的狀態(tài)。狀態(tài)4：離開(kāi)注釋前的中間狀態(tài)。124start52othersothers/*/圖1.3 接受注釋的DFA狀態(tài)5：注釋結(jié)束狀態(tài)，即接受狀態(tài)。在這個(gè)DFA中，最容易忽略的是狀態(tài)4到本身的*轉(zhuǎn)換。這個(gè)邊的含義是：在離開(kāi)注釋前的中間狀態(tài)，若下一個(gè)字符是*，那么把剛才讀過(guò)的*看成是注釋中的一個(gè)字符，而把這下一個(gè)字符看成可能是結(jié)束注釋的第一個(gè)字符。若沒(méi)有這個(gè)邊，那么象/* This is a comment */這樣的注釋就被拒絕。另外，上面的狀態(tài)轉(zhuǎn)換圖并不完整。例如，對(duì)于狀態(tài)1，沒(méi)有指明遇到其它字符怎么辦。要把狀態(tài)轉(zhuǎn)換圖畫(huà)完整，還需引入一個(gè)死狀態(tài)6，進(jìn)入這個(gè)狀

11、態(tài)就再也出不去了。因?yàn)樗皇墙邮軤顟B(tài)，因此進(jìn)入這個(gè)狀態(tài)的串肯定不被接受。完整的狀態(tài)轉(zhuǎn)換圖見(jiàn)下面圖1.4，其中all表示任意字符。在能夠說(shuō)清問(wèn)題時(shí)，通常我們省略死狀態(tài)和所有到它的邊。124start52othersothers/*/6othersothersall all圖1.4 接受注釋的完整DFA8某操作系統(tǒng)下合法的文件名為device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，長(zhǎng)度不限，但至少為1，畫(huà)出識(shí)別這種文件名的確定有限自動(dòng)機(jī)。答案 見(jiàn)圖1.5，圖中的標(biāo)記d表示任意字母。

12、分析 這個(gè)DFA和一些教材上接受無(wú)符號(hào)數(shù)的DFA有類(lèi)似的地方。我們首先考慮device:和.extension全都出現(xiàn)的情況。這時(shí)的DFA比較容易構(gòu)造，見(jiàn)圖1.6。dd123456d:dd.dstart圖1.6 文件名的三部分都出現(xiàn)的DFA然后考慮缺省情況。因?yàn)?extension可缺省，因此把狀態(tài)4也作為接受狀態(tài)。因?yàn)閚ame和device一樣，都是字母序列，因此在device:缺省時(shí)，把到狀態(tài)2為止得到的字母序列看成是name，所以從狀態(tài)2畫(huà)一條轉(zhuǎn)換邊到狀態(tài)5，標(biāo)記為.。（如果構(gòu)成name和device的字符完全不一樣，那么可以從狀態(tài)1到狀態(tài)4畫(huà)一條邊，其標(biāo)記同狀態(tài)3到狀態(tài)4的標(biāo)記一樣。）

13、由于device:和.extension都可缺省，因此把狀態(tài)2也作為接受狀態(tài)。9構(gòu)造一個(gè)DFA，它接受å=0, 1上0和1的個(gè)數(shù)都是偶數(shù)的字符串。解：狀態(tài)0：偶數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)1：奇數(shù)個(gè)1偶數(shù)個(gè)0 11001100狀態(tài)2：奇數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)3：奇數(shù)個(gè)0奇數(shù)個(gè)110設(shè)有非確定的有自限動(dòng)機(jī) NFA M=(A，B，C，0，1，A，C)，其中： (A，0)=C (A，1)=A，B (B，1)=C (C，1)=C。請(qǐng)畫(huà)出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：d01ACA，BBÆCCÆC狀態(tài)轉(zhuǎn)換圖為：1101111設(shè) LÍ a,b,c* 是滿(mǎn)足下述條件的

14、符號(hào)串構(gòu)成的語(yǔ)言： (1)若出現(xiàn) a ，則其后至少緊跟兩個(gè) c ； (2)若出現(xiàn) b ，其后至少緊跟一個(gè) c 。 試構(gòu)造識(shí)別 L 的最小化的 DFA ，并給出描述 L 的正規(guī)表達(dá)式。 答：DFA 如圖所示。相應(yīng)的正規(guī)式為 (c|acc|bc)* 。12寫(xiě)出字母表 = a, b上語(yǔ)言L(fǎng) = w | w的最后兩個(gè)字母是aa或bb的正規(guī)式，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。解答：語(yǔ)言L(fǎng)的正規(guī)式是：(a|b)*(aa|bb) 1start3aabb204aaabbb接受該語(yǔ)言的最簡(jiǎn)DFA是：13有窮自動(dòng)機(jī)M接受字母表0,1上所有滿(mǎn)足下述條件的串：串中至少包含兩個(gè)連續(xù)的0或兩個(gè)連續(xù)的1。請(qǐng)寫(xiě)出與M等價(jià)的正規(guī)

15、式。 解答：(0|1)*(00|11)(0|1)*14有正規(guī)式 b*abb*(abb*)* ，(1) 構(gòu)造該正規(guī)式所對(duì)應(yīng)的 NFA(畫(huà)出狀態(tài)轉(zhuǎn)換圖) 。(2) 將所求的 NFA 確定化(畫(huà)出確定化的狀態(tài)轉(zhuǎn)換圖)。 (3) 將所求的 NFA 最小化. (畫(huà)出最小化后的狀態(tài)轉(zhuǎn)換圖)。15求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)式. SàbS|aA AàaA|bB BàaA|bC|b CàbS|aA 16給出與下圖的NFA等價(jià)的正規(guī)式。S0S1S3S217把下面的NFA確定化。123456101110118下面兩個(gè)文法中哪一個(gè)不是LR（1）文法？對(duì)非LR（1）的那個(gè)文

16、法。給出那個(gè)有移進(jìn)歸約沖突的規(guī)范的LR（1）項(xiàng)目集。S ® aAcS ® aAcA ® bbA | bA ® bAb | b解答：S->aAc A->bAb|b 不是LR(1)文法。因?yàn)镮(0): S->.S $S->.a A c $I(1): S->S. $I(2): S->a.Ac $A->.bAb cA->.b cI(3)：S->Aa.c $I(4):A->b.Ab cA->b. cA->.bAb bA->.b bI(5):S->aAc. $I(6)：A->b

17、.Ab bA->b. bA->.bAb bA->.b b所以在項(xiàng)目集I(6)會(huì)出現(xiàn)移近和規(guī)約的沖突。所以不是LR(1)文法。0123aababba,b19將下面的DFA化成最簡(jiǎn)形式。20為語(yǔ)言L(fǎng) w | w Î (a | b)*并且在w的任何前綴中，a的個(gè)數(shù)不少于b的個(gè)數(shù)寫(xiě)一個(gè)LR（1）文法，不準(zhǔn)超過(guò)6個(gè)產(chǎn)生式。解答：S> aBS | bAS |A> a | BaaB>b | aBB21寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。 解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB

18、|2|4|6|8 C0|D22考查文法G(s): S( T ) | a + S | aTT, S | S(1) 消除文法的左遞歸；(2) 提取公共左因子；(3) 對(duì)每個(gè)非終結(jié)符，寫(xiě)出不帶回朔的遞歸子程序。解答：. S( T ) | a + S | a TST T ，ST| . S( T ) | aR R+S| T ，ST| . Procedure S Begin If SYM=( Then ADVANCE; E; If SYM=( Then ADVANCE; Else ERROR; Else If SYM=a Then Begin R; End Else ERROR; End; Pr

19、ocedure R Begin If SYM=+ Then Begin ADVANCE; S; End; End; Procedure T Begin If SYM=+ Then Begin ADVANCE; S; T; End; End;23設(shè)文法G(S)： S(L)|a S|a LL，S|S (1)消除左遞歸和回溯； (2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3)構(gòu)造預(yù)測(cè)分析表。 解： (1) S(L)|aS SS| LSL LSL| 評(píng)分細(xì)則：消除左遞歸2分，提公共因子2分。  (2) FIRST

20、)S)(，aFOLLOW(S)#，) FIRST(S)，a, FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L)， FOLLOW(L ) 24消除下列文法的左遞歸. SàSaP|Sf|P PàQbP|Q QàcSd|e 25已知文法 G ：AàaABe|a BàBb|d 給出與上述文法等價(jià)的 LL(1)文法 G'。26已知文法GA：A aAB | a B Bb | d（1）構(gòu)造與GA等價(jià)的LL(1)文法；（2）構(gòu)造GA的預(yù)測(cè)分析表。27程序的文法如下：P &#

21、174; DD ® D ; D | id : T | proc id ; D ; S（1）寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義，打印該程序一共聲明了多少個(gè)id。（2）寫(xiě)一個(gè)翻譯方案，打印該程序每個(gè)變量id的嵌套深度。28構(gòu)造下面文法的LL（1）分析表。D ® TLT ® int | realL ® id RR ® , id R | e解答：int realid,$DD®TLD®TLTT®intT®realLL®id RRR ®, id RR ® e29考慮下文法：D à TVT &#

22、224; int floatV à id , V | ida. 在該文法中提取左公因子。b. 為所得文法的非終結(jié)符構(gòu)造First和Follow集合。c. 說(shuō)明所得的文法是LL(1)文法。d. 為所得文法構(gòu)造LL(1)分析表。e. 假設(shè)有輸入串int x , y , z 寫(xiě)出相應(yīng)LL(1)分析程序的動(dòng)作。 答：在看一遍消除左遞歸a. 文法存在左公因子，提取左公因子后的文法為：D T VT int | floatV id V'V' ,V |b. 非終結(jié)符First集合Follow集合D int , float $ T int , float id V id $ V'

23、; , , $ c. (1) First ( TV ) = int , float First(int) First(float)=intfloat=; First(id V')=id； First(,V) First()=, =; (2) V'=>, First(V')Follow(V')= , , $ = 根據(jù)LL(1)文法的定義判斷，此文法是LL(1)文法；d. LL(1)分析表為：intfloatid,$DD TVD TVTT intT floatVVidV'V'V' ,VV'e. 輸入串int x,y,z的LL(1

24、)分析：步驟分析棧輸入串分析程序的動(dòng)作1$Dint x,y,z$D TV2$VTint x,y,z$T int3$V intint x,y,z$int匹配4$Vx,y,z$VidV'5$ V'xx,y,z$x匹配6$ V',y,z$V' ,V7$ V,y,z$, 匹配8$ Vy,z$VidV'9$ V'yy,z$y匹配10$ V',z$V' ,V11$ V,z$, 匹配12$ Vz$VidV'13$ V'zz$z匹配14$接受30說(shuō)明如下文法是否是LL（1）文法，若不是，將其轉(zhuǎn)換為L(zhǎng)L（1）文法。最后給出該文法的L

25、L（1）分析表。 A à B e B à B b | a 解答：文法中有左遞歸，不是LL(1)文法.            轉(zhuǎn)換為 G ：                         A 

26、; B e                          B  a B                    

27、60;    Bb B |                   Predict(A  B e) = a  .1            Predict(B  aB) = a  .2   

28、60;        Predict(B bB)= b  .3            Predict(B ) = e  .4LL(1)分析表：       a      b     

29、; e A     1   B     2   B      3     431設(shè)有文法：Pbegin XYendXXd;Xd;YY;sYs(1) 該文法含有左遞歸嗎？若有，消除它。(2) 改造后的文法是LL(1)文法嗎？若是，給出其預(yù)測(cè)分析表。(3) 寫(xiě)出句子 begin d；s end的分析過(guò)程。32已給

30、文法 GS ： S SaP | Sf | P P qbP | q 將 GS 改造成 LL （ 1 ）文法，并給出 LL （ 1 ）分析表。 答：改造后的文法： S PS' S' aPS'| fS' | e P qP' P' bP | e各候選式的 FIRST 集，各非終結(jié)符的 FOLLOW 集為產(chǎn)生式FIRST 集FOLLOW 集S PS'q#S' aPS' fS' eaf e #P qP'qa,f,#P' bP eb e a,f,#LL(1) 分析表為33設(shè)文法G(S)： S(L)|a S|a L

31、L，S|S (1) 消除左遞歸和回溯； (2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預(yù)測(cè)分析表。 34給定文法 GS ： S Aa|dAb|Bb|dBa A c B c 構(gòu)造文法 GS 的 LR （ 1 ）分析表。 解答：分析表如下圖所示35已知文法G(S) Sa|(T) TT，S|S 寫(xiě)出句子(a，a)，a)的規(guī)范歸約過(guò)程及每一步的句柄。 解答：句型規(guī)約規(guī)則句柄(a，a)，a)Saa (S，a)，a)TSS(T，a)，a)Saa(T，S)，a)TT，S T，S (S)，a) TSS(T)，a)SS(T)(T) (S，a)

32、TSS (T，a)Saa (T，S)TT，S T，S (T)S(T)(T)S36已知文法G(E) ET|ET TF|T *F F(E)|i 給出句型(T *Fi)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； 解：(1) 最右推導(dǎo)： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) 37說(shuō)明下面的文法不是SLR(1)文法，并重寫(xiě)一個(gè)等價(jià)的SLR(1)文法。S à M a | b M c | d c | b d aM à d解答：S ® S S ® M a | b M c | d c |

33、b d aM ® d因?yàn)閍是M的后繼符號(hào)之一，因此在上面最右邊一個(gè)項(xiàng)目集中有移進(jìn)-歸約沖突。等價(jià)的SLR(1)文法是S ® d a | b d c | d c | b d a38在PASCAL語(yǔ)言中，簡(jiǎn)單類(lèi)型的變量的聲明例舉如下：m, n : integerp, q, r : real為這樣的聲明寫(xiě)一個(gè)LR（1）文法（為簡(jiǎn)單起見(jiàn)，變量標(biāo)識(shí)符都用id表示），并根據(jù)你的文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義（或叫做為你的文法加上語(yǔ)義動(dòng)作），它將變量的類(lèi)型填入符號(hào)表。39一個(gè)非LR（1）的文法如下：L ® MLb | aM ® e請(qǐng)給出所有有移進(jìn)歸約沖突的LR（1）項(xiàng)目集，以

34、說(shuō)明該文法確實(shí)不是LR（1）的。解答：40若有文法 G(S)的產(chǎn)生式如下：SàL=R SàR Là*R Lài RàL,構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的 DFA.，判斷該文法是否是 SLR(1)文法，說(shuō)明理由。 41現(xiàn)有句型g ba lb 和產(chǎn)生式A® ba，分別指出LL（1）方法和LR（1）方法在掃描到此句型的什么位置決定用此產(chǎn)生式？42為下面的算術(shù)表達(dá)式文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的翻譯方案，它將每個(gè)子表達(dá)式E的符號(hào)（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數(shù)都不為零，這樣就不用擔(dān)心零的

35、符號(hào)。E ® E *E | +E | -E | unsigned_integer解答：E ® E1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG E ® +E1 E.sign := E1.sign E ® -E1 if E1.sign= POS then E.sign := NEG else E.sign := POSE ® unsigned_integer E.sign := POS43一個(gè)文法如下： S ® ( S ) S ® a 請(qǐng)給出該文法中

36、對(duì)活前綴(有效的LR (1)項(xiàng)目。44為下面文法添加語(yǔ)義規(guī)則（或叫動(dòng)作子程序），輸出S¢產(chǎn)生的二進(jìn)制數(shù)的值，如輸入是101時(shí)，輸出5。S¢ ® SS ® S B | BB ® 0 | 145寫(xiě)出表達(dá)式(ab*c)/(ab)d的逆波蘭表示及三元式序列。 解答：逆波蘭表示： abc*ab/d三元式序列：  (*，b，c)  (，a，)  (，a，b)  (/，)  (，d)【附：幾個(gè)練習(xí)】(1)aba0b0解答：逆波蘭表示為：aba0b0。

37、(2)a(a*bd)*(ab*d)/d解答：逆波蘭表示為：aab*dabd*d/。(3)ab0a0(ab)>2解答：逆波蘭表示為：ab0a0ab2。(4)a*(b*ca)bcd解答：逆波蘭表示為：abc*a*bcd。46把表達(dá)式- (a+b)*(c+d)+(a+b+c)翻譯成三地址碼序列。47設(shè)布爾表達(dá)式的文法為 E E1E2 E E1E2 E i 假定它們將用于條件控制語(yǔ)句中，請(qǐng) (1)改寫(xiě)文法，使之適合進(jìn)行語(yǔ)法制導(dǎo)翻譯； (2)寫(xiě)出改寫(xiě)后的每個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作。 解：(1) E0E(1)  EE0E(2)  EAE(1)  EEAE(

38、2)  Ei  (2) EE(1) BACKPATCH(E(1)·FC，NXQ)； E0·TC：E(1)·TC EE0E(2) E·FC：E(2)·FC；  E·TC：MERG(E0·TC，E(2)·TC) EAE(1) BACKPATCH(E(1)·TC，NXQ)； E0·FC：E(1)·FC  EEAE(2)  E·

39、;TC：E(2)·TC； E·FC：MERG(EA·FC，E(2)·FC) Ei E·TC：NXQ；E·FC：NXQ1； GEN(jn2，entry(i)，0)； GEN(j，0) 48將語(yǔ)句 if (A<X Ù B>0) while ( C>0 ) C=C+D; 翻譯成三地址碼序列。49設(shè)有基本塊如下：T1=S+RT2= 3T3= 12/T2T4=S/RA=T1-T4T5=S+RB=T5T6=T5*T3B=T6(1) 畫(huà)出中間代碼的流圖；(2)

40、設(shè)A、B是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的三地址碼序列。50設(shè)已構(gòu)造出文法G(S)：(1) S ® BB (2) B ® aB (3) B® b的LR分析表如下ACTIONGOTO狀態(tài)ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為abab，請(qǐng)給出LR分析過(guò)程(即按照步驟給出狀態(tài)，符號(hào)，輸入串的變化過(guò)程)。解答：步驟狀態(tài)符號(hào)輸入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#

41、901#S#acc51給出活動(dòng)記錄空間結(jié)構(gòu)。并給出各部分的存儲(chǔ)對(duì)象。解答：52將下面程序段翻譯成四元式序列。while( A<CB<D )if ( A=1) C=C+1 ; else while ( A<D ) A=A+2; 解： (1) (j，a，0，5)  (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，×，1，T1) (6) (：，T1，×) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) 

42、;(10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15)  評(píng)分細(xì)則：控制結(jié)構(gòu)4分，其它3分。 53有一語(yǔ)法制導(dǎo)翻譯如下所示：S bAb print(“1”) A (B print(“2”) A a print(“3”) B Aa) print(“4”) 若對(duì)輸入序列b(aa)a)a)b 進(jìn)行自底向上分析，請(qǐng)寫(xiě)出輸出序列。解答：3424242154畫(huà)出IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1)的

43、翻譯方案圖。55下面是一個(gè)C語(yǔ)言程序：main()long i;long a04;long j;i = 4; j = 8;printf(“%d, %dn”, sizeof(a), a00);雖然出現(xiàn)long a04這樣的聲明，在X86/Linux機(jī)器上該程序還是能通過(guò)編譯并生成目標(biāo)代碼。請(qǐng)回答下面兩個(gè)問(wèn)題：（1）sizeof(a)的值是多少，請(qǐng)說(shuō)明理由。（2）a00的值是多少，請(qǐng)說(shuō)明理由。解答：（1）按照數(shù)組size的計(jì)算公式，sizeof(a)的值一定是0。（2）a00的值是4。雖然a的size是0，但它仍然有起始地址，并且a00的地址等于a的起始地址。由于X86/Linux機(jī)器上，活動(dòng)記錄

44、棧向低地址方向增長(zhǎng)，另外由于低地址放低位字節(jié)，因此a00的地址和i的地址一致，其值和i的值一樣，等于4。56將下面的條件語(yǔ)句表示成三地址碼序列： if ( a>b ) x=a+b*c ; else x=b-a; 解答：四元式：(1) ( j>, a, b, (3)(2) ( j, , , (7) )(3) ( *, b, c, T1)(4) ( +, a, T1, T2)(5) ( :=, T2, , x)(6) ( j, , , (9)(7) ( -, b, a, T3)(8) ( :=, T3, , x)(9) ( )57考慮下面的三地址語(yǔ)句序列：b := 1b := 2if

45、w <= x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y <= z goto L4goto L5L4:g := g + 1h := 8goto L1L5:h := 9（1）在該代碼中用水平的橫線(xiàn)將代碼分成基本塊，并給每個(gè)基本塊一個(gè)序號(hào)。（2）畫(huà)出該代碼的控制流圖，每個(gè)基本塊就用（1）的序號(hào)表示。（3）若有循環(huán)的話(huà)，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。解答：58一個(gè)C語(yǔ)言程序如下：func(i1,i2,i3)long i1,i2,i3;long j1,j2,j3; printf("Addresses of i1,

46、i2,i3 = %o,%o,%on",&i1,&i2,&i3);printf("Addresses of j1,j2,j3 = %o,%o,%on",&j1,&j2,&j3);main()long i1,i2,i3;func(i1,i2,i3);該程序在SUN工作站上的運(yùn)行結(jié)果如下：Addresses of i1,i2,i3 = 35777773634,35777773640,35777773644Addresses of j1,j2,j3 = 35777773524,35777773520,35777773514從

47、上面的結(jié)果可以看出，func 函數(shù)的3個(gè)形式參數(shù)的地址依次升高，而3個(gè)局部變量的地址依次降低。試說(shuō)明為什么會(huì)有這個(gè)區(qū)別。解答： 由于實(shí)參表達(dá)式是反序進(jìn)入活動(dòng)記錄，而局部變量是順序在活動(dòng)記錄中分配。編譯計(jì)算時(shí)，每個(gè)類(lèi)型的大小都是靜態(tài)確定的59一個(gè)C語(yǔ)言程序如下：void fun(struct int x; double r; val) main()struct int x; double r; val;fun(val);該程序在X86/Linux機(jī)器上的用cc命令編譯時(shí)，報(bào)告的錯(cuò)誤信息如下：1: warning: structure defined inside parms1: warning:

48、 anonymous struct declared inside parameter list1: warning: its scope is only this definition or declaration,1: warning: which is probably not what you want.7: incompatible type for argument 1 of fun 請(qǐng)問(wèn)，報(bào)告最后一行的錯(cuò)誤的原因是什么？如何修改程序，使得編譯時(shí)不再出現(xiàn)這個(gè)錯(cuò)誤信息。解答：C語(yǔ)言對(duì)所有的類(lèi)型都采用結(jié)構(gòu)等價(jià)，唯有結(jié)構(gòu)類(lèi)型例外，采用名字等價(jià)。這里的類(lèi)型不相容是因?yàn)閮蓚€(gè)val不是名字等價(jià)

49、的。要消除這個(gè)錯(cuò)誤，包括所有的警告，程序修改如下：struct sint x;double r;void fun(struct s val) main()struct s val;fun(val);60一個(gè)C語(yǔ)言程序如下：main()func();printf("Return from funcn");func()char s4;strcpy(s,"12345678");printf("%sn",s);該程序在PC機(jī)linux操作系統(tǒng)上的運(yùn)行結(jié)果如下：12345678Segmentation fault (core dumped)試分

50、析為什么會(huì)出現(xiàn)這樣的運(yùn)行錯(cuò)誤。解答： 活動(dòng)記錄中存放返址的單元被串拷貝破壞【參數(shù)反序壓棧，局部變量順序分配】61一個(gè)C語(yǔ)言函數(shù)如下：func(i)long i;long j;j=i-1;func(j);該函數(shù)在PC機(jī)linux操作系統(tǒng)上編譯生成的匯編代碼如下：.file"stack.c"gcc2_compiled.:_gnu_compiled_c:.text.align 2.globl _func.type_func,function_func:pushl %ebpmovl %esp,%ebpsubl $4,%espmovl 8(%ebp),%edxdecl %edxmov

51、l %edx, -4(%ebp)movl -4(%ebp),%eaxpushl %eaxcall _funcaddl $4,%espL1:leaveretLfe1:.size_func,Lfe1-_func試畫(huà)出該函數(shù)的一個(gè)活動(dòng)記錄的內(nèi)容，包括活動(dòng)記錄的每個(gè)單元存放什么東西、執(zhí)行movl 8(%ebp),%edx指令時(shí)棧頂指針?biāo)傅牡奈恢谩⑴c活動(dòng)記錄有關(guān)的另一個(gè)指針?biāo)傅奈恢煤偷刂吩鲩L(zhǎng)方向。解答：62一個(gè)C語(yǔ)言的函數(shù)如下：func(c,l)char c;long l; func(c,l);在X86/Linux機(jī)器上編譯生成的匯編代碼如下：.file"parameter.c"

52、.version"01.01"gcc2_compiled.:.text.align 4.globl func.type func,functionfunc:pushl %ebp 將老的基地址指針壓棧movl %esp,%ebp 將當(dāng)前棧頂指針作為基地址指針subl $4,%esp 分配空間movl 8(%ebp),%eaxmovb %al,-1(%ebp)movl 12(%ebp),%eaxpushl %eaxmovsbl -1(%ebp),%eaxpushl %eaxcall funcaddl $8,%esp.L1:leave 和下一條指令一起完成恢復(fù)老的基地址指針，將棧頂ret 指針恢復(fù)到調(diào)用前參數(shù)壓棧后的位置，并返回調(diào)用者.Lfe1:.size func,.Lfe1-func.ident"GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"(a) 請(qǐng)指出對(duì)應(yīng)源程序第5行的函數(shù)調(diào)用func(c,l)的匯編指令是哪幾條。(b)