《编译原理习题课.pptx》由会员分享，可在线阅读，更多相关《编译原理习题课.pptx（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章2.2(1)L(GN)=(0|1|2|3|4|5|6|7|8|9)+L(GN)=可带前导0的正整数2.3(1)L1=ambn|m,n=1S-ABA-a|aAB-b|bB2.3(2)L2=anbnci|n=1,i=0S-Ac|AA-ab|aAb2.3(3)L3=anbncmdm|m,n=1S-ABA-aAb|abB-cBd|cd2.3(4)L4=0n|n=0A-A0|第1页/共32页2.3(5)L5=a2n+1|n=0S-aAA-aaA|或A-aAa|a2.3(6)L6=1n0m1m0m|n,m=0S-1S0|oA1|A-0A1|2.4写一个文法，不以0开头的奇数N-1|3|5|7|
2、9|BNB-1|2|3|4|5|6|7|8|9|B0第2页/共32页2.6短语：E+T*F,T*F直接短语：T*F句柄：T*FEE+TT*F2.7G1：S-ABA-aA|B-bc|bBcL(G1S)=aibncn|i=0,n=1G2：S-aA|aA-aSL(G2S)=a2n+1|n=0第3页/共32页2.9短语：T*P(T*F),P(T*F),(T*F),T*F,P直接短语：T*F,P句柄：PTT*FFPP(T)T*F第4页/共32页2.11短语:(SaA)(b),(SaA)(b),(SaA),(b)直接短语:(SaA),(b)句柄:(SaA)S(AS)(AS)(SaA)(b)第5页/共32页
3、第第三三章章3.1(3)(0|1)*|(11)*XAYB11C0,1Q01X,A,C,YA,C,YB,A,C,YA,C,YA,C,YB,A,C,YB,A,C,YA,C,YA,C,YX01第6页/共32页3.1(4)(0|11*0)*重命名Q01XX,A,YA,YB,C,D1A,YA,YB,C,D2B,C,DA,YC,D3C,DA,YC,D初始划分：X,1;2,3Q01XX22X2第7页/共32页3.2(a)初始划分：A,B;C第8页/共32页3.2(b)初始划分：0,1;2,3,4,50,1a=1;0,1b=2,42,3,4,5a=1,3,0,5;2,3,4,5b=3,2,5,4再次划分：0,
4、1;2,4;3,50,1a=1;0,1b=2,42,4a=1,0;2,4b=3,53,5a=3,5;3,5b=2,4230bbaaaa第9页/共32页3.3构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。0*(0|10)*0*初始划分：1,2,4;3ca100第10页/共32页3.9试证明正规式（a|b）*与正规式（a*|b*）*是等价的。第11页/共32页3.11设字母表=a,b,给出上的正规式R=b*ab(b|ab)*第12页/共32页3.11初始划分：1,2,3,5;4,6再次划分：1,3;2,5;4,6Qab1212-4424第13页/共32页3.1
5、1（2）对应的右线性文法G=（X,W,Y,a,b,P,X）P:XaW|bXWbY|bYaW|bY|b第14页/共32页第第四四章章4.1FIRSTFOLLOWAa,b,c,d,g$,fBb,$,a,c,d,f,gCa,c,dc,d,gDd,$,a,b,c,g,fEg,c$,a,c,d,f,g第15页/共32页因此该文法是LL(1)文法第16页/共32页4.2FIRSTFOLLOWE(,id),$E+,),$T(,id+,),$T*,+,),$F(,id+,*,),$SELECT(E-+TE)SELECT(E-)=FIRST(+TE)FOLLOW(E)=SELECT(T-*FT)SELECT(T
6、-)=FIRST(*FT)FOLLOW(T)=SELECT(F-(E)SELECT(F-id)=FIRST(E)FIRST(id)=因此该文法是LL(1)文法第17页/共32页FIRSTFOLLOWE(,id),$E+,),$T(,id+,),$T*,+,),$F(,id+,*,),$id+*()$EE-TEE-TEEE-+TEE-E-TT-FTT-FTTT-T-*FTT-T-FF-idF-(E)第18页/共32页4.3第19页/共32页4.3SELECT(A-iBA)SELECT(A-)=FIRST(iBA)FOLLOW(A)=SELECT(B-+CB)SELECT(B-)=FIRST(+C
7、B)FOLLOW(B)=SELECT(C-)A*)SELECT(C-()=FIRST()A*)FIRST()=FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*第20页/共32页(i+)*$SS-AS-AAA-BAA-BAAA-iBAA-A-BB-CBB-CBBB-B-+CBB-B-CC-(C-)A*FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*第21页/共32页4.5设有表格结构文法GS：S-a|(T)T-T,S|S第22页/共32页4.5设有表格结构文法GS：
8、S-a|(T)T-T,S|S第23页/共32页4.5设有表格结构文法GS：S-a|(T)T-T,S|S第24页/共32页4.80.S-S1.S-AS2.S-b3.A-SA4.A-a第25页/共32页(2).I1,I5,I6存在“移进-归约”冲突。不是LR(0)文法。(3).对于abab有两棵不同的语法树，任何二义性文法不是SLR(1)文法，也不是LALR(1)或LR(1)文法。SASaASSAbbaSASSAbASbab第26页/共32页4.90.S-S1.S-rD2.D-D,i3.D-i(2).I3中有“移进-归约”冲突，不是LR(0)文法第27页/共32页(3).FOLLOW(S),=$,=,可以用SLR(1)文法解决4.90.S-S1.S-rD2.D-D,i3.D-i状态ACTIONGOTOr,i$SD0S211acc2S433S5r14r3r35S66r2r2第28页/共32页4.13第29页/共32页不含有冲突，因此是LR(1)文法合并同心集6和9，I69:A-x,d/e,B-,d/e出现“归约-归约”冲突，因此不是LALR(1)文法第30页/共32页Thank you!第31页/共32页感谢您的观看。第32页/共32页