1、第三、四章習(xí)題,P64：7,8,9,12,14,15,20,補(bǔ)充題 P81：1,2,3,4,5,2,詞法分析,正規(guī)式,自動(dòng)機(jī),正規(guī)文法,3,正規(guī)式與正規(guī)文法的轉(zhuǎn)化,: 令 VT = 對(duì)任意正規(guī)式 R 選擇一個(gè)非終結(jié)符 Z 生成規(guī)則ZR，并令 SZ； 若 a 和 b 都是正規(guī)式，對(duì)形如 Aab的規(guī)則轉(zhuǎn)換成 AaB 和 Bb； 在已轉(zhuǎn)換的文法中，將形如 Aa*b 的規(guī)則進(jìn)一步轉(zhuǎn)換成 A aA | b； 不斷利用上上面后兩條規(guī)則進(jìn)行轉(zhuǎn)換，直到每條規(guī)則最多含有一個(gè) 終結(jié)符為止。,: 將每個(gè)非終結(jié)符表示成關(guān)于它的正規(guī)式方程，獲得一個(gè)聯(lián)立方程組。 依照求解規(guī)則： 若 x = x | (或x = x+)，則

2、解為x = * 若 x = x | (或x = x+)，則解為x = * 以及正規(guī)式的分配率、交換率和結(jié)合率求關(guān)于文法開始符號(hào)的正規(guī)式 方程組的解。,4,正規(guī)式轉(zhuǎn)化為NFA(1/2),(1)引進(jìn)初始結(jié)點(diǎn) X 和終止結(jié)點(diǎn) Y，把 R 表示成拓廣轉(zhuǎn)換圖。如圖,(2)分析 R 的語法結(jié)構(gòu)，用如下規(guī)則對(duì) R 中的每個(gè)基本符號(hào)構(gòu)造 NFA。 R，構(gòu)造 NFA 如圖： R，構(gòu)造 NFA 如圖：,Ra(a)，構(gòu)造 NFA 如圖：,5,正規(guī)式轉(zhuǎn)化為NFA(2/2),若 R 是復(fù)合正規(guī)式，則按下圖的轉(zhuǎn)換規(guī)則對(duì) R 進(jìn)行分裂和加進(jìn)新結(jié)，直至每個(gè)邊上只留下一個(gè)符號(hào)（或 ）為止。,整個(gè)分裂過程中，所有新結(jié)點(diǎn)均采用不同

3、的名字，保留 X，Y 為全圖唯一初態(tài)結(jié)點(diǎn)和終態(tài)結(jié)點(diǎn),6,NFA確定化為DFA,首先將從初態(tài) S 出發(fā)經(jīng)過任意條 弧所能到達(dá)的狀態(tài)所組成的集合作為 M 的初態(tài) S，然后從 S 出發(fā)，經(jīng)過對(duì)輸入符號(hào) a 的狀態(tài)轉(zhuǎn)移所能到達(dá)的狀態(tài)(包括讀輸入符號(hào)之前或之后所有可能的 轉(zhuǎn)移所能到達(dá)的狀態(tài))所組成的集合作為 M 的新狀態(tài)，如此重復(fù)，直到不再有新的狀態(tài)出現(xiàn)為止。,從 NFA N=(Q,F,S,Z)構(gòu)造等價(jià)的DFA M=(Q,F,S,Z)的方法,7,DFA的化簡(jiǎn),將 DFA M 的狀態(tài)集 Q 分成兩個(gè)子集：終態(tài)集 F 和非終態(tài)集 F，形成初始分劃 。 對(duì) 建立新的分劃 new。對(duì) 的每個(gè)狀態(tài)子集 G 進(jìn)行如

