編譯原理例題與習(xí)題解答課件

14三月2024編譯原理例題與習(xí)題解答回顧程序語言的定義一個(gè)程序語言是一個(gè)記號(hào)系統(tǒng),它主要由以下方面定義：語法語義

每個(gè)句子構(gòu)成的規(guī)律研究語言

每個(gè)句子的含義語法語義2語法={詞法規(guī)則+語法規(guī)則}詞法規(guī)則：單詞符號(hào)的形成規(guī)則。單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。描述工具：正規(guī)式和有限自動(dòng)機(jī)理論語法規(guī)則：語法單位的形成規(guī)則。語法單位通常包括：表達(dá)式、語句、子程序、過程、函數(shù)、程序等;描述工具：上下文無關(guān)文法回顧3標(biāo)識(shí)符與名字標(biāo)識(shí)符：以字母開頭的，由字母數(shù)字組成的字符串。標(biāo)識(shí)符與名字兩者有本質(zhì)區(qū)別：標(biāo)識(shí)符是語法概念名字有確切的意義和屬性回顧4上下文無關(guān)文法的定義：一個(gè)上下文無關(guān)文法G是一個(gè)四元式G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT

VN=

S：文法的開始符號(hào)，S

VNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P，P

VN，(VT

VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次?；仡?假定G是一個(gè)文法，S是它的開始符號(hào)。如果S

，則稱

是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G)L(G)=｛

|S

&

∈VT*｝文法產(chǎn)生語言*+回顧6定義：如果一個(gè)文法存在某個(gè)句子對應(yīng)兩顆不同的語法樹，則說這個(gè)文法是二義的。語言的二義性：一個(gè)語言是二義性的，如果對它不存在無二義性的文法?？赡艽嬖贕和G’，一個(gè)為二義的，一個(gè)為無二義的。但L(G)=L(G’)回顧文法和語言的二義性7例題2.1：有一個(gè)文法G=({S,A,B},{a,b},P,S),其中P:S

aB|bAA

a|aS|bAAB

b|bS|aBB采用最左推導(dǎo)產(chǎn)生句子aabbab并畫出相應(yīng)的語法樹。S

aB

aaBB

aabSB

aabbAB

aabbaB

aabbabSaBaBBbSbbAa8例題2.2試構(gòu)造生成語言

L={anbnci|n

1,i0}的文法分析：要求a和b的個(gè)數(shù)一樣多，并至少為一個(gè)，而c的個(gè)數(shù)為0個(gè)以上即可，所以可以用一個(gè)終結(jié)符去生成anbn串，用另一個(gè)非終結(jié)符去生成ci。G(Z):ZABAaAb|abBcB|9例題2.3請證實(shí)文法G(E):E

EiT|TT

T+F|iF|FF

E*|(是一個(gè)二義文法。10P36-6.文法G6為:N→D|NDD→0|1|2|3|4|5|6|7|8|9（1）G6的語言L(G6)是什么?G6的語言是：0~9的數(shù)字組成的任意非空數(shù)字串L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+}（2）給出句子0127、34和568的最左和最右推導(dǎo)。11注意：1)步驟，和的區(qū)別；2)不能寫為→解：0127的最左推導(dǎo)：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推導(dǎo)：NNDN7ND7N27ND27N127D1270127+P36-7寫一文法,使其語言是奇數(shù)集,但不允許出現(xiàn)以0打頭的奇數(shù)。解:將奇數(shù)劃分為三個(gè)部分：最高位允許出現(xiàn)1～9,用非終結(jié)符B表示;中間部分可出現(xiàn)任意多位數(shù)字0～9,每一位用非終結(jié)符D表示;最低位只出現(xiàn)1,3,5,7,9,用A表示。由于中間部分可任意位,故需另引入一非終結(jié)符M,它包括最高位和中間部分。13MB…最高位中間位DDDA最低位14解:奇數(shù)集文法G[N]為:G=({0,1,…,9},{N,A,M,B,D},N,ξ)ξ:N→A|MAM→B|MDA→1|3|5|7|9B→1|2|3|4|5|6|7|8|9D→0|B158.令文法為E→T|E+T|E-TT→F|T*F|T/FF→(E)|i

(1)給出i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo)。解：此處僅以i*(i+i)為例給出答案最左推導(dǎo)ETT*FF*F

i*Fi*(E)i*(E+T)

i*(T+T)

i*(F+T)

i*(i+T)

i*(i+F)

i*(i+i)

最右推導(dǎo)ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)

T*(i+i)

F*(i+i)

i*(i+i)

