1、編譯原理A 1. 簡要說明語義分析的基本功能。2. 考慮文法 GS: S (T) | a+S | a T T,S | S 消除文法的左遞歸及提取公共左因子。3試為表達式 w+(a+b)*(c+d/(e-10)+8) 寫出相應的逆波蘭表示。4. 按照三種基本控制結構文法將下面的語句翻譯成四元式序列：while (A<C B<D) if (A 1) C=C+1;else while (A D)A=A+2;。5. 已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。A答案1答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態語義檢 查。2解：消除文法

2、GS的左遞歸： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 3答：w a b + c d e 10 - / + 8 + * +4答：該語句的四元式序列如下(其中E1、E2和E3分別對應ACBD、A1和AD，并且關系運算符優先級高)： 100 (j<,A,C,102) 101 (j,_,_,113) 102 (j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j,

3、A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 1135答：證明： 由文法GS：SaSb|Sb|b，對句子aabbbb對應的兩棵語法樹為： 因此，文法GS為二義文法。 編譯原理B 1. 什么是句子？ 什么是語言 ?2. 寫一文法，使其語言是偶正整數的集合,要求：    (1)允許0打頭；   (2) 不允許0打頭。3. 已知文法 GE 為：     ET|E+T|E-T   &

4、#160; TF|T*F|T/F     F （ E ） |i 該文法的開始符號（識別符號）是什么？ 請給出該文法的終結符號集合 VT 和非終結符號集合 VN 。 找出句型 T+T*F+i 的所有短語、簡單短語和句柄。4. 構造正規式相應的 NFA : 1(0|1)*101。5. 寫出表達式(ab*c)/(ab)d的逆波蘭表示和三元式序列。B卷答案1答：(1)設G是一個給定的文法，S是文法的開始符號，如果S x(其中xVT*),則稱x是文法的一個句子。 (2)設GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)xS x,xVT*

5、 。2解：(1)GS=(S,P,D,N,0,1,2,9,P,S) P: S->PD|D P->NP|N D->0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)GS=(S,P,R,D,N,Q ,0,1,2,9,P,S) P: S->PD|P0|D P->NR|N R->QR|Q D->2|4|6|8 N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|93解： 該文法的開始符號（識別符號）是E。 該文法的終結符號集合VT=+、-、*、/、（、）、i。 非終結符號集合VN=E、T、F

6、。 句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i; 簡單短語為i、T*F、第一個T;句柄為第一個T。4解：1(0|1)*101對應的NFA為 5解：逆波蘭表示： abc*ab/d 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)編譯原理C1(10分) 對下列錯誤信息，請指出可能是編譯的哪個階段（詞法分析、語法分析、語義分析、代碼生成）報告的。（1） else 沒有匹配的if（2） 數組下標越界（3） 使用的函數沒有定義（4） 在數中出現非數字字符（5）函數調用時實參與形參類型不一致。2(15分) 構造一個DFA，它接收=0,1上所有滿足如下條件的字符

7、串：每個1 都有0 直接跟在右邊。并給出該語言的正規式3(10分) 為下面的語言設計文法：（1） ambn, 其中m ³ n （2） w | wÎa, b*，w的長度為奇數證明 E + T*（id）是文法的一個句型，指出該句型的所有短語、直接短語和句柄。5(15分) 給定文法：E E + T | E - T |TT T * F | T / F |FF (E) | idC卷答案1答案：（每小題2分）（1） 語法分析（2） 語法分析（3） 語義分析（4） 詞法分析（5） 語義分析2答案： 按題意相應的正規表達式是(0*10)*0*，或0*(0 | 10)*0* ，構造相應的DF

8、A。3答案：（每小題 10分）（1）考慮在先產生同樣數目的a,b，然后再生成多余的a。以下是一種解法：S aSb | aS | （2） A aB | bBB aA | bA | 5證明 E + T*（id）是文法的一個句型，指出該句型的所有短語、直接短語和句柄。答：，短語：id，（id）， T*（id）， E+ T*（id）。直接短語：id。句柄是id。編譯原理D卷3、何謂“標識符”，何謂“名字”，兩者的區別是什么？4、令 、* 和代表加、乘和乘冪，按如下的非標準優先級和結合性質的約定，計算11*2*12的值：（1）、優先順序（從高至低）為、* 和，同級優先采用左結合。（2）、優先順序為、*，