4、下變換： 把 G 分劃成新的子集，使得 G 的兩個(gè)狀態(tài) s 和 t 屬于同一子集，當(dāng)且僅當(dāng)對(duì)任何輸入符號(hào) a，狀態(tài) s 和 t 轉(zhuǎn)換到的狀態(tài)都屬于 的同一子集。 用 G 分劃出的所有新子集替換 G，形成新的分劃 new 。 如果 new，則執(zhí)行第（4）步；否則令new，重復(fù)第（2）步。 分劃結(jié)束，對(duì)分劃中的每個(gè)狀態(tài)子集，選出一個(gè)狀態(tài)作代表，而刪去其它一切等價(jià)的狀態(tài)，并把射向其余狀態(tài)的箭弧都改為射向作為“代表”的狀態(tài)。,8,增加新初態(tài) X，與所有原初態(tài)用相連， 增加新終態(tài) Y，與所有原終態(tài)用相連， 從而構(gòu)成一個(gè)新的 FA M， 它只有一個(gè)初態(tài) X 和一個(gè)終態(tài) Y。 在X 與 Y 之間進(jìn)行弧合并：

5、,在X 和 Y之間的表達(dá)式即為所求的正規(guī)式 R。,代之以,代之以,代之以,自動(dòng)機(jī)轉(zhuǎn)化為正規(guī)式,9,正規(guī)文法轉(zhuǎn)化為自動(dòng)機(jī)(1/2),設(shè)給定一個(gè)右線性正規(guī)文法 G=(VN,VT,P,S)，則相應(yīng)的有窮自動(dòng)機(jī) M=(Q,f,q0,Z) （1）將VN中的每一個(gè)非終結(jié)符視作 M 中的一個(gè)狀態(tài)， 并增加一個(gè)新終態(tài) D，且 DVN， 令 Q=VND,Z=D,=VT,q0=S （2）對(duì) AaB（A,BVN,aVT ），令f(A,a)=B。 構(gòu)造弧 （3）對(duì) Aa（AVN,aVT ），令f(A,a)=D。 構(gòu)造弧,10,正規(guī)文法轉(zhuǎn)化為自動(dòng)機(jī)(2/2),設(shè)給定一個(gè)左線性正規(guī)文法 G=(VN,VT,P,S)，則相應(yīng)

6、的有窮自動(dòng)機(jī) M=(Q,f,q0,Z) （1）將VN中的每一個(gè)非終結(jié)符視作 M 中的一個(gè)狀態(tài)， 并增加一個(gè)初始狀態(tài) q0，且 q0VN， 令 Q=VNq0,Z=S,=VT (將文法G的開始符號(hào)S看成終態(tài)) （2）對(duì) ABa（A,BVN,aVT ）令f(B,a)=A。 構(gòu)造弧 （3）對(duì) Aa（AVN,aVT ），令f(q0,a)=A。 構(gòu)造弧,11,自動(dòng)機(jī)轉(zhuǎn)化為正規(guī)文法(1/2),設(shè)給定有窮自動(dòng)機(jī) M=(Q,f,q0,Z)，按照下述方法可 以從 M 構(gòu)造出相應(yīng)的右線性正規(guī)文法 G=(VN,VT,P,S)， 使得L(M)=L(G) (1)令 VN=Q,VT=,S=q0 (2)若f(A,a)=B且B

7、Z時(shí)， 則將規(guī)則 AaB 加到P中。 (3)若f(A,a)=B且BZ時(shí)，則將規(guī)則 AaBa 或 AaB, B 加到P中。 (4)若文法的開始符號(hào) S 是一個(gè)終態(tài)，則將規(guī)則 S 加到P中。,注意: 若終態(tài)無出弧，則去掉該非終結(jié)符,起點(diǎn)開始，考慮出??！,12,自動(dòng)機(jī)轉(zhuǎn)化為正規(guī)文法(1/2),設(shè)給定有窮自動(dòng)機(jī) M=(Q,f,q0,Z)，按照下述方法可 以從 M 構(gòu)造出相應(yīng)的左線性正規(guī)文法 G=(VN,VT,P,S)， 使得L(M)=L(G) (1)令 VN=Q,VT=,S=Z (2)若f(S,a)=A,則Aa|Sa (3)若f(A,a)=B,則BAa(AS),注意: 若初態(tài)無入弧，則去掉該非終結(jié)符,

