1、第一章練習12、典型的編譯程序可劃分為哪幾個主要的邏輯部分？各部分的主要功能是什么？典型的編譯程序具有7個邏輯部分：第二章練習2.24.試證明：A+=AA*=A*A證：:A*=A0UA+,A+=A1UA2U-UAnU-得：A*=A0UA1UA2U-UAnU-.AA*=AA0UA1UA2U-UAnU=AA0UAA1UAA2U-UAAnU-=AUA2UA3UAn+1U=A+同理可得：A*A=A=A0AUA1AUA2AUUAnAU=AUA2UA3UAn+1U-=A+因此：A+=AA*=A*A練習2.3.設G標識符的規則是：標識符：:=a|b|c|標識符a|標識符c|標識符0|標識符1試寫出VT和VN

2、,并對下列符號串a,abO,aOcO1Qa,11,aa跆出可能的一些推導解：VT=a,b,c,0,1,VN=標識符1不能推導出abO,11,0a2標識符=a3標識符=標識符1=標識符01=標識符c01=標識符0c01=a0c014標識符=標識符a=標識符aa=aaa.寫一文法，其語言是偶整數的集合解：Gv偶整數刁：v偶整數二二曲號,v偶數字|v符號,哪字串禺數字V符號：=+IIV數字串：=嗷字串哪字|v數字V數字禺數字|1|3|5|7|9v偶數字:=0|2|4|6|84.設文法G的規則是：:=b|cc試證明：cc,bcc,bbcc,bbbc(LG證：1=cc2=b=bcc3=b=bb=bbcc

3、4=b=bb=bbb=bbbcc又cc,bcc,bbcc,bbbccEVt*由語言定義,cc,bcc,bbcc,bbbcLG5試對如下語言構造相應文法：1aa|n=0,1,2,3,，其中左右圓括號為終結符。2anbn|n=1,2,3,解：1文法G:S:=aaB:=bB|&v2文法G:-錯了，兩個n不等S:=A:=aA|aB:=bB|b7.對文法G3表達式表達式:=項|表達式+項|表達式-項項:=因子|項*因子|項/因子因子：:=表達式|i列出句型表達式+項*因子的所有短語和簡單短語表達式=裱達式+領=裱達式+領*因子短語有：表達式+項*因子和項*因子簡單短語是：項*因子8文法V:=aaV|bc

4、的語言是什么？?解：LGV=a2nbc|n=0,1,2；)V?aaV?aaaaV?.?a2nbcn1V?bcn=0練習2.45.已知文法GE:E:=ET+|TT:=TF*|FF:=FP?|PP:=舊i有句型tf*ppT+,問此句型的短語，簡單短語，和句柄是什么？解：此句型的短語有：TF*PPT+,TF*,PPT,p簡單短語有：TF*,P句柄是：TF*8.證明下面的文法G是二義的：S:=iSeS|iS|i證：由文法可知iiiei是該文法的句子,又由文法可知iiiei有兩棵不同的語法樹。所以該文法是二義性文法。第三章練習3.1畫出下述文法的狀態圖Z:=BeB:=AfA:=e|Ae使用該狀態圖檢查下

5、列句子是否是該文法的合法句子f,eeff,eefe2、有下列狀態圖,其中S為初態,Z為終態。1寫出相應的正則文法：2寫出該文法的V,Vn和Vt;3該文法確定的語言是什么？解：1qA1|0A-A0|02V=A,Z,0,1Vn=A,ZVt=0,1：3L=喊On1,n1L=0|00*1練習3.21.令A,B,C是任意正則表達式，證明以下關系成立：A|A=A：A*=A*A*=&|AA*：AB*A=ABA*：A|B*=：A*B*=A*|B*證明：AIA=xIxLAxL=xIxL=AA*=：A*OU：A*1U：A*2U-UA*n=UU=&UAOUA1UA2U-UAn=A*|AA*所表示的語言是：ULA-L

