编译原理(清华大学 第2版)课后习题答案

第三章N=>D=>{0,1,2,3,4,5,6,7,8,9}N=>ND=>NDDL={a|a(0|1|3..|9)n且n>=1}(0|1|3..|9)n且n>=1{ab,}anbnn>=1第6题.(1)<表达式>=><项>=><因子>=>i(2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)(3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=i*i(4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<项>=><因子>*<因子>+<因子>=i*i+i(5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=i+<项>=>i+<因子>=>i+(<表达式>)=>i+(<表达式>+<项>)=>i+(<因子>+<因子>)=>i+(i+i)(6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+<项>*<因子>=>i+<因子>*<因子>=i+i*i第7题第9题语法树推导:S=>SS*=>SS+S*=>aa+a*11.推导:E=>E+T=>E+T*F语法树:短语:T*FE+T*F直接短语:T*F句柄:T*F12．短语：<T><F><MOP><E><T><F><MOP><POP>直接短语：<T><F><MOP>句柄：<T><F><MOP>13.(1)最左推导：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>a1b1b2a2a3(2)文法：SABSSAaSεAaBb(3)短语：a1,b1,b2,a2,,bb,aa,abbaa,直接短语：a1,b1,b2,a2,,句柄：a114(1)SABAaAb|εBaBb|ε(2)S1S0SAA0A1|ε第四章1.1.构造下列正规式相应的DFA(1)1(0|1)*101NFA(2)1(1010*|1(010)*1)*0NFA(3)NFA(4)NFA2.解：构造DFA矩阵表示01{Z}{X}{X}0{Z}*{X,Z}*{X,Z}{X,Z}{Y}{X,Y}{Y}{X,Y}{X,Y}{X,Y,Z}*{X,Y,Z}{X,Y,Z}{X}{X,Y}其中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}{Q,U}{Z,V}*{Z,V}{V}{Z}{Q,U}{Q,U,Z}{Z}{V}{Z}{Q,U,Z}*{V,Z}{Z}{Z}{Q,U,Z}{Z}其中0表示初态，*表示终态替换后的矩阵011200123*34625645*663656构造DFA状态转换图（略）4．（1）解构造状态转换矩阵：ab{0}0*{0,1}{1}{0,1}*{0,1}{1}{1}{0}转换为a1b20*1*2102{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},{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}）7.去除多余产生式后，构造NFA如下确定化，构造DFA矩阵abSAB,ZQDAAQQAAQQB,ZDD,ZBDD,ZBD变换为a1b30012*1324345*311564634化简：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,