8、終點(diǎn)開始，考慮入?。?13,習(xí)題7(1/4),7、構(gòu)造下列正規(guī)式的相應(yīng)的DFA 1(0|1)*101 解題步驟： 1.由正規(guī)式R構(gòu)造NFA N 2.構(gòu)造確定化后的DFA的狀態(tài)矩陣 3.生成確定化后的DFA的狀態(tài)轉(zhuǎn)換圖 4.化簡(jiǎn)DFA,14,習(xí)題7(2/4),由正規(guī)式構(gòu)造NFA 構(gòu)造確定化后的DFA的狀態(tài)矩陣,15,生成確定化后的DFA的狀態(tài)轉(zhuǎn)換圖,B,F,D,E,0,1,0,C,1,1,0,0,A,1,0,1,習(xí)題7(3/4),1,16,化簡(jiǎn)DFA,0,首先 M的狀態(tài)分成兩組：終態(tài)組F，非終態(tài)組A,B,C,D,E 考察A,B,C,D,E，由于A,B,C,D,E1 屬于B,C,F, 它既不包含在

9、A,B,C,D,E中也不包含在F之中，因此，應(yīng)把A,B,C,D,E一分為二。因?yàn)闋顟B(tài) E 經(jīng) 1 弧到達(dá)狀態(tài) F，而狀態(tài)A、B,C,D經(jīng) 1 弧都到達(dá) B,C，因此，應(yīng)把 E 分出來，形成A,B,C,D、E、F。 A,B,C,D0 屬于D,E,它不含在任何劃分中，因?yàn)闋顟B(tài) C 經(jīng) 0弧到達(dá)狀態(tài) E，而狀態(tài)A,B,D經(jīng) 0 弧都到達(dá) D，因此，應(yīng)把 C 分出來，形成A,B,D、C、E、F。 由于A,B,D1=B,C，它不包含在任何劃分之中，因此，應(yīng)把A,B,D一分為二。因?yàn)闋顟B(tài)B、D經(jīng) 1 弧都到達(dá) C，經(jīng) 0弧都到達(dá) D因此，應(yīng)把 A分出來，形成A、B,D、C、E、F。B,D無法再分。 至此，

10、整個(gè)分劃含有四組： A、B,D、C、E、F 。每個(gè)組都不可再分。,習(xí)題7(4/4),17,習(xí)題8(1/3),8、給出下面正規(guī)表達(dá)式 (1)以01結(jié)尾的二進(jìn)制數(shù)串; (2)能被5整除的十進(jìn)制整數(shù); (3)包含奇數(shù)個(gè)1或者奇數(shù)個(gè)0的二進(jìn)制數(shù)串; (7)不包含子串a(chǎn)bb的由a和b組成的符號(hào)串的全體。,18,習(xí)題8(2/3),解： (1)末兩位是01，其他位為0、1組成的任意的字符串。 (a|b)*表示a、b組成的任意字符串。 所以正規(guī)表達(dá)式為(0|1)*01。 (2) 若是一位數(shù)，為0或5 若是多于一位的數(shù)，為 (1|2|3|9)(0|1|2|9)*(0|5) 所以正規(guī)表達(dá)式為(1|2|3|9)(0

11、|1|2|9)*(0|5)|0|5,19,習(xí)題8(3/3),(3) 奇數(shù)個(gè)1：0*1(0|10*1)* 奇數(shù)個(gè)0：1*0(1|01*0)* 所以正則表達(dá)式為 0*1(0|10*1)*| 1*0(1|01*0)* (7)ab后只能跟a,所以可以是ab、a組成的任意符號(hào)串，即(a|ab)*。 又若以b開始，所以正則表達(dá)式為 b* (a|ab)*。,20,習(xí)題9(1/3),9、對(duì)下面的情況給出DFA以及正規(guī)表達(dá)式。 (1)0，1上的含有子串010的所有串。 解：首先必須含有010，然后首尾為0、1組成的任意字符串，所以正規(guī)式為(0|1)*010(0|1)*。,X,1,5,0,1,0,Y,2,3,4,

