第三四章習(xí)題課編譯原理講課講稿

第三(dìsān)、四章習(xí)題P64：7,8,9,12,14,15,20,補(bǔ)充(bǔchōng)題P81：1,2,3,4,5第一頁，共65頁。詞法(cífǎ)分析正規(guī)(zhèngguī)式自動機(jī)正規(guī)(zhèngguī)文法①②③④⑤⑥正規(guī)式正規(guī)文法NFADFA狀態(tài)最小

DFA詞法

分析器分裂法轉(zhuǎn)換規(guī)則子集法分劃法2第二頁，共65頁。正規(guī)(zhèngguī)式與正規(guī)(zhèngguī)文法的轉(zhuǎn)化②:令VT=∑對任意正規(guī)(zhèngguī)式R選擇一個(gè)非終結(jié)符Z生成規(guī)則ZR，并令S＝Z；若a和b都是正規(guī)(zhèngguī)式，對形如Aab的規(guī)則轉(zhuǎn)換成AaB和Bb；在已轉(zhuǎn)換的文法中，將形如Aa*b的規(guī)則進(jìn)一步轉(zhuǎn)換成AaA|b；不斷利用上上面后兩條規(guī)則進(jìn)行轉(zhuǎn)換，直到每條規(guī)則最多含有一個(gè)終結(jié)符為止。①:將每個(gè)非終結(jié)符表示成關(guān)于它的正規(guī)式方程，獲得一個(gè)聯(lián)立方程組。依照求解(qiújiě)規(guī)則：若x=x|(或x=x+)，則解為x=*若x=x|(或x=x+)，則解為x=*以及正規(guī)式的分配率、交換率和結(jié)合率求關(guān)于文法開始符號的正規(guī)式方程組的解。3第三頁，共65頁。正規(guī)(zhèngguī)式轉(zhuǎn)化為NFA(1/2)(1)引進(jìn)初始結(jié)點(diǎn)X和終止(zhōngzhǐ)結(jié)點(diǎn)Y，把R表示成拓廣轉(zhuǎn)換圖。如圖XYR(2)分析R的語法結(jié)構(gòu)，用如下規(guī)則對R中的每個(gè)基本符號(fúhào)構(gòu)造NFA。R＝，構(gòu)造NFA如圖：R＝，構(gòu)造NFA如圖：XYXYR＝a(a)，構(gòu)造NFA如圖：XYa4第四頁，共65頁。正規(guī)(zhèngguī)式轉(zhuǎn)化為NFA(2/2)若R是復(fù)合正規(guī)式，則按下圖的轉(zhuǎn)換規(guī)則對R進(jìn)行分裂(fēnliè)和加進(jìn)新結(jié)，直至每個(gè)邊上只留下一個(gè)符號（或）為止。ABr1r2ABr1Cr2代換為ABr1|r2ABr1r2代換為ABr1*ABC代換為r1整個(gè)分裂過程中，所有(suǒyǒu)新結(jié)點(diǎn)均采用不同的名字，保留X，Y為全圖唯一初態(tài)結(jié)點(diǎn)和終態(tài)結(jié)點(diǎn)5第五頁，共65頁。NFA確定(quèdìng)化為DFA首先將從初態(tài)S出發(fā)經(jīng)過任意條弧所能到達(dá)的狀態(tài)(zhuàngtài)所組成的集合作為M的初態(tài)S’，然后從S’出發(fā)，經(jīng)過對輸入符號a的狀態(tài)(zhuàngtài)轉(zhuǎn)移所能到達(dá)的狀態(tài)(zhuàngtài)(包括讀輸入符號之前或之后所有可能的轉(zhuǎn)移所能到達(dá)的狀態(tài)(zhuàngtài))所組成的集合作為M的新狀態(tài)(zhuàngtài)，如此重復(fù)，直到不再有新的狀態(tài)(zhuàngtài)出現(xiàn)為止。從NFAN=(Q,,F,S,Z)構(gòu)造(gòuzào)等價(jià)的DFAM=(Q’,,F’,S’,Z’)的方法6第六頁，共65頁。DFA的化簡將DFAM的狀態(tài)集Q分成兩個(gè)子集：終態(tài)集F和非終態(tài)集F，形成初始分劃。對建立新的分劃new。對的每個(gè)狀態(tài)子集G進(jìn)行如下變換：把G分劃成新的子集，使得G的兩個(gè)狀態(tài)s和t屬于同一子集，當(dāng)且僅當(dāng)對任何輸入符號(fúhào)a，狀態(tài)s和t轉(zhuǎn)換到的狀態(tài)都屬于的同一子集。用G分劃出的所有新子集替換G，形成新的分劃new。如果new＝，則執(zhí)行第（4）步；否則令＝new，重復(fù)第（2）步。分劃結(jié)束，對分劃中的每個(gè)狀態(tài)子集，選出一個(gè)狀態(tài)作代表，而刪去其它一切等價(jià)的狀態(tài)，并把射向其余狀態(tài)的箭弧都改為射向作為“代表”的狀態(tài)。7第七頁，共65頁。增加新初態(tài)X，與所有原初(yuánchū)態(tài)用ε相連，

