編譯原理課后習(xí)題解答.doc

4a127bc8a3b06af203f32b386ef05472.pdf1/27/2020 Page 23 of 23第一章 引言1解釋下列名詞 源程序，目標(biāo)程序，翻譯程序，匯編程序，編譯程序，遍 答： 源程序： 由匯編語(yǔ)言或高級(jí)程序語(yǔ)言編寫的程序。 目標(biāo)程序：由目標(biāo)語(yǔ)言編寫的程序。 翻譯程序：把源程序轉(zhuǎn)化為目標(biāo)程序的程序。 匯編程序：把由匯編語(yǔ)言編寫的源程序轉(zhuǎn)換成目標(biāo)程序(由機(jī)器語(yǔ)言編寫)的翻譯程序。 編譯程序：把由高級(jí)程序語(yǔ)言編寫的源程序轉(zhuǎn)換為一臺(tái)具體計(jì)算機(jī)的機(jī)器語(yǔ)言或匯編語(yǔ)言程序的翻譯程序。 遍：對(duì)源程序或源程序的中間形式從頭到尾掃描一遍，并做有關(guān)的加工處理，生成新的源程序的中間形式或目標(biāo)程序。2典型的編譯程序可劃分為哪幾個(gè)主要的邏輯部分？各部分的主要功能是什么？ 答：典型的編譯程序可劃分7個(gè)主要的邏輯部分（模塊）。 詞法分析 將字符串形式的源程序分解為具有獨(dú)立語(yǔ)法語(yǔ)意的單詞符 號(hào)（Token）; 語(yǔ)法分析 從詞法分析程序取得源程序，并將一個(gè)或多個(gè)單詞組合為 語(yǔ)言的各種語(yǔ)法類。 語(yǔ)義分析 確定源程序的意義（語(yǔ)義）。 代碼生成 將源程序的中間形式轉(zhuǎn)化為匯編語(yǔ)言或機(jī)器語(yǔ)言。 代碼優(yōu)化 獲得更高效的目標(biāo)程序。 出錯(cuò)出理 對(duì)源程序的錯(cuò)誤精確定位并能夠跳過(guò)錯(cuò)誤繼續(xù)編譯。 符號(hào)表管理 保存每個(gè)標(biāo)志符及其屬性，并保存過(guò)程名及其參數(shù)。 注意：區(qū)分編譯過(guò)程的5個(gè)階段和編譯程序的7個(gè)邏輯組成部分。第二章 文法和語(yǔ)言的概念和表示設(shè)關(guān)于句子的一組規(guī)則為：句子：=主語(yǔ)謂語(yǔ)主語(yǔ)：=名詞短語(yǔ)名詞短語(yǔ)：=名詞名詞短語(yǔ)：= 形容詞名詞短語(yǔ)形容詞：=big形容詞：=brown形容詞：=roasted名詞：=John名詞：=peanut謂語(yǔ)：=動(dòng)詞直接賓語(yǔ)動(dòng)詞：=ate直接賓語(yǔ)：=冠詞名詞短語(yǔ)冠詞：=the給出下述句子的推導(dǎo)，并畫出語(yǔ)法樹。解：（A） 句子=主語(yǔ)謂語(yǔ)=主語(yǔ)動(dòng)詞直接賓語(yǔ)=主語(yǔ)動(dòng)詞冠詞名詞短語(yǔ)=主語(yǔ)動(dòng)詞冠詞形容詞名詞短語(yǔ)=主語(yǔ)動(dòng)詞冠詞形容詞名詞=主語(yǔ)動(dòng)詞冠詞形容詞peanut=主語(yǔ)動(dòng)詞冠詞big peanut=主語(yǔ)動(dòng)詞the big peanut=主語(yǔ)ate the big peanut=名詞短語(yǔ)ate the big peanut=名詞ate the big peanut= John ate the big peanut (語(yǔ)法樹略) (B) 句子=主語(yǔ)謂語(yǔ)=名詞短語(yǔ)謂語(yǔ)=名詞謂語(yǔ)= John謂語(yǔ)= John動(dòng)詞直接賓語(yǔ)= John ate直接賓語(yǔ)= John ate冠詞名詞短語(yǔ)= John ate the名詞短語(yǔ)= John ate the形容詞名詞短語(yǔ)= John ate the big名詞短語(yǔ)= John ate the big形容詞名詞短語(yǔ)= John ate the big brown名詞短語(yǔ)= John ate the big brown名詞= John ate the big brown peanut （語(yǔ)法樹略） (C) 句子=主語(yǔ)謂語(yǔ)=名詞短語(yǔ)謂語(yǔ)=名詞謂語(yǔ)= John謂語(yǔ)= John動(dòng)詞直接賓語(yǔ)= John ate直接賓語(yǔ)= John ate冠詞名詞短語(yǔ)= John ate the名詞短語(yǔ)= John ate the形容詞名詞短語(yǔ)= John ate the big名詞短語(yǔ)= John ate the big形容詞名詞短語(yǔ)= John ate the big roasted名詞短語(yǔ)= John ate the big roasted名詞= John ate the big roasted peanut（語(yǔ)法樹略）2.利用規(guī)則2-1，除最左推導(dǎo)外，給出句子the big elephant ate the peanut的另外兩種推導(dǎo)（其中一種為最右推導(dǎo)）。 答：(A) 最右推導(dǎo) 句子=主語(yǔ)謂語(yǔ)=主語(yǔ)動(dòng)詞直接賓語(yǔ)=主語(yǔ)動(dòng)詞冠詞名詞=主語(yǔ)動(dòng)詞冠詞peanut=主語(yǔ)動(dòng)詞the peanut=主語(yǔ)ate the peanut=冠詞形容詞名詞ate the peanut=冠詞形容詞 elephant ate the peanut=冠詞big elephant ate the peanut= the big elephant ate the peanut (B) 句子=主語(yǔ)謂語(yǔ) =主語(yǔ)動(dòng)詞直接賓語(yǔ) =冠詞形容詞名詞動(dòng)詞直接賓語(yǔ) =冠詞形容詞名詞動(dòng)詞冠詞名詞 = the形容詞名詞動(dòng)詞冠詞名詞 = the big名詞動(dòng)詞冠詞名詞 = the big elephant動(dòng)詞冠詞名詞 = the big elephant ate冠詞名詞 =the big elephant ate the名詞=the big elephant ate the peanutP191.令A(yù)=$,又令Z=$,寫出如下的符號(hào)串以及它們的長(zhǎng)度：Z，ZZ，Z2 ，Z3，Z0，A*=？ 解：Z=$ |Z|=1 ZZ=$ |ZZ|=2 Z2=ZZ=$ | Z2|=2 Z3=$ | Z3|=3 Z0= | Z0|=1 A*=,$,$,$, |A*|= 2.令A(yù)=0,1,2,又令x=01，y=2，z=001，寫出如下符號(hào)串及它們的長(zhǎng)度： xy, xyz, x4, (x3)(y2), (xy)2 解：xy=012, |xy|=3xyz =012001, | xyz |=6 x4=xxxx=01010101, | x4 |=8 (x3)(y2)=01010122, | (x3)(y2)|=8 (xy)2=012012, |(xy)2 |=6令A(yù)=0,1,2,寫出集合A+和集合A*的7個(gè)最短的符號(hào)串。解：A+的7個(gè)最短的符號(hào)串為： 0，1，2，00，01，02，10 （答案不唯一）A*的7個(gè)最短的符號(hào)串為：，0，1，2，00，01，02， （答案不唯一） 4. 試證明：A+=AA*=A*A 證： A*=A0A+，A+=A1A2An 得：A*=A0A1A2An AA*=A（A0A1A2An） = AA0AA1AA2A An =AA2A3An +1= A+ 同理可得：A*A =(A0A1A2An)A =A0 AA1AA2AANA = AA2A3AN+1 = A+ 因此：A+ =AA*=A*AP261.設(shè)G標(biāo)志符的規(guī)則是 ：標(biāo)志符:=a|b|c|標(biāo)志符a|標(biāo)志符c|標(biāo)志符0|標(biāo)志符1 試寫出VT和VN，并對(duì)下列符號(hào)串a(chǎn),ab0,a0c01,0a,11,aaa給出可能的一些推導(dǎo)。 解：VT =a,b,c,0,1， VN =標(biāo)志符 不能推導(dǎo)出ab0,11,0a標(biāo)志符=a 標(biāo)志符=標(biāo)志符1 =標(biāo)志符01 =標(biāo)志符c01 =標(biāo)志符0c01 = a0c01 (4)標(biāo)志符=標(biāo)志符a =標(biāo)志符aa =aaa2. 寫一文法，使其語(yǔ)言是偶整數(shù)的集合。 解：G偶整數(shù)： 偶整數(shù):=符號(hào)偶數(shù)字|符號(hào)數(shù)字串偶數(shù)字，（作用是一位和多位） 符號(hào):= + | | 數(shù)字串:= 數(shù)字串?dāng)?shù)字|數(shù)字 數(shù)字:= 偶數(shù)字| 1 | 3 | 5 | 7 | 9 偶數(shù)字:=0 | 2 | 4 | 6 | 83. 寫一文法，使其語(yǔ)言是偶整數(shù)的集合，但不允許有以0 開頭的偶整數(shù)。 解：G偶整數(shù)： 偶整數(shù):= 符號(hào)單偶數(shù)|符號(hào)首數(shù)字?jǐn)?shù)字串尾偶數(shù) 符號(hào):= + | | 單偶數(shù):=2 | 4 | 6 | 8 尾偶數(shù):= 0 |單偶數(shù) 首數(shù)字:= 1 | 3 | 5 | 7 | 9 |單偶數(shù) 數(shù)字串:= 數(shù)字串?dāng)?shù)字|數(shù)字| 數(shù)字:= 0 |首數(shù)字4. 設(shè)文法G的規(guī)則是： A:=b| cc 試證明：cc, bcc, bbcc, bbbccLG 證：（1）A=cc （2）A=bA=bcc （3）A=bA=bbA=bbcc （4）A=bA=bbA=bbbA=bbbcc 又cc, bcc, bbcc, bbbccVt* 由語(yǔ)言定義，cc, bcc, bbcc, bbbccLG5. 試對(duì)如下語(yǔ)言構(gòu)造相應(yīng)文法： a(bn)a | n=0,1,2,3,其中左右圓括號(hào)為終結(jié)符。 （an）（bn） | n=1,2,3, 解：（1）文法GS： S:= a(B)a B:= bB |b|( 2 ) 文法GS： S := (A)(B) A:= aA|a B:= bB|b6. 文法G3表達(dá)式： 表達(dá)式:=項(xiàng)|表達(dá)式+項(xiàng)|表達(dá)式項(xiàng) 項(xiàng):=因子|項(xiàng)*因子|項(xiàng)/因子 因子:=（表達(dá)式）| i 試給出下列符號(hào)串的推導(dǎo)： i, (i), i*i, i*i+i, i*(i+i)解：（1）表達(dá)式=項(xiàng)=因子= i ( 2 ) 表達(dá)式=項(xiàng)=因子=（表達(dá)式）=（項(xiàng)）=（因子）=（i） （3）表達(dá)式=項(xiàng) =項(xiàng)*因子=項(xiàng)* i=因子* i= i*i（4）表達(dá)式=表達(dá)式+項(xiàng)=表達(dá)式+因子=表達(dá)式+ i=項(xiàng)+ i=項(xiàng)*因子+ i=項(xiàng)* i + i=因子* i + i= i * i + i （5）表達(dá)式=項(xiàng)=項(xiàng)*因子=項(xiàng)*（表達(dá)式）=項(xiàng)*（表達(dá)式+項(xiàng)）=項(xiàng)*（表達(dá)式+因子）=項(xiàng)*（表達(dá)式+ i）=項(xiàng)*（項(xiàng)+ i）=項(xiàng)*（因子+ i）=項(xiàng)*（i+ i）=因子*（i+ i）= i *（i+ i）7. 對(duì)文法G3表達(dá)式（見(jiàn)上題），列出句型表達(dá)式+項(xiàng)*因子的所有短語(yǔ)和簡(jiǎn)單短語(yǔ)。解：句型表達(dá)式+項(xiàng)*因子的短語(yǔ)有： 表達(dá)式+項(xiàng)*因子和項(xiàng)*因子 簡(jiǎn)單短語(yǔ)是：項(xiàng)*因子 注意：求短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄盡量用語(yǔ)法樹。8. 文法V:= aaV | bc的語(yǔ)言是什么？ 解：L（GV）= a2nbc | n=0,1,2, 9. 設(shè)文法G為： N:=D|ND D:=0|1|2|3|4|5|6|7|8|9G的語(yǔ)言是什么？給出句子0125和783的最右推導(dǎo)（規(guī)范推導(dǎo)）和最左推導(dǎo)。 解：（1）L（G）=所有無(wú)符號(hào)整數(shù) （2）N=ND=N5=ND5=N25=ND25=N125=0125（最右推導(dǎo)（規(guī)范推導(dǎo)） N=ND=NDD=DDD=7DD=78D=783（最左推導(dǎo)）P331.給定文法GE為： E:=RP|P P:=（E）| iR:=RP+ | RP* | P + | P*證明 （1）i+i* (i+i)是文法G的句子。 （2） 畫出該句子的語(yǔ)法樹。 證：（1）E=RP=RP* P=RP*（E）=RP*（RP）=RP*（P+P）=RP*（P+i）= RP*（i+i）=P+P*（i+i）= P+i*（i+i）= i+i*（i+i）Vt* i+i* (i+i)是文法G的句子（對(duì)應(yīng)的語(yǔ)法樹略）2.畫出下列推導(dǎo)的語(yǔ)法樹。（1）123123 (2) 由上圖可知兩種推導(dǎo)的語(yǔ)法樹是相同的。4. 由下述語(yǔ)法樹構(gòu)造推導(dǎo)：（語(yǔ)法樹書上P34上，未畫）。解：（1）表達(dá)式=項(xiàng) =項(xiàng)*因子 =因子*因子 = i*因子 = i* i ( 2 ) 表達(dá)式=項(xiàng)=項(xiàng)*因子 =因子*因子= i*因子= i * (表達(dá)式)= i * (表達(dá)式+項(xiàng))= i * (項(xiàng)+項(xiàng))= i * (因子+項(xiàng))= i * ( i +項(xiàng))= i * ( i +因子)= i * ( i + i )5 已知文法GE：E:=ET+ | TT:=TF* |FF:=FP |PP:=（E）| i 有句型TF*PP+，問(wèn)此句型的短語(yǔ)，簡(jiǎn)單短語(yǔ)，和句柄是什么？解：此句型的短語(yǔ)有：TF*PP+，TF*，PP，P簡(jiǎn)單短語(yǔ)有：TF*，P句柄是：TF* 注意：求短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄盡量用語(yǔ)法樹。6. 分別對(duì)i+i*i和i+i+i中的每一個(gè)句子構(gòu)造兩棵語(yǔ)法樹，從而證明下列文法G表達(dá)式是二義的。 表達(dá)式:= i | (表達(dá)式) |表達(dá)式運(yùn)算符表達(dá)式 運(yùn)算符:= + | | * | / 解：以i+i*i為例: 8 證明下面的文法G是二義的：S:= iSeS | iS | i證：由文法可知iiiei是該文法的句子，又由文法可知iiiei有兩棵不同的語(yǔ)法樹。所以該文法是二義性文法。7 文法G3表達(dá)式為： 表達(dá)式:=項(xiàng)|表達(dá)式+項(xiàng)|表達(dá)式項(xiàng) 項(xiàng):=因子|項(xiàng)*因子|項(xiàng)/因子 因子:=（表達(dá)式）| i證明此文法的句子i+i*i和i+i+i是無(wú)二義性的。在句子i+i*i中，哪種運(yùn)算符是優(yōu)先的？在句子i+i+i中，又是哪種運(yùn)算符？證：J（容易證明文法規(guī)則右邊出現(xiàn)有選折項(xiàng)時(shí)，各項(xiàng)首符號(hào)集不相交，且該文法不是左遞歸文法）。 在句子i+i*i中，運(yùn)算符*是優(yōu)先的在句子i+i+i中，第一個(gè)+運(yùn)算符是優(yōu)先的9有文法GN：N:=SE|EE:=0|2|4|6|8|10S:=SD|DD:=0|1|2|9舉例說(shuō)明文法GN 是二義的。此文法描述的語(yǔ)言是什么？試寫出另一文法G，使L（G）=L（G），且G是無(wú)二義性的。解：由文法可知10是該文法的句子，又由文法可知10有兩棵不同的語(yǔ)法樹。 此文法描述的語(yǔ)言L（G）=無(wú)符號(hào)偶數(shù) 所求文法G無(wú)符號(hào)偶數(shù)： 無(wú)符號(hào)偶數(shù):=偶數(shù)字|數(shù)字串偶數(shù)字 數(shù)字串:= 數(shù)字串?dāng)?shù)字|數(shù)字 數(shù)字:= 偶數(shù)字| 1 | 3 | 5 | 7 | 9 偶數(shù)字:=0 | 2 | 4 | 6 | 8 （*上述提供文法中的第二條規(guī)則右部的10選折項(xiàng)去掉似乎就符合要求了行*） 第三章P671解： 其狀態(tài)圖為： start e由狀態(tài)圖知： f ,eeff不是合法的句子 eefe是該文法的句子。2解：正則文法為GZ： ZA10 AA00該文法的 V=Z,A,1,0 Vn=Z,A Vt=1,0該文法所確定的語(yǔ)言為：LGZ0n1或0n15證明：AAxxLA或xLAxxLAA（A*）*（A*）0（A*）1（A*）2（A*）n(A0A1A2An) (A1) A0A1A2An AAA*所表示的語(yǔ)言是LALA*LA0LA（LA0LA1LA2）LA0LA1LA2LA*故AA*A*(LALB)*LA=(LALBLALBLALBLALBLALBLALB) LA =LALALBLALALBLALBLALALBLALBLALBLA = LA(LBLALBLALBLA) = LA(LBLA) (AB)*=A(AB)*三個(gè)表達(dá)式所描述的語(yǔ)言都是LALA中任意組合 （A|B）*=(A*B*)=(A*|B*)*6解： R1=01對(duì)應(yīng)的自動(dòng)機(jī)為 (R1)*=(0|1)* 對(duì)應(yīng)的自動(dòng)機(jī)為M2將M2確定化start01P0P1P2P3start10P1 P2eefeSABZ狀態(tài) 輸入 01 P0P1,P3 P1P2P2 P2P1,P3 P3 I I0 I1(空)狀態(tài) 輸入 0 1P0,P1,P3P1,P2,P3P1,P2,P3 P0P1P1P1,P2,P3P1,P2,P3P1,P2,P30,1start01q2q1q0start0P0P11 P1P1P11000000100111S0S1S2S8S4S14S7S5S6S11S31110001S10S12S130startS9010P1P2P401P0start111100100P10P12P13P30105P6P7P8P11P9P141110011q2q7q1startq0q9q100000011q6q5q4q3q8P00,1（注：上圖中的（空）列表示沒(méi)有該列。即上圖為兩個(gè)獨(dú)立的表）狀態(tài)轉(zhuǎn)換圖為：簡(jiǎn)化為：R=1(0|1)*|0 的DFA M為： R1=1010*|1(010)*1對(duì)應(yīng)的DFA M為：R2=(1010*|1(0|0)*1)* 對(duì)應(yīng)的DFA M為：對(duì)應(yīng)R=1(1010*|1(010)*1)*0 的DFA M為：8.解：(a) I Ia Ib 0 0,1 1 0,1 0,1 1 1 0 DFA的狀態(tài)轉(zhuǎn)換矩陣為： 狀態(tài) 輸入 a b q0 q1 q2 q1 q1 q2 q2 q0 YNSym=(?)nextsymNSym=d(?) BNSym=)(?)errornextsym BSym=e(?)nextsymerrorYerrorNSym=c(?)nextsymnextsymNSym=c(?) 化簡(jiǎn)：p0= q0= q1 p1= q2a 狀態(tài)圖為 ：abstartP1P0 10解：它所識(shí)別的語(yǔ)言為：(1010)*第四章 語(yǔ)法分析P801. 解：（見(jiàn)課本）2解：文法有左遞歸，故先改寫文法：A A=(B)|dBe B=cc下面給出兩個(gè)分析子程序的框圖： BY YYNY兩分析子程序如下：procedure A; IF sym=( THEN Begin Nextsym; B; If sym=) Then Nextsym; Else Error End; ELSE If sym=d Then Begin Nextsym; B; if sym=e then Nextsym else Error End; Else Error; Procedure B;NYYNSym=c(?)NSym=a(?) A BSym=c(?)Sym=d(?) B nextsym errorZNYYNSym=c(?)errror nextsymSym=a(?) BAYYSym=a(?)NerrrornextsymSym=c(?)ANB IF sym=c THEN Begin Nextsym; While sym=c do Nextsym End ELSE Error;/*程序中nextsym為讀字符子程序，error為出錯(cuò)處理子程序*/*主程序*/ program G; VAR sym:CHAR; BEGIN Nextsym; A; END3解：（1）。 FIRST(AcB)=c FIRST(Bd)=a FIRST(AaB)=c FIRST(c)=c FIRST(aA)=a FIRST(a)=a(2). 若用不帶回溯的自頂向下的語(yǔ)法分析程序，必須改寫文法： ZAcB|Bd AcaB BaA 因?yàn)檎{(diào)用分析子程序A的過(guò)程中，調(diào)用了B子程序，在B中又調(diào)用了A，相當(dāng)于A間接的調(diào)用了A，所以該文法應(yīng)編寫成遞歸子程序。(3). 三個(gè)分析子程序框圖如下： YY三個(gè)分析子程序?yàn)椋篊reated by ITLearner-2004 1/27/2020- 23 -procedure Z; if sym=c thenbegin A; If sym=c then B; Else ErrorEnd; ElseIf sym=a then Begin B; If sym=d then Nextsym; Else Error End;Else Error;Procedure A;If sym=c then Begin Nextsym; While sym=a do B; End;Else Error;Procedure B;If sym=a then Begin Nextsym; If sym=c then A; End;Else Error;4解：首先改寫文法如下：語(yǔ)句變量表達(dá)式 if表達(dá)式then語(yǔ)句else語(yǔ)句變量i()|)表達(dá)式項(xiàng)+項(xiàng)項(xiàng)因子*因子因子變量|()語(yǔ)法分析程序(pascal)共有五個(gè)子程序statement,expr,item,factor,varprocedure statement;if sym=if then begin nextsym; expr; if sym=then then begin nextsym; statement; if sym=else then begin nextsym; statement; end; end; else error; end;else begin var; if sym=:= then begin nextsym; expr; end; else error; end;procedure expr;item;while sym=+ do begin nextsym; item; end;procedure item;factor;while sym=* do begin nextsym; factor; end;procedure var;if sym=i then begin nextsym; if sym=( then begin nextsym; expr; if sym=) then nextsym; else error; end; end;else error;procedure factor;if sym=( then begin nextsym; expr; if sym=) then nextsym; else error; end;else var;P871.解：（1）。FIRST(P)=(,a,b,) FOLLOW(E)=#, ) FIRST(F)=, FOLLOW(E)= #,) FIRST(F)=(,a,b,) FOLLOW(T)= #,+ FIRST(T)= (,a,b, ) FOLLOW(T)= #,+ FIRST(T)= (,a,b, FOLLOW(F)= (,a,b, ),+,# FIRST(E)=+, FOLLOW(F)= (,a,b, ),+# FIRST(E)= (,a,b,) FOLLOW(P)= (,a,b, ),+,#,*(2)證明：對(duì)于E+E| FIRST(+E)=+ FIRST()= FOLLOW(E)=#, FIRST(+E)FIRST()= FIRST(+E)FOLLOW(E)= 對(duì)于TT| FIRST(T)FOLLOW(T)= 對(duì)于F*F| FIRST(*F)FOLLOW(F)= 對(duì)于P(E)|a|b| FIRST(E)=() FIRST(a)=a FIRSTb=b FIRST= 根據(jù)LL(1)文法的充要條件可以斷定該文法是LL(1)文法.(3).構(gòu)造其分析表如下： a b ( ) * + # EETEETEETEETE EEE+EE TTFTTFTTFTTFT TTTTTTTTTTTT FFPFFPFFPFFPF FFFFFFF*FFF PPaPbPP(E) (注：空白處均為ERROR)2解： （2）FIRST（aABbcd）=a;FIRST(e)=e;FIRST(Asd)=a,d;FRIST(SAh)=a,h;FIRST(eC)=e; FRIST(Sf)=a,f;FIRST(Cg)=g,a,f;FRITS(aBD)=a; （3）對(duì)于CSf | Cg，F(xiàn)IRST（Sf） FIRST（Cg）=a,f此文法不是LL（1）文法。解：本題錯(cuò)誤。6解：一個(gè)文法是文法的充要條件是：AVn,A的任何兩條不同的規(guī)則A:=|有下列條件成立：* FIRST()FIRST()= =，則FIRST()FOLLOW(A)= 證明：充分性：*對(duì)于任意非終結(jié)符A 若A:=|滿足上述條件，取分析表項(xiàng)MA,a,aVt若A=a假設(shè)=a即aFIRST() FIRST()FIRST()= * aFIRST() 分析表項(xiàng)MA,a= A:= 若=,且aFOLLOW (A) aFIRST() MA,a= A:= 否則 MA,a=error 綜上，分析表的元素?zé)o多重定義，符合LL(1)文法定義,是LL(1)文法必要性： 令對(duì)于LL(!)文法G的 AVn, A:=|條件不成立 FIRST()FIRST()=B FIRST()FIRST()=C* 若a,則MA,a中，可同時(shí)存在 A:=及A:= 若=則MA,a中,可同時(shí)存在A:= A:= 兩條規(guī)則 這與定義相矛盾，假設(shè)錯(cuò)誤必要性得證。P1003.解：procedure INSERT(u,a) if not Lu,a then begin Lu,a:=true; 將(u,a)壓入棧STACK end;program MAIN; begin for 每個(gè)非終結(jié)符U和終結(jié)符a do Lu,a:=false; For 每條形如U:=a或U:= aV規(guī)則 do INSERT(U,a); While STACK 非空 DO Begin 將STACK棧頂彈出，記為(V,a); for 每條形如U:=V規(guī)則 do INSERT(U,a); End; EndP1092.解：I0=closure(S.E#)=S.E#,E.wX,E.xYI1=goto(I0,E)=closure(SE.#)=SE.#I2=goto(I0,w)=closure(Ew.X)=Ew.X,X.yX,X.zI3=goto(I0,x)=closure(Ex.Y)=Ex.Y,Y.yY,Y.zI4=goto(I1,#)=closure(SE#.)= SE#.I5=goto(I2,X)=closure(EwX.)= EwX.I6=goto(I2,y)=closure(Xy.X)= Xy.X, X.yX,X.z I7=goto(I2,z)=closure(X.z)= Xz.I8=goto(I3,Y)=closure(ExY.)= ExY.I9=goto(I3,y)=closure(Yy.Y)= YyY.I10=goto(I3,z)=c