12、6,0,0,1,1,21,習(xí)題9(2/3),B,H,C,0,1,D,1,1,0,0,A,0,0,1,G,E,F,1,1,1,0,0,0,1,化簡(jiǎn)后的DFA：,B,A,0,E,D,0,1,0,0,1,1,1,22,習(xí)題9(3/3),(2) 0，1上不含子串010的所有串。 解：1*(0|111*)*1*,X,1,3,Y,4,2,5,6,1,1,6,6,1,0,1,1,A,C,B,E,G,D,F,H,1,0,0,0,0,0,0,0,1,1,1,1,1,1,A,B,D,0,1,1,1,0,化簡(jiǎn)后的DFA,DFA,NFA,23,習(xí)題12(1/3),12、將圖3.18的(a)和(b)分別確定化和最少化。

13、,(a),24,習(xí)題12(2/3),(a),25,已經(jīng)是確定化，對(duì)其最小化。 1:0,1,2,3,4,5 0,1a=0,1 0,1b=2,4 2,3,4,5a=1,3,0,5 2:0,1,2,4,3,5 2,4b=3,5 3,5b=2,4,習(xí)題12(3/3),26,習(xí)題14(1/2),14、構(gòu)造DFA,接收0，1上所有滿足每個(gè)1都有0直接跟在后面的字符串。 解：正規(guī)表達(dá)式為(10|0)*,27,(10|0)*,X,Y,1,0,1,2,0,0,1,0,1,0,A,B,C,習(xí)題14(2/2),28,習(xí)題15(1/3),15、給定右線性文法G： S0S|1S|1A|0B A1C|1 B0C|0 C0

14、C|1C|1|0 求出一個(gè)與G等價(jià)的左線性文法。,29,習(xí)題15(2/3),解：與文法G等價(jià)的自動(dòng)機(jī)M=(S,A,B,C,D,0,1,f,S,D) f(S,0)=S,B f(S,1)=S,A f(A,1)=C,D f(B,0)=C,D f(C,0)=C,D f(C,1)=C,D,S,A,1,0,1,B,0,0,1,1,0,0,D,C,0,1,1,30,習(xí)題15(3/3),與文法G等價(jià)的左線性文法GL=(S,A,B,C,D,0,1,f,D) DA1|B0|C0|C1 CA1|B0|C0|C1 B0|S0 A1|S1 S0|1|S0|S1,31,習(xí)題20(1/3),20、假定有正規(guī)定義式 A0a|

15、b A1A0A0 AnAn-1An-1 考慮詞形An (1)把An中所有簡(jiǎn)名都換掉，最終所得的正規(guī)式的長(zhǎng)度是多少； (2)字集An的元素是什么？把它們非形式地表示成n的函數(shù)； (3)證明識(shí)別An的DFA只需要用2n+1個(gè)狀態(tài)就足夠了。,32,習(xí)題20(2/3),解: (1)AnAn-1An-1 An-2An-2An-2An-2 An-3An-3An-3An-3An-3An-3An-3An-3 即 ，所以長(zhǎng)度為2n。 (2)f(n)=,33,習(xí)題20(3/3),(3)用歸納法證明。 當(dāng)n=0時(shí)，只需要1個(gè)狀態(tài)，即 假設(shè)當(dāng)n=k時(shí)成立，需要2k+1個(gè)狀態(tài)； Ak+1= (a|b)(a|b),S,a

