资源描述：
《编译原理课后习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章P36-6(1)是0~9组成的数字串(2)最左推导:最右推导:P36-7G(S)P36-8文法：最左推导:最右推导:语法树：/********************************P36-11/***************L1:L2:L3:L4:***************/9、对下面情况给出DFA及正规表达式：(1）{0,1}上的含有子串010的所有串。正规式：(0
2、1)*010(0
3、1)*(2）{0,1}上不含子串010的所有串。正规式：1*(0
4、11*1)*1*(0
5、11)*1*1*0*1*(0
6、11)*(0
7、1)10.一个人带着狼、山羊、白菜在一条河的
8、左岸。状态左岸右岸0人，羊，狼，菜NULL1狼，菜人，羊2人，狼，菜羊3狼人，羊，菜4人，羊，狼菜5羊人，狼，菜6人，羊狼，菜7NULL人，羊，狼，菜P64–12(a)a10a,ba确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ给状态编号：ab012112203333a10aabbb32ba最小化：210bbab(b)032bbaabaab541baaa已经确定化了,进行最小化最小化：021bbaabaP81–1(1)按照T,S的顺序消除左递归递归子程序：procedureS;beginifsym='a'orsym='^'thenabvancee
9、lseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;end;procedure;beginifsym=','thenbeginadvance;S;endend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}
10、预测分析表a^(),#ST是LL(1)文法P81–2文法：(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,
11、+,),#}(2)考虑下列产生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EE'TT'F
12、F'P(4)procedureE;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginT;E'endelseerrorendprocedureE';beginifsym='+'thenbeginadvance;Eendelseifsym<>')'andsym<>'#'thenerrorendprocedureT;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginF;T'endelseerrorendprocedureT';beginifsym='('orsym='a'orsym='b
13、'orsym='^'thenTelseifsym='*'thenerrorendprocedureF;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginP;F'endelseerrorendprocedureF';beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym='a'orsym='b'orsym='^'thenadvanceelseifsym='('then
