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

1、2021/3/1712021/3/172選擇題（10小題,共20分,每題2分）1.編譯程序必須完成的工作有 。詞法分析 語法分析語義分析中間代碼生成中間代碼優(yōu)化目標(biāo)代碼生成A. B. C. D. 2.下列關(guān)于編譯和解釋的說法,正確的是 。解釋方式和編譯方式的區(qū)別在于解釋程序?qū)υ闯绦虿]有進(jìn)行真正翻譯。編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。解釋程序和編譯程序都是語言處理程序。與編譯系統(tǒng)相比，解釋系統(tǒng)比較簡單，可移植性好，執(zhí)行速度慢。編譯程序是將高級語言程序翻譯成匯編語言程序或機(jī)器語言程序解釋程序是將匯編語言程序翻譯成機(jī)器語言程序A.B. C. D.CD2021/3/1733. 這樣一

2、些語言,它們能被確定有限自動機(jī)識別,但不能用正則表達(dá)式表示。A存在 B.不存在 C.無法判定是否存在4.已知文法GS:S SaS | SbS | ScS | dSe | f,下列句型中, 是規(guī)范句型。AfafbS B.faSbS C.SaSbf. D.faS BCSaSSSbSffSaSSSbSfSaSSS b SSaSSff2021/3/1745.下列文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) B.句型句型:( ) ( )(SSS)S(SS)SA(SS

3、S)S(SS)S2021/3/1755.下列文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) C.句型句型:ababSSbSaSbSaSSbSaSaSbA2021/3/1765.下列文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)D.句型句型:a+a*S + SS S * a a S *SS + SaaA2021/3/1776

4、.后綴表達(dá)式ab+c*de*+ 的中綴形式是 。Aa*(b+c)+d*eB(a+b)*c+d*eCa+b*c*d+eDa+b*c+d*e B2021/3/178后綴式后綴式(逆波蘭式逆波蘭式 )n例例:pos(A*B+C*D)=AB*CD*+n逆波蘭式的特點(diǎn)逆波蘭式的特點(diǎn):逆波蘭式中的變量的次序與中綴式中的變逆波蘭式中的變量的次序與中綴式中的變量的次序完全一致。量的次序完全一致。逆波蘭式中無括號。逆波蘭式中無括號。逆波蘭式中的運(yùn)算符已按計(jì)算順序排列。逆波蘭式中的運(yùn)算符已按計(jì)算順序排列。2021/3/1797.合并無沖突的合并無沖突的LR（1）狀態(tài)機(jī)得到的）狀態(tài)機(jī)得到的LALR（1）狀態(tài)機(jī)中一定

5、不會出現(xiàn)）狀態(tài)機(jī)中一定不會出現(xiàn) 沖突。沖突。A. 移入移入/移入沖突移入沖突B. 移入移入/歸約沖突歸約沖突C. 歸約歸約/歸約沖突歸約沖突 B2021/3/1710例如例如,假定假定Si、Sj是某一是某一LR(1)狀態(tài)機(jī)的兩個(gè)狀態(tài)狀態(tài)機(jī)的兩個(gè)狀態(tài),其中其中,u1、u2、v1、v2、t1、t2分別為歸約展望符集分別為歸約展望符集 , a VT。 在在Si中有中有: u1 v1=、u1 a=、v1 a=;在在Sj中有中有: u2 v2=、u2 a=、v2 a=。顯然顯然Si和和Sj是同心狀態(tài)，合并后得到新狀態(tài)是同心狀態(tài)，合并后得到新狀態(tài)Sij :ABCau1v1t1SiABCau2v2t2SjA

