北方工業(yè)大學編譯原理習題集

1、編譯原理課后習題(修訂版)第二章高級語言及其語法描述3、何謂“標識符”，何謂“名字”，兩者的區(qū)別是什么？解：標識符是高級語言中定義的字符串，一般是以英文字母(包括大小寫字母)或下劃線開頭的，由數(shù)字、字母和下劃線組成的一定長度的字符串，它只是一個標志，沒有其他含義。名字是用標識符表示的，但名字不僅僅是一個字符串,它還具有屬性和值。4、令+、*和T代表加、乘和乘幕，按如下的非標準優(yōu)先級和結合性質的約定,計算1+1*2T*1t2的值：(1)、優(yōu)先順序(從高至低)為十、*和個，同級優(yōu)先采用左結合。解：(1)、(2)、1+1*2T*11+1*2T*1(2)、優(yōu)先順序為T、+、:同級優(yōu)先采用右結合。t2=

2、2*2T*1T2=4T*1T2=4M2=t2=6、令文法G為NHDINRD->0I1I2I3I4I5I6I7I8I9(1)、G的語言L(G6)是什么？(2)、給出句子0127、34和568的最左推導和最右推導。分析：根據(jù)產(chǎn)生式NDIND可以看出，N最終可推導出1個或多個(可以是無窮多個)D,根據(jù)產(chǎn)生式A0I1I2I3I4I5I6I7I8I9可以看出，每個D可以推導出0至9中的某一個數(shù)字。因此，N最終推導出的是由0至IJ9這10個數(shù)字組成的字符串。解：(1)、L(G)是由0到9這10個數(shù)字組成的字符串。(2)、句子0127、34和568的最左推導：N=>ND=>NDD=>

3、NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568句子0127、34和568的最右推導：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687、寫一個文法，使其語言

4、是奇數(shù)集，且每個奇數(shù)不以0開頭。分析：本題要構造一個文法，由它產(chǎn)生的句子是奇數(shù)，且不以0開頭。也就是說它的每個句子都以1、3、5、7、9中某數(shù)結尾。如果數(shù)字只有一位，則滿足要求；如果有多位，則要求第一位不能是0;而中間有多少位，每位是什么數(shù)字則沒有要求。因此我們可以把這個文法分3部分完成，分別用3個非終結符來產(chǎn)生句子的第一位、中間部分和最后一位。引入幾個非終結符，其中，一個用作產(chǎn)生句子的開頭，可以是1到9中的數(shù)，不包括0;一個用來產(chǎn)生句子的結尾，為奇數(shù)；另一個則用來產(chǎn)生以非0整數(shù)開頭后面跟任意多個數(shù)字的數(shù)字用，進行分解之后，這個文法就很好寫了。解：G(S):A-2I4I6I8IDB一AI0C-

5、CBIAD-1I3I5I7I9S-CDID8、令文法為HE+TIE-TT-FIT*FIT/FF一(E)Ii(1)給出i+i*i、i*(i+i)的最左推導和最右推導；(2)給出i+i+i、i+i*i和i-i-i的語法樹。解：(1)最左推導為：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i

6、*(i+i)最右推導為：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>F*F=>F*(E)=>F*(E+T)=>F*(E+F)=>F*(E+i)=>F*(T+i)=>F*(F+i)=>F*(i+i)=>i*(i+i)(2)語法樹：Fi9、證明下面的文法是二義的：STSeSIiSIi分析：根據(jù)文法二義性定義，如果要證明該文法是二義的，必須找到一個句子，使該句子具有兩個不同的最右推導或兩個不同的語法樹

7、。我們首先分析這個文法，根據(jù)我們對程序語言的了解，不難發(fā)現(xiàn)這個文法應該是用來表示ifelse結構的(用“i”表示“if”或語句集，用e代表else)。因此我們就要到ifelse結構中去找二義性。我們知道，程序語言一般都規(guī)定else部分是和它前面離它最近的沒有被匹配的if語句進行匹配。而上面的這個文法體現(xiàn)不出這種限制，因此我們可以找這樣一個句子，在else前面有兩個if(如何子iiiei),else和不同的if進行匹配時就會產(chǎn)生不同的語義。解：考慮句子iiiei,存在如下兩個最右推導：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSe

8、S=>iiSei=>iiiei由此該文法是二義的。10、把下面文法改為無二義的：S-SSI(S)I()分析：本題給出的文法是二義的，關鍵在于S-SS是產(chǎn)生二義性的根源。我們將該產(chǎn)生式改造成等價的遞歸結構，消除二義性。解：S-TSIT,Tf(S)I()11、給出下面語言的相應文法：Li=anbnciIn>1,i>0,l_2=aibncnIn>1,i>0L3=anbnabmIn,m>0L4=1n0m1n0nIn,0分析：語言_1要求a和b的個數(shù)一樣多，且至少為一個；c的個數(shù)為0個以上。因此我們可用一個非終結符去生成anbn用，用另外一個非終結符去生成cio

9、語言L2要求b和c的個數(shù)一樣多，因此可用一個非終結符去生成bncn,而使用另外一個非終結符去生成aio因此可以模仿L1生成_2。對于L3,可將anbnambm分兩段考慮，即anbn和ambm,然后用兩個非終結符分別去產(chǎn)生他們。L4不能采用分段處理的方式，它要求中間的0和1的個數(shù)相同，而且一前一后的0和1的個數(shù)相同。對于這種題型我們可以采用從里向外擴展的方式進行，即先用一個非終結符生成處于中間的m個0和m個1,然后，使用另外一個非終結符在該用的基礎上擴充前后的n個0和n個1。解：L1的文法：S-ACAaAblab;CfcCI£L2的文法：S-AB2aAl&BfbBcIbcL3的