16、,b,S,A,B,C,a,a,b,b,.,第2k+1個(gè)狀態(tài),D,E,a,a,b,b,所以Ak+1需要2(k+1)+1個(gè)狀態(tài)，即n=k+1 時(shí)成立。綜上所述，識(shí)別An的DFA只需要用 2n+1個(gè)狀態(tài)。,34,補(bǔ)充題,構(gòu)造a,b上的含有偶數(shù)個(gè)a且奇數(shù)個(gè)b的 正規(guī)文法。 解：左線性文法GL=(S,A,B,C,0,1,f,S) S識(shí)別偶數(shù)個(gè)a,偶數(shù)個(gè)b; A識(shí)別奇數(shù)個(gè)a,偶數(shù)個(gè)b; B識(shí)別奇數(shù)個(gè)a,奇數(shù)個(gè)b; C識(shí)別偶數(shù)個(gè)a,奇數(shù)個(gè)b.,S,a,A,a,b,b,C,B,a,a,b,b,SaA|bC| AaS|bB BaC|bA CaB|bS,35,語法分析自上而下分析(1/5),自上而下分析法,確定的

17、自上而下分析法 非確定的自上而下分析法 (帶回溯的自上而下分析法),遞歸下降分析法 預(yù)測(cè)分析法,36,語法分析自上而下分析(2/5),LL(1)文法要求： （1）文法不含左遞歸。 （2）對(duì)文法中的每一個(gè)非終極符 A， 若 A 1|2|.|n， 則 FIRST（i） FIRST（j）= （3）對(duì)文法中的每一個(gè)非終極符 A，若它存在某個(gè)候選首符集包含 ， 則 FIRST（A） FOLLOW（A）=,左遞歸的消除： PP| 改為： PP P P|,FIRST集： FIRST()= a | a, a VT 若 ， FIRST(),FOLLOW集： FOLLOW(A)=a |S .Aa.，aVT 若S.

18、A，則規(guī)定 #FOLLOW（A）,*,*,非LL(1)文法改寫為L(zhǎng)L(1)文法： 消除左遞歸和反復(fù)提取公共左因子。 提取公共左因子： A1|2|.|n|1|2|.|m 修改成： A A|1|2|.|m A1|2|.|n,37,語法分析自上而下分析(3/5),遞歸下降分析程序的構(gòu)造： 當(dāng)遇到終結(jié)符 a 時(shí)，則編寫語句 if (當(dāng)前讀到的輸入符號(hào)=a) 讀入下一個(gè)輸入符號(hào)。 當(dāng)遇到非終結(jié)符 A 時(shí)，則編寫語句調(diào)用 A. 當(dāng)遇到 A 規(guī)則時(shí)，則編寫語句 if (當(dāng)前讀到的輸入符號(hào) FOLLOW(A) ERROR。 當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式時(shí)，按LL(1)文法的條件唯一現(xiàn)在一個(gè)候選式進(jìn)行推導(dǎo)。

