《编译原理-习题课.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|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
2、-1|3|5|7|9|BNB-1|2|3|4|5|6|7|8|9|B02.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=02.9短语：T*P(T*F),P(T*F),(T*F),T*F,P直接短语：T*F,P句柄：PTT*FFPP(T)T*F2.11短语:(SaA)(b),(SaA)(b),(SaA),(b)直接短语:(SaA),(b)句柄:(SaA)S(AS)(AS)(SaA)(b)第第三三章章3.1(3)(0|1)*|(11)
3、*XAYB11C0,1Q01X,A,C,YA,C,YB,A,C,YA,C,YA,C,YB,A,C,YB,A,C,YA,C,YA,C,YX013.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,3Q01XX22X23.2(a)初始划分：A,B;C3.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,1;2,4;3,50,1a=1;0,1b=2,42,4a=1,0;2,4b=3,53,5
4、a=3,5;3,5b=2,4230bbaaaa3.3构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。0*(0|10)*0*初始划分：1,2,4;3ca1003.9试证明正规式（a|b）*与正规式（a*|b*）*是等价的。3.11设字母表=a,b,给出上的正规式R=b*ab(b|ab)*3.11初始划分：1,2,3,5;4,6再次划分：1,3;2,5;4,6Qab1212-44243.11（2）对应的右线性对应的右线性文法文法G=（X,W,Y,a,b,P,X）P:XaW|bXWbY|bYaW|bY|b第第四四章章4.1FIRSTFOLLOWAa,b,c,d,g
5、$,fBb,$,a,c,d,f,gCa,c,dc,d,gDd,$,a,b,c,g,fEg,c$,a,c,d,f,g因此该文法是LL(1)文法4.2FIRSTFOLLOWE(,id),$E+,),$T(,id+,),$T*,+,),$F(,id+,*,),$SELECT(E-+TE)SELECT(E-)=FIRST(+TE)FOLLOW(E)=SELECT(T-*FT)SELECT(T-)=FIRST(*FT)FOLLOW(T)=SELECT(F-(E)SELECT(F-id)=FIRST(E)FIRST(id)=因此该文法是LL(1)文法FIRSTFOLLOWE(,id),$E+,),$T(,
6、id+,),$T*,+,),$F(,id+,*,),$id+*()$EE-TEE-TEEE-+TEE-E-TT-FTT-FTTT-T-*FTT-T-FF-idF-(E)4.34.3SELECT(A-iBA)SELECT(A-)=FIRST(iBA)FOLLOW(A)=SELECT(B-+CB)SELECT(B-)=FIRST(+CB)FOLLOW(B)=SELECT(C-)A*)SELECT(C-()=FIRST()A*)FIRST()=FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*(i+)*$SS-AS-AAA-BAA-BA
7、AA-iBAA-A-BB-CBB-CBBB-B-+CBB-B-CC-(C-)A*FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*4.5设有表格结构文法GS：S-a|(T)T-T,S|S4.5设有表格结构文法GS：S-a|(T)T-T,S|S4.5设有表格结构文法GS：S-a|(T)T-T,S|S4.80.S-S1.S-AS2.S-b3.A-SA4.A-a(2).I1,I5,I6存在“移进-归约”冲突。不是LR(0)文法。(3).对于abab有两棵不同的语法树，任何二义性文法不是SLR(1)文法，也不是LALR(1)或LR(1)文法。SASaASSAbbaSASSAbAS bab4.90.S-S1.S-rD2.D-D,i3.D-i(2).I3中有“移进-归约”冲突，不是LR(0)文法(3).FOLLOW(S),=$,=,可以用SLR(1)文法解决4.90.S-S1.S-rD2.D-D,i3.D-i状状态ACTIONGOTOr,i$SD0S211acc2S433S5r14r3r35S66r2r24.13不含有冲突，因此是LR(1)文法合并同心集6和9，I69:A-x,d/e,B-,d/e出现“归约-归约”冲突，因此不是LALR(1)文法Thank you!