资源描述:
《编译原理(清华大学 第2版)课后习题答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第三章N=>D=>{0,1,2,3,4,5,6,7,8,9}N=>ND=>NDDL={a
2、a(0
3、1
4、3..
5、9)n且n>=1}(0
6、1
7、3..
8、9)n且n>=1{ab,}anbnn>=1第6题.(1)<表达式>=><项>=><因子>=>i(2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=i*i(4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子
9、>+<项>=><因子>*<因子>+<因子>=i*i+i(5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=i+<项>=>i+<因子>=>i+(<表达式>)=>i+(<表达式>+<项>)=>i+(<因子>+<因子>)=>i+(i+i)(6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*<因子>=>i+<因子>*<因子>=i+i*i第7题36第9题语法树推导:S=>SS*=>SS+S*=>aa+a*11.推导:E=>E+T=>E+T*F
10、语法树:短语:T*FE+T*F直接短语:T*F句柄:T*F12.36短语:直接短语:句柄:13.(1)最左推导:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导:S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>a1b1b2a2a3(2)文法:SàABSSàAaSàεAàaBàb(3)短语:a1,b
11、1,b2,a2,,bb,aa,abbaa,直接短语:a1,b1,b2,a2,,句柄:a114(1)SàABAàaAb
12、εBàaBb
13、ε(2)Sà1S0SàAAà0A1
14、ε第四章1.1.构造下列正规式相应的DFA(1)1(0
15、1)*101NFA(2)1(1010*
16、1(010)*1)*0NFA36(3)NFA(4)NFA2.解:构造DFA矩阵表示01{X}0{Z}{X}{Z}*{X,Z}{Y}{X,Z}*{X,Z}{X,Y}{Y}{X,Y}36{X,Y}{X,Y,Z}{X}{X,Y,Z}*{X,Y,Z}{X,Y}
17、其中0表示初态,*表示终态用0,1,2,3,4,5分别代替{X}{Z}{X,Z}{Y}{X,Y}{X,Y,Z}得DFA状态图为:3.解:构造DFA矩阵表示构造DFA的矩阵表示01{S}0{V,Q}{Q,U}{V,Q}{Z,V}{Q,U}{Q,U}{V}{Q,U,Z}{Z,V}*{Z}{Z}{V}{Z}{Q,U,Z}*{V,Z}{Q,U,Z}{Z}{Z}{Z}其中0表示初态,*表示终态替换后的矩阵0100121322453*66465*35666构造DFA状态转换图(略)4.(1)解构造状态转换矩阵:36ab{0
18、}0*{0,1}{1}{0,1}*{0,1}{1}{1}{0}转换为ab0*121*1220{2,3}{0,1}{2,3}a={0,3}{2},{3},{0,1}{0,1}a={1,1}{0,1}b={2,2}(2)解:首先把M的状态分为两组:终态组{0},和非终态组{1,2,3,4,5}此时G=({0},{1,2,3,4,5}){1,2,3,4,5}a={1,3,0,5}{1,2,3,4,5}b={4,3,2,5}由于{4}a={0}{1,2,3,5}a={1,3,5}因此应将{1,2,3,4,5}划分为{4
19、},{1,2,3,5}G=({0}{4}{1,2,3,5}){1,2,3,5}a={1,3,5}{1,2,3,5}b={4,3,2}因为{1,5}b={4}{23}b={2,3}所以应将{1,2,3,5}划分为{1,5}{2,3}G=({0}{1,5}{2,3}{4}){1,5}a={1,5}{1,5}b={4}所以{1,5}不用再划分{2,3}a={1,3}{2,3}b={3,2}因为{2}a={1}{3}a={3}所以{2,3}应划分为{2}{3}所以化简后为G=({0},{2},{3},{4},{1,5}
20、)7.去除多余产生式后,构造NFA如下36确定化,构造DFA矩阵abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD变换为ab00131122*343354165*14634化简:G={(0,1,3,4,6),(2,5)}{0,1,3,4,6}a={1,3}{0,1,3,4,6}b={2,3,4,5,6}所以将{0,1,3,4,6}划分为{0,4,6}{1,3}G={(0,4