武汉大学2015-2016《编译原理》期末试卷答案

武汉大学计算机学院2015-2016学年第一学期2013级《编译原理》参考答案一、(1)..0.start.1.1.5.1.1.5.1.2.𝜀.𝑏.𝑎.𝑏.𝑏.𝑎.𝑏.𝜀(2)𝐴t0,1,2,4,5u,𝐵t3,4,5u,𝐶t1,2,4,5u,𝐷t4,5u.状态转换图为：..𝐴.start.𝐵.𝐷.𝐶.𝑎.𝑏.𝑏.𝑎.𝑏.𝑏(3)最小DFA如下所示：..𝐴𝐶.start.𝐵𝐷.𝑎.𝑏.𝑏(4)由𝑎和𝑏组成且没有连续𝑎的字符串.(5)𝑟p𝑎𝑏|𝑏qp𝑎|𝜀q.二、(1)最左推导如下：𝑆ùñ𝑙𝑚t𝐼uùñ𝑙𝑚t𝐼,𝐼uùñ𝑙𝑚t𝐶,𝐼uùñ𝑙𝑚t𝑖∶𝐸,𝐼uùñ𝑙𝑚t𝑖∶𝑖,𝐼uùñ𝑙𝑚t𝑖∶𝑖,𝐶uùñ𝑙𝑚t𝑖∶𝑖,𝑖∶𝐸uùñ𝑙𝑚t𝑖∶𝑖,𝑖∶𝑖u(2)消除左递归后的文法如下：𝑆Ñt𝐼u𝐼Ñ𝐶𝐼1𝐼1Ñ,𝐼𝐼1|𝜀𝐶Ñ𝑖∶𝐸𝐸Ñ𝑖|𝑆1(3)Firstp𝑆qt{u;Firstp𝐼qFirstp𝐶qt𝑖u;Firstp𝐼1qt𝜀,,u;Firstp𝐸qt𝑖,{u.Followp𝑆qt$,},,u;Followp𝐼qFollowp𝐼1qFollowp𝐶qFollowp𝐸qt},,u.(4)LL(1)分析表如下所示：𝑖{},∶$𝑆𝑆Ñt𝐼u𝐼𝐼Ñ𝐶𝐼1𝐼1𝐼1Ñ𝜀𝐼1Ñ,𝐼𝐼1|𝜀𝐶𝐶Ñ𝑖∶𝐸𝐸𝐸Ñ𝑖𝐸Ñ𝑆(5)语句“t𝑖∶𝑖u’’的分析过程如下所示：剩余串分析栈分析动作t𝑖∶𝑖u$𝑆$𝑆Ñt𝐼ut𝑖∶𝑖u$t𝐼u$match-advance𝑖∶𝑖u$𝐼u$𝐼Ñ𝐶𝐼1𝑖∶𝑖u$𝐶𝐼1u$𝐶Ñ𝑖∶𝐸𝑖∶𝑖u$𝑖∶𝐸𝐼1u$match-advance∶𝑖u$𝐸𝐼1u$match-advance𝑖u$𝐸𝐼1u$𝐸Ñ𝑖𝑖u$𝑖𝐼1u$match-advanceu$𝐼1u$𝐼1Ñ𝜀u$u$match-advance$$分析成功三、(1)语句“t𝑎∶𝑎,𝑎∶𝑎,𝑎∶𝑎u’’的两颗不同的语法树为：语法树1：..𝑆.t.𝐼.𝐼.𝐼.𝐶.𝑖.∶.𝐸.𝐸.𝑖.,.𝐼.𝐶.𝑖.∶.𝐸.𝐸.𝑖.,.𝐼.𝐶.𝑖.∶.𝐸.𝐸.𝑖.u语法树2：2..𝑆.t.𝐼.𝐼.𝐶.𝑖.∶.𝐸.𝐸.𝑖.,.𝐼.𝐼.𝐶.𝑖.∶.𝐸.𝐸.𝑖.,.𝐼.𝐶.𝑖.∶.𝐸.𝐸.𝑖.u(2)无二义文法：𝑆Ñt𝐼u𝐼Ñ𝐼,𝐶|𝐶𝐶Ñ𝑖∶𝐸𝐸Ñ𝑖|𝑆四、(1)状态𝐼1的LR(0)项目集为t𝑆Ñt𝐼uut𝑆Ñt𝐼u,𝐼Ñ𝐼,𝐼,𝐼Ñ𝐶,𝐶Ñ𝑖∶𝐸u(2)状态𝐼1所接受的终结符组成的活前缀即是从开始状态𝐼0到状态𝐼1所有可能的路经对应的边标记序列.而经过终结符为状态转移边能到达状态𝐼1的只有状态𝐼0,𝐼1,𝐼5和𝐼9.故对应的正则表达式为：tp𝑖∶tq.(3)Followp𝑆qt$,},,u;Followp𝐼qFollowp𝐶qFollowp𝐸qt},,uSLR分析表如下所示：actiongoto状态𝑖{},:$𝑆𝐼𝐶𝐸0s141s5322r3r33s7s64acc5s96s5827r1r1r18r2r29s10s1121110r5r511r4r412r6r63(4)语句“t𝑖∶𝑖u’’的分析过程如下所示：剩余串分析栈分析动作t𝑖∶𝑖u$0shift𝑖∶𝑖u$0t1shift∶𝑖$0t1𝑖5shift𝑖u$0t1𝑖5∶9shiftu$0t1𝑖5∶9𝑖10reduce𝐸Ñ𝑖u$0t1𝑖5∶9𝐸11reduce𝐶Ñ𝑖∶𝐸u$0t1𝐶2reduce𝐼Ñ𝐶u$0t1𝐼3shift$0t1𝐼3u7reduce𝑆Ñt𝐼u$0𝑆4分析成功五、(1)产生式语义规则𝑆Ñt𝐼u𝑆.xml𝐼.xml𝐼Ñ𝐼1,𝐼2𝐼.xml𝐼1.xml𝐼2.xml𝐼Ñ𝐶𝐼.xml𝐶.xml𝐶Ñ𝑖∶𝐸𝐶.xml𝑖.lexval𝐸.xml/𝑖.lexval𝐸Ñ𝑖𝐸.xml𝑖.lexval𝐸Ñ𝑆𝐸.xml𝑆.xml(2)转换后的XML语言如下：glossarytitleexampleglossary/titleGlossDivtitleS/titleGlossListGlossEntryIDSGML/IDAbbrevISO8879:19864/AbbrevGlossDefparaAmeta-markuplanguage./para/GlossDefGlossSeemarkup/GlossSee/GlossEntry/GlossList/GlossDiv/glossary六、L0:t0:=x+1|x:=t1x:=t0|ifnot(ef)gotoL0ifnot(ab)gotoL1|ifnot(gh)gotoL1if(cd)gotoL1|if(ik)gotoL0t1:=x+2|L1:七、声明为数组的形参C语言编译器会自动转换为指针，因此sizeof(src)=4.所以foo()仅拷贝了s前4字符到t，且没有拷贝’\0’.5