增加新終態(tài)Y，與所有原終態(tài)用ε相連，

從而構(gòu)成一個(gè)新的FAM’，

它只有一個(gè)初態(tài)X和一個(gè)終態(tài)Y。在X與Y之間進(jìn)行弧合并：ACBr1r2ABr1r2r2ACBr1r3ABr1r2ABr1|r2ABr1r2*r3在X和Y之間的表達(dá)式即為所求的正規(guī)(zhèngguī)式R。代之以代之以代之以自動機(jī)轉(zhuǎn)化(zhuǎnhuà)為正規(guī)式8第八頁，共65頁。正規(guī)(zhèngguī)文法轉(zhuǎn)化為自動機(jī)(1/2)設(shè)給定一個(gè)右線性正規(guī)文法G=(VN,VT,P,S)，則相應(yīng)的有窮自動機(jī)M=(Q,,f,q0,Z)（1）將VN中的每一個(gè)非終結(jié)符視作M中的一個(gè)狀態(tài)， 并增加(zēngjiā)一個(gè)新終態(tài)D，且DVN，

令Q=VN{D},Z={D},=VT,q0=S（2）對AaB（A,BVN,aVT{}），令f(A,a)=B。

構(gòu)造弧（3）對Aa（AVN,aVT{}），令f(A,a)=D。

構(gòu)造弧ABaADa9第九頁，共65頁。正規(guī)文法(wénfǎ)轉(zhuǎn)化為自動機(jī)(2/2)設(shè)給定一個(gè)(yīɡè)左線性正規(guī)文法G=(VN,VT,P,S)，則相應(yīng)的有窮自動機(jī)M=(Q,,f,q0,Z)（1）將VN中的每一個(gè)(yīɡè)非終結(jié)符視作M中的一個(gè)(yīɡè)狀態(tài)， 并增加一個(gè)(yīɡè)初始狀態(tài)q0，且q0VN，

令Q=VN{q0},Z={S},=VT

(將文法G的開始符號S看成終態(tài))（2）對ABa（A,BVN,aVT{}）令f(B,a)=A。

構(gòu)造?。?）對Aa（AVN,aVT{}），令f(q0,a)=A。

構(gòu)造弧BAaq0Aa10第十頁，共65頁。自動機(jī)轉(zhuǎn)化(zhuǎnhuà)為正規(guī)文法(1/2)設(shè)給定有窮自動機(jī)M=(Q,,f,q0,Z)，按照下述方法可以從M構(gòu)造出相應(yīng)的右線性正規(guī)文法(wénfǎ)G=(VN,VT,P,S)，使得L(M)=L(G)(1)令VN=Q,VT=,S=q0(2)若f(A,a)=B且BZ時(shí)，

則將規(guī)則AaB加到P中。(3)若f(A,a)=B且BZ時(shí)，則將規(guī)則

AaBa

或AaB,Bε加到P中。(4)若文法(wénfǎ)的開始符號S是一個(gè)終態(tài)，則將規(guī)則

