编译原理课后习题答案陈俊老师.doc

第1章 1(1) (2) (3) (4) (5) (6) 第2章1(1) (2) (3) (4) (5) (6) 2（1）终结符：0，1，2，3，4，5，6，7，8，9，10非终结符：N，S，E，D（2）N SES10 D10110N SES0 SD0S10D101101DESN1D01 110最右推导的语法树0ESNDS1（3）偶数的集合3（1）句子abab的两个相应的最右推导：S aSbS aSbaSbS aSbaSb aSbab ababS aSbS aSb abSaSb abSab abab （2）此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。4能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。所求文法GS:SMF|5F5|0N1|2|3|4|5|6|7|8|9DN|0MMD|N其中，S代表能被5整除且不以0开头的无符号整数;F代表可以出现在个位上的数字;D代表所有数字;N代表所有非零数字;M代表不以零开头的数字串。5（1）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下： S aE|Ea|bSS|SbS|SSbE aEbE|bEaE|（2）设文法开始符号为S，产生的w中满足|a|b|2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）： S aSBS|BSaS|B b|bb（3）SHMT|HT|TH1|2|3|4|5|6|7|8|9T 1|3|5|7|9MMN|NN0|H其中，H代表奇数头，T代表奇数尾，M代表整数，N代表数字6（1）1型（2）2型（3）3型7正确的程序为：var a,b,c;begin read(a,b); c:=100; if a0 thenbegin b:=b+1;write(b)end; write(a,b,c);end.8(1) 扩充条件语句的语法图为：EBNF的语法描述为：条件语句if条件then语句else语句(2) 扩充repeat语句的语法图为：EBNF的语法描述为：repeat循环语句 repeat语句；语句until条件 第3章1(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) 2注意 正规式不唯一（1）(0|1)*01 （2）1*01* （3）(11)* （4）(0*10*10*)* （5）(0|1)*01(0|1)* （6）1*0* 3（1）必须以 x 开头和x结尾的串（2）每个 y 至少有一个 x 跟在后边的串（3）所有含两个相继的x或两个相继的y的串412453othersothers/*/标记为others的边是指字符集中未被别的边指定的任意其它字符。分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。在这个DFA中，最容易忽略的是状态4到本身的*转换。这个边的含义是：在离开注释前的中间状态，若下一个字符是*，那么把刚才读过的*看成是注释中的一个字符，而把这下一个字符看成可能是结束注释的第一个字符。若没有这个边，那么象/* This is a comment */这样的注释就被拒绝。另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。12453othersothers/*/6othersothersall all5先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：羊空菜羊狼空羊羊空狼羊菜空羊现给出一个NFA:M=(,Q,0,9,f)其中=羊，空，菜，狼Q=0,1,2,3,4,5,6,7,8,9转换函数f(0,羊)=1, f(1,空)=2, f(2,菜)=3, f(2,狼)=5, f(3,羊)=4 f(5,羊)=6, f(4,狼)=7, f(6,菜)=7, f(7,空)=8, f(8,羊)=96这个DFA和无符号数的DFA有类似的地方。首先考虑device:和.extension全都出现的情况。（即：device:name.extension）这时的DFA比较容易构造。ll123456l:ll.l文件名的三部分都出现的DFA然后考虑缺省情况：(1) 因为.extension可缺省（即：device:name），因此把状态4也作为接受状态。(2) 因为name和device一样，都是字母序列，所以在device:缺省时，把到状态2为止得到的字母序列看成是name。由于device:和.extension都可缺省（即： name），因此把状态2也作为接受状态。(3) （即：name.extension）因为name和device一样，都是字母序列，因此在device:缺省时，把到状态2为止得到的字母序列看成是name，所以从状态2画一条转换边到状态5，标记为.。135246l:ll.l.ll 接受文件名的DFA7文法所对应的正规式为：S=0A|1B =0(1S|1)| 1(0S|0) =0(1S|1)|1(0s!0) 分配率=01S|01|10S|10 交换率=01S|10S|01|10 分配率=(01|10)S|(01|10)=(01|10)*(01|10)8该正规式所表示的语言为：L(G)=X|X以三个0结尾的二进制数字串 由于除了长度可以无限、最后是三个0外，语言的句子没有其他的限制，因此在构造正则文法时，将句子分成(0|1)*和000两部分考虑。(0|1)*可以通过递归实现，000则只需要逐个生产即可。所以构造其等价的右线性文法如下：GS:S0S|1S|0AA0BB09（1）根据题意，得到相应的正规式：0(0|1)*1（2）构造相应的NFA如下图所示：0A101SZ（3）NFA确定化后的DFA如下图所示：30112001（4）此DFA不存在多余状态和等价状态，是最小化的DFA。10（1）L(G)=X|X是至少含有两个连续1的二进制数字串（2）正规式为：(0|1)*11(0|1)*正规式到正规文法的转换过程为： S(0|1)*11(0|1)* S(0|1)S S11(0|1)* S0S|1S S1A A1(0|1)* S0S|1S|1A A1B B(0|1)* S0S|1S|1A A1B B(0|1)B Be S0S|1S|1A A1B B0B|1B Be（3）NFA确定化后的DFA如下图所示：014021011301（4）DFA最小化的结果如下图所示：310121010第4章1(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12)2短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单短语有: F ，i 句柄是: F 最左素短语是: E+F 3句型(SdG)a的短语：(SdG)y goto 32: goto 03: if yz goto 54: goto 85: T1=x+z6: x=T17: goto 108: T2=y+z9: x=T210: goto 111有PL/0的源程序如下：procedure p;var a,b,c,m;begin read(a,b,c); m:=a; if ab then m:=b; if mc then m:=c; write(m)end;begin call pend.（1）符号表如下：namekindlevel/