




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、會(huì)計(jì)學(xué)1編譯原理編譯原理(yunl)總復(fù)習(xí)總復(fù)習(xí)第一頁,共76頁。選擇題(10小題,共20分,每題2分)1.編譯程序必須完成的工作有 。詞法分析語法分析語義分析中間代碼生成中間代碼優(yōu)化目標(biāo)代碼生成A. B. C. D. 2.下列關(guān)于編譯和解釋的說法,正確的是 。解釋方式和編譯方式的區(qū)別在于解釋程序?qū)υ闯绦虿]有進(jìn)行真正翻譯。編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。解釋程序和編譯程序都是語言(yyn)處理程序。與編譯系統(tǒng)相比,解釋系統(tǒng)比較簡單,可移植性好,執(zhí)行速度慢。編譯程序是將高級(jí)語言(yyn)程序翻譯成匯編語言(yyn)程序或機(jī)器語言(yyn)程序解釋程序是將匯編語言(yyn)程序
2、翻譯成機(jī)器語言(yyn)程序A.B. C. D.CD第1頁/共76頁第二頁,共76頁。3. 這樣一些語言,它們能被確定有限自動(dòng)機(jī)識(shí)別,但不能用正則表達(dá)式表示。A存在 B.不存在 C.無法判定是否存在4.已知文法GS:S SaS | SbS | ScS | dSe | f,下列句型(j xn)中, 是規(guī)范句型(j xn)。AfafbS B.faSbS C.SaSbf. D.faS BCSaSSSbSff SaSSSbSfSaSSSbSSaSSff第2頁/共76頁第三頁,共76頁。5.下列(xili)文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S a
3、SbS | bSaS | D. S a | S + S | SS | S* | (S) B.句型句型(j xn):( ) ( )(SSS)S(SS)SA(SSS)S(SS)S第3頁/共76頁第四頁,共76頁。5.下列文法(wnf)中不是二義性文法(wnf)的是 。AS +SS | -SS | a B. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) C.句型句型(j xn):ababSSbSaSbSaSSbSaSaSbA第4頁/共76頁第五頁,共76頁。5.下列文法(wnf)中不是二義性文法(wnf)的是 。AS +SS
4、| -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)D.句型句型(j xn):a+a* S + SS S * a a S *SS + SaaA第5頁/共76頁第六頁,共76頁。6.后綴(huzhu)表達(dá)式ab+c*de*+ 的中綴形式是 。Aa*(b+c)+d*eB(a+b)*c+d*eCa+b*c*d+eDa+b*c+d*e B第6頁/共76頁第七頁,共76頁。第7頁/共76頁第八頁,共76頁。7.合并無沖突合并無沖突(chngt)的的LR(1)狀態(tài)機(jī)得到的)狀態(tài)機(jī)得到的LALR(1)狀態(tài)機(jī)中一定不會(huì)出
5、現(xiàn))狀態(tài)機(jī)中一定不會(huì)出現(xiàn) 沖突沖突(chngt)。移入移入/移入沖突移入沖突(chngt)B. 移入移入/歸歸約沖突約沖突(chngt)C. 歸約歸約/歸約沖突歸約沖突(chngt) B第8頁/共76頁第九頁,共76頁。ABCau1v1t1SiABCau2v2t2SjABCau1 u2v1 v2 t1 t2Si因:因:(u1 u2 ) a=(v1 v2 ) a=所以不可能所以不可能(knng)產(chǎn)生移入產(chǎn)生移入歸約沖歸約沖突。突。因:因:(u1 u2 ) (v1 v2 ) =?所以可能產(chǎn)生所以可能產(chǎn)生(chnshng)歸約歸約歸約歸約沖突。沖突。第9頁/共76頁第十頁,共76頁。8.編譯程序(b
6、in y chn x)使用 區(qū)別標(biāo)識(shí)符的作用域。A.聲明標(biāo)識(shí)符的過程或函數(shù)名B. 聲明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層數(shù)C.聲明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層數(shù)D.標(biāo)識(shí)符的行號(hào) B第10頁/共76頁第十一頁,共76頁。9.適合采用靜態(tài)存儲(chǔ)分配策略的程序設(shè)計(jì)語言的限制有適合采用靜態(tài)存儲(chǔ)分配策略的程序設(shè)計(jì)語言的限制有 。 數(shù)據(jù)數(shù)據(jù)(shj)實(shí)體所需空間在編譯時(shí)能確定實(shí)體所需空間在編譯時(shí)能確定 過程調(diào)用不允許遞歸過程調(diào)用不允許遞歸 不能動(dòng)態(tài)建立數(shù)據(jù)不能動(dòng)態(tài)建立數(shù)據(jù)(shj)實(shí)體實(shí)體 運(yùn)行時(shí)每個(gè)數(shù)據(jù)運(yùn)行時(shí)每個(gè)數(shù)據(jù)(shj)對象只能有一個(gè)實(shí)例對象只能有一個(gè)實(shí)例 數(shù)組的上下界是常量數(shù)組的上下界是常量A. B.C.
7、D.10.目標(biāo)代碼生成器的輸出可以是目標(biāo)代碼生成器的輸出可以是 。絕對機(jī)器代碼絕對機(jī)器代碼可重定位機(jī)器代碼可重定位機(jī)器代碼匯編匯編代碼代碼 虛擬機(jī)代碼虛擬機(jī)代碼 抽象語法樹抽象語法樹三地址代碼三地址代碼AB. C. D. AD第11頁/共76頁第十二頁,共76頁。二、簡答題(5小題,共30分,每個(gè)6分)1.對于文法GS:S aAbB A c | AcB d | dB請畫出句型aAcbdd的語法樹,并求出該句型的所有短語(duny)、簡單短語(duny)和句柄。第12頁/共76頁第十三頁,共76頁。 2. 2.棵簡單子樹的葉組成簡單短語。棵簡單子樹的葉組成簡單短語。 3. 3.最左簡單子樹的葉組
8、成句柄。最左簡單子樹的葉組成句柄。第13頁/共76頁第十四頁,共76頁。GS:S aAbB A c | AcB d | dB 句型句型(j xn)aAcbddSaAbBAcdBdaAcbddAcddd短語短語(duny):簡單簡單(jindn)短語:短語:Acd 句柄:句柄:Ac第14頁/共76頁第十五頁,共76頁。二、二、2.寫出類型寫出類型Grade07的內(nèi)部表示,其中每個(gè)的內(nèi)部表示,其中每個(gè)int、char類型數(shù)類型數(shù)據(jù)各占據(jù)各占1個(gè)內(nèi)存?zhèn)€內(nèi)存(ni cn)單元。單元。typedef struct char name20; int num;student;typedef student
9、Grade07400;第15頁/共76頁第十六頁,共76頁。ElemTypeSizeKindSubSizeArrayTyLow Up其中各個(gè)域的含義如下:其中各個(gè)域的含義如下:Size表示數(shù)組類型所占空間的大小,是數(shù)組所有成分?jǐn)?shù)據(jù)表示數(shù)組類型所占空間的大小,是數(shù)組所有成分?jǐn)?shù)據(jù)占用空間的和,需要占用空間的和,需要(xyo)通過計(jì)算得到,通過計(jì)算得到,Size = (Up-Low+1)*sizeof(ElemType), 其中其中sizeof是一個(gè)輔助函數(shù),用是一個(gè)輔助函數(shù),用于計(jì)算每種類型的于計(jì)算每種類型的size;Kind = arrayTy, 表示是數(shù)組類型;表示是數(shù)組類型;Low表示數(shù)組下
10、標(biāo)的下界,在表示數(shù)組下標(biāo)的下界,在C語言中語言中Low = 0;Up表示數(shù)組下標(biāo)的上界;表示數(shù)組下標(biāo)的上界;ElemType 表示數(shù)組成分類型的內(nèi)部表示指針。表示數(shù)組成分類型的內(nèi)部表示指針。 數(shù)組類型數(shù)組類型(lixng)(lixng):第16頁/共76頁第十七頁,共76頁。FieldListKindSize結(jié) 構(gòu) 體 與 共 用結(jié) 構(gòu) 體 與 共 用 ( n ( n yn)yn)體類型體類型其中各個(gè)域的含義如下:其中各個(gè)域的含義如下:Size表示該類型數(shù)據(jù)所占空間的大小,結(jié)構(gòu)體是所有域表示該類型數(shù)據(jù)所占空間的大小,結(jié)構(gòu)體是所有域占用空間的和,共用占用空間的和,共用(n yn)體類型則是所有域
11、中占體類型則是所有域中占用空間的最大者的值。用空間的最大者的值。Kind = structTy, 表示是結(jié)構(gòu)體或共用表示是結(jié)構(gòu)體或共用(n yn)體類體類型;型;FieldList 是域名表的表頭指針。是域名表的表頭指針。第17頁/共76頁第十八頁,共76頁。其中各個(gè)域的含義如下:其中各個(gè)域的含義如下:Name表示標(biāo)識(shí)符的名字;表示標(biāo)識(shí)符的名字;Type = TypePtr,TypePtr是域名是域名(y mn)標(biāo)識(shí)符類型的標(biāo)識(shí)符類型的內(nèi)部表示指針;內(nèi)部表示指針;Off表示域名表示域名(y mn)標(biāo)識(shí)符相對于記錄類型分配的內(nèi)存塊標(biāo)識(shí)符相對于記錄類型分配的內(nèi)存塊起始地址的偏移量,對于聯(lián)合類型而言
12、,所有的域名起始地址的偏移量,對于聯(lián)合類型而言,所有的域名(y mn)標(biāo)識(shí)符的起始偏移都是相同的,所以可以省略;標(biāo)識(shí)符的起始偏移都是相同的,所以可以省略;OffTypeName域名標(biāo)識(shí)符的內(nèi)部表示域名標(biāo)識(shí)符的內(nèi)部表示(biosh)如下:如下: 結(jié)構(gòu)體與共用體類型結(jié)構(gòu)體與共用體類型(lixng)-(lixng)-域域名表名表第18頁/共76頁第十九頁,共76頁。charPtr 20 ArrayTy 019typedef struct char name20; int num;student;typedef student Grade07400;structTy0name20intPtrnum A
13、rrayTy0399840021第19頁/共76頁第二十頁,共76頁。第20頁/共76頁第二十一頁,共76頁。 Predict(A ) First( ) 當(dāng)當(dāng) First( ) = First( )- Follow(A) 當(dāng)當(dāng) First( ) 第21頁/共76頁第二十二頁,共76頁。First(X)nStep2.形如形如:X a , a VT則則 : a First(X)第22頁/共76頁第二十三頁,共76頁。第23頁/共76頁第二十四頁,共76頁。第24頁/共76頁第二十五頁,共76頁。第25頁/共76頁第二十六頁,共76頁。lPredict(A ) First( ) ,當(dāng),當(dāng)First(
14、 )不含不含 = First( )- Follow(A) ,當(dāng),當(dāng)First( )含含第26頁/共76頁第二十七頁,共76頁。n其 中其 中 P 表 示 所 有 產(chǎn) 生表 示 所 有 產(chǎn) 生(chnshng)式的集合。式的集合。第27頁/共76頁第二十八頁,共76頁。error。第28頁/共76頁第二十九頁,共76頁。文法(wnf)GA的LL(1)分析表。A aABe 1 | Bc 2B dB 3 | 4文法符號(hào)文法符號(hào)First集集Follow集集AB#,d, e,c(1)求每個(gè)產(chǎn)生)求每個(gè)產(chǎn)生(chnshng)式的式的Predict集:集:Predict( A aABe )= aPredi
15、ct( A Bc )= d,cPredict( B dB )= dPredict( B )= c,ee a ,d ,d ,c第29頁/共76頁第三十頁,共76頁。acde#AB每個(gè)產(chǎn)生每個(gè)產(chǎn)生(chnshng)式的式的Predict集:集:Predict( A aABe 1 )= aPredict( A Bc 2 )= d,cPredict( B dB 3 )= dPredict( B 4 )= c,eA aABeA BcA BcB dBB B acde#A122B434第30頁/共76頁第三十一頁,共76頁。二、二、4. 過程活動(dòng)記錄過程活動(dòng)記錄(AR)一般應(yīng)包含一般應(yīng)包含(bohn)哪些信
16、息?哪些信息?答:答:動(dòng)態(tài)鏈指針動(dòng)態(tài)鏈指針;返回地址返回地址(dzh);返回值返回值;過程層數(shù)過程層數(shù);size;寄存器狀態(tài);寄存器狀態(tài);變量訪問環(huán)境變量訪問環(huán)境;形參形參;局部變量局部變量;臨時(shí)變量臨時(shí)變量.第31頁/共76頁第三十二頁,共76頁。二、二、5. 假定當(dāng)前假定當(dāng)前(dngqin)函數(shù)的層數(shù)為函數(shù)的層數(shù)為L,偏移量是,偏移量是off,每個(gè)函數(shù)的局部數(shù)據(jù)區(qū)的起始偏移為,每個(gè)函數(shù)的局部數(shù)據(jù)區(qū)的起始偏移為InitOff,每個(gè)每個(gè)int類型數(shù)據(jù)占類型數(shù)據(jù)占1個(gè)單元。請給出個(gè)單元。請給出A至至F位置的層位置的層數(shù)和偏移量信息。數(shù)和偏移量信息。(L,offL,off)int time = 1
17、00;int time = 100;A Aint fac(int fac(B B int x) int x)C Cif (x0) return -1;if (x0) return -1;if (x = 0)| (x = 1) return 1;if (x = 0)| (x = 1) return 1;else return xelse return x* *fac(x-1);fac(x-1); D Dvoid main()void main()int i = 1;int i = 1;E Ewhile (i=time)while (i=time)fac(i);fac(i);i+;i+; F F第
18、32頁/共76頁第三十三頁,共76頁。第33頁/共76頁第三十四頁,共76頁。II.處理完函數(shù)首部處理完函數(shù)首部:處理前可用的處理前可用的 處理內(nèi)容處理內(nèi)容 處理后可用的處理后可用的抽象抽象(chuxing)地址地址 抽象抽象(chuxing)地址地址(,off) Proc p() (+1,off1)(,off) Func f():T (+1,off1)(,off) Proc P() (,off+2)(,off) Func F():T (,off+2)第34頁/共76頁第三十五頁,共76頁。第35頁/共76頁第三十六頁,共76頁。(L,offL,off)int time = 100;int t
19、ime = 100;A Aint fac(int fac(B B int x) int x)C Cif (x0) return -1;if (x0) return -1;if (x = 0)| (x = 1) return 1;if (x = 0)| (x = 1) return 1;else return xelse return x* *fac(x-1);fac(x-1); D Dvoid main()void main()int i = 1;int i = 1;E Ewhile (i=time)while (i+AA=+A,則稱,則稱A A是左遞歸的。是左遞歸的。v對文法中的某個(gè)對文法中
20、的某個(gè)(mu )(mu )非終極符非終極符A A,若有:,若有:A=+ A A=+ A ,則稱,則稱A A是右遞歸的。是右遞歸的。v對文法中的某個(gè)對文法中的某個(gè)(mu )(mu )非終極符非終極符A A,若有:,若有:A=+ A A=+ A ,則稱,則稱A A是遞歸的。是遞歸的。第55頁/共76頁第五十六頁,共76頁。v左遞歸情形,一定使得左遞歸情形,一定使得(sh de)自頂向下的語法分析分析自頂向下的語法分析分析條件不成立。條件不成立。 v消除直接左遞歸的簡單情形:消除直接左遞歸的簡單情形:v A A | v即有即有A=(至少有一個(gè)(至少有一個(gè))??捎孟旅娣侵苯幼螅???捎孟旅娣侵苯幼筮f歸的
21、產(chǎn)生式定義:遞歸的產(chǎn)生式定義:vA AvA A | 文法等價(jià)文法等價(jià)(dngji)(dngji)變換技術(shù)變換技術(shù): :消除直接左遞歸(消除直接左遞歸(續(xù)續(xù)1 1) 第56頁/共76頁第五十七頁,共76頁。(2)去除)去除(q ch)左遞歸:左遞歸:A bA 4A aA 5 | 6S aS 1S SAb 2 | 3A Aa | bS aS 1S SAb 2 | 3A bA 4A aA 5 | 6第57頁/共76頁第五十八頁,共76頁。文法符號(hào)First集Follow集S a S a, A b A a, #,bbb,b(3)求每個(gè)產(chǎn)生)求每個(gè)產(chǎn)生(chnshng)式的式的Predict集:集:Pr
22、edict(S aS)= aPredict(S SAb)= aPredict(S )= b,#Predict(A bA)= bPredict(A aA)= aPredict(A )= b S aS 1S SAb 2 | 3A bA 4A aA 5 | 6第58頁/共76頁第五十九頁,共76頁。第59頁/共76頁第六十頁,共76頁。第60頁/共76頁第六十一頁,共76頁。語法分析主程序:語法分析主程序:Begin ReadToken; S ; Match(#) end第61頁/共76頁第六十二頁,共76頁。終極符產(chǎn)生匹配命令,而非終極符則產(chǎn)生調(diào)用命終極符產(chǎn)生匹配命令,而非終極符則產(chǎn)生調(diào)用命令。因
23、為文法令。因?yàn)槲姆?wnf)遞歸相應(yīng)子程序也遞歸,遞歸相應(yīng)子程序也遞歸,所以稱這種方法為遞歸子程序方法或遞歸下降法所以稱這種方法為遞歸子程序方法或遞歸下降法。其中其中(qzhng)(qzhng):令:令i=X0X1X2Xni=X0X1X2Xn,則:,則: ( (i) = i) = (X0); (X0); (X1); (X1); (X2); ; (X2); ; (Xn);(Xn); 如果如果X XVNVN,(X)= X (X)= X 如果如果X XVTVT,(X)= Match(X) (X)= Match(X) 如果如果X= X= , , ( () = skip() = skip(空語句空語句)
24、 )第62頁/共76頁第六十三頁,共76頁。(4)各個(gè))各個(gè)(gg)遞歸子程序如下:遞歸子程序如下:S( ) if (ch = a) match(a); S(); else error( );S( ) if (ch =a) S( );A( );match(b); else if (ch = b or #) ; else error( );A( ) if (ch = b) match(b); A( ); else error( );A( ) if (ch = a) match(a); A( ); else if (ch = b); else error( );Predict(S aS )= aP
25、redict(S SAb)= aPredict(S )= b,#Predict(A bA)= bPredict(A aA)= aPredict(A )= bmain ( ) ReadToken; S ; Match(#) ;第63頁/共76頁第六十四頁,共76頁。第64頁/共76頁第六十五頁,共76頁。WhileWhile語句語句(yj)(yj)的中間代碼的中間代碼結(jié)構(gòu):結(jié)構(gòu): ( WHILE ,-,-,- ) ( WHILE ,-,-,- ) E E 的中間代碼的中間代碼( DO ,E.FORM ,-,-)( DO ,E.FORM ,-,-) S S的中間代碼的中間代碼(ENDWHILE ,
26、-,-,- )(ENDWHILE ,-,-,- )if E then S1 else S2if E then S1 else S2中間代碼結(jié)構(gòu)中間代碼結(jié)構(gòu)(jigu):(jigu): E E 的中間代碼的中間代碼( THEN , E.FORM , , )( THEN , E.FORM , , )S1 S1 的中間代碼的中間代碼(ELSE , , , )(ELSE , , , )S2 S2 的中間代碼的中間代碼(ENDIF , , , ) (ENDIF , , , ) 第65頁/共76頁第六十六頁,共76頁。第66頁/共76頁第六十七頁,共76頁。第67頁/共76頁第六十八頁,共76頁。(ASS
27、IG, 100, 1, time)(Entry, Lfac, , 0)(LT, x, 0, t1)(THEN, t1,_,_)(RETURN, _, _, -1)(ENDIF, _, _, _)(EQ, x, 0, t2)(THEN, t2, _, _)(RETURN, _, _, 1)(ENDIF, _, _, _)(EQ, x, 1, t3)(THEN, t3, -,-)(RETURN, _, _, 1)( ELSE, _, _, _)int time = 100;int fac(int x)if (x0) return -1;if (x = 0) return 1;if (x = 1) return 1;else return x*fac(x-1); (SUBI, x, 1, t4)(ValAct, t4, initoff, 1)(CALL, Lfac,true,t5)(MULTI, x, t5, t6)(RETURN, _, _, t
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 醫(yī)護(hù)工作服采購合同
- 維修保養(yǎng)合同范本:機(jī)械設(shè)施
- 高級(jí)顧問聘用合同
- 合伙協(xié)議合同簡化版范本
- 酒店投資合作合同范本
- 化學(xué)品運(yùn)輸服務(wù)承包合同
- 私人裝修合同協(xié)議書范本
- 企業(yè)設(shè)備抵押融資合同樣本
- 寵物臨時(shí)寄養(yǎng)服務(wù)合同范本
- 合同簽約盛宴:五十二條經(jīng)典致辭美句鑒賞
- 腹水形成的原因及治療
- 單晶爐車間安全培訓(xùn)
- 高中地理必修第一冊期末試卷及答案-中圖版-2024-2025學(xué)年
- 護(hù)理核心制度測試題+參考答案
- 機(jī)械制造技術(shù)基礎(chǔ)(課程課件完整版)
- 《2023版CSCO卵巢癌診療指南》解讀課件
- 《預(yù)防未成年人犯罪》課件(圖文)
- 【醫(yī)院藥品管理系統(tǒng)探析與設(shè)計(jì)(論文)10000字】
- 螺旋體病梅毒課件
- 2024年咸寧市引進(jìn)人才44名歷年高頻難、易錯(cuò)點(diǎn)500題模擬試題附帶答案詳解
- (小學(xué)組)全國版圖知識(shí)競賽考試題含答案
評(píng)論
0/150
提交評(píng)論