8.令文法為E→T|E+T|E-TT→F|T*F|T/FF→(E)|iEE-TE-TTFFiFiii-i-i的語法樹(2)給出i+i+i、i+i*i和i-i-i的語法樹。EE+TE+TTFFiFiii+i+i的語法樹i+i*i的語法樹EE+TTTFFiFii*注意：樹枝和符號(hào)均不可隨意增減！9、證明文法:S→iSeS|iS|i

是二義的。二義性的含義:如果文法存在某個(gè)句子對應(yīng)兩棵以上不同的語法樹，或者兩種以上不同的最左/右推導(dǎo)，則稱這個(gè)文法是二義的。首先：找到此文法對應(yīng)的一個(gè)句子iiiei其次：構(gòu)造與之對應(yīng)的兩棵語法樹SiSeSiSiiSiSiSeSii結(jié)論：因?yàn)樵撐姆ù嬖诰渥觟iiei對應(yīng)兩棵不同的語法樹，因而該文法是二義的。1810.把下面文法改寫成無二義性的文法S->SS|(S)|()解答：S->TS|TT->(S)|()19L2={aibncn|n≥1,i≥0}G2(S):S→ABA→aA|εB→bBc|bcL3={anbnambm|m,n≥0}G3(S):S→ABA→aAb|εB→aBb|ε11、給出下面語言的相應(yīng)文法20L4={1n0m1m0n|n,m≥0}可以看成是兩部分：剩下兩邊的部分就是：S→1S0中間部分是0m1m：A→0A1|ε所以G4[S]可以寫為：S→1S0|AA→0A1|ε|A21例題與習(xí)題解答

第三章221.

假定NFAM=<S,

,

,S0,F>，我們對M的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造：1)引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y，X,Y

S，從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條

箭弧，從F中任意狀態(tài)結(jié)點(diǎn)連一條

箭弧到Y(jié)。2)對M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行替換，其中k是新引入的狀態(tài)。非確定有限自動(dòng)機(jī)狀態(tài)圖的改造23代之為ikABjijAB代之為ijA|BijBA代之為ijA*ik

jA按下面的三條規(guī)則對V進(jìn)行分裂:逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為

上的一個(gè)字符或

，最后得到一個(gè)NFAM’，顯然L(M’)=L(M)24確定有限自動(dòng)機(jī)的確定化——采用子集法設(shè)I是M’的狀態(tài)集的一個(gè)子集，定義I的

-閉包-closure(I)為:i)若sI，則s-closure(I)；ii)若sI，則從s出發(fā)經(jīng)過任意條

弧而能到達(dá)的任何狀態(tài)s’都屬于-closure(I)即：-closure(I)=I{s’|從某個(gè)sI出發(fā)經(jīng)過任意條

弧能到達(dá)s’}25設(shè)a是

中的一個(gè)字符，定義Ia=-closure(J)其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)集合。把確定化的過程:不失一般性，設(shè)字母表只包含兩個(gè)a和b，我們構(gòu)造一張表:26對一個(gè)DFAM最少化的基本思想:把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。DFAM最少化27具體做法:對M的狀態(tài)集進(jìn)行劃分首先，把S劃分為終態(tài)和非終態(tài)兩個(gè)子集，形成基本劃分

。假定到某個(gè)時(shí)候，

已含m個(gè)子集，記為

={I(1)，I(2)，

，I(m)}，檢查

中的每個(gè)子集看是否能進(jìn)一步劃分:對某個(gè)I(i)，令I(lǐng)(i)={s1,s2,

,sk}，若存在一個(gè)輸入字符a使得Ia(i)

不會(huì)包含在現(xiàn)行

的某個(gè)子集I(j)中，則至少應(yīng)把I(i)分為兩個(gè)部分。28例如，假定狀態(tài)s1和s2經(jīng)a弧分別到達(dá)t1和t2，而t1和t2屬于現(xiàn)行

中的兩個(gè)不同子集，說明有一個(gè)字

，t1讀出

后到達(dá)終態(tài)，而t2讀出

后不能到達(dá)終態(tài)，或者反之，那么對于字a

，s1讀出a

后到達(dá)終態(tài)，而s2讀出a

不能到達(dá)終態(tài)，或者反之，所以s1和s2不等價(jià)。s1t1as2t2a

i

j29例題3.1給出下面描述的正規(guī)表達(dá)式以01結(jié)尾的二進(jìn)制數(shù)串能被5正除的十進(jìn)制整數(shù)包含奇數(shù)個(gè)1或者奇數(shù)個(gè)0的二進(jìn)制數(shù)串30例題3.2構(gòu)造下面正規(guī)式相應(yīng)的DFA

