编译原理课后习题.docx

编译原理课后习题.docx弟一早P36-6(1)厶(G)是0~9组成的数字串⑵最左推导:NnNDnNDDnNDDDnDDDDn0DDDn01DDn012Dn0127NnND=DDn3D=34NnNDnNDDnDDDn5DD=56Dn5b8最右推导:NnNDnNTnND7nNZ1nNDT1=>N127n0127n0127NnNDnN4nD4n34NnNDnNZNDSn7V68nD68=>568P36-7G(S)Ot1|3|5|7|9Nt2|4|6|&ODtO|NS^O\AOAD\NP36-8文法:E^T\E+T\E-TTtF\T^F\TIFFt(E)W最左推导:EnE+TnT+TnF+T"+:rm+T*F"+F*Fm+i*Fm+i*iE=>T=>:T*F=>F*F=>i*F=>i*(E)=>j*(E+T)=>i*(T+:O=>j*(F+T)=>z*(z+T)=>z*(z4-F)=>i*(z+z)最右推导:E=>E+T=>E+T*FnE+T*inE+F*inE+i*inT+i*iaF+i*i=>i+i*iEnT=>F*T=>F*F=>F*(E)nF*(E+T)=>F*(£+F)nF*(£+i)=>F*(T+i)=>F*(F+i)=>F*(i+i)nz*(i+z)语法树./********************************ETFTEF F iETFT■1i+i+i•••1-1-11i+i*iP36-11/ >1%^T%#T% ^1%LI:StACATaAb|abC—>cC|£12Stab4taAI£BTbBc|beStABA―>aAb|sB->aBb\£L4:StA|BAT0A11£Bt1B0|A9、对下面情况给出DFA及正规表达式:(1){0,1}上的含有子串010的所有串。正规式:(0|1)*010(0|1)*(2){0,1}±不含了串010的所有串。正规式:1*(0111*1)*1*(0|11)*1*1*0*1*(0|11)*(0|1)、山羊、口菜在一条河的左岸。状态左岸右岸0人,羊,狼,菜NULL1狼,菜人,羊2人,狼,菜羊3狼人,羊,菜4人,羊,狼菜5羊人,狼,菜6人,羊狼,菜7NULL人,羊,狼,菜P64-12(a)a确定化:ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}e4>0©给状态编号:ab0**********最小化:{0,1},{2,3}{0,1}广{1} {0,1}厂{2}{2,3}“二{0,3} {2,3}/?二{3}{0,1},⑵,⑶(b)24已经确定化了,进行最小化最小化:{{0,1},{2,3,4,5}}{0,1}严{1} {0,1}严{2,4}{2,3,4,5}“={1,3,0,5} {2,3,4,51.={2,3,4,5}{2,4}“={1,0} {2,4},={3,5}{3,5}“={3,5} {3,5}〃={2,4}{{0,1},{2,4},{3,5}}{0,1}.={1} {0,1}严{2,4}{2,4}“={1,0} {2,4}.={3,5}{3,5},={3,5} {3,5},={2,4}aP81-1⑴按照T,S的顺序消除左递归G©STdW)TtST'VT,S厂I£递归了程序:procedureS;beginifsym-aorsym二,thenabvaneeelseifsym二'(’thenbeginadvance;T;ifsym=')‘thenadvanee;elseerror;endelseerrorend;procedureT;begins;rend;procedureT‘;beginifsym二,,thenbeginadvanee;s;rendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,\(}FIRST(T)={a/,(}FIRST(厂)二{,,£}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(F)={)}预测分析表aS-yciSt人St(7)TtST'TfST'TtST'rr^£T'fST'是I丄⑴文法P81-2文法:EtTE'£T+E|£TtFT'厂T门£FtPF'F't*F|£Pt(E)|q|/?F仃)FIRST(E)={(,a,b/}FIRST(E,)={+,e}FIRST(T)={(,a,b/}FIRST(D={(,a,b,\e}FIRST(F)={(,a,b/}FIRST(F,)={*,e}FIRST(P)={(,a,b/}FOLLOW(E)={#,)}FOLLOW(E*)={#,)}FOLLOW(T)={+,),#}FOLLOW(TJ)={+,),#}FOLLOW(E)={(,a,b「,+,),#}FOLLOW(