19、,38,實(shí)驗(yàn)二：預(yù)測(cè)分析算法的設(shè)計(jì)與實(shí)現(xiàn),預(yù)測(cè)分析器 預(yù)測(cè)分析表 分析棧 總控程序,Tj,分 析 棧 Sk,總控程序,預(yù)測(cè)分析表,輸出,39,預(yù)測(cè)分析表的構(gòu)造,1、構(gòu)造文法 G 的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集 2、構(gòu)造分析表 MA，a （1）對(duì)文法G的每個(gè)規(guī)則A，執(zhí)行第二步和第三步； （2）對(duì)每個(gè)終極符aFIRST(）,則置MA,a=A； （3）若FIRST(）,則對(duì)任何bFOLLOW（A）, 則置MA,bA； （4）把所有無定義的 MA,a 標(biāo)上“出錯(cuò)標(biāo)志” (表中用空格表示)。,40,FIRST集的構(gòu)造,若XVT，則 FIRST(X)=X。 若XVN，且有規(guī)則Xa，aVT，

20、則aFIRST(X)。 若XVN，且有規(guī)則X，則FIRST(X)中。 若有規(guī)則XY1Y2Yn，對(duì)任意的i(1in)， 當(dāng)Y1Y2Yi-1都是非終極符且Y1Y2Yi-1= (即對(duì)任何j(1ji-1)，F(xiàn)IRST(YJ)都含有)， 則把 FIRST(Yi)中的所有非-元素加到 FIRST(X)中； 特別地，若Y1Y2Yn=(即所有的FIRST(Yj)中均含有，1jn)，則FIRST（X）。 反復(fù)使用上面的規(guī)則，直到每個(gè)FIRST集不再增大為止,41,FOLLOW集的構(gòu)造,(1)對(duì)文法的開始符號(hào) S，置#于FOLOOW（S）中； (2)若AB 是一個(gè)規(guī)則，則把FIRST()-加到FOLLOW(B)中

21、； (3)若AB 是一個(gè)規(guī)則， 或AB 是一個(gè)規(guī)則，而 =，即FIRST(),則把FOLLOW(A)加至FOLLOW(B)中。 (4)反復(fù)使用上面的規(guī)則，直到每個(gè)非終結(jié)符的FOLLOW集 不再增大為止。,42,總控程序,43,預(yù)測(cè)分析的過程,若X=a=#，則宣布分析成功； 若X=a#，則將棧頂符號(hào) X（終極符）彈出，讓 IP 指針指向下一個(gè)輸入符號(hào)； 若 X 是一個(gè)非終極符，則查看分析表 M。如果分析表的 MA,a 中是一條產(chǎn)生式，則先將棧頂符號(hào) X（非終極符）彈出，然后把該產(chǎn)生式右端符號(hào)串按反序（從右到左）壓入棧中（串不入棧）。,44,習(xí)題1(1/4),1、考慮下面文法G1： Sa|(T)

22、TT,S|S （1）消去G1的左遞歸，然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序。 （2）經(jīng)過改寫的文法是否是LL（1）的？給出它的預(yù)測(cè)分析表。,45,習(xí)題1(2/4),解：（1）消去G1的左遞歸：Sa|(T) TST T ,ST| 遞歸子程序： PROCEDURE S; IF SYM=a THEN ADVANCE ELSE IF SYM= THEN ADVANCE ELSE IF SYM= ( THEN BEGIN ADVANCE T; IF SYM= ) THEN ADVANCE ELSE ERROR END ELSE ERROR;,PROCEDURE T; BEGIN S;T END;

23、PROCEDURE T; IF SYM= , THEN BEGIN ADVANCE S;T END; ELSE IF SYM) THEN ERROR,判斷輸入符號(hào)是否 屬于FOLLOW集,46,習(xí)題1(3/4),（2）FIRST(a)=a FIRST()= FIRST(T)= ( FIRST(,ST)=, FIRST()= FIRST(S)= a,( FOLLOW(S)= #, , , , ) FIRST(T)= a,( FOLLOW(T)= ) FIRST(T)= , FOLLOW(T)= ) FIRST(a)FIRST() FIRST(T)= FIRST(,ST) FIRST()= FIR

24、ST(T) FOLLOW(T)= 所以改寫后的文法是LL（1）文法。,47,習(xí)題1(4/4),預(yù)測(cè)分析表如下：,48,習(xí)題2(1/6),2、對(duì)下面的文法G： ETE E+E| TFT TT| FPF F*F| P(E)|a|b| (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLLOW。 (2)證明這個(gè)文法是LL(1)的。 (3)構(gòu)造它的預(yù)測(cè)分析表。 (4)構(gòu)造它的遞歸下降分析程序。,49,習(xí)題2(2/6),解： (1)FIRST和FOLLOW集如下表：,50,習(xí)題2(3/6),(2)FIRST(+E)FIRST()= + = FIRST(T) FIRST()= (,a,b, = FIRST

25、(*F)FIRST()= * = FIRST(E)FIRST(a) FIRST(b) FIRST()= ( a b = FIRST(E) FOLLOW(E)= FIRST(T) FOLLOW(T)= FIRST(F) FOLLOW(F)= 所以該文法是LL(1)文法。,51,習(xí)題2(4/6),(3)預(yù)測(cè)分析表為：,52,習(xí)題2(5/6),(4)遞歸下降分析程序?yàn)椋?PROCEDURE E; BEGIN T;E END; PROCEDURE T; BEGIN F;T END; PROCEDURE E; IF SYM=+ THEN BEGIN ADVANCE; E END; ELSE IF SYM

26、) AND SYM# THEN ERROR,PROCEDURE F; BEGIN P;F END; PROCEDURE T; IF SYM=a OR SYM=b OR SYM= OR SYM=( THEN BEGIN ADVANCE; T END; ELSE IF SYM) AND SYM+ AND SYM# THEN ERROR,53,習(xí)題2(6/6),PROCEDURE P; IF SYM=( THEN BEGIN ADVANCE; E; IF SYM!=) THEN ADVANCE; ELSE ERROR END ELSE IF SYM=a OR SYM=b OR SYM= THEN A

27、DVANCE; ELSE ERROR,PROCEDURE F; IF SYM=* THEN BEGIN ADVANCE; F; END ELSE IF SYM( AND SYMa AND SYMb AND SYM AND SYM+ SYM) AND SYM# THEN ERROR,54,習(xí)題3(1/3),3、下面文法那些是LL(1)文法？ (1)S Abc A a| Bb| (2)S Ab A a|B| Bb| (3)S ABBA A a | Bb| (4)S aSe|B B bBe |C CcCe|d,55,習(xí)題3(2/3),解： (1)文法無左遞歸 FIRST(a)FIRST()= a =

28、 FIRST(b)FIRST()= b = FIRST(A)FOLLOW(A)= a, b= FIRST(B)FOLLOW(B)= b, = 所以該文法是LL(1)文法。 (2)文法無左遞歸 FIRST(a)FIRST(B)FIRST()= ab, 所以該文法不是LL(1)文法。,56,習(xí)題3(3/3),(3)文法無左遞歸 FIRST(a)FIRST()= a = FIRST(b)FIRST()= b = FIRST(A)FOLLOW(A)= a, a,b, # 所以該文法不是LL(1)文法。 (4)文法無左遞歸 FIRST(aSe)FIRST(B)= a b,= FIRST(bBe)FIRS

29、T(C)= b c,d= FIRST(cCe)FIRST(d)= c d= 所以該文法是LL(1)文法。,57,習(xí)題4(1/3),4、對(duì)下面文法： Expr_Expr Expr(Expr)| Var ExprTail ExprTail_ Expr| Varid VarTail VarTail(Expr)| (1)構(gòu)造LL（1）分析表 (2)給出對(duì)句子id_ _id(id) 的分析過程,58,習(xí)題4(2/3),解： (1)FIRST集和FOLLOW集如下表：,LL(1)分析表為：,59,習(xí)題4(3/3),(2) 步驟 符號(hào)棧 輸入串 所用產(chǎn)生式,反序壓入棧,60,習(xí)題5(1/5),5、把下面文法

30、改寫為L(zhǎng)L(1)的： DeclistDeclist；Decl|Decl DeclIdList:Type IdListIdList,id|id TypeScalarType|array(ScalarTypeList) of Type ScalarTypeid|Bound.Bound BoundSign IntLiteral|id Sign+|-| ScalarTypeListScalarTypeList,ScalarType|ScalarType,61,習(xí)題5(2/5),解：消除左遞歸： DeclistDeclDeclist Declist;DeclDeclist| DeclIdList:Type IdListidIdList IdList,idIdList| TypeScalarType|array(ScalarTypeList) of Type ScalarTypeid|Bound.Bound BoundSign IntLiteral|i