6、BCau1 u2v1 v2 t1 t2Si因因:(u1 u2 ) a=(v1 v2 ) a=所以不可能產(chǎn)生移所以不可能產(chǎn)生移入入歸約沖突。歸約沖突。因因:(u1 u2 ) (v1 v2 ) =?所以可能產(chǎn)生歸約所以可能產(chǎn)生歸約歸歸約沖突。約沖突。2021/3/17118.編譯程序使用 區(qū)別標(biāo)識符的作用域。A.聲明標(biāo)識符的過程或函數(shù)名B. 聲明標(biāo)識符的過程或函數(shù)的靜態(tài)層數(shù)C.聲明標(biāo)識符的過程或函數(shù)的動態(tài)層數(shù)D.標(biāo)識符的行號 B2021/3/17129.適合采用靜態(tài)存儲分配策略的程序設(shè)計(jì)語言的限制有適合采用靜態(tài)存儲分配策略的程序設(shè)計(jì)語言的限制有 。 數(shù)據(jù)實(shí)體所需空間在編譯時(shí)能確定數(shù)據(jù)實(shí)體所需空間在

7、編譯時(shí)能確定 過程調(diào)用不允許遞歸過程調(diào)用不允許遞歸 不能動態(tài)建立數(shù)據(jù)實(shí)體不能動態(tài)建立數(shù)據(jù)實(shí)體 運(yùn)行時(shí)每個(gè)數(shù)據(jù)對象只能有一個(gè)實(shí)例運(yùn)行時(shí)每個(gè)數(shù)據(jù)對象只能有一個(gè)實(shí)例 數(shù)組的上下界是常量數(shù)組的上下界是常量A. B.C. D.10.目標(biāo)代碼生成器的輸出可以是目標(biāo)代碼生成器的輸出可以是 。絕對機(jī)器代碼絕對機(jī)器代碼可重定位機(jī)器代碼可重定位機(jī)器代碼匯編代碼匯編代碼 虛擬機(jī)代碼虛擬機(jī)代碼抽象語法樹抽象語法樹三地址代碼三地址代碼AB. C. D. AD2021/3/1713二、簡答題（5小題小題,共共30分分,每個(gè)每個(gè)6分）分）1.對于文法對于文法GS:S aAbB A c | AcB d | dB請畫出句型請畫

8、出句型aAcbdd的語法樹的語法樹,并求出該句并求出該句型的所有短語、簡單短語和句柄。型的所有短語、簡單短語和句柄。2021/3/1714定義定義1 1: :由某一結(jié)點(diǎn)及其所有分支組成的部分樹由某一結(jié)點(diǎn)及其所有分支組成的部分樹稱為原樹的一棵子樹。稱為原樹的一棵子樹。定義定義2 2: :只有單層分支的子樹稱為簡單子樹。只有單層分支的子樹稱為簡單子樹。定義定義3 3: :最左簡單子樹的葉稱為句柄。最左簡單子樹的葉稱為句柄。定理：定理： 1.1.每個(gè)句型都有一棵語法樹每個(gè)句型都有一棵語法樹, ,每個(gè)語法樹每個(gè)語法樹的葉組成該句型。的葉組成該句型。 2.2.每棵子樹的葉組成短語每棵子樹的葉組成短語,

9、,每棵簡單子樹每棵簡單子樹的葉組成簡單短語。的葉組成簡單短語。 3.3.最左簡單子樹的葉組成句柄。最左簡單子樹的葉組成句柄。2021/3/1715GS:S aAbB A c | AcB d | dB 句型句型aAcbddSaAbBAcdBdaAcbddAcddd短語短語:簡單短語簡單短語:Acd 句柄句柄:Ac2021/3/1716二、二、2.寫出類型寫出類型Grade07的內(nèi)部表示的內(nèi)部表示,其中每個(gè)其中每個(gè)int、char類型類型數(shù)據(jù)各占數(shù)據(jù)各占1個(gè)內(nèi)存單元。個(gè)內(nèi)存單元。typedef struct char name20; int num;student;typedef student