1(0|1)*101步驟:①.根據(jù)正規(guī)式畫出對應(yīng)的狀態(tài)轉(zhuǎn)換圖;②.根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣;③.根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到重命名后的狀態(tài)轉(zhuǎn)換矩陣;④.根據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的DFA.311(0|1)*101①.狀態(tài)轉(zhuǎn)換圖

abadb1(0|1)*101

a1(0|1)*101

dcef1εε01101ggg32②.狀態(tài)轉(zhuǎn)換矩陣II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1ab

dcef1εε0101g33II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}③.重命名后的狀態(tài)轉(zhuǎn)換矩陣S01A(始態(tài))ΦBBCDCCDDEDECF(終態(tài))F(終態(tài))ED

AB10C1D010E10101F④.DFA34例題3.3設(shè)M=({x,y},{a,b},f,x,{y})，其中f定義如下：f(x,a)={x,y}f(x,b)={y}f(y,a)=φf(y,b)={x,y}請構(gòu)造對應(yīng)的確定有限自動(dòng)機(jī)。35【解答】對照自動(dòng)機(jī)的定義，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)。先畫出NFAM相應(yīng)的狀態(tài)圖，36用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣IIaIb{x}{x,y}{y}{y}-{x,y}{x,y}{x,y}{x,y}37重命名后的狀態(tài)轉(zhuǎn)換矩陣Sab0211-222238391(1010*|1(010)*1)*0ab

dc1εε0e0101fghiεε01110jklmnεε①.狀態(tài)轉(zhuǎn)換圖P64-7.構(gòu)造下列正規(guī)式相應(yīng)的DFA。

40②.狀態(tài)轉(zhuǎn)換矩陣II

0I

1{0}Φ{1,2,3}{1,2,3}{4}{5,9,10,11}{5,9,10,11}{6,12}{2,3}{6,12}Φ{2,3,7,8,13}{2,3}{4}{5,9,10,11}{2,3,7,8,13}{2,3,4,8,10,11}{5,9,10,11}{2,3,4,8,10,11}{2,3,4,8,12}{2,3,5,9,10,11}{2,3,4,8,12}{2,3,4,8}{5,9,10,11,13}{2,3,5,9,10,11}{4,6,12}{2,3,5,9,10,11}{2,3,4,8}{2,3,4,8}{5,9,10,11}{5,9,10,11,13}{6,10,11,12}{2,3}{4,6,12}Φ{2,3,7,8,13}{6,10,11,12}{12}{2,3,7,8,13}{12}Φ{13}{13}{10,11}Φ{10,11}{12}{2,3}41③.重命名后的狀態(tài)轉(zhuǎn)換矩陣II

0I

11Φ22344565Φ7634784891091112101310111141214613Φ71415715Φ161617Φ17156④.DFA428、給出下面正規(guī)表達(dá)式（4）英文字母組成的所有符號(hào)串，要求符號(hào)串中的字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（5）沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體。令ri=i|,i=0,1,2,...,9R0|R1|R2|...|R9記為P(0,1,2...,9)表示0,1,2...,9的全排列

43（6）最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串全體(7)不包含子串a(chǎn)bb的由a和b組成的符號(hào)串的全體b*(a|ab)*4412、將圖3.18的(a)和(b)分別確定化和最少化。(a)aaa,b10

①.狀態(tài)轉(zhuǎn)換矩陣IIaIb

{0}{0,1}{1}{1}{0,1}{0,1}{1}{0}φ②.重命名后的狀態(tài)轉(zhuǎn)換矩陣IIaIb

01221120φ0

a2baba③.DFA④.最小化Π0=({0,1},{2})1{0,1}a={1}{0,1}b={2}因此，不能再分0

2baa45023145

aaaabbbbbbaa(b)這道題實(shí)質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化Π：{2，3，4，5}{0，1}{2，3，4，5}a={0，1，3，5}分屬兩區(qū)，所以分為{2，4}{3，5}{0，1}a={1}{0，1}b={2，4}所以0，1等價(jià){2，4}a={0，1}{2，4}b={3，5}所以2，4等價(jià){3，5}a={3，5}{3，5}b={2，4}所以3，5等價(jià)所以分為{0，1}{2，4}{3，5}

023aabbba46P64-14.構(gòu)造一個(gè)DFA，它接受{0,1}上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構(gòu)造NFA，再把NFA確定化和最小化。47(1)先寫出滿足條件的正規(guī)式正規(guī)式:(10|0)*