6、A*=LAOULA：LAOULA1ULA2U-=LAOULA1ULA2U=LA*AA*=A*LA=ULLBJLALBLALBLALBLALBLALBU-LA=LAULALBLAJLALBLALBLALALBLALBLALBULA-=LAU=LA*A=A*三個表達式所描述的語言都是LALB中任意組合A|B*=*.構造下列正則表達式相應的DFA110|1*|0211010*|1010*1*04.(0)I(oj)|tiojj(ojo;IDI10)|- TOC o 1-5 h z 舟it廠、.Ci-o)G.1、I.、*.br/5.構造一DFA它接受2=0,1上所有滿足如下條件的字符串：每個1都有0直接

7、跟在右邊。第四章練習4.2.有文法GA:A:=|dBeB:二c|Bc試設計自頂向下的語法分析程序。解：消除左遞歸：A:=|dBeB:=ccprocedureB;ifCLASS=cthenbeginnextsym;whileCLASS=cdonextsym;end;elseerror;programG;beginnextsym;A;end;procedureA;ifCLASS=thennextsym；elseerrorend；elseifCLASS=dthenbeginnextsym;B;ifCLASS=ethennextsym;elseerror;end;elseerror;.有文法GZ:Z:

8、=AcB|BdA:=AaB|cB:=aA|a1試求各選擇候選式的FIRS博合；2該文法的自頂向下的語法分析程序是否要編成遞歸子程序？為什么？3試用遞歸下降分析法設計其語法分析程序。解：FIRST=aFIRST=cFIRST=a,cFIRST=cFIRST=cFIRST=aFIRST=cFIRST=aFIRST=a要編成遞歸子程序，因為文法具有遞歸性改寫文法：Z:=AcB|BdA:=caBB:=aA練習4.3.對下面的文法GE:E-TEE，7+E|TFTrt&FPFF7*F|eP-|a|b|A1計算這個文法的每個非終結符號的FIRS林口FOLLOW集合2證明這個文法是LLV1制3構造它的預測分析

9、表解：FIRST=,a,1FOLLOW=#,FIRST=+,FOLLOW=#,FIRST=,a,MFOLLOW=#,+FIRST=,a,M,eFOLLOW=#,+FIRST=,a,b,FOLLOW=,+FIRST=*,FOLLOW=,+FIRST=,a,b,FOLLOW=*,+證明：FIRSTnFIRST%=+A=/FIRSTnFOLLOW=+0#,=/FIRSTHFIRST%=,a,b,AA=爐FIRSTHFOLLOW=,+=爐FIRSTAFIRST=*A=/FIRSTAFOLLOW=*,+=爐FIRST引FIRSTAFIRSTAFIRST=爐所以此文法是LL對每一個非終結符號，構造FOLL

10、OVW；2對每一產生式的各侯選式構造FIRST；3指出此文法是否為LL1文法。解：1FIRSTS=奔 TOC o 1-5 h z FIRST=a,d,!FIRSTvB=d,h,e,!FIRST=a,f,g,!FIRST=a,FOLLOW=d,a,f,h#FOLLOW=a,h,e,b,dFOLLOW=b,aFOLLOW=g,b,aFIRST=aFIRST=FIRST=a,dFIRST=FIRST=a,d,hFIRST=eFIRST=FIRST=a,fFIRST=a,f,g)FIRST=不是LL1或法，因FIRSTAFIRST=afa,f,g產步或FOLLOWnFIRSTd,a,f,h#Aa?步或

11、FOLLOWAFIRSTa,h,e,b,dAa,d廣步或FOLLOWAFIRSTa,bAa,d,h產爐或FOLLOWAFIRSTg,a,bAa,f步或FOLLOWAFIRSTg,a,bAa,f,g?步一個文法G是LL1制必要與充分條件是什么？試證明之。充要條件是：對于G的每一個非終結符A的任何兩條不同規則A:=0cIB,有：FIRSTAFIRST=爐彳段若B=*=&,則FIRSTSAFOLLOW=爐證明：充分性：條件證明：充分性：條件12成立反證：若分析表中存在多重入口，即成立反證：若分析表中存在多重入口，即MB,a=B:=%1,B:=%2，表明FIRSTAFIRST半或MB,a=B:=%1,