10、Grade07400;2021/3/1717ElemTypeSizeKindSubSizeArrayTyLow Up其中各個(gè)域的含義如下其中各個(gè)域的含義如下:ZSize表示數(shù)組類型所占空間的大小表示數(shù)組類型所占空間的大小,是數(shù)組所有成分?jǐn)?shù)據(jù)是數(shù)組所有成分?jǐn)?shù)據(jù)占用空間的和占用空間的和,需要通過計(jì)算得到需要通過計(jì)算得到,Size = (Up-Low+1)*sizeof(ElemType), 其中其中sizeof是一個(gè)輔助函數(shù)是一個(gè)輔助函數(shù)，用于計(jì)算每種類型的，用于計(jì)算每種類型的size;ZKind = arrayTy, 表示是數(shù)組類型表示是數(shù)組類型;ZLow表示數(shù)組下標(biāo)的下界，在表示數(shù)組下標(biāo)的下界

11、，在C語言中語言中Low = 0;ZUp表示數(shù)組下標(biāo)的上界；表示數(shù)組下標(biāo)的上界；ZElemType 表示數(shù)組成分類型的內(nèi)部表示指針。表示數(shù)組成分類型的內(nèi)部表示指針。 數(shù)組類型數(shù)組類型: :2021/3/1718FieldListKindSize結(jié)構(gòu)體與共用體類型結(jié)構(gòu)體與共用體類型其中各個(gè)域的含義如下其中各個(gè)域的含義如下:Size表示該類型數(shù)據(jù)所占空間的大小表示該類型數(shù)據(jù)所占空間的大小,結(jié)構(gòu)體是所有域占結(jié)構(gòu)體是所有域占用空間的和用空間的和,共用體類型則是所有域中占用空間的最大者共用體類型則是所有域中占用空間的最大者的值。的值。Kind = structTy, 表示是結(jié)構(gòu)體或共用體類型表示是結(jié)構(gòu)體

12、或共用體類型;FieldList 是域名表的表頭指針。是域名表的表頭指針。2021/3/1719其中各個(gè)域的含義如下其中各個(gè)域的含義如下:Name表示標(biāo)識符的名字表示標(biāo)識符的名字;Type = TypePtr,TypePtr是域名標(biāo)識符類型的內(nèi)部表是域名標(biāo)識符類型的內(nèi)部表示指針示指針;Off表示域名標(biāo)識符相對于記錄類型分配的內(nèi)存塊起始表示域名標(biāo)識符相對于記錄類型分配的內(nèi)存塊起始地址的偏移量地址的偏移量,對于聯(lián)合類型而言對于聯(lián)合類型而言,所有的域名標(biāo)識符的起所有的域名標(biāo)識符的起始偏移都是相同的，所以可以省略始偏移都是相同的，所以可以省略;OffTypeName域名標(biāo)識符的內(nèi)部表示如下域名標(biāo)識符的

13、內(nèi)部表示如下: 結(jié)構(gòu)體與共用體類型結(jié)構(gòu)體與共用體類型-域名表域名表2021/3/1720charPtr 20 ArrayTy 019typedef struct char name20; int num;student;typedef student Grade07400;structTy0name20intPtrnum ArrayTy03998400212021/3/1721二、3. 請給出下面文法GA的LL(1)分析表。A aABe 1 | Bc 2B dB 3 | 42021/3/1722vFirst集集 First( ) = a VT | * a. (if * then else )