Sε加到P中。ABa注意(zhùyì):若終態(tài)無出弧，則去掉該非終結(jié)符起點(diǎn)開始，考慮出弧！11第十一頁，共65頁。自動機(jī)轉(zhuǎn)化為正規(guī)(zhèngguī)文法(1/2)設(shè)給定(ɡěidìnɡ)有窮自動機(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(A≠S)注意(zhùyì):若初態(tài)無入弧，則去掉該非終結(jié)符終點(diǎn)開始，考慮入??！12第十二頁，共65頁。習(xí)題(xítí)7(1/4)7、構(gòu)造下列正規(guī)式的相應(yīng)的DFA 1(0|1)*101解題步驟(bùzhòu)：1.由正規(guī)式R構(gòu)造NFAN2.構(gòu)造確定化后的DFA的狀態(tài)矩陣3.生成確定化后的DFA的狀態(tài)轉(zhuǎn)換圖4.化簡DFA13第十三頁，共65頁。習(xí)題(xítí)7(2/4)由正規(guī)式構(gòu)造NFA構(gòu)造確定(quèdìng)化后的DFA的狀態(tài)矩陣Y234101X11010Q’10A{X}{0,1,2}B{0,1,2}{0,2,3}{0,2}C{0,2,3}{0,2,3}{0,2,4}D{0,2}{0,2,3}{0,2}E{0,2,4}{0,2,3,Y}{0,2}F{0,2,3,Y}{0,2,3}{0,2,4}14第十四頁，共65頁。生成確定(quèdìng)化后的DFA的狀態(tài)轉(zhuǎn)換圖BFDE010C1100A101習(xí)題(xítí)7(3/4)115第十五頁，共65頁?；咲FAABlllFEC00l0lBFDE01C11100A10100首先M的狀態(tài)分成兩組：終態(tài)組{F}，非終態(tài)組{A,B,C,D,E}考察{A,B,C,D,E}，由于{A,B,C,D,E}1屬于{B,C,F},

它既不包含在{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,D}0屬于{D,E},它不含在任何劃分(huàfēn)中，因?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,D}1={B,C}，它不包含在任何劃分(huàfēn)之中，因此，應(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}無法再分。

至此，整個(gè)分劃含有四組：{A}、{B,D}、{C}、{E}、{F}。每個(gè)組都不可再分。習(xí)題(xítí)7(4/4)16第十六頁，共65頁。習(xí)題(xítí)8(1/3)8、給出下面正規(guī)表達(dá)式(1)以01結(jié)尾的二進(jìn)制數(shù)串;(2)能被5整除的十進(jìn)制整數(shù)(zhěngshù);(3)包含奇數(shù)個(gè)1或者奇數(shù)個(gè)0的二進(jìn)制數(shù)串;(7)不包含子串a(chǎn)bb的由a和b組成的符號串的全體。17第十七頁，共65頁。習(xí)題(xítí)8(2/3)解：(1)末兩位是01，其他位為0、1組成的任意(rènyì)的字符串。(a|b)*表示a、b組成的任意(rènyì)字符串。所以正規(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|1|2|…|9)*(0|5)|0|518第十八頁，共65頁。習(xí)題(xítí)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組成的任意(rènyì)符號串，即(a|ab)*。又若以b開始，所以正則表達(dá)式為b*(a|ab)*。19第十九頁，共65頁。習(xí)題(xítí)9(1/3)9、對下面的情況給出DFA以及正規(guī)表達(dá)式。(1){0，1}上的含有子串010的所有串。解：首先(shǒuxiān)必須含有010，然后首尾為0、1組成的任意字符串，所以正規(guī)式為(0|1)*010(0|1)*。X15010Y2346001120第二十頁，共65頁。習(xí)題(xítí)9(2/3)Q’01A{X,5,1}{5,1,2}{5,1}B{5,1,2}{5,1,2}{5,1,3}C{5,1}{5,1,2}{5,1}D{5,1,3}{5,1,2,4,6,Y}{5,1}E{5,1,2,4,6,Y}{5,1,2,6,Y}{5,1,3,6,Y}F{5,1,2,6,Y}{5,1,2,6,Y}{5,1,3,6,Y}G{5,1,3,6,Y}{5,1,2,4,6,Y}{5,1,6,Y}H{5,1,6,Y}{5,1,6,Y}{5,1,6,Y}BHC01D1100A001GEF111000,1化簡后的DFA：BA0ED0,10011121第二十一頁，共65頁。習(xí)題(xítí)9(3/3)(2){0，1}上不含子串010的所有(suǒyǒu)串。解：1*(0|111*)*1*X13Y425611661011ACBEGDFH10000000111111ABD01110化簡后的DFADFANFA22第二十二頁，共65頁。習(xí)題(xítí)12(1/3)12、將圖3.18的(a)和(b)分別(fēnbié)確定化和最少化。a,baa015042a3ba1abaaabbbb(b)(a)23第二十三頁，共65頁。習(xí)題(xítí)12(2/3)a,baa01(a)Q’abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}ababaCBAbaaAB24第二十四頁，共65頁。5042a3ba1abaaabbbb(b)已經(jīng)(yǐjing)是確定化，對其最小化。1:{0,1},{2,3,4,5}{0,1}a={0,1}{0,1}b={2,4}{2,3,4,5}a={1,3,0,5}2:{0,1},{2,4},{3,5}{2,4}b={3,5}{3,5}b={2,4}baa02bb3a習(xí)題(xítí)12(3/3)25第二十五頁，共65頁。習(xí)題(xítí)14(1/2)14、構(gòu)造(gòuzào)DFA,接收{(diào)0，1}上所有滿足每個(gè)1都有0直接跟在后面的字符串。解：正規(guī)表達(dá)式為(10|0)*26第二十六頁，共65頁。