9、同級優先采用右結合。6、令文法G6為NDND，D0123456789（1）、G6的語言L(G6)是什么？（2）、給出句子0127、34和568的最左推導和最右推導。7、寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。8、令文法為ETE+ TE-T TFT*FT/F F(E)i（1） 給出i+i*i、i*(i+i)的最左推導和最右推導；給出i+i+i、i+i*i和i-i-i的語法樹。9、證明下面的文法是二義的：SiSeSiSi11、給出下面語言的相應文法：L1=anbncin1，i0， L2=aibncnn1，i0L3=anbnambmn，m0L4=1n0m1m0nn，m03解：標識符是高級

10、語言中定義的字符串，一般是以英文字母（包括大小寫字母）或下劃線開頭的，由數字、字母和下劃線組成的一定長度的字符串，它只是一個標志，沒有其他含義。名字是用標識符表示的，但名字不僅僅是一個字符串，它還具有屬性和值。4解：（1）、11*2*12 = 2*2*12 = 4*12 = 42 = （2）、11*2*12 = 6解：（1）、L(G6)是由0到9這10個數字組成的字符串。（2）、句子0127、34和568的最左推導：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>

11、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解：G(S)：A2468D BA0 CCBA D13579 SCDD8解：（1） 最左推導為：E => E+T => T+T => F+T =

12、> 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*(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 =>

13、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） 語法樹：TE+EFi+TFiiE+TEFi*TFiTFiEE-TEFiTFi-Fi9解：考慮句子iiiei，存在如下兩個最右推導：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>iiiei由此該文法是二義的。11解：L1的文法：S

14、AC；AaAbab；CcCL2的文法：SAB；AaA；BbBcbcL3的文法：SAB；AaAb；BaBbL4的文法： S1S0A； A0A1；編譯原理E卷1、 令A、B和C是任意正規式，證明以下關系成立：AA=A(A*)*= A*A*=A A*(AB)*A=A(BA)*(AB)*=(A*B*)*=(A*B*)*A=baA當且僅當A=a*b2、 構造下列正規式相應的DFA1(01)*1011(1010*1(010)*1)*00*10*10*10*(0011)*(0110)(0011)*(0110)(0011)*)*3、 給出下面正規表達式：（1） 以01結尾的二進制數串；（2） 能被5整除的十進

15、制整數；包含奇數個1或奇數個0的二進制數串；4、 對下面情況給出DFA及正規表達式： （1）0，1上不含子串010的所有串。5、 將圖3.18的（a）和（b）分別確定化和最小化。10a，baa(a)20baa(b)1543bbbbbaaaaa6、 構造一個DFA，它接受=0，1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。、7、 給定右線性文法G：S0S1S1A0BA1C1B0C0C0C1C01求出一個與G等價的左線性文法。文法G對應的狀態轉換圖如下所示：SZ100，1BCA10，10，1001E卷答案1證明：（1）、AA=AL(AA)=L(A)L(A)=L(A)，所以有AA=A。（2