14、vFollow集集 Follow(A) = a VT | S+ .Aa. (if S*.A then # # else )vPredict集集(Select集集) Predict(A ) First( ) 當(dāng)當(dāng) First( ) = First( )- Follow(A) 當(dāng)當(dāng) First( ) 2021/3/1723v 若若X VT : First(X)=Xv若若X VN : 對每一個(gè)產(chǎn)生式進(jìn)行如下處理對每一個(gè)產(chǎn)生式進(jìn)行如下處理:uStep1.形如形如: X , 則則: First(X)uStep2.形如形如:X a , a VT則則 : a First(X)2021/3/1724uStep

15、3.對對每一個(gè)形如下的產(chǎn)生式每一個(gè)形如下的產(chǎn)生式: XY1Y2Yi-1YiYn若若:Y1,Y2, ,Yi VN且且Y1,Y2, ,Yi-1* 則則: First(Y1)- , First(Y2)- , , First(Yi-1)- , First(Yi)都包含在都包含在First(X)中。中。若若: Yi VN且且Yi * (i=1,2,n), 則則: First(Y1) , First(Y2), , First(Yn) 都包含在都包含在First(X)中。中。重復(fù)重復(fù)Step3 ,直至對所有直至對所有A VN,First(A)收斂為止。收斂為止。2021/3/1725若符號串若符號串 =X1

16、X2Xn,v當(dāng)當(dāng)X1,X2, , Xi-1* ,Xi 不能不能 * ,則則: First( )= 1i-1(First(Xj)- ) First(Xi)v若所有若所有Xi 都能都能* ，則則: First( )= 1n First(Xj)2021/3/17261: 對所有對所有A VN 且且 A非非開始符開始符 : 令令Follow(A):= ; 對開始符對開始符 S : 令令Follow(S)= # # ; 2: 若有產(chǎn)生式若有產(chǎn)生式AxBy: 如果如果 First(y) 則則: Follow(B) = Follow(B) (First(y) Follow(A) 否則否則: Follow(B

17、)= Follow(B) First(y) 3: 重復(fù)重復(fù)2和和3,直至對所有直至對所有A VN,Follow(A)收收 斂為止。斂為止。2021/3/1727lPredict(A ) First( ) ,當(dāng)當(dāng)First( )不含不含 = First( )- Follow(A) , ,當(dāng)當(dāng)First( )含含2021/3/1728vLL(1)分析表的定義分析表的定義: T T: :V VN N V VT T P P Error Error T(A,t)=AT(A,t)=A 若若t t Predict( APredict( A ) ) T(A,t)=Error T(A,t)=Error 否則否則

18、 其中其中P表示所有產(chǎn)生式的集合。表示所有產(chǎn)生式的集合。2021/3/1729vLL(1)分析表的構(gòu)造方法分析表的構(gòu)造方法:對文法的每一個(gè)產(chǎn)生式求其對文法的每一個(gè)產(chǎn)生式求其predict集集;對文法的每一個(gè)產(chǎn)生式對文法的每一個(gè)產(chǎn)生式AA 進(jìn)行如下進(jìn)行如下處理處理: Predict( APredict( A )= )=（a a1 1,a,a2 2,.,a,.,an n);); 則令則令: : T(A,aT(A,ai i)=A)=A ,i=1,2,3,n ,i=1,2,3,n LL(1)分析表的其它元素為分析表的其它元素為error。2021/3/1730文法GA的LL(1)分析表。A aABe

19、1 | Bc 2B dB 3 | 4 #,d, e,c（1）求每個(gè)產(chǎn)生式的）求每個(gè)產(chǎn)生式的Predict集集:Predict（ A aABe ）= aPredict（ A Bc ）= d,cPredict（ B dB ）= dPredict（ B ）= c,ee a ,d ,d ,c2021/3/1731每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式的Predict集集:Predict（ A aABe 11 ）= aPredict（ A Bc 22 ）= d,cPredict（ B dB 33 ）= dPredict（ B 44 ）= c,eA aABeA BcA BcB dBB B 2021/3/1732二、二、4

20、. 過程活動記錄過程活動記錄(AR)一般應(yīng)包含哪些信息一般應(yīng)包含哪些信息?答答:動態(tài)鏈指針動態(tài)鏈指針;返回地址返回地址;返回值返回值;過程層數(shù)過程層數(shù);size;寄存器狀態(tài)寄存器狀態(tài);變量訪問環(huán)境變量訪問環(huán)境;形參形參;局部變量局部變量;臨時(shí)變量臨時(shí)變量.2021/3/1733二、二、5. 假定當(dāng)前函數(shù)的層數(shù)為假定當(dāng)前函數(shù)的層數(shù)為L,偏移量是偏移量是off,每個(gè)函數(shù)的每個(gè)函數(shù)的局部數(shù)據(jù)區(qū)的起始偏移為局部數(shù)據(jù)區(qū)的起始偏移為InitOff,每個(gè)每個(gè)int類型數(shù)據(jù)占類型數(shù)據(jù)占1個(gè)單元。請給出個(gè)單元。請給出A至至F位置的層數(shù)和偏移量信息。位置的層數(shù)和偏移量信息。（L,offL,off）int time