(10|0)*XY10120Q’01A{X,1,Y}{1,Y}{2}B{1,Y}{1,Y}{2}C{2}{1,Y}01010ABC100AC習(xí)題(xítí)14(2/2)27第二十七頁，共65頁。習(xí)題(xítí)15(1/3)15、給定右線性文法G：S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|1|0求出一個(gè)(yīɡè)與G等價(jià)的左線性文法。28第二十八頁，共65頁。習(xí)題(xítí)15(2/3)解：與文法(wénfǎ)G等價(jià)的自動機(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}SA10,1B00,1100DC0,1129第二十九頁，共65頁。習(xí)題(xítí)15(3/3)與文法(wénfǎ)G等價(jià)的左線性文法(wénfǎ)GL=({S,A,B,C,D},{0,1},f,{D})D→A1|B0|C0|C1C→A1|B0|C0|C1B→0|S0A→1|S1S→0|1|S0|S130第三十頁，共65頁。習(xí)題(xítí)20(1/3)20、假定有正規(guī)定義式A0→a|bA1→A0A0…An→An-1An-1考慮詞形An(1)把An中所有簡名都換掉，最終所得的正規(guī)式的長度是多少；(2)字集An的元素是什么？把它們非形式地表示成n的函數(shù)；(3)證明識別An的DFA只需要用2n+1個(gè)狀態(tài)(zhuàngtài)就足夠了。31第三十一頁，共65頁。習(xí)題(xítí)20(2/3)解:(1)An＝＞An-1An-1＝＞An-2An-2An-2An-2＝＞An-3An-3An-3An-3An-3An-3An-3An-3＝＞…＝＞即，所以(suǒyǐ)長度為2n。(2)f(n)=32第三十二頁，共65頁。習(xí)題(xítí)20(3/3)(3)用歸納法證明。當(dāng)n=0時(shí)，只需要1個(gè)狀態(tài)(zhuàngtài)，即假設(shè)當(dāng)n=k時(shí)成立，需要2k+1個(gè)狀態(tài)(zhuàngtài)；Ak+1=(a|b)(a|b)SabSABCaabb...第2k+1個(gè)狀態(tài)(zhuàngtài)DEaabb所以Ak+1需要2(k+1)+1個(gè)狀態(tài)，即n=k+1時(shí)成立。綜上所述，識別An的DFA只需要用2n+1個(gè)狀態(tài)。33第三十三頁，共65頁。補(bǔ)充(bǔchōng)題構(gòu)造{a,b}上的含有偶數(shù)(ǒushù)個(gè)a且奇數(shù)個(gè)b的正規(guī)文法。解：左線性文法GL=({S,A,B,C},{0,1},f,{S})S識別偶數(shù)(ǒushù)個(gè)a,偶數(shù)(ǒushù)個(gè)b;A識別奇數(shù)個(gè)a,偶數(shù)(ǒushù)個(gè)b;B識別奇數(shù)個(gè)a,奇數(shù)個(gè)b;C識別偶數(shù)(ǒushù)個(gè)a,奇數(shù)個(gè)b.SaAabbCBaabbS→aA|bC|εA→aS|bBB→aC|bAC→aB|bS34第三十四頁，共65頁。語法分析——自上而下(zìshànɡérxià)分析(1/5)自上而下(zìshànɡérxià)分析法確定(quèdìng)的自上而下分析法非確定(quèdìng)的自上而下分析法