(2)NFA:確定化:YX10ε0ε1201001012II0I1{X,1,Y}{1,Y}{2}

{1,Y}{1,Y}{2}{2}{1,Y}

II0I1初終0

12

終11

2

2

1

DFA:4801001012DFA:10010DFA:(最簡化)49例題與習(xí)題解答

第四章50源程序單詞符號(hào)取下一單詞...語法分析樹詞法分析器語法分析器符號(hào)表編譯程序后續(xù)部分語法分析器在編譯程序中的地位51自上而下分析法(Top-down)基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對輸入串的識(shí)別。預(yù)測分析程序優(yōu)點(diǎn)：直觀、簡單和宜于手工實(shí)現(xiàn)。52困難和難點(diǎn):分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)時(shí)，不得不“回溯”。文法左遞歸問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。53左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為 P→P

|

其中

不以P開頭。我們可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：P→

P

P

→

P

|

左遞歸變右遞歸54間接左遞歸例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a雖沒有直接左遞歸，但S、Q、R都是左遞歸的S

Qc

Rbc

Sabc潛在左遞歸即形如：N->αN而αε55消除左遞歸的算法:1.把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，…，Pn；按此順序執(zhí)行；2.FORi:=1TOnDOBEGIN

FORj:=1TOi-1DO將Pj代入Pi的產(chǎn)生式（若可代入的話）消除關(guān)于Pi規(guī)則的直接左遞歸性END3.化簡由2所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。56消除回溯、提左因子為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。57令G是一個(gè)不含左遞歸的文法，對G的所有非終結(jié)符的每個(gè)候選

定義它的終結(jié)首符集FIRST(

)為：特別是，若，則規(guī)定

FIRST(

)。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選

i和

jFIRST(

i)∩FIRST(

j)＝

當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的

。58如何把一個(gè)文法改造成任何非終結(jié)符的所有侯選式的首符集兩兩不相交？提取公共左因子:假定關(guān)于A的規(guī)則是A→

1|

2|…|

n|

1|

2|…|

m (其中，每個(gè)

不以

開頭)那么，可以把這些規(guī)則改寫成A→

A

|

1|

2|…|

mA

→

1|

2|…|

n經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。59構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸，2.對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A→

1|

2|…|

n則FIRST(

i)∩FIRST(

j)＝

(i

j)3.對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含

，則FIRST(

i)∩FOLLOW(A)=

i=1,2,...,n如果一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法。 LL(1)文法60假定S是文法G的開始符號(hào)，對于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定＃

FOLLOW(A)FOLLOW提醒：要掌握構(gòu)造First和Follow集合的方法61遞歸下降分析程序構(gòu)造在不含左遞歸和每個(gè)非終結(jié)符的所有候選式的終結(jié)首符集都兩兩不相交條件下，構(gòu)造一個(gè)不帶回溯的自上而下分析程序，該分析程序由一組遞歸過程組成，每個(gè)過程對應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。62預(yù)測分析程序使用一張分析表和一個(gè)棧同樣可實(shí)現(xiàn)遞歸下降分析，用這種方法實(shí)現(xiàn)的語法分析程序叫預(yù)測分析程序……a……﹟總控程序預(yù)測分析表MX…#輸出棧輸入串63分析表M[A，a]的構(gòu)造構(gòu)造FIRST(

)和FOLLOW(A)構(gòu)造分析表M[A，a]64在對文法G的每個(gè)非終結(jié)符A及其任意候選

都構(gòu)造出FIRST(

)和FOLLOW(A)之后，現(xiàn)在可以用它們來構(gòu)造G的分析表M[A，a]。1.對文法G的每個(gè)產(chǎn)生式A→

執(zhí)行第2步和第3步；2.對每個(gè)終結(jié)符a

FIRST(

)，把A→

加至M[A，a]中；3.若

FIRST(

)，則對任何b

FOLLOW(A)把A→

加至M[A，b]中。4.把所有無定義的M[A，a]標(biāo)上“出錯(cuò)標(biāo)志”。65總控程序根據(jù)現(xiàn)行棧頂符號(hào)X和當(dāng)前輸入符號(hào)a，執(zhí)行下列三種動(dòng)作之一:1.若X＝a＝‘?！?，則宣布分析成功，停止分析。2.若X＝a