21、 = 100;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+;

22、F F2021/3/1734I.I.處理聲明部分處理聲明部分: :處理前可用的處理前可用的 處理內(nèi)容處理內(nèi)容 處理后可用的處理后可用的抽象地址抽象地址 抽象地址抽象地址（, ,offoff） LabelDec LabelDec （, ,offoff） （, ,offoff） ConstDec ConstDec （，offoff）（，offoff） TypeDec TypeDec （，offoff） （，offoff） Var id:T Var id:T （，off+noff+nT T）（，offoff） ProcDec ProcDec （，offoff） （，offoff） FuncDec F

23、uncDec （，offoff）2021/3/1735II.處理完函數(shù)首部處理完函數(shù)首部:處理前可用的處理前可用的 處理內(nèi)容處理內(nèi)容 處理后可用的處理后可用的抽象地址抽象地址 抽象地址抽象地址(,off） Proc p() （+1,off1）(,off） Func f():T （+1，off1）(，off） Proc P() （，off+2）(，off） Func F():T （，off+2）2021/3/1736III. III. 處理形式參數(shù)處理形式參數(shù): :( (, ,offoff） Var ID:T Var ID:T （, ,off+1off+1）( (, ,offoff） ID:T

24、ID:T （， off+ noff+ nT T ）IV.IV.處理過程名及左括號之后處理過程名及左括號之后: : ( (，offoff） Proc p( Proc p( （+1+1，offoff0 0）( (，offoff） Func f( Func f( （+1+1，offoff0 0）( (，offoff） Proc P( Proc P( （+1+1，offoff0 0）( (，offoff） Fucn F( Fucn F( （+1+1，offoff0 0）注注: :小寫字母的標(biāo)識符表示實(shí)在標(biāo)識符，大寫字母的標(biāo)識符則表示形參小寫字母的標(biāo)識符表示實(shí)在標(biāo)識符，大寫字母的標(biāo)識符則表示形參標(biāo)識符。

25、標(biāo)識符。n nT T 表示類型表示類型T T的長度，的長度，offoff1 1表示處理完形參部分（實(shí)在過程表示處理完形參部分（實(shí)在過程首部）時(shí)的偏移值，首部）時(shí)的偏移值，offoff0 0表示形參的開始偏移量。表示形參的開始偏移量。 2021/3/1737（L,offL,off）int time = 100;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

26、 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+A，則，則稱稱A是是左遞歸的左遞歸的。 對文法中的某個(gè)非終極符對文法中的某個(gè)非終極符A，若有：，若有：A=+ A ，則，則稱稱A是是右遞歸的右遞歸的。 對文法中的某個(gè)非終極符對文法中的某個(gè)非終極符A，若有：，若有：A=+ A ，則稱則稱A是是遞歸的遞歸的。2021/3/1757v左遞歸情形左遞歸情形,一定使得自頂向下的語法分析分析條一定使得自頂向下的語法

27、分析分析條件不成立。件不成立。 v消除直接左遞歸的簡單情形消除直接左遞歸的簡單情形: A A | 即有即有A=（至少有一個(gè)（至少有一個(gè)）?？捎孟旅娣牵?。可用下面非直接左遞歸的產(chǎn)生式定義直接左遞歸的產(chǎn)生式定義:A AA A | 2021/3/1758（2）去除左遞歸）去除左遞歸:A bA 4A aA 5 | 6S aS 1S SAb 2 | 3A Aa | bS aS 1S SAb 2 | 3A bA 4A aA 5 | 62021/3/1759#,bbb,b（3）求每個(gè)產(chǎn)生式的）求每個(gè)產(chǎn)生式的Predict集集:Predict（S aS）= aPredict（S SAb）= aPredict（

28、S ）= b,#Predict（A bA）= bPredict（A aA）= aPredict（A ）= b S aS 1S SAb 2 | 3A bA 4A aA 5 | 62021/3/1760v遞歸下降法遞歸下降法(Recur(Recursive-Descent Parsing)-Descent Parsing) 對對每個(gè)非終極符每個(gè)非終極符構(gòu)造相應(yīng)的一個(gè)子程構(gòu)造相應(yīng)的一個(gè)子程序序( (稱為語法分析子程序稱為語法分析子程序) ), ,其功能是識別、其功能是識別、分析該分析該非終極符所能推導(dǎo)出的字符串。非終極符所能推導(dǎo)出的字符串。 2021/3/1761一、遞歸下降法語法分析程序的構(gòu)造一、

29、遞歸下降法語法分析程序的構(gòu)造引進(jìn)下面兩個(gè)基本動作引進(jìn)下面兩個(gè)基本動作: vReadToken:從輸入流把下一個(gè)從輸入流把下一個(gè)TOKEN碼碼讀到變量讀到變量token中。中。vMatch(a):檢查檢查token=a? 若是若是,則執(zhí)行則執(zhí)行ReadToken,否則報(bào)錯(cuò)并作相應(yīng)的處理。否則報(bào)錯(cuò)并作相應(yīng)的處理。其中其中a是終極符。是終極符。2021/3/1762v 對每一個(gè)非終極符對每一個(gè)非終極符A構(gòu)造構(gòu)造子程子程: : 當(dāng)產(chǎn)生式中形如當(dāng)產(chǎn)生式中形如: A : A 1 1| | 2 2| | | | n n 則按下面的方法編寫子程序則按下面的方法編寫子程序A A: : procedure A(

30、)procedure A( ) begin begin if token if token Predict(APredict(A1 1) then ) then ( ( 1 1) else) else if token if token Predict(APredict(A2 2) then ) then ( ( 2 2) else) else if token if token Predict(APredict(An) then n) then ( ( n n) else) else err( ) err( ) end end 語法分析主程序語法分析主程序:Begin ReadToken;

31、S ; Match(#) end2021/3/1763終極符產(chǎn)生匹配命令終極符產(chǎn)生匹配命令,而非終極符則產(chǎn)生調(diào)用命令。而非終極符則產(chǎn)生調(diào)用命令。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸,所以稱這種方法所以稱這種方法為遞歸子程序方法或遞歸下降法。為遞歸子程序方法或遞歸下降法。其中其中: :令令 i=X0X1X2Xn,則則: ( i) = (X0); (X1); (X2); ; (Xn); 如果如果X V VN N, , (X)= X 如果如果X V VT T, , (X)= Match(X) 如果如果X= , ( ) = skip(空語句空語句)2021/3/1764（4）各個(gè)遞

32、歸子程序如下）各個(gè)遞歸子程序如下: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 ）= aPredict（S SAb）= aPredict（S ）= b,#P

33、redict（A bA）= bPredict（A aA）= aPredict（A ）= bmain ( ) ReadToken; S ; Match(#) ;2021/3/1765v五、給出如下程序段的四元式序列五、給出如下程序段的四元式序列:（14分）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); void main() int i = 1;while (i=time)fac(i);i+; 2021/3/1766Whil

34、eWhile語句的中間代碼結(jié)構(gòu)語句的中間代碼結(jié)構(gòu): : ( WHILE ,-,-,- )( WHILE ,-,-,- ) E E 的中間代碼的中間代碼( DO ,E.FORM ,-,-)( DO ,E.FORM ,-,-) S S的中間代碼的中間代碼(ENDWHILE ,-,-,- )(ENDWHILE ,-,-,- )if E then S1 else S2if E then S1 else S2中間代碼結(jié)構(gòu)中間代碼結(jié)構(gòu): : E E 的中間代碼的中間代碼( THEN , E.FORM , , )( THEN , E.FORM , , )S1 S1 的中間代碼的中間代碼(ELSE , , ,

35、 )(ELSE , , , )S2 S2 的中間代碼的中間代碼(ENDIF , , , (ENDIF , , , ) ) 2021/3/1767v對應(yīng)過程對應(yīng)過程函數(shù)聲明的中間代碼有函數(shù)聲明的中間代碼有: : ( ENTRY , Label ( ENTRY , LabelQ Q , Size , SizeQ Q , Level , LevelQ Q ) ) ( ENDPROC , , , ) ( ENDPROC , , , ) 或或 ( ENDFUNC , , , )( ENDFUNC , , , ) 其中其中: Label: LabelQ Q 是給過程是給過程Q Q分配的代碼入口標(biāo)號分配的代

36、碼入口標(biāo)號; ; SizeSizeQ Q 是過程是過程( (函數(shù)函數(shù))Q)Q的的ARAR空間大小空間大小, ,該空間暫時(shí)不包該空間暫時(shí)不包括臨時(shí)變量部分括臨時(shí)變量部分, ,此時(shí)此時(shí)SizeSizeQ Q實(shí)際是臨時(shí)變量的初始實(shí)際是臨時(shí)變量的初始Offset Offset , ,在代碼生成階段處理完臨時(shí)變量時(shí)才可完全確定在代碼生成階段處理完臨時(shí)變量時(shí)才可完全確定; ; LevelLevelQ Q是過程是過程Q Q的層數(shù)的層數(shù); ; ENTRYENTRY和和ENDPROCENDPROC（或（或ENDFUNCENDFUNC）分別表示子程序的入口）分別表示子程序的入口和出口。和出口。2021/3/176

37、8 E E1 1 的中間代碼的中間代碼.E En n 的中間代碼的中間代碼( VarACT / ValACT , t( VarACT / ValACT , t1 1 , Offset , Offset1 1 , Size , Size1 1 ) ).(VarACT / ValACT , t(VarACT / ValACT , tn n , Offset , Offsetn n , Size , Sizen n) )(CALL , (CALL , Labelf , true/false , , true/false , Result ) Result )2021/3/1769（ASSIG, 10

38、0, 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

39、 1;else return x*fac(x-1); （SUBI, x, 1, t4）（ValAct, t4, initoff, 1）（CALL, Lfac,true,t5）（MULTI, x, t5, t6）（RETURN, _, _, t6）（ENDIF, _, _, _）（ENDFUNC, _, _, _） InitOff+7或設(shè)第一個(gè)形參的區(qū)距為或設(shè)第一個(gè)形參的區(qū)距為IntOff。設(shè)每個(gè)函數(shù)的局部數(shù)據(jù)區(qū)的起始偏移為設(shè)每個(gè)函數(shù)的局部數(shù)據(jù)區(qū)的起始偏移為InitOff。2021/3/1770void main() int i = 1;while (i=time)fac(i);i+; （Ent

40、ry, Lmain, , 0）（ASSIG, 1, 1, i）（WHILE, _, _, _）（LE, i, time, t1）（DO, t1, _, _）（VALACT,i,initoff,1 ）（Call, Lfac, true, t2）（ADDI, i, 1, t3）（ASSIG, t3, 1, i）（ENDWHILE, _, _, _）（ENDFUNC, _, _, _）InitOff+42021/3/1771六、判斷下面文法是否是六、判斷下面文法是否是LR（1）文法）文法,并說明并說明理由。（理由。（12分）分）S Aa | bAc | Bc | bBaA dB d2021/3/1772vLR(1)LR(1)項(xiàng)目項(xiàng)目: :AA, a , a 。LR(0)LR(0)項(xiàng)目及一個(gè)項(xiàng)目及一個(gè)V VT T #的展望符的展望符。vIS:IS:LR(1)LR(1)項(xiàng)目集項(xiàng)目集vISIS(X)(X): : IS IS(X)(X) = A = A X X,a | A,a | AX X ,a,a IS IS 2021/3/1773v