(帶回溯的自上而下分析法)遞歸下降分析法

預(yù)測分析法35第三十五頁，共65頁。語法分析——自上而下(zìshànɡérxià)分析(2/5)LL(1)文法要求：（1）文法不含左遞歸。（2）對文法中的每一個(gè)非終極符A，若A→α1|α2|...|αn，則FIRST（αi）FIRST（αj）=（3）對文法中的每一個(gè)非終極符A，若它存在某個(gè)候選(hòuxuǎn)首符集包含ε，則FIRST（A）FOLLOW（A）=左遞歸的消除(xiāochú)：P→Pα|β改為：P→βP’P’→αP’|εFIRST集：FIRST()={a|a…,a∈VT}若ε，ε∈FIRST()FOLLOW集：FOLLOW(A)={a|S...Aa...，a∈VT}若S...A，則規(guī)定#∈FOLLOW（A）**非LL(1)文法改寫為LL(1)文法：消除左遞歸和反復(fù)提取公共左因子。提取公共左因子：

A→α1|α2|...|αn|1|2|...|m修改成：

A→αA’|1|2|...|mA’→1|2|...|n36第三十六頁，共65頁。語法分析——自上而下(zìshànɡérxià)分析(3/5)遞歸下降分析程序的構(gòu)造：當(dāng)遇到終結(jié)符a時(shí)，則編寫語句

if(當(dāng)前讀到的輸入符號==a)讀入下一個(gè)輸入符號。當(dāng)遇到非終結(jié)符A時(shí)，則編寫語句調(diào)用A.當(dāng)遇到A規(guī)則時(shí)，則編寫語句

if(當(dāng)前讀到的輸入符號FOLLOW(A))ERROR。當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選(hòuxuǎn)式時(shí)，按LL(1)文法的條件唯一現(xiàn)在一個(gè)候選(hòuxuǎn)式進(jìn)行推導(dǎo)。37第三十七頁，共65頁。實(shí)驗(yàn)二：預(yù)測(yùcè)分析算法的設(shè)計(jì)與實(shí)現(xiàn)預(yù)測(yùcè)分析器預(yù)測(yùcè)分析表分析棧總控程序a1a2…ai…an$X…$T[j]分

析

棧

S[k]總控程序(chéngxù)

預(yù)測分析表輸出38第三十八頁，共65頁。預(yù)測分析(fēnxī)表的構(gòu)造1、構(gòu)造文法G的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集2、構(gòu)造分析表M[A，a]