‘＃’，則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。663.若X是一個(gè)非終結(jié)符，則查看分析表M。若M[X，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧(若右部符號(hào)為

，則意味不推什么東西進(jìn)棧)。若M[X，a]中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序ERROR。如：M[X，a]={X—＞UVW},就用WVU（U在頂）替換棧頂?shù)腦作為輸出；如：M[X，a]=error，則調(diào)用error程序。671.考慮下面文法G1:S→a|^|(T)T→T，S|S(1)消去G1的左遞歸。然后對每個(gè)非終結(jié)符,寫出不帶回溯的遞歸子程序。解(1)消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε練習(xí)解答68解(1)不帶回溯的遞歸子程序:S→a|^|(T)ProcedureS;Beginifsym=‘a(chǎn)’orsym=‘^’thenadvanceelseifsym=‘(‘thenbeginadvance;T;ifsym=‘)’thenadvanceelseerrorendelseerrorEnd;解(1)

不帶回溯的遞歸子程序:T→ST’ProcedureT;BeginS;T’;end;

解(1)不帶回溯的遞歸子程序:T’→,ST’|εprocedureT’;beginifsym=‘,’thenbeginadvance;S;T’;endEnd;(2)經(jīng)改寫后的文法是否是LL(1)的?給出它的預(yù)測分析表。消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε因?yàn)镚1’:①文法不含左遞歸;②對S→a|^|(T)FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③對T’→,ST’|εFIRST(,ST’)={,},FIRST(ε)={ε},其交集為空。但ε∈FIRST(T’)=FIRST(,ST’)∪FIRST(ε)={，,ε},然而，F(xiàn)OLLOW(T’)={)}FIRST(T’)={，,ε}，兩者不相交。所以，G1’是LL(1)文法。構(gòu)造G1’的預(yù)測分析表:①對S→a|^|(T)②對T→ST’FIRST(a)={a}FIRST(ST’)={a,^,(}FIRST(^)={^}③對T’→,ST’|εFIRST((T))={(}FIRST(,ST’)={,}

FOLLOW(T’)={)}

a^(),#SS→aS→^S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’722、對下面的文法G：ETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。（2）證明這個(gè)文法是LL（1）的。（3）構(gòu)造它的預(yù)測分析表。（4）構(gòu)造它的遞歸下降分析程序。73解：（1）計(jì)算FIRST與FOLLOW集FIRST(P)={(,a,b,^}FIRST(F’)={*,

}FIRST(F)=FIRST(P)={(,a,b,^}FIRST(T’)=FIRST(T){}={(,a,b,^,

}FIRST(T)=FIRST(F)={(,a,b,^}FIRST(E’)={+,}FIRST(E)=FIRST(T)={(,a,b,^}FOLLOW(E)={),#}FOLLOW(E’)=FOLLOW(E)={),#}FOLLOW(T)=FIRST(E’)\FOLLOW(E)={+,),#}FOLLOW(T’)=FOLLOW(T)=={+,),#}FOLLOW(F)=FIRST(T’)\FOLLOW(T)={(,a,b,^,+,),#}FOLLOW(F’)=FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(P)=FIRST(F’)\FOLLOW(F)={*,(,a,b,^,+,),#}ETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾74FIRSTFOLLOWE(,a,b,^),#E’+,),#T(,a,b,^+,),#T’(,a,b,^,

+,),#F(,a,b,^(,a,b,^,+,),#F’*,

(,a,b,^,+,),#P),a,b,^*,(,a,b,^,+,),#75（2）證明這個(gè)文法是LL（1）的。對產(chǎn)生式P(E)｜a｜b｜^，有FIRST((E))FISRT(a)FIRST(b)FIRST(^)=對產(chǎn)生式E’＋E｜

FIRST(+E)FOLLOW(E’)={+}{),#}=對產(chǎn)生式T’T｜

FIRST(T)FOLLOW(T’)=

{(,a,b,^}{+,),#}=對產(chǎn)生式F‘*F’｜

FIRST（*F’)FOLLOW(F’)={*}{(,a,b,^,+,),#}=文法不含左遞歸。綜上i,ii,iii可知，文法G是LL（1）的。ETE‘E’＋E｜

TFT‘T’T｜

FPF‘F’*F‘｜

P(E)｜a｜b｜＾76（3）構(gòu)造預(yù)測分析表。（ab^)+*#ETE’TE’TE’TE’E’

+E

TFT’FT’FT’FT’T’TTTT

FPF’PF’PF’PF’F’

*F’

P(E)ab^77（1）設(shè)置過程advance為讀下一個(gè)單詞送全程變量（2）設(shè)置過程error為錯(cuò)誤處理程序1.主程序Beginadvance;E;End2.E過程ProcedureEBeginT;E’;end（4）構(gòu)造遞歸下降分析程序。ETE‘E’＋E｜