编译原理(习题课)(二)

1编译原理朱雪峰朱雪峰博士计算机科学技术和计算机科学技术与特尔3360 89733787 (o)电子邮件3360 xuefeng.zhu 2第6个问题(第P36 11个问题)解决方案：L2分析，b和c的数量相同，因此可以使用非终结器生成bncn字符串。因为使用其他非终结器创建ai，所以L1可以使用非终结器创建bncn，并模拟使用其他非终结器创建ai。L2的语法：SAB A aA | B bBc | BC 3的第六个问题(P36的第11个问题)解决方案：通过分析L3，可以将anbnambm除以anbn和ambm，从而分别使用两个非终结器生成anbnambm。L3语法：SAB A aAb | B aBb | 4的第六个问题(P36的第11个问题)解决方案：L4不能使用分段处理。中间0和1的数字必须相同，前面后面1和0的数字必须相同。对于此语法，我们可以从里向外扩展，使用生成连续m 0和m 1的非终止符。然后，可以使用另一个非终结器基于该字符串在前后扩展n个1和n个0。L4: A0A1 | S 1S0 | A 5第7个问题(第7个问题(第P64第7个问题)7)。以下常规相应的DFA1(0 | 1)* 1011(1010 * | 1(010)* 1)* 00 * 10 * 10 *(00 | 11)*() y 5 2，3，4，y 5 2，3 2，2，3，5 4 2，3，4 3 2，5，3 3 1 x 0状态8的第7个问题(P64的第7个问题)问题3 2，4，3 2，5，3，4，y 4 2，2 初始分割：0，1，2，3，4，0，1，2，3，4 0=2，4，_，0，1，20不能使用字符0，因此必须拆分状态0。此外，由于在读取状态4万字符1后进入状态5，因此分割状态4将分割以下四个集合：0、1，2，3、4、5。-嗯？对于集合1，2，3，1，2，30=2，4，因此必须进一步拆分1，2，3，除以的结果为0、1，2、3由于1，2 0=2，1，2 1=3，因此检查集合1，2时不再需要拆分。因此，最终的拆分结果是5个集合：0，1，2，3，4，5 10第7个问题(第7个问题(第P64 7个问题)第11个问题(第7个问题(第7个问题) 6，9 5，6，9 5，8，2 5，2 4，7 4，7 3，6 3，6 9 10状态13第7个问题(P64第7个问题) 14第7个问题(P64第7个问题)问题 0 * 10 * 10 * 10 * 15第7个问题(P64 7问题 (00) 标题 11，4 6 14，7 6 11，4 5，13 14，7 13，5 11 提供以下正则表达式：以01结尾的二进制字符串；可被5整除的十进制整数；包含奇数1或奇数0的二进制字符串；所有由字母组成的符号要按字母顺序排列符号字符串中的字母。没有重复数字的数字符号字符串的完整；数字符号字符串的总数，最多重复1个数字；由不包含子字符串abb的a和b组成的符号字符串的完整。19第八个问题(P64的第8个问题)的解决方法：(1)这个问题需要由0和1组成的二进制字符串，必须以01结束，所以这个问题可以分成由0和1组成的任意字符串的两部分。一个配置01，另一个连接01就可以了。因此，答案是(1|0)*01。20第8个问题(第8个问题(第P64个问题8)(2)需要十进制整数，即0到9的10个数字组成的字符串，不能以0(整数0除外)开头，并且字符串必须以0或5结尾才能被5整除)。可以分为两种情况。一种是整数只有1位的情况下，有两种可能性：0和5。在其他情况下，如果整数是多个位，则可以将该整数分成三部分来考虑。第一个位不能为零，第二个必须为0或5，第三个可以包含中间部分、无中间部分或0到9之间的任意数字。因此，此问题的正则表达式为(1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)(0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)考虑包含奇数0的字符串：由于只对零个奇偶校验感兴趣，所以可以将二进制字符串分成多个段来考虑。第一段是从第一个0开始的二进制字符串的第一个0，0之前有0个或多个1。对于剩馀的二进制字符串，以0开始，以0结束，中间可以有0个或更多的1。这样划分一个二进制字符串后，如果其馀部分都是完整的1字符串(这两个完整的1个字符串之间或最后一个字符串)，则该二进制字符串将包含奇数0，因此，此二进制字符串可以描述为以第一个段(1*0)开头，后跟完整的1字符串(1*)和包含0的字符串(01*0)这个问题的答案是1*0(1|01*0)* | 0*1(0|10*1)* 22第8个问题(P64的第8个问题)问题(4)(a | a)* *.(z | z) * 23第八个问题(第8个问题(P64的第8个问题)问题)(5)命令ri=I | (I=0，1，2，(9) r0 | R1 | R2 | | r9表示p (0，1，2，9)表示I=0、1、2、9的整个数组910 iii rrl)9，1，0(，910 ll PIII9，2，1，0(Li R 24的第8个问题，P64的第8个问题)满足条件的字符串：字符串的开头可以有0个或更多的b，但如果出现a，则b*(a|ab)* 26第9个问题(第9个问题(第P64第12个问题)12，因为后面或a出现时只有一个b，后面可以有a。分别确定和最小化图3.18中的(a)和(b)。27第九个问题(第P64第12个问题)解决：图(a)是NFA，必须先确定。获取DFA，然后将其最小化。第一步：结晶，获得DFA。结晶的结果见左表。给出状态编号，并获得右侧表中列出的状态转换矩阵。 0 1 0，1 0，1 0，1 0 0，1 0 解决ba状态02 211 210 ba状态28第9个问题(第9个问题(第P64 12个问题)将状态分为0，1 a=1、0，1 b=2两个集合，因此0，1和2成为最小化的DFA，如下图所示。30第9个问题(第P64第12个问题)解决方案：图(b)中列出了DFA，因此无需确认，只需最小化即可。首先，将状态设置为两个集合0，1、2，3，4，5、0，1a=1、0，1b=2，4和2，3，4，5a=然后，0，1a=1、0，1b=2，4、2，4a=1，0、2，4b=3，5、2，4第32个问题(第10个问题(第P65第14个问题)14。配置接受满足以下标准的所有字符串的DFA:每个1有0，就在右边。第33列问题(第10个问题(P65的第14个问题)第一步：创建正则表达式。根据标题，此DFA允许的字符串包括0和1，每个1后紧跟0。因为可以将此字符串解释为包含0和10的字符串，所以相应的正则表达式是(0|10)*第二步：配置NFA。首先导出图1。然后，根据P50的替代规则分解图1，得到图2所示的NFA。第34栏问题(第P65栏问题)XY (0|10)* 1 NFA 35栏问题(第10个问题(第P65 14个问题)第3步：决定并取得DFA。结晶的结果如左表所示，给出状态号码，得到右表所示的状态变换矩阵。1，y 2 1，y 1，y 2 1，y 10状态12 211 210状态36第十个问题(P65列14问题在第10个问题37(第10个问题(第P65列问题)的第4步中，使用P57方法最小化DFA。最小分析过程如下：初始分区：0，1，2请求相应的DFA，如下图所示。0 DFA 1 0 1 0 38第11个问题(第P81个问题)1。以下语法G1: s a | (t) t t，s | s 删除G1的左耳。然后，为每个非终结器创建没有回溯的递归子例程。重写的语法是LL(1)吗？请提供预测分析表。39问题11(问题P81)解决方法：(1)按t、s顺序删除左递归，以获得语法：g (s):sa | ( first (t)=a，-，( first (t)=， FOLLOW(S)=#，) P79页配置分析表m中的算法tST tt tST