（1）對文法G的每個(gè)規(guī)則A→α，執(zhí)行第二步和第三步；（2）對每個(gè)終極符a∈FIRST(α）,則置M[A,a]=A→α；（3）若ε∈FIRST(α）,則對任何b∈FOLLOW（A）,

則置M[A,b]＝A→α；（4）把所有無定義(dìngyì)的M[A,a]標(biāo)上“出錯(cuò)標(biāo)志”

(表中用空格表示)。39第三十九頁，共65頁。FIRST集的構(gòu)造(gòuzào)若X∈VT，則FIRST(X)={X}。若X∈VN，且有規(guī)則Xa…，a∈VT，則a∈FIRST(X)。若X∈VN，且有規(guī)則Xε，則ε∈FIRST(X)中。若有規(guī)則X→Y1Y2…Yn，對任意(rènyì)的i(1in)，

當(dāng)Y1Y2…Yi-1都是非終極符且Y1Y2…Yi-1=>ε

(即對任何j(1ji-1)，F(xiàn)IRST(YJ)都含有ε)，

則把FIRST(Yi)中的所有非ε-元素加到FIRST(X)中；

特別地，若Y1Y2…Yn=>ε(即所有的FIRST(Yj)中均含有ε，1jn)，則ε∈FIRST（X）。反復(fù)使用上面的規(guī)則，直到每個(gè)FIRST集不再增大為止40第四十頁，共65頁。FOLLOW集的構(gòu)造(gòuzào)(1)對文法的開始符號S，置‘#’于FOLOOW（S）中；(2)若A→αB是一個(gè)規(guī)則，則把FIRST()-{ε}加到FOLLOW(B)中；(3)若A→αB是一個(gè)規(guī)則，

或A→αB是一個(gè)規(guī)則，而=>ε，即ε∈FIRST(),則把FOLLOW(A)加至FOLLOW(B)中。(4)反復(fù)使用上面(shàngmiɑn)的規(guī)則，直到每個(gè)非終結(jié)符的FOLLOW集不再增大為止。41第四十一頁，共65頁。總控程序(chéngxù)42第四十二頁，共65頁。預(yù)測(yùcè)分析的過程若X=a=‘#’，則宣布分析(fēnxī)成功；若X=a‘#’，則將棧頂符號X（終極符）彈出，讓IP指針指向下一個(gè)輸入符號；若X是一個(gè)非終極符，則查看分析(fēnxī)表M。如果分析(fēnxī)表的M[A,a]中是一條產(chǎn)生式，則先將棧頂符號X（非終極符）彈出，然后把該產(chǎn)生式右端符號串按反序（從右到左）壓入棧中（ε串不入棧）。43第四十三頁，共65頁。習(xí)題(xítí)1(1/4)1、考慮(kǎolǜ)下面文法G1：S→a|∧|(T)T→T,S|S（1）消去G1的左遞歸，然后對每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序。（2）經(jīng)過改寫的文法是否是LL（1）的？給出它的預(yù)測分析表。44第四十四頁，共65頁。習(xí)題(xítí)1(2/4)解：（1）消去(xiāoqù)G1的左遞歸：S→a|∧|(T)T→ST’T’→,ST’|ε遞歸子程序：PROCEDURES;IFSYM=‘a(chǎn)’THENADVANCEELSEIFSYM=‘∧’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCET;IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;PROCEDURET;BEGINS;T’END;PROCEDURET’;IFSYM=‘,’THENBEGINADVANCES;T’END;ELSEIFSYM<>‘)’THENERROR判斷輸入(shūrù)符號是否屬于FOLLOW集45第四十五頁，共65頁。習(xí)題(xítí)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(ε)=ФFIRST(T’)∩FOLLOW(T’)=Ф所以改寫(gǎixiě)后的文法是LL（1）文法。46第四十六頁，共65頁。習(xí)題(xítí)1(4/4)預(yù)測分析(fēnxī)表如下：47第四十七頁，共65頁。習(xí)題(xítí)2(1/6)2、對下面(xiàmian)的文法G：E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLLOW。(2)證明這個(gè)文法是LL(1)的。(3)構(gòu)造它的預(yù)測分析表。(4)構(gòu)造它的遞歸下降分析程序。48第四十八頁，共65頁。習(xí)題(xítí)2(2/6)解：(1)FIRST和FOLLOW集如下(rúxià)表：49第四十九頁，共65頁。習(xí)題(xítí)2(3/6)(2)FIRST(+E)∩FIRST(ε)={+}∩{ε}=ФFIRST(T)∩FIRST(ε)={(,a,b,∧}∩{ε}=ФFIRST(*F’)∩FIRST(ε)={*}∩{ε}=ФFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(∧)={(}∩{a}∩∩{∧}=ФFIRST(E’)∩FOLLOW(E’)=ФFIRST(T’)∩FOLLOW(T’)=ФFIRST(F’)∩FOLLOW(F’)=Ф所以(suǒyǐ)該文法是LL(1)文法。50第五十頁，共65頁。習(xí)題(xítí)2(4/6)(3)預(yù)測(yùcè)分析表為：51第五十一頁，共65頁。習(xí)題(xítí)2(5/6)(4)遞歸下降(xiàjiàng)分析程序?yàn)椋篜ROCEDUREE;BEGINT;E’END;PROCEDURET;BEGINF;T’END;PROCEDUREE’;IFSYM=‘+’THENBEGINADVANCE;EEND;ELSEIFSYM<>‘)’ANDSYM<>‘#’THENERRORPROCEDUREF;BEGINP;F’END;PROCEDURET’;IFSYM=‘a(chǎn)’ORSYM=‘b’ORSYM=‘∧’ORSYM=‘(’THENBEGINADVANCE;TEND;ELSEIFSYM<>‘)’ANDSYM<>‘+’ANDSYM<>‘#’

THENERROR52第五十二頁，共65頁。習(xí)題(xítí)2(6/6)PROCEDUREP;IFSYM=‘(’THENBEGINADVANCE;E;IFSYM!=‘)’THENADVANCE;ELSEERRORENDELSEIFSYM=‘a(chǎn)’ORSYM=‘b’ORSYM=‘∧’THENADVANCE;ELSEERRORPROCEDUREF’;IFSYM=‘*’THENBEGINADVANCE;F’;ENDELSEIFSYM<>‘(’ANDSYM<>‘a(chǎn)’ANDSYM<>‘b’ANDSYM<>‘∧’ANDSYM<>‘+’SYM<>‘)’ANDSYM<>‘#’THENERROR53第五十三頁，共65頁。習(xí)題(xítí)3(1/3)3、下面(xiàmian)文法那些是LL(1)文法？(1)S→AbcA→a|εB→b|ε(2)S→AbA→a|B|εB→b|ε(3)S→ABBAA→a|εB→b|ε(4)S→aSe|BB→bBe|CC→cCe|d54第五十四頁，共65頁。習(xí)題(xítí)3(2/3)解：(1)文法無左遞歸FIRST(a)∩FIRST(ε)={a}∩{ε}=ФFIRST(b)∩FIRST(ε)=∩{ε}=ФFIRST(A)∩FOLLOW(A)={a,ε}∩=ФFIRST(B)∩FOLLOW(B)={b,ε}∩Ф=Ф所以(suǒyǐ)該文法是LL(1)文法。(2)文法無左遞歸FIRST(a)∩FIRST(B)∩FIRST(ε)={a}∩{b,ε}∩{ε}≠Ф所以(suǒyǐ)該文法不是LL(1)文法。55第五十五頁，共65頁。習(xí)題(xítí)3(3/3)(3)文法(wénfǎ)無左遞歸FIRST(a)∩FIRST(ε)={a}∩{ε}=ФFIRST(b)∩FIRST(ε)=∩{ε}=ФFIRST(A)∩FOLLOW(A)={a,ε}∩{a,b,#}≠Ф所以該文法(wénfǎ)不是LL(1)文法(wénfǎ)。(4)文法(wénfǎ)無左遞歸FIRST(aSe)∩FIRST(B)={a}∩{b,ε}=ФFIRST(bBe)∩FIRST(C)=∩{c,d}=ФFIRST(cCe)∩FIRST(d)={c}∩yuyvqlz=Ф所以該文法(wénfǎ)是LL(1)文法(wénfǎ)。56第五十六頁，共65頁。習(xí)題(xítí)4(1/3)4、對下面(xiàmian)文法：Expr→_ExprExpr→(Expr)|VarExprTailExprTail→_Expr|εVar→idVarTailVarTail→(Expr)|ε(1)構(gòu)造LL（1）分析表(2)給出對句子id__id((id))的分析過程57第五十七頁，共65頁。習(xí)題(xítí)4(2/3)解：(1)FIRST集和FOLLOW集如下(rúxià)表：LL(1)分析(fēnxī)表為：58第五十八頁，共65頁。習(xí)題(xítí)4(3/3)(2)步驟符號棧輸入(shūrù)串所用產(chǎn)生式反序壓入棧59第五十九頁，共65頁。習(xí)題(xítí)5(1/5)5、把下面(xiàmian)文法改寫為LL(1)的：Declist→Declist；Decl|DeclDecl→IdList:TypeIdList→IdList,id|idType→ScalarType|array(ScalarTypeList)ofTypeScalarType→id|Bound..BoundBound→SignIntLiteral|idSign→+|-|εScalarTypeList→ScalarTypeList