编译原理课后答案

第二章2.3阐述用以下正则表达式描述的语言：(a) 0(0|1)*0在字母 0，1 中，以0开始就结束的至少是2的01列(b) (|0)1*)*在字母 0，1 中，包括全部01字符串、空白字符串(c) (0|1)*0(0|1)(0|1)在字母 0，1 中，倒数第三是0的01列(d) 0*10*10*10*字母 0，1 包含3个1的01列(e ) (00|11 ) * (01|10 ) (00|11 ) * (01|10 ) (00|11 ) * ) *字母 0，1 包含偶数个0和偶数个1的01列2.4编写下列语言的正规定义：c语言注释是以/*开头的字符串和以*/结尾的字符串。 但是，前缀(不包括本身)不以*/结尾。解答othera|b|other是指*以外的c语言的其他文字other1a|b|other1是指*和/以外的c语言的其他字符comment/* other * (* other1other * ) * * * * /(f )由偶数个0和偶数个1组成的所有0和1的列。解答主题分析表明，一个符号串由0和1构成时，0和1的数量只有4个因为x偶数个0和偶数个1 (用状态0表示) x偶数个0和奇数个1 (用状态1表示) x奇数个0和偶数个1 (用状态2表示) x奇数个0和奇数个1 (用状态3表示)当读取1时，x状态0 (偶数个0和偶数个1 )变为偶数个0和奇数个1 (状态1 )当读取0时，x状态0 (偶数个0和偶数个1 )变为奇数个0和偶数个1 (状态2 )。当读取1时，x状态1 (偶数个0和奇数个1 )变为偶数个0和偶数个1 (状态0 )当x状态1 (偶数个0和奇数个1 )读取0时，0和1的数目变为奇数个0和奇数个1 (状态3 )。当x状态2 (奇数个0和偶数个1 )读取1时，0和1的数目变为奇数个0和奇数个1 (状态3 )。当x状态2 (奇数个0和偶数个1 )读取0时，0和1的数量变为偶数个0和偶数个1 (状态0 )当x状态3 (奇数个0和奇数个1 )读取1时，0和1的数目变为奇数个0和偶数个1 (状态2 )。当x状态3 (奇数个0和奇数个1 )读取0时，0和1的数目变为偶数个0和奇数个1 (状态1 )。其原因是，为了求出由偶数个0和偶数个1构成的所有的0和1的列，状态0是初始状态还是终止状态，其状态转移图如下由此，可以按如下方式写正规语法s 01 s1|0s2|s 11 s0|0s3|1s 21 s3|0s0|0s 31 s2|0s 1在不考虑S0生成式的情况下，可以将语法变形为s0=1s1s2s1=1s0s31s2=1s3s0s0S3=1S2 0S1因此： S0=(00|11)S0 (01|10)S3 11 00(1)S3=(00|11)S3 (01|10)S0 01 10(2)解(2)式的取得：将S3=(00|11)*(01|10)S0 (01|10 ) )代入(1)式s0=(00|11 ) s0 (01|10 ) (00|11 ) * (01|10 ) s0 (01|10 ) ) (00|11 )=s0=(00|11 ) (01|10 ) (00|11 ) * (01|10 ) ) s0 (01|11 ) * (01|10 ) (00|11 ) * (00|11 )=s0=(00|11 )|(00|11 ) (01|10 ) * (00|11 ) (01|10 ) (00|11 ) * (01|10 ) )=s0=(00|11 )|(01|10 ) (00|11 ) * (01|10 ) )因为S0所以由偶数个0和偶数个1构成的所有0和1列的正规定义为s 0(00|11 )|(01|10 ) (00|11 ) * (01|10 ) ) *(g )由偶数个0和奇数个1组成的所有0和1的列。解答这个题目可以参考问题的结论来处理。对偶数个0和奇数个1构成的全部0和1的列，按情况进行讨论(1)若符号串的开头字符为0，则剩馀字符串必定为奇数个的0和奇数个的1，因此除了偶数个的0和偶数个的1个符号串之外，还需要读取10 (红色的轨迹)或者01 (蓝色的轨迹)，另外，能够在01和13之间进行多次循环(红色的虚线的轨迹)，因此， 同样需要添加02和23 (蓝色虚线轨迹)，因此需要增加符号串(00|11)*，偶数个0和偶数个1用S0表示用s表示偶数个0和奇数个1时，其正规定义如下s0 (00|11 ) * (01|10 ) s0s 0(00|11 )|(01|10 ) (00|11 ) * (01|10 ) ) *(2)如果符号串的开头字符为1，则馀数字符串必定是偶数个的0和偶数个的1，其正规定义为： S1S0s0(00|11 )|(01|10 ) (00|11 ) * (01|10 ) ) *综合(1)和(2)，由偶数个0和奇数个1构成的所有0和1列，其正规定义为s0 (00|11 ) * (01|10 ) s0|s0s0(00|11 )|(01|10 ) (00|11 ) * (00|11 )2.7(c) (|a)b*)*01a.a234567乙组联赛58sf.f开始ababbab : s-4-0-1-5-6-7-8-4-0-1-5-6-7-8-4-0-0-5-6-8-f2.12是以下正规结构的最简单的DFA :(b)(a|b)*a(a|b)(a|b )(1)根据算法2.4，如图构筑与该正规式相对应的NFA。(2)通过算法2.2 (子集法)将NFA变换为等价的DFA (确定化过程)初始状态s0=- closure (0)= 0，1，2，4，7 标记状态s0S1=-closure(move(S0，a ) )=- closure ( 5，8 )= 1，2，4，5，6，7，8，9，11 S2=- closure (move (s0，b ) )=- closure (3 )= 1，2，3，4，6，7 标记状态S1S3=-closure(move(S1，a ) )=- closure ( 5，8，12 )= 1，2，4，5，6，7，8，9，11，12，13，14，16 S4=-closure(move(S1，b ) )=- closure ( 3，10 )= 1，2，4，5，6，7，10，13，14，16 标记状态S2S1=-closure(move(S2，a ) )=- closure ( 5，8 )= 1，2，4，5，6，7，8，9，11 S2=- closure (move (S2，b ) )=- closure (3 )= 1，2，3，4，6，7 标记状态S3S5=-closure(move(S3，a ) )=- closure ( 5，8，12，17 )= 1，2，4，5，6，7，8，9，11，12，13，14，16，17，18 S6=-closure(move(S3，b ) )=- closure ( 3，10，15 )= 1，2，4，5，6，7，10，13，14，15，16，18 标记状态S4S7=-closure(move(S4，a ) )=- closure ( 5，8，17 )= 1，2，4，5，6，7，8，9，11，17，18 S8=-closure(move(S4，b ) )=- closure ( 3，15 )= 1，2，3，4，6，7，15，18 标记状态S5S5=-closure(move(S5，a ) )=- closure ( 5，8，12，17 )= 1，2，4，5，6，7，8，9，11，12，13，14，16，17，18 S6=-closure(move(S5，b ) )=- closure ( 3，10，15 )= 1，2，4，5，6，7，10，13，14，15，16，18 标记状态S6S7=-closure(move(S6，a ) )=- closure ( 5，8，17 )= 1，2，4，5，6，7，8，9，11，17，18 S8=-closure(move(S6，b ) )=- closure ( 3，15 )= 1，2，3，4，6，7，15，18 标记状态S7S3=-closure(move(S7，a ) )=- closure ( 5，8，12 )= 1，2，4，5，6，7，8，9，11，12，13，14，16 S4=-closure(move(S7，b ) )=- closure ( 3，10 )= 1，2，4，5，6，7，10，13，14，16 标记状态S8S1=-closure(move(S8，a ) )=- closure ( 5，8 )= 1，2，4，5，6，7，8，9，11 S2=- closure (move (S8，b ) )=- closure (3 )= 4，6，7 由此，如上所述，确定后的DFA的状态集合S=S0，S1，S2，S3，S4，S5，S6，S7，S8、输入符号集合=a，b、状态转移函数move表示S0为开始状态、接收状态集合F=S5，S6，S7，S8的状态转移图(3)通过算法2.3使DFA最小化初次区分： S0，S1，S2，S3，S4S5，S6，S7，S8S0，S1，S2，S3，S4a=S1，S3，S1，S5，S7第二次区分： S0，S1，S2S3，S4S5，S6，S7，S8S0，S1，S2a=S1，S3，S1第三次划分： S0，S2S1S3，S4S5，S6，S7，S8S0，S2a=S1S0，S2b=S2S0，S2不能区分，即等价。 S5，S6，S7，S8a=S5，S7，S3，S1第4次划分： S0，S2S1S3，S4S5，S6S7，S8S3，S4a=S5，S7第5次划分： S0，S2S1S3S4S5，S6S7，S8S5，S6a=S5，S7第6次划分： S0，s2S1s3s5s6s7，S8S7，S8a=S3，s1第7次划分： S0，s2 s1 s3 s4 s5 s6 s7 s8集合不能再划分因此，S0、S2等价，选择S0显示S0、S2，其状态转移图，即主题所要求的最简单的DFA如下第三章3.13.23.103.113.203.23第四章4.1主题有些不同的方法4.7(a )4.10(a )第六章6.36.56.126.236.9c语言函数f的定义如下： int f (int x，*py，*ppz) *ppz=1； *py=2； x=3； return x *py *ppz； 以下称为变量a是指向b的指针；变量b是指向c的指针；变量c是当前值为4的整数变量。 调用f(a，b，c )后，返回值是什么？由于调用顺序不正确，因此f(c，b，a )应该符合函数的定义。 否则我们无法编译。 调用时不要强制转换。如果在强制变换后调用，那么在f函数内，ppz是波形参数，指针为整数指针，ppz的实际参数是c，其值是4，指向的地址空间是错误的。 py很好，但实际参照是b，指c，*py的值是c的值，是4。 x的实数是a，实际上是整数指针的指针，函数内作为整数使用，但其值不确定。按照f(c，b，a )的顺序调用*ppz=1时，c=*b=*a=5； *py=2之后，c=*b=*a=7，x=3之后，x=7，c=*b=*a=7(这是因为x为值传递，即使c变化x也没有变化，x变化c也没有变化)最终返回到7 7 7=21。第七章7.13