10、文法：S-AB;ZaAbl£BfaBbI£L4的文法：S1S0IA;A0A1Ie;第三章詞法分析1、編寫一個對于Pascal源程序的預處理程序。該程序的作用是，每次被調用時都將下一個完整的語句送進掃描緩沖區(qū)，去掉注釋行，同時要對源程序列表打印。2、請給出以下C+附序段中的單詞符號及其屬性值。intCInt:nMulDiv(intn1,intn2)(if(n3=0)return0；elsereturn(n1*n2)/n3;3、用類似C或Pascal的語言編寫過程GetChar,GetBC和Concat。4、用某種高級語言編寫并調試一個完整的詞法分析器。5、證明中關于正規(guī)式的交

11、換律、結合律等五個關系6、令A、B和C是任意正規(guī)式，證明以下關系成立:AlA=A(A*)*=A*A*=£IAA*(AB)*A=A(BA)*(AIB)*=(A*B*)*=(A*IB*)*A=bIaA當且僅當A=a*b證明：(1)、AIA=AL(AIA)=L(A)UL(A)=L(A),所以有AlA=A(2)、(A*)*=A*、A*=£IAA*通過證明兩個正規(guī)式所表示的語言相同來證明兩個正規(guī)式相等。L(&IAA*)=L(&)UL(A)L(A*)=L(£)UL(A)(L(A)*=L(e)UL(A)(L(A)0U(L(A)1U(L(A)2U(L(A)3U)=

12、L(e)U(L(A)1U(L(A)2U(L(A)3U(L(A)4U=(L(A)*=L(A*)即：L(£IAA*)=L(A*),所以有：A*=£IAA*(4)、(AB)*A=A(BA)*利用正規(guī)式的分配率和結合律直接推導。(AB)*A=(AB)0I(AB)1I(AB)2I(AB)3I)A=£AI(AB)1AI(AB)2AI(AB)3AI=AeIA(BA)1IA(BA)2IA(BA)3I=A(£I(BA)1I(BA)2I(BA)3I)=A(BA)*即：(AB)*A=A(BA)*(5)、(AIB)*=(A*B*)*=(A*IB*)*證明：先證(AIB)*=(A

13、*B*)*因為L(A)L(A)*L(B)*,L(B)L(A)*L(B)*故:L(A)UL(B)L(A)*L(B)*于是由本題第二小題結論可知(L(A)UL(B)*(L(A)*L(B)*)*又L(A)L(A)UL(B),L(B)L(A)UL(B)故:L(A)*(L(A)UL(B)*L(B)*(L(A)UL(B)*因此有:L(A)*L(B)*(L(A)UL(B)*(L(A)UL(B)*=(L(A)UL(B)*)故(L(A)*L(B)*)*(L(A)UL(B)*)*由本題第二小題得：(L(A)UL(B)*)*=(L(A)UL(B)*故得：(L(A)*L(B)*)*(L(A)UL(B)*則由得：(L(

14、A)UL(B)*=(L(A)*L(B)*)*由于L(A*B*)*=(L(A*B*)*=(L(A*)L(B*)*=(L(A)*L(B)*)*即有(L(A)UL(B)*=L(A*B*)*而(A|B)*對應的語言為(L(A)UL(B)*,且(A*B*)*對應的語言為L(A*B*)*則根據(jù)得(A|B)*=(A*B*)*再證:(A*|B*)*=(A*B*)*因為:A,B是任意正規(guī)式，由以上結論得：(A*|B*)*=(A*)*(B*)*)*又由本題第二小題目的結論可得：(A*)*=A*,(B*)*=B*因此，(A*|B*)*=(A*B*)*綜合上述兩種結論，最后得：(AIB)*=(A*B*)*=(A*IB

15、*)*(6)、A=bIaA當且僅當A=a*b7、構造下列正規(guī)式相應的DFA1(0I1)*1011(1010*I1(010)*1)*00*10*10*10*(00I11)*(01I10)(00I11)*(01I10)(00I11)*)*解：、1(0I1)*101第一步：根據(jù)正規(guī)式構造NFA先引入初始狀態(tài)X和終止狀態(tài)Y:1(0再對該轉換圖進行分解，得到分解后的NFAfc下圖:根據(jù)轉換矩陣獲得相應的DFA第二步：對NFA3行確定化，獲得狀態(tài)轉換矩陣:狀態(tài)01X?1，2,31，2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,

16、52,3,4第三步：化簡該DFA獲得最簡的DFA即為所求。首先根據(jù)是否終止狀態(tài)將所有狀態(tài)分為兩個集合0,1,2,3,4和5,這里集合5已經(jīng)不可劃分，只需考慮集合0,1,2,3,400,1,2,3,4。=2,4,-,0,1,2,3,4尸1,3,5因為1,3,5和2,4,-不在一個集合里面，所以需要對集合0,1,2,3,4進行進一步的劃分，檢查其中的所有狀態(tài)。狀態(tài)0不能接受字符0,需要把狀態(tài)0劃分出來；另外，只有狀態(tài)4讀入字符1后進入狀態(tài)5,因此將狀態(tài)4劃分出來，劃分的結果為4個集合：0,1,2,3,4,5。檢查集合1,2,3,1,2,30=2,4,不屬于同一個集合，因此要對集合1,2,3進行進一

17、步劃分，劃分結果為5個集合：0,1,2,3,4,5。檢查集合1,2,1,2。=2,1,2尸3,不需要進行進一步劃分。所以最終劃分結果為5個集合：0,1,2,3,4,5。所以，最終所求DF做口下圖示：0(2)、1(1010*I1(010)*1)*0、0*10*10*10*(4)、(00I11)*(01I10)(00I11)*(01I10)(00I11)*)*8、給出下面正規(guī)表達式：(1)以01結尾的二進制數(shù)用；(2)能被5整除的十進制整數(shù)；(3)包含奇數(shù)個1或奇數(shù)個0的二進制數(shù)用；(4)英文字母組成的所有字符用，要求符號用中的字母依照字典序排列；(5)沒有重復出現(xiàn)的數(shù)字的數(shù)字符號用的全體；(6)

18、最多有一個重復出現(xiàn)的數(shù)字的數(shù)字符號用的全體；(7)不包含子用abb的由a和b組成的符號用的全體。解：(1)以01結尾的二進制數(shù)用；分析題意，要求的是二進制數(shù)用，即由0和1構成的用，并且必須以01結尾，所以本題可以分兩步完成：一部分實現(xiàn)由0和1構成的任意用，一部分即01,然后將它們連結在一起就可以了，所以所求為(1I0)*01。(2)能被5整除的十進制整數(shù)；分析題意，本題要求的是十進制整數(shù)，也就是由0至9這10個數(shù)字組成的字符串，并且不能以0開頭(整數(shù)“0”除外)，要求能被5整除，則該申必須以0或者5結尾。根據(jù)分析，可以把本題分成兩種情況考慮：一種情況時該整數(shù)只有一位，則該整數(shù)有0和5兩種可能；

19、另一種情況是該整數(shù)有多位，則該整數(shù)可以分成三部分考慮：一是第一位必須不為0;二是最后一位必須為0或5;三是中間部分可有可無，并且可以由0到9之間任意數(shù)字構成，所以所求為(1I2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7I8|9)*(0|5)(0|5)。(3)包含奇數(shù)個1或奇數(shù)個0的二進制數(shù)用；本題求二進制用，并且要求包含奇數(shù)個0或奇數(shù)個1,由于0和1都可以在二進制用中任何地方出現(xiàn)，所以本題只需要考慮一種情況，另一種情況也可以類似求得?？紤]包含奇數(shù)個0的字符串：由于只關心0的個數(shù)的奇偶數(shù)，我們可以把二進制用分成多段來考慮，第一段為二進制用的開始到第一個0為止，這一段包含一個0

20、,并且0的前面有0個或多個1。對于剩下的二進制用按照每段包含兩個0的方式去劃分，即以0開始，以0結尾，中間可以有0個或多個1。如果一個二進制串被這樣劃分完后，剩下的部分如果全部是全1用(這些全1用在前面劃分的用之間或最后)，則該二進制用就有奇數(shù)個0,所以該二進制用可以這樣描述：以第一段(1*0)開始，后面由全1申(1*)以及包含兩個0的用(01*0)組成，所以包含奇數(shù)個0的正規(guī)表達式為1*0(1|01*0)*。所以本題所求為1*0(1|01*0)*|0*1(0|10*1)*0(4)英文字母組成的所有字符用，要求符號用中的字母依照字典序排列；(5)沒有重復出現(xiàn)的數(shù)字的數(shù)字符號用的全體；(6)最多

21、有一個重復出現(xiàn)的數(shù)字的數(shù)字符號用的全體；(7)不包含子用abb的由a和b組成的符號用的全體。9、對下面情況給出DFA及正規(guī)表達式：(1) 0,1上的含有子用010的所有用；(2) 0,1上不含子用010的所有用。解：(3) 、(4) 、直接寫出滿足條件的正規(guī)表達式?？紤]滿足條件的字符串中的1:在用的開始部分可以有0個或多個1,用的尾部也可以有0個或多個1,但用的中間只要出現(xiàn)1則至少在兩個以上，所以滿足條件的正規(guī)表達式為1*(0I111*)*1*。所求的DFAfc下圖所示：10、 一個人帶著狼、山羊和白菜在一條河的左岸。有一條船，大小正好能裝下這個人和其他三件東西中的一件。人和他的隨行物都要過到

22、河的右岸。人每次只能將一件東西擺渡過河。但若人將狼和羊留在同一岸而無人照顧的話,狼將把羊吃掉。類似地，若羊和白菜留下來無人照看，羊將會吃掉白菜。請問是否有可能渡過河去，使得羊和白菜都不被吃掉？如果可能，請用有限自動機寫出渡河的方法。解：11、12、將圖的（a）和（b）分別確定化和最小化(a（1）、圖（a）中為一個NFA所以需要先對它進行確定化，得到DFA然后再對DFA進行最小化。狀態(tài)ab00,110,10,1110?首先進行確定化，如下兩個表所示:狀態(tài)ab0r1211220根據(jù)狀態(tài)轉換矩陣得到如下圖所示的DFA0a1化簡后的DFA為:ba(2)、題中所給即為一個DFA不需要確定化，只對它進行最

23、小化即可。最后劃分結果是最小化后的首先將狀態(tài)劃分為兩個集合0,1,2,3,4,5。有0,1a=1,0,1)b=2,4和2,3,4,5a=1,3,0,5,2,3,4,5b=2,3,4,5),所以可以進一步劃分為0,1,2,4,3,5,然后有0,1a=1,0,1b=2,4,2,4a=1,0,2,4b=3,5,3,5a=3,5,3,5b=2,4。因此,0,1,2,4,3,5)。DF做口下圖所示：13、 (1)給出描述C浮點數(shù)的DFA14、 構造一個DFA它接受三=0,1上所有滿足如下條件的字符用：每個1都有0直接跟在右邊。分析：對這類題型的固定解法分4步進行：首先根據(jù)語言寫出正規(guī)表達式；然后根據(jù)正規(guī)

24、表達式構造相應的NFA然后，對NFA!行確定化得到DFA最后對DFA化簡得到最簡DFA第一步：寫出正規(guī)表達式。根據(jù)題意，該DFAg受的字符串由0和1組成，并且每個1的后面都有0直接跟在右邊，因此，可以將該字符串理解為由0和10構成的用，則相應的正規(guī)表達式就是(0|10)*。第二步：構造NFA首先得出下圖：(0然后對上圖進行分解后得到如下圖所示的NFA第三步：確定化，得到DFA確定化結果如表所列；給狀態(tài)編號，得到表所示的狀態(tài)轉換矩陣：狀態(tài)01X,1,Y1，Yr21，Y1，Y221，Y?狀態(tài)01012n11221表狀態(tài)轉換矩陣表新的狀態(tài)轉換矩陣根據(jù)狀態(tài)轉換矩陣得到DF做口下圖所示：第四步：對該DF

25、A3行最小化。其分析過程如下:0,1,20,1。=1,0,1尸20,1,2最小化后的DF做口圖所示，該DFAffl為所求。15、 給定右線性文法G:5- 0SI1SI1AI0BZ1CI1A0CI0C0CI1CI0I1求出一個與G等價的左線性文法。分析：根據(jù)右線性文法求左線性文法沒有直接的方法，但可以通過狀態(tài)轉換圖去轉換?？梢韵惹蟪鑫姆℅的狀態(tài)轉換圖，再根據(jù)狀態(tài)轉換圖寫出相應的左線性文法。文法G對應的狀態(tài)轉換圖如下所示：對狀態(tài)轉換圖進行確定化，得到狀態(tài)轉換矩陣:狀態(tài)01SS,BS,AS,BS,B,C,ZS,AS,AS,BS,A,C,ZS,B,C,ZS,B,C,ZS,A,C,ZS,A,C,ZS,B

26、,C,ZS,A,C,Z給狀態(tài)編號，得到新的狀態(tài)轉換矩陣:狀態(tài)01012132214334434根據(jù)狀態(tài)轉換矩陣獲得DF做口下:還可以對上圖的所示：DFA®行化簡，狀態(tài)3和4可以合并，化簡后的DFA如下圖0,1不難看出，該DFAg受的語言是0,1上包含00或11的字符串。根據(jù)化簡后的DFA我們可以寫出相應的左線性文法G':T-A0IB1IT0IT1ZB0I0AA1I116、 *非形式的說明17、 *下面的字集是否為正規(guī)集？或寫出其正規(guī)式，或給出否證。(1) l_1=anbnIn>0；(2) _2=x;(3) _3=。18、 假定L和M都是正規(guī)集：(1) 證明LUMLAM和

27、M(補集)也是正規(guī)的；(2) L'是L中每個字的逆轉，證明L也是正規(guī)的。19、 寫出描述ANSIC的單詞符號的LEX程序。20、 假定有正規(guī)定義式A一aIbA-AAqAn-An-1An-1考慮詞形A(1)把A中所有簡名都換掉，最終所得的正規(guī)式的長度是多少？(2)字集A的元素是什么？把它們非形式的表示成n的函數(shù)；(3)證明識別A的DFAR需用2n+1個狀態(tài)就足夠了。21、 把LEX的“動作”成分加以充實使得可用它來編寫語法制導編輯器第四章語法分析一一自上而下分析1、考慮下面的文法G:5- aIAI(T)TfT,SIS(1)消去G的左遞歸。然后對每個非終結符，寫出不帶回溯的遞歸子程序(2)

28、經(jīng)改寫后的文法是否是LL(1)的？給出它的預測分析表。解：(1)按照T、S的順序消除左遞歸，得到文法：G'(S)S-aIAI(T)T-ST'丁,ST'I£對于非終結符S,T,T'的遞歸子程序如下：ProcedureS;BeginIfsym=，a，orsym=，八，ThenadvanceElseifsym='('ThenbeginAdvance;T;Ifsym=，)，ThenadvanceElseerrorEndElseerrorEnds;ProcedureT;BeginS;T'Ends;ProcedureT'BeginI

29、fsym=；ThenbeginAdvance;S;TEndsends;(2)計算每個非終結符的FIRST集合和FOLLO牧合:FIRST(S)=a,A,()FIRST(T)=a,A,()FIRST()=,FOLLOWS)=),',',#FOLLOWT)=)FOLLOWS)=)從而可見改造后的文法符合LL(1)文法的充分必要條件，所以是LL(1)的該文法的預測分析表aA(),#SS->aS->AS->(T)TT->ST'T->ST'T->ST'T->己T->,ST，2、對下面的文法G:JTE'E

30、9;+EI£T-FT'一TI£1PF'F'一*F'I£P(E)IaIbIA(1)計算這個文法的每個非終結符的FIRST和FOLLOW(2)證明這個文法是LL(1)的。(3)構造它的預測分析表。(4)構造它的遞歸下降分析程序。分析：對于這類題目，我們首先應當檢查文法是否符合LL(1)文法的條件，根據(jù)需要，先通過消除左遞歸、提取右公因子的方法，把文法改造成符合LL(1)文法的條件，在此基礎上，我們才能構造出不帶回溯的遞歸下降識別程序。注意，本題在構造子程序時，對于每個產(chǎn)生式候選，在調用第一個非終結符對應的子程序之前，檢查了首符集。解：(

31、1)計算每個非終結符的FIRST集合和FOLLO濂合如下：FIRST(E)=(,a,b,AFIRST(E')=+,£FIRST(T)=(,a,b,AFIRST(T)=(,a,b,A,£FIRST(F)=(,a,b,AFIRST(F')=*,£FIRST(P)=(,a,b,AFOLLOWE)=#,)FOLLOWE')=#,)FOLLOWT)=+,),#FOLLOWS)=+,),#FOLLOWF)=(,a,b,A,+,),#FOLLOWF')=(,a,b,A,+,),#FOLLOWS=*,(,a,b,A,+,),#(2) 本文法是LL(

32、1)文法。證明：通過觀察可知文法中不含有左遞歸，滿足LL(1)文法定義的第一個條件?？紤]下列產(chǎn)生式：E'一+EIe一TI£F'一*F'I£P-(E)IaIbIA因為：FIRST(+E)AFIRST(£)=+A£=?FIRST(E')AFOLLOWE')=+#,)=?FIRST(T)nFIRST(e)=(,a,b,An£=?FIRST(丁)nFOLLOW)=(,a,b,An+,),#=?FIRST(*F')AFIRST(e)=*A£=?FIRST(F')nFOLLOWF')

33、=*A(,a,b,A,+,),#=?FIRST(E)nFIRST(a)nFIRST(b)nFIRST(A)=?所以該文法是LL(1)文法。(3)構造其預測分析表：預測分析表+*()abA#EETE'ETE'ETE，ETE，E，E'+EE，己E'->TTFTFTTFTTFT丁士丁TTT'TT丁士FFPFFPF'PPF'FPF'F，EF'*F'F己F，己F，己F'己F'己F'己PP(E)PaPbPA(4)構造其遞歸下降分析程序:ProcedureE;BeginT;E，End;Procedu

34、reE'BeginIfsym='+ThenbeginAcvance;EEndEnd;ProcedureT;BeginF;TEnd;ProcedureT;BeginIfsymCfirst(T)ThenTElseifsym='*'thenerrorEnd;ProcedureF;BeginIfsymCfirst(P)P;FEnd;ProcedureFBeginIfsym='*ThenbeginAdvance;F，EndEnd;ProcedurePBeginIfsym=aorsym=b'orsym=ThenacvanceElseifsym='(T

35、henbeginAdvance;E;Ifsym=ThenadvanceElseerrorEndElseerrorEnd;3、下面文法中，哪些是LL(1)的，說明理由(1)、SfAbcAfaI£BfbI£(2)、SfAbAfaIBI£B->bI£(3)、SfABBAAfaI£B->bI£(4)、SfaSelBBfbBeICCfcCeId分析：判斷文法是否是LL(1)的，要根據(jù)LL(1)文法的條件逐一檢查：首先要確定文法不含左遞歸；隨后計算文法的各非終結符(X)的首符集FIRST(X)和隨符集FOLLOWX)。首先要理解這兩個

36、集合的計算方法，特別要注意算法終止的條件：直到集合不再變化為止。也就是說，反復檢查每一個產(chǎn)生式，直到從頭到尾檢查了所有產(chǎn)生式，而FIRST集合和FOLLOW1合都沒有變化了，這時候計算才能結束。最后根據(jù)LL(1)文法的充分必要條件(即LL(1)文法定義)來判斷是否是LL(1)文法。解：(1)該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW1合如下：FIRST(S)=a,b,cFIRST(A)=a,£FIRST(B)=b,eFOLLOWS)=#FOLLOWA)=b,cFOLLOWB)=c可見該文法滿足LL(1)文法的三個條件，是LL(1)文法。(2)該文法不含左遞歸，計

37、算每個非終結符的FIRST集合和FOLLOW1合如下：FIRST(S)=a,bFIRST(A)=a,b,£FIRST(B)=b,£FOLLOWS)=#FOLLOWA)=bFOLLOWB)=b考慮KaIBle,因為FIRST(B)nFOLLOWA)=bw?,所以該文法不是LL(1)文法。(3)該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW1合如下：FIRST(S)=a,b,£FIRST(A)=a,£FIRST(B)=b,£FOLLOWS)=#FOLLOWA)=a,b,#FOLLOWB)=a,b,#考慮A-aI£和Bfb

38、I£,因為FIRST(a)nFOLLOWA)=aw?FIRST(b)nFOLLOWB)=bw?所以該文法不是LL(1)文法。(4)該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW1合如下：FIRST(S)=a,b,c,dFIRST(B)=b,c,dFIRST(C)=c,dFOLLOWS)=e,#FOLLOWB)=e,#FOLLOWC)=e,#可見該文法滿足LL(1)文法的三個條件，是LL(1)文法。4、對下面文法：ExprfExprExprf(Expr)IVarExprTailExprI8Var-idVarTailVarTailf(Expr)I£(1)、構造

39、LL(1)分析表。(2)、給出對句子id-id(id)的分析過程。分析：構造文法的預測分析表，通常應當按下列順序進行：(1)、消除文法的左遞歸(包括所有直接左遞歸和間接左遞歸)；(2)、對消除左遞歸后的文法，提取左公因子；(3)、對經(jīng)過上述改造后的文法，計算它的每個非終結符的FIRST集合和FOLLOW1合；(4)、根據(jù)FIRST集合和FOLLOW1合構造預測分析表。第一步對文法G的每個產(chǎn)生式A-a執(zhí)行第一步和第三步；第二步對每個終結符aFIRST(a),把Afa加至MA,a中；第三步若£FIRST(a),則對任彳bFOLLOW(AEA-a加至MA,b中；第四步把所有無定義的MA,a

40、標上“出錯標志”。解：(1)、計算每個非終結符的FIRST集合和FOLLO濂合如下：FIRST(Expr)=-,(,idFIRST(ExprTail)=-,&FIRST(Var)=idFIRST(VarTail)=(,FOLLOW(Expr)=),#FOLLOW(ExprTail)=),#FOLLOW(Var)=-,),#FOLLOW(VarTail)=-,I,#構造其預測分析表如下：-id()#ExprExprfExprExprExprExpr-(Expr)ExprTailExprTail-ExprExprTail-£ExprTail-£VarVar一idVarT

41、ailVarTailVarTail一£VarTail一(Expr)VarTail一£VarTail一£(2)、句子id-id(id)的分析過程如下:步驟符號棧輸入用所用產(chǎn)生式0#Exprid-id(id)#1#ExprTailVarid-id(id)#ExprfVarExprTail2#ExprTailVarTailidid-id(id)#Var一idVarTail3#ExprTailVarTail-id(id)#4#ExprTail-id(id)#VarTail一£5#Expr-id(id)#1ExprTailExpr6#Expr-id(id)#7#E

42、xpr-id(id)#ExprfExpr8#Exprid(id)#9#ExprTailVarid(id)#ExprfVarExprTail10#ExprTailVarTailidid(id)#Var一idVarTail11#ExprTailVarTail(id)#12#ExprTail)Expr(id)#VarTail一(Expr)13#ExprTail)Expr(id)#14#ExprTail)Expr(id)#15#ExprTail)Exprid)#16#ExprTail)ExprTalVarid)#ExprfVarExprTail17#ExprTail)ExprTailVarTailid

43、id)#Var一idVarTail18#ExprTail)ExprTailVarTail)#19#ExprTail)ExprTail)#VarTail一£20#ExprTail)#ExprTailf821#ExprTail)#22#ExprTail#23#ExprTailf8suc5、把下面文法改寫為LL(1)的：Declist-Declist;DeclIDeclDecIdList:TypeIdList-IdList,idIidTypefScalarTypeIarray(ScalarTypeList)ofTypeScalarTypefidIBound.BoundBouncHSignI

44、ntLiteralIidSignf+I-I£ScalarTypeListfScalarTypeList,ScalarTypeIScalarType分析：本題主要考察理解和運用消除文法的左遞歸、提取公因子等算法的能力，為判斷文法是否是LL(1)文法，還要計算文法的FIRST集合和FOLLO課合。消除文法的左遞歸的基本思想是，將文法規(guī)則中的左遞歸結構變換成等價的右遞歸結構。提取左公因子的算法，是對包含公共左因子的產(chǎn)生式候選，反復提取左因子，就能夠把每個非終結符(包括新引進者)的所有候選首符集變成為兩兩不相交。消除文法的左遞歸、提取左公共因子后，再計算文法的各非終結符(X)的首符集FIRS

45、T(X)和隨符集FOLLOW(X)然后根據(jù)LL(1)文法的充分必要條件(即LL(1)文法的定義)來判斷文法是否是LL(1)文法。解：首先消除左遞歸，得到文法G(Declist):Declist-DeclDeclist'Declist'一；DeclDeclist'I&DeclTdList:TypeIdList-idIdList'IdList'一，idList'I&TypefScalarTypeIarray(ScalarTypeList)ofTypeScalarTypefidIBound.BoundBouncRSignIntLiter

46、alIidSignf+I-I£ScalarTypeListfScalarTypeScalarTypeList'ScalarTypeList'f,ScalarTypeScalarTypeList'I&顯然，改造后的文法沒有左公共因子，計算每個非終結符的FIRST集合和FOLLO課合如下：FIRST(Declist)=idFIRST(Declist')=;,eFIRST(Decl)=idFIRST(IdList)=idFIRST(IdList')=;,eFIRST(Type)=id,+,-,IntLiteral,arrayFIRST(Sca

47、larType)=id,+,-,IntLiteralFIRST(Bound)=id,+,-,InLiteralFIRST(Sign)=+,-,eFIRST(ScalarTypeList)=id,+,-,IntLiteralFIRST(ScalarTypeList'尸一eFOLLOW(Declist)=#FOLLOW(Declist'尸#FOLLOW(Decl)=id,;FOLLOW(IdList尸:FOLLOW(IdList'尸:FOLLOW(Type尸id,;FOLLOW(ScalarType)=idFOLLOW(Bound尸id;,)','.FOLL

48、OW(Sign尸IntLiteralFOLLOW(ScalarTypeList)=)FOLLOW(ScalarTypeList')=)顯然，改造后的文法是LL(1)的。第五章語法分析一一自下而上分析1、令文法G為JE+TITT-T*FIF1(E)Ii證明E+T*F是它的一個句型，指出這個句型的所有短語，直接短語和句柄。解：因為E=>E+T=>E+T*F所以E+T*F是該文法的一個句型。短語：E+T*F,T*F直接短語：T*F句柄：T*F2、考慮下面的表格結構文法G:S-aIAI(T)TfT,SIS(1)給出(a,(a,a)和(a,a),A,(a),a)的最左和最右推導。(2

49、)指出(a,a),A,(a),a)的規(guī)范歸約及每一步的句柄。根據(jù)這個規(guī)范歸約，給出“移進-歸約”的過程，并給出它的語法樹自下而上的構造過程。分析：要理解最左推導和最右推導的含義。所謂最左推導是指任何一步a=>B都是對a中的最左非終結符進行替換的；最右推導是指任何一步a=>B都是對a中的最右非終結符進行替換的。解：(1)最左推導：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T)=>(a,(T,S)=>(a,(S,S)=>(a,(a,S)=>(a,(a,a)S=>(T)=>(T,S)=>(S,

50、S尸>(T),S尸>(T,S),S尸>(T,S,S),S)=>(S,S,S),S尸>(T),S,S),S)=>(T,S),S,S),S)=>(S,S),S,S),S)=>(a,S),S,S),S)=>(a,a),S,S),S)=>(a,a),A,S),S)=>(a,a),A,(T),S)=>(a,a),A,(S),S)=>(a,a),A,(a),S)=>(a,a),A,(a),a)最右推導：S=>(T)=>(T,S)=>(T,(T)=>(T,(T,S)=>(T,(T,a)=>

51、(T,(S,a)=>(T,(a,a)=>(S,(a,a)=>(a,(a,a)S=>(T,S)=>(T,a)=>(S,a尸>(T),a尸>(T,S),a尸>(T,(T),a尸>(T,(S),a尸>(T,(a),a尸>(T,S,(a),a尸>(T,A,(a),a)=>(S,A,(a),a)=>(T),A,(a),a)=>(T,S),A,(a),a)=>(T,a),A,(a),a)=>(S,a),A,(a),a)=>(a,a),A,(a),a)(2)(a,a),A,(a),a)的規(guī)范歸約

52、如下：(a,a),A,(a),a)(S,a),A,(a),a)(T,a),A,(a),a)(T,S),A,(a),a)(T),A,(a),a)(S,A,(a),a)(T,A,(a),a)(T,S,(a),a)(T,(a),a)(T,(S),a)(T,(T),a)(T,S),a)(T),a)(S,a)(T,S)(T)“移進一歸約”過程：步驟棧輸入用動作0#(a,a),A,(a),a)#預備1#(a,a),A,(a),a)#進2；#(a,a),A,(a),a)#進3#(a,a),A,(a),a)#進4#(a,a),A,(a),a)#進51#(Sr,a),A,(a),a)#歸6#(T,a),A,(a),a)#歸7#(T,a),A,(a),a)#進8#(T,a),A,(a),a)#進9#(T,S),A,(a),a)#歸10#(T),A,(a),a)#歸11#(T)；A,(a),a)#進12#(S，八，(a),a)#歸13#(T,A,(a),a)#歸14#(T,A,(a),a)#進15#(T,A；(a),a)#進16#(T,S，(a),a)#歸17:#(T,(a),a)#歸18#(T,(a),a)#進19#(T,(a),a)#進20#(T,(a),a)#進21#(T,(S),a)#歸22