12、B:=%2淇中2=e或2=+=表明FIRSTAFOLLOW?爐與條件12矛盾。必要性：文法是矛盾。必要性：文法是LL1或法，即分析表中不含多重入口若條件文法，即分析表中不含多重入口若條件不成立，即存在某非終結符B的兩條規則B:=%1|%2,FIRSTAFIRST/則對任意的aSFIRSTAFIRST，有MB,a=B:=a1,B:=%2,矛盾若條件矛盾若條件2不成立，即存在某非終結符B的兩條規則B:=%1|%2,%2=*=&有FIRSTAFOLLOW?爐則對任意的aFIRSTAFOLLOWB市MB,a=B:=a1,B:=%2,矛盾練習4.44.有文法GE:E:=E+T|TT:=T*F|FF:=|

13、i列出下述句型的短語和素短語：ET、i、T*F、F*F、i*F、F*i、F+F+F練習4.51.考慮具有下列規則的文法SE#ET|E+TTP|PTTPF|P*FFi|下列句型的最右推導步驟中，其活前綴的集合是什么？1E+i*i#2E+PT#為下列輸入串構造最右推導的逆：1i+i*i#2i+iT#解：1句柄為i,所以活前綴集合為：E,E,E+i2句柄為i,所以活前綴集合為：E,E+,E+P,E+PT,E+PT,E+PT1 TOC o 1-5 h z i+i*i#=F+i*i#=P+i*i#=T+i*i#=E+i*i#=E+F*i#=E+P*i#=E+P*F#=E+P#=E+T#=E#=S練習4.

14、61.給定具有如下產生式的文法SE#EE-T|TTF|FfTFi|試求下列活前綴的有效項目集：FTE-E-T解：ETT7.FTFf.TTfFTTF.iF.E-F7,E7.E-T,E7.T,T7.F,T7.FfT,T.i,T.E-TEE-T.練習4.7.給定下列產生式的文法：SEET|E+TTP|T*PPF|FTPFi|為該文法構造SLR1分析表。第五章練習53.如下非分程序結構語言的程序段,畫出編譯該程序段時將生成的有序符號表。BLOCKREALX,Y,Z1,Z2,Z3;INTEGERI,J,K,LASTI;STRINGLIST-OF-NAMES;LOGICALENTRY-ONEXIT-OFF

15、;ARRAYREALVAL;ARRAYINTEGERMIN-VAL-IND;ENDOFBLOCK;5.畫出下面的分程序結構的程序段當程序段3和4的編譯即將完成以前的棧式符號表的圖形包括有效部分和失效部分。第六章練習6.22考慮下面的類ALGO瞠序，畫出當程序執行到和時，運行棧內容的圖像。第七章練習72.將下面的語句A:=TE+*F轉換成三元式，間接三元式和四元式序列。第九章練習9.1試分別構造一個符號串翻譯文法,它將由一般中綴表達式文法所定義的中綴表達式翻譯成波蘭前綴表達式和波蘭后綴表達式.解：翻譯為波蘭前綴表達式的文法為：E-+E+TE-TT-*T*FT-FF-F-ii翻譯為波蘭后綴表達式的文法為：E-E+T+E-TT-T*F*T-FF-F-ii構造一符號串翻譯文法,它將接受由0和1組成的任意輸入符號串,并產生下面的輸出符號串：輸入符號串倒置輸入符號串本身。aS-0S0或S-0S0S-1S1S-1S1S-S-cE-00EE-11EE-以下的符號串翻譯文法能做什么？-CENHIGL