《编译原理》作业与试题讲解.ppt

编译原理作业与试题讲解 黄冈师范学院 计科院 基础理论教研室 张瑞红 2.4 写出下述语言的正规式描述 2.4 写出下述语言的正规式描述 2.4 写出下述语言的正规式描述 2.4 写出下述语言的正规式描述 2.4 写出下述语言的正规式描述 2.4 写出下述语言的正规式描述 2.4 写出下述语言的正规式描述 2.9 用自然语言给出下述正规式所描述的语言，并构造 它们的最小DFA10*1 (0|1)*011(0|1)* 2.10 2.10 构造SLR（1）分析表的方法： 试题举例一、简答题 二、填空题 三、计算题（3.3） * * （1）由偶数个0和奇数个1构成的所有01串 采用算法解决：首先构造出识别偶数个0和奇数个1的自动机，然后使用自动机到正则表达式的算法求解。具体步骤参考《自动机理论、语言和计算导论》。 ((00+01(11)*10)*(1+01(11)*0)(0(11)*0)*(1+0(11)*10))*(00+01(11)*10)*(1+01(11)*0)(0(11)*0)* JFLAP 注：JFLAP中的“或”用“+”表示 （1）由偶数个0和奇数个1构成的所有01串 另一种思路：先写出偶数个0和偶数个1的正则表达式A，在此基础上，使用A、0、1构造出偶数个0和奇数个1的正则表达式。A=((00+11)+(10+01)(00+11)*(10+01))* A1A+A0A1A0A （1）由偶数个0和奇数个1构成的所有01串 另一种思路：先写出偶数个0和偶数个1的正则表达式A，在此基础上，使用A、0、1构造出偶数个0和奇数个1的正则表达式。A=((00+11)+(10+01)(00+11)*(10+01))* 1A+0A(10+01)A 若是1开头，则再加偶0和偶1即得结果; 若是0开头，则讨论0A后可跟： 跟00、11，则等价于0A； 跟01、10，则是0A(01+10)，已是偶0奇1，则再加偶0和偶1即得结果 （2）所有不含子串011的01串 思路一：3种状态：只接收了1，接收了0，接收了01 思路二：接收011的RE-DFA-不接收011的DFA-RE 接收011的DFA 不接收011的DFA x （2）所有不含子串011的01串 1*(0|01)* 1*(λ+0(0+10)*(λ+1)) 不接收011 (0|1)*011(0|1)* 1*00*1(00*1)*1(0+1)* 接收011 归纳结果 JFLAP算法结果 注：JFLAP中的“ε”用“λ”表示 （3）每个a后面至少紧随两个b的ab串 思路：abb应该为一个整体，和b进行组合，串的形式如下 bbbbb abb abb bbbb abb bbbbb...... (b*|abb)* (b|abb)* （4）C的形如/*…*/ 的注释。其中…代表不含*/的字符串 思路：接收*/的DFA-不接收*/的DFA-RE 接收*/的DFA中有3个状态：没有接收*；接收了*；接收了*/ ([^*] | **[^*/])* ** /* ([^*] | **[^*/])* ** */ x 所谓用自然语言描述：即解释字符串的性质 练习目的：锻炼思维推理能力 归纳：由特殊到一般的推理，如根据要求写正规式 演绎：由一般到特殊的推理，如根据正规式生成字符串 解： 10*1：首尾是1中间有零或若干个0的01串 (0|1)*011(0|1)* ：至少含一个011的01串 有一NFA的状态转换矩阵下表，其中S为初态，D为终态 S B C D A A B C C D A B B C A A A,B.C D C,D A,B S ε c b a 求出它的最小DFA 用正规式描述DFA所接受的语言 问题：根据DFA写出对应的正规式，通常的考虑和步骤是什么？ 正规式、DFA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是把正规集作为桥梁，先分析清楚DFA识别出的是一个什么集合，然后再设计此集合的正规式。(当然也可以采用机械化的算法来实现，不过结果往往很复杂，难以理解) 该DFA从初态到终态有三条路径：b|c|a(a|c)*b，而且是这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)*b)+ 3.6 设字母表∑={0,1}，设计下列语言的文法。对于正规语言，可用正规式表示。 （2）0和1个数相等的字符串； （3）0和1个数不相等的字符串； （2）（3）均不能用正规式表示，为什么？（鸽巢原理反证） （2）思路：S包含0、1个数相等，0、1相等的最小项是ε、01、10，则给它们加上S，则0、1个数仍相等 S - S0S1S | S1S0S | ε 消除直接左递归 S - S’ S’ - 0S1S