16、）、(A*)*= A*（3）、A*=A A*通過證明兩個正規式所表示的語言相同來證明兩個正規式相等。L(A A*)=L()L(A)L(A*)= L()L(A)(L(A) )*=L()L(A)(L(A)0(L(A)1(L(A)2(L(A)3)=L()(L(A)1(L(A)2(L(A)3(L(A)4=(L(A)*=L(A*)即：L(A A*)=L(A*)，所以有：A*=A A*（4）、(AB)*A=A(BA)*利用正規式的分配率和結合律直接推導。(AB)*A=(AB)0(AB)1(AB)2(AB)3)A=A(AB)1A(AB)2A(AB)3A=AA (BA)1A (BA)2A (BA)3=A(BA

17、)1(BA)2(BA)3)=A(BA)*即：(AB)*A=A(BA)*（5）、(AB)*=(A*B*)*=(A*B*)*證明:先證(AB)*=(A*B*)*因為L(A)L(A) *L(B) *,L(B) L(A) *L(B) *故:L(A) L(B) L(A) *L(B) *于是由本題第二小題結論可知(L(A)L(B) *(L(A) *L(B)*)* 又L(A)L(A)L(B), L(B) L(A)L(B)故:L(A)*(L(A)L(B)* L(B)*(L(A)L(B)*因此有:L(A)*L(B)* (L(A)L(B)* (L(A)L(B)*=( (L(A)L(B)*) 2故(L(A)*L(B

18、)*)*(L(A)L(B)*)*由本題第二小題得: (L(A)L(B)*)*= (L(A)L(B) * 故得: (L(A)*L(B)*)*(L(A)L(B) * 則由得: (L(A)L(B) *=(L(A)*L(B)*)*由于L(A*B*)*=(L(A*B*)*=(L(A*)L(B*)*=(L(A)*L(B)*)*即有(L(A)L(B)*=L(A*B*)* 而(A|B)*對應的語言為(L(A)L(B)*,且(A*B*)*對應的語言為L(A*B*)*則根據得(A|B)*=(A*B*)*再證:(A*|B*)*=(A*B*)*因為:A,B是任意正規式,由以上結論得: (A*|B*)*=(A*)*(B

19、*)*)*又由本題第二小題目的結論可得：（A*）*=A*，（B*）*=B*因此，（A*|B*）*=（A*B*）*綜合上述兩種結論，最后得：(AB)*=(A*B*)*=(A*B*)*2解：(1)、1(01)*101第一步：根據正規式構造NFA，先引入初始狀態X和終止狀態Y：X1(01)*101Y再對該轉換圖進行分解，得到分解后的NFA如下圖：X12345Y110101第二步：對NFA進行確定化，獲得狀態轉換矩陣：狀態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，52，3，4根據轉換矩陣

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

21、于同一個集合，因此要對集合1，2，3進行進一步劃分，劃分結果為5個集合：0，1，2，3，4，5。檢查集合1，2，1，20=2，1，21=3，不需要進行進一步劃分。所以最終劃分結果為5個集合：0，1，2，3，4，5。所以，最終所求DFA如下圖示：013410010115013解：（1）以01結尾的二進制數串； (10)*01。（2）能被5整除的十進制整數； (123456789) (0123456789)*(05)(05)。（3）包含奇數個1或奇數個0的二進制數串；1*0（101*0）*0*1（010*1）*。4解：（1）、直接寫出滿足條件的正規表達式。考慮滿足條件的字符串中的1：在串的開始部分

22、可以有0個或多個1，串的尾部也可以有0個或多個1，但串的中間只要出現1則至少在兩個以上，所以滿足條件的正規表達式為1*(0111*)*1*。所求的DFA如下圖所示：AS10a11B05 解：（1）、圖（a）中為一個NFA，所以需要先對它進行確定化，得到DFA，然后再對DFA進行最小化。首先進行確定化，如下兩個表所示：207狀態ab00，110，10，1110Ø 狀態ab01211220根據狀態轉換矩陣得到如下圖所示的DFA：210bbaaa化簡后的DFA為：20baa（2）、題中所給即為一個DFA，不需要確定化，只對它進行最小化即可。首先將狀態劃分為兩個集合0，1，2，3，4，5。有

23、0，1a=1，0，1b=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。最小化后的DFA如下圖所示：10b aa2b ba6解：第一步：寫出正規表達式。根據題意，該DFA接受的字符串由0和1組成，并且每個1的后面都有0直接跟在右邊，因此，可以將該字符串理解為由0和10構成的串，則相應的正規表達式就是(010)*。第二步：構造NFA。首先得出下圖：(010)*XY然后對上圖

24、進行分解后得到如下圖所示的NFA。XY12010第三步：確定化，得到DFA。確定化結果如表14.1所列；給狀態編號，得到表14.2所示的狀態轉換矩陣：狀態01X，1，Y1，Y21，Y1，Y221，YØ表14.1 狀態轉換矩陣狀態0101211221表14.2 新的狀態轉換矩陣根據狀態轉換矩陣得到DFA如下圖所示：21011000第四步：對該DFA進行最小化。其分析過程如下：0，1，20，10=1，0，11=20，1，2最小化后的DFA如圖所示，該DFA即為所求。10100對狀態轉換圖進行確定化，得到狀態轉換矩陣：狀態01SS，BS，AS，BS，B，C，ZS，AS，AS，BS，A，C，

25、ZS，B，C，ZS，B，C，ZS，A，C，ZS，A，C，ZS，B，C，ZS，A，C，Z給狀態編號，得到新的狀態轉換矩陣：狀態01012132214334434根據狀態轉換矩陣獲得DFA如下：040123100101101還可以對上圖的DFA進行化簡，狀態3和4可以合并，化簡后的DFA如下圖所示：0，1ST01BA0101不難看出，該DFA接受的語言是0，1上包含00或11的字符串。根據化簡后的DFA，我們可以寫出相應的左線性文法G：TA0B1T0T1AB00BA11編譯原理F卷1、考慮下面的文法G1： Sa(T)TT，SS（1）消去G1的左遞歸。然后對每個非終結符，寫出不帶回溯的遞歸子程序。（

26、2）經改寫后的文法是否是LL(1)的？給出它的預測分析表。（2）計算每個非終結符的FIRST集合和FOLLOW集合：FIRST（S）=a，( FIRST（T）=a，( FIRST（T）=，FOLLOW（S）= )，#FOLLOW（T）= ) FOLLOW（T）= ) 從而可見改造后的文法符合LL(1)文法的充分必要條件，所以是LL(1)的。 該文法的預測分析表a(),#SS->aS->S->(T)TT->S TT->S TT->S TTT->T->,S T2、對下面的文法G：ETEE+ETFTTTFPFF*FP(E)ab（1） 計算這個文法的每個

27、非終結符的FIRST和FOLLOW。（2） 證明這個文法是LL(1)的。（3） 構造它的預測分析表。（4） 構造它的遞歸下降分析程序。3、下面文法中，哪些是LL(1)的，說明理由。（1）、SAbcAaBb（2）、SAbAaBBb（3）、SABBAAaBb（4）、SaSeBBbBeCCcCed4、對下面文法：Expr-ExprExpr(Expr)Var ExprTail-ExprVarid VarTailVarTail(Expr)（1）、構造LL(1)分析表。（2）、給出對句子id-id(id)的分析過程。5、把下面文法改寫為LL(1)的：DeclistDeclist；DeclDeclDeclI

28、dList：TypeIdListIdList，ididTypeScalarTypearray(ScalarTypeList) of TypeScalarTypeidBound.BoundBoundSign IntLiteralidSign+-ScalarTypeListScalarTypeList，ScalarTypeScalarType1、令文法G1為EE+TTTT*FFF(E)i證明E+T*F是它的一個句型，指出這個句型的所有短語，直接短語和句柄。2、考慮下面的表格結構文法G2：Sa(T)TT，SS（1） 給出(a，(a，a)和(a，a)，(a)，a)的最左和最右推導。指出(a，a)，(a

29、)，a)的規范歸約及每一步的句柄。根據這個規范歸約，給出“移進-歸約”的過程，并給出它的語法樹自下而上的構造過程。3、（1）計算練習2文法G2的FIRSTVT和LASTVT。（2）計算G2的優先關系。G2是一個算符優先文法嗎？（3）給出輸入串（a，（a，a）的算符優先分析過程。4、考慮文法：SASbASAa（1） 列出這個文法的所有LR(0)項目。（2） 構造這個文法的LR(0)項目集規范族及識別活前綴的DFA。（3） 這個文法是SLR的嗎？若是，構造出它的SLR分析表。（4） 這個文法是LALR或LR(1)的嗎？F卷答案1答：解：（1）按照T、S的順序消除左遞歸，得到文法：G(S)Sa(T)

30、TSTT，ST 對于非終結符S,T, T的遞歸子程序如下：Procedure S;Begin If sym = a or sym = Then advanceElse ifsym = (Then begin Advance ; T; If sym = ) Then advance Else errorEndElse errorEnds;Procedure T;Begin S; T;Ends;Procedure TBegin If sym = ,Then begin Advance ;S; T Endsends;2解：（1） 計算每個非終結符的FIRST集合和FOLLOW集合如下：FIRST（E

31、）=(，a，b，FIRST（E）=+，FIRST（T）=(，a，b，FIRST（T）=(，a，b，FIRST（F）=(，a，b，FIRST（F）=*，FIRST（P）=(，a，b，FOLLOW（E）=#，)FOLLOW（E）=#，)FOLLOW（T）=+，)，#FOLLOW（T）=+，)，#FOLLOW（F）=(，a，b，+，)，#FOLLOW（F）=(，a，b，+，)，#FOLLOW（P）=*，(，a，b，+，)，#（2） 本文法是LL ( 1 )文法。證明： 通過觀察可知文法中不含有左遞歸，滿足LL (1)文法定義的第一個條件。考慮下列產生式：E+ETTF*FP(E)ab因為：FIRST（

32、+E）FIRST（）=+=ØFIRST（E）FOLLOW（E）=+#，)= ØFIRST（T）FIRST（）=(，a，b，=ØFIRST（T）FOLLOW（T）=(，a，b，+，)，#=ØFIRST（*F）FIRST（）=*=ØFIRST（F）FOLLOW（F）=*(，a，b，+，)，#= ØFIRST（E）FIRST（a）FIRST（b）FIRST（）= Ø所以該文法是LL(1)文法。（3） 構造其預測分析表： 預測分析表+ * ( ) a b #EEàT EEàT EEàT EEà

33、T EEEà+EE àE ->TT àFTTàFTTàFTTàFTTTàT à TTàTàTTàTT àTTàFF àPFFàPFPàPFFàPFFF à F à*FF à FàFàFàFàFàPP à(E)PàaPàbPà （4） 構造其遞歸下降分析程序： Procedure E;Begin T ;E

34、End ;Procedure E ;Begin Ifsym = + Then begin Acvance ;E End End ;ProcedureT ;Begin F ; TEnd ;Procedure T ;Begin If sym first ( T ) Then T Else if sym = * then errorEnd ;Procedure F ;Begin If sym first ( P ) P; F;End ; Procedure F BeginIf sym = * Then begin Advance ; F EndEnd;Procedure P Begin Ifsym

35、= a orsym = b or sym = Then acvance Else if sym = ( Then begin Advance ; E ; If sym = ) Then advance Else errorEndElse error End;3解：（1） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，cFIRST（A）=a，FIRST（B）=b，FOLLOW（S）=#FOLLOW（A）=b，cFOLLOW（B）=c可見該文法滿足LL(1)文法的三個條件，是LL(1)文法。（2） 該文法不含左遞歸，計算每個非終結符的FIRST

36、集合和FOLLOW集合如下：FIRST（S）=a，bFIRST（A）=a，b，FIRST（B）=b，FOLLOW（S）=#FOLLOW（A）=bFOLLOW（B）=b考慮AaB，因為FIRST（B）FOLLOW（A）=bØ，所以該文法不是LL(1)文法。（3） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，FIRST（A）=a，FIRST（B）=b，FOLLOW（S）=#FOLLOW（A）=a，b，#FOLLOW（B）=a，b，#考慮Aa和Bb，因為FIRST（a）FOLLOW（A）=aØFIRST（b）FOLLOW（B

37、）=bØ所以該文法不是LL(1)文法。（4） 該文法不含左遞歸，計算每個非終結符的FIRST集合和FOLLOW集合如下：FIRST（S）=a，b，c，dFIRST（B）=b，c，dFIRST（C）=c，dFOLLOW（S）=e，#FOLLOW（B）=e，#FOLLOW（C）=e，#可見該文法滿足LL(1)文法的三個條件，是LL(1)文法。4解：（1）、計算每個非終結符的FIRST集合和FOLLOW集合如下：FIRST(Expr)=-，(，idFIRST(ExprTail)=-，FIRST(Var)=idFIRST(VarTail)=(，FOLLOW(Expr)=)，#FOLLOW(E

38、xprTail)=)，#FOLLOW(Var)=-，)，#FOLLOW(VarTail)=-，#構造其預測分析表如下：-id()#ExprExpr- ExprExpr ExprExpr-( Expr)ExprTailExprTail-ExprExprTailExprTailVarVarid VarTailVarTailVarTailVarTail(Expr)VarTailVarTail（2）、句子id-id(id)的分析過程如下：步驟符號棧輸入串所用產生式0# Exprid-id(id) #1# ExprTail Varid-id(id) #ExprVar ExprTail2# ExprTai

39、l VarTail idid-id(id) #Varid VarTail3# ExprTail VarTail-id(id) #4# ExprTail-id(id) #VarTail5# Expr -id(id) #ExprTail-Expr6# Expr-id(id) #7# Expr -id(id) #Expr-Expr8# Exprid(id) #9# ExprTail Varid(id) #ExprVar ExprTail10# ExprTail VarTail idid(id) #Varid VarTail11# ExprTail VarTail(id) #12# ExprTail

40、) Expr (id) #VarTail(Expr)13# ExprTail ) Expr(id) #14# ExprTail ) ) Expr (id) #15# ExprTail ) ) Exprid) #16# ExprTail ) ) ExprTal Varid) #ExprVar ExprTail17# ExprTail ) ) ExprTail VarTail idid) #Varid VarTail18# ExprTail ) ) ExprTail VarTail) #19# ExprTail ) ) ExprTail) #VarTail20# ExprTail ) ) #Exp

41、rTail21# ExprTail ) #22# ExprTail#23#ExprTailsuc5解：首先消除左遞歸，得到文法G(Declist)：DeclistDecl DeclistDeclist；Decl DeclistDeclIdList：TypeIdListid IdListIdList，id ListTypeScalarTypearray(ScalarTypeList) of TypeScalarTypeidBound.BoundBoundSign IntLiteralidSign+-ScalarTypeListScalarType ScalarTypeListScalarType

42、List，ScalarType ScalarTypeList顯然，改造后的文法沒有左公共因子，計算每個非終結符的FIRST集合和FOLLOW集合如下：FIRST(Declist)=idFIRST(Declist)=；，FIRST(Decl)=idFIRST(IdList)=idFIRST(IdList)=；，FIRST(Type)=id，+，-，IntLiteral，arrayFIRST(ScalarType)=id，+，-，IntLiteralFIRST(Bound)=id，+，-，InLiteralFIRST(Sign)=+，-，FIRST(ScalarTypeList)=id，+，-，I

43、ntLiteral FIRST(ScalarTypeList)=，FOLLOW(Declist)=#FOLLOW(Declist)=#FOLLOW(Decl)=id，；FOLLOW(IdList)=：FOLLOW(IdList)=：FOLLOW(Type)=id，；FOLLOW(ScalarType)=id，；，），FOLLOW(Bound)=id，；，），.FOLLOW(Sign)=IntLiteralFOLLOW(ScalarTypeList)=)FOLLOW(ScalarTypeList)=)顯然，改造后的文法是LL(1)的。1解：因為E=>E+T=>E+T*F，所以E+T*

44、F是該文法的一個句型。短語：E+T*F，T*F直接短語：T*F句柄：T*F2解：（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，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)，S)，S)=>(a，a)，(T)，S)=>(a，a)，(S)，S)=>(a，a)，(a)，S)=>(a，a)，(a)，a)最右推導：S=>(T)