《编译原理教程》习题解析与上机指导课件

单击此处编辑母版标题样式,*,第二章 词法分析,第二章 词法分析,第二章 词法分析,1,2.1 完成下列选择题：(1) 词法分析所依据的是,。A语义规则 B构词规则 C语法规则 D等价变换规则(2) 词法分析器的输入是,。A单词符号串B源程序 C语法单位 D目标程序(3) 词法分析器的输出是,。A单词的种别编码 B单词的种别编码和自身的值C单词在符号表中的位置 D单词自身值,2.1 完成下列选择题：(1) 词法分析所依据的是,2,(4) 状态转换图(见图2-1)接受的字集为 _。A以0开头的二进制数组成的集合B以0结尾的二进制数组成的集合 C含奇数个0的二进制数组成的集合 D含偶数个0的二进制数组成的集合,图2-1 习题2.1的DFA M,(4) 状态转换图(见图2-1)接受的字集为 _,3,(5) 对于任一给定的NFA M，,一个DFA M，使L(M)= L(M)。A一定不存在 B一定存在 C可能存在 D可能不存在(6) DFA适用于,。A定理证明 B语法分析 C词法分析 D语义加工,(5) 对于任一给定的NFA M， 一个DFA M,4,(7) 下面用正规表达式描述词法的论述中，不正确的是,。A词法规则简单，采用正规表达式已足以描述B正规表达式的表示比上下文无关文法更加简洁、直观和易于理解C正规表达式描述能力强于上下文无关文法D有限自动机的构造比下推自动机简单且分析效率高(8) 与(a|b)*(a|b)等价的正规式是,。A(a|b) (a|b)* Ba*|b* C(ab)*(a|b)* D(a|b)*,(7) 下面用正规表达式描述词法的论述中，不正确的是,5,(9) 在状态转换图的实现中，,一般对应一个循环语句。A不含回路的分叉结点 B含回路的状态结点C终态结点 DAC都不是(10) 已知DFA M,d,=(s,0,s,1,s,2,a,b,f,s,0,s,2,)，且有：f(s,0,a)=s,1,f(s,1,a)=s,2,f(s,2,a)=s,2,f(s,2,b)=s,2,则该DFA M所能接受的语言可以用正规表达式表示为,。A(ab)* Baa(ab)* C(ab)*aa Da(ab)*a,(9) 在状态转换图的实现中， 一般对应一个循环语,6,【解答】,(1) 由教材第一章1.3节中的词法分析，可知词法分析所遵循的是语言的构词规则。故选B。(2) 词法分析器的功能是输入源程序，输出单词符号。故选B。(3) 词法分析器输出的单词符号通常表示为二元式：(单词种别，单词自身的值)。故选B。(4) 虽然选项A、B、D都满足题意，但选项D更准确。故选D。(5) NFA可以有DFA与之等价，即两者描述能力相同；也即，对于任一给定的NFA M，一定存在一个DFA M，使L(M)=L(M)。故选B。,【解答】(1) 由教材第一章1.3节中的词法分析，,7,(6) DFA便于识别，易于计算机实现，而NFA便于定理的证明。故选C。(7) 本题虽然是第二章的题，但答案参见第三章3.1.3节。即选C。(8) 由于正则闭包R+=R*R=RR*，故(a|b)*(a|b)=(a|b) (a|b)*。故选A。(9) 含回路的状态结点一般对应一个循环语句。故选B。(10) DFA Md所对应的DFA如图2-2所示。故选B。,(6) DFA便于识别，易于计算机实现，而NFA便于定,8,图2-2 DFA M,图2-2 DFA M,9,2.2 什么是扫描器？扫描器的功能是什么？,【解答】,扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。2.3 设M=(x,y, a,b, f, x, y)为一非确定的有限自动机，其中f定义如下： f(x,a)=x,y fx,b=y f(y,a)= fy,b=x,y试构造相应的确定有限自动机M。,2.2 什么是扫描器？扫描器的功能是什么？【解答,10,【解答】,对照自动机的定义M=(S,f,s,0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。先画出NFA M相应的状态图，如图2-3所示。,图2-3 习题2.3的NFA M,【解答】 对照自动机的定义M=(S,f,s0,11,用子集法构造状态转换矩阵，如表2-1所示。,表2-1 状态转换矩阵,用子集法构造状态转换矩阵，如表2-1所示。表2-1 状,12,将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到M=(0,1,2,a,b,f,0,1,2)，其状态转换图如图2-4所示。,图2-4 习题2.3的DFA M,将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转,13,表2-2 重命名后的状态转换矩阵,表2-2 重命名后的状态转换矩阵,14,将图2-4所示的DFA M最小化。首先，将M的状态分成终态组1,2与非终态组0。其次，考察1,2。由于1,2a=1,2b=2,1,2，因此不再将其划分了，也即整个划分只有两组：0和1,2。令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-5所示的化简了的DFA M。,将图2-4所示的DFA M最小化。首先，将M的状态分,15,图2-5 图2-3化简后的DFA M,图2-5 图2-3化简后的DFA M,16,2.4 正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。,【解答】,正规式(ab)*a对应的NFA如图2-6所示，正规式a(ba) *对应的NFA如图2-7所示。,图2-6 正规式(ab)*a对应的NFA,2.4 正规式(ab)*a与正规式a(ba)*是否等价,17,图2-7 正规式a(ba)*对应的NFA,图2-7 正规式a(ba)*对应的NFA,18,用子集法将图2-6和图2-7分别确定化为如图2-8(a)和(b)所示的状态转换矩阵，它们最终都可以得到最简DFA，如图2-9所示。因此，这两个正规式等价。,图2-8 图2-6和图2-7确定化后的状态转换矩阵,用子集法将图2-6和图2-7分别确定化为如图2-8(a),19,图2-9 最简DFA,图2-9 最简DFA,20,实际上，当闭包*取0时，正规式(ab) *a与正规式a(ba)*由初态X到终态Y之间仅存在一条a弧。由于(ab)*在a之前，故描述(ab)*的弧应在初态结点X上；而(ba)*在a之后，故(ba)*对应的弧应在终态结点Y上。因此，(ab)*a和a(ba)*所对应的NFA也可分别描述为如图2-10(a)和(b)所示的形式，它们确定化并化简后仍可得到图2-9所示的最简DFA。,实际上，当闭包*取0时，正规式(ab) *a与正规式a(,21,图2-10 (ab)*a和a(ba)*分别对应的NFA,图2-10 (ab)*a和a(ba)*分别对应的NFA,22,2.5 设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1) 给出描述该语言的正规表达式；(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。,【解答】,该语言对应的正规表达式为a(aa)*bb(bb)* a(aa)*，正规表达式对应的NFA如图2-11所示。,2.5 设有L(G)=a2n+1b2ma2p+1|,23,图2-11 习题2.5的NFA,图2-11 习题2.5的NFA,24,用子集法将图2-11确定化，如图2-12所示。,图2-12 习题2.5的状态转换矩阵,用子集法将图2-11确定化，如图2-12所示。图2-12,25,由图2-12重新命名后的状态转换矩阵可以看出：状态0和状态2面对输入字符a、b的下一状态相同，状态3和状态5面对输入字符a、b的下一状态相同，即得到划分后的状态子集为0,2 1 3,5 4 6 7按顺序重新命名为0、1、2、3、4、5后得到最简的DFA如图2-13所示。,由图2-12重新命名后的状态转换矩阵可以看出：状态0和状,26,图2-13 习题2.5的最简DFA,图2-13 习题2.5的最简DFA,27,注意，如果将状态4和状态6作为等价状态，即得到划分后的状态子集为0,2 1 3,5 4,6 7按顺序重新命名为0、1、2、3、4后得到最简的DFA如图2-14所示。由图2-14可以看出，由状态4输入a可以到达状态3，由状态3输入b可以到达状态2，即可形成如下的字符串：aaabbbaaabbbaaabbbaaa而不是本题正规表达式可形成的字符串：aaabbbaaa。,注意，如果将状态4和状态6作为等价状态，即得到划分后的状,28,图2-14 习题2.5的最简DFA,图2-14 习题2.5的最简DFA,29,2.6 有语言L=w|w(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机(DFA)。,【解答】,对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1 (00(00)*1)*00(00)*10*，画出与正规式对应的NFA，如图2-15所示。,2.6 有语言L=w|w(0,1)+，并且w中,30,图2-15 习题2.6的NFA,图2-15 习题2.6的NFA,31,用子集法将图2-15所示的NFA确定化，如图2-16所示。,图2-16 习题2.6的状态转换矩阵,用子集法将图2-15所示的NFA确定化，如图2-16所示,32,由图2-16可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为0 1 2,4 3 5 6,8 7按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-17所示。,图2-17 习题2.6的最简DFA,由图2-16可看出非终态2和4的下一状态相同，终态6和8,33,2.7 已知正规式(a|b)*|aa)*b和正规式(a|b)*b。(1) 试用有限自动机的等价性证明这两个正规式是等价的；(2) 给出相应的正规文法。,【解答】,(1) 正规式(a|b)*|aa)*b对应的NFA如图2-18所示。,2.7 已知正规式(a|b)*|aa)*b和正,34,图2-18 正规式(a|b)*|aa)*b对应的NFA,图2-18 正规式(a|b)*|aa)*b对应的NF,35,用子集法将图2-18所示的NFA确定化为DFA，如图2-19所示。,图2-19 图2-18确定化后的状态转换矩阵,用子集法将图2-18所示的NFA确定化为DFA，如图2-,36,由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。,表2-3 合并后的状态转换矩阵,由于对非终态的状态1、2来说，它们输入a、b的下一状态是,37,由此得到最简DFA，如图2-20所示。,图2-20 习题2.7的最简DFA,由此得到最简DFA，如图2-20所示。图2-20 习题2.,38,正规式(a|b)*b对应的NFA如图2-21所示。,图2-21 正规式(a|b)*b对应的NFA,正规式(a|b)*b对应的NFA如图2-21所示。图,39,用子集法将图2-21所示的NFA确定化为如图2-22所示的状态转换矩阵。,图2-22 图2-21确定化后的状态转换矩阵,用子集法将图2-21所示的NFA确定化为如图2-22所示,40,比较图2-22与图2-19，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-20所示。因此，两个自动机完全一样，即两个正规文法等价。 (2) 对图2-20，令A对应状态1，B对应状态2，则相应的正规文法GA为GA：AaA|bB|b BaA|bB|bGA可进一步化简为GS：SaS|bS|b(非终结符B对应的产生式与A对应的产生式相同，故两非终结符等价，即可合并为一个产生式)。,比较图2-22与图2-19，重新命名后的转换矩阵是完全一,41,2.8 构造一个DFA，它接收=a,b上所有不含子串abb的字符串。,【解答】,本题对应的正规表达式为b*(aab)*，对应的NFA如图2-23所示。,图2-23 正规式b*(a|ab)*对应的NFA,2.8 构造一个DFA，它接收=a,b上所有不,42,用子集法将图2-23所示的NFA确定化为DFA，如图2-24所示。,图2-24 图2-23确定化后的状态转换矩阵,用子集法将图2-23所示的NFA确定化为DFA，如图2-,43,由图2-24重新命名后的转换矩阵可以看出：状态0、状态1和状态2对输入字符b的下一状态都是不一样的，故状态0、状态1和状态2已为最简状态。由此得到最简DFA，如图2-25所示。,图2-25 习题2.8的最简DFA,由图2-24重新命名后的转换矩阵可以看出：状态0、状态1,44,注意，诸如a*b*这类正规式简化的NFA只能画成图2-26的形式，而不能画成图2-27的形式，图2-27对应的是正规式(ab)*。本题对应的另一个正规表达式为b*(aba)*(ab)*。,图2-26 a*b*的NFA 图2-27 (ab)*的NFA,注意，诸如a*b*这类正规式简化的NFA只能画成图2-2,45,2.9 构造一个DFA，它接收=a,b上所有含偶数个a的字符串。,【解答】,根据题意可以构造出字符串中含偶数个a的正规表达式：(b,ab*a)*。根据此正规表达式画出相应的NFA M如图2-28所示。,图2-28 习题2.9的NFA M,2.9 构造一个DFA，它接收=a,b上所有含,46,用子集法将图2-28所示的NFA确定化为DFA，如图2-29所示。,图2-29 图2-28确定化后的状态转换矩阵,用子集法将图2-28所示的NFA确定化为DFA，如图2-,47,由图2-29重新命名后的转换矩阵可以看出：状态0和状态2对输入字符a、b的下一状态都是一样的，故状态0和状态2可合并为一个状态。最终得到最简DFA如图2-30所示。当然，我们也可以将图2-28中的状态X和状态Y与状态1合并而直接得到图2-30。,图2-30 习题2.9的最简DFA M,由图2-29重新命名后的转换矩阵可以看出：状态0和状态2,48,编译原理教程习题解析与上机指导课件,49,图2-31 习题2.11的NFA,图2-31 习题2.11的NFA,50,【解答】,用子集法将NFA确定化，如图2-32所示。,图2-32 习题2.11的状态转换矩阵,【解答】 用子集法将NFA确定化，如图2-32所示。图,51,图2-32所对应的DFA如图2-33所示。对图2-33所示的DFA进行最小化。首先将状态分为非终态集和终态集两部分：0,1,2,5和3,4,6,7。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其划分为0,1,2,5，4，3,6,7对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为0，1，2，5，4，3,6,7按顺序重新命名为0、1、2、3、4、5，得到最简DFA如图2-34所示。,图2-32所对应的DFA如图2-33所示。对图2-,52,图2-33 习题2.11的DFA,图2-33 习题2.11的DFA,53,图2-34 习题2.11的最简DFA,图2-34 习题2.11的最简DFA,54,2.12 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放大于等于3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。(1) 写出售货机售糖的正规表达式；(2) 构造识别上述正规式的最简DFA。,【解答】,(1) 设a=1，b=2，则售货机售糖的正规表达式为a (b|a(a|b)|b(a|b)。(2) 画出与正规表达式a(b|a(a|b)|b(a|b)对应的NFA，如图2-35所示。,2.12 有一台自动售货机，接收1分和2分硬币，出售3,55,图2-35 习题2.12的NFA,图2-35 习题2.12的NFA,56,用子集法将图2-35所示的NFA确定化，如图2-36所示。,图2-36 习题2.12的状态转换矩阵,用子集法将图2-35所示的NFA确定化，如图2-36所示,57,由图2-36可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态0、1、2，3、4。按顺序重新命名为0、1、2、3，则得到最简DFA，如图2-37所示。,图2-37 习题2.12的最简DFA,由图2-36可看出，非终态2和非终态3面对输入符号a或b,58,