编译原理作业集-第三章-修订版

1、第三章词法分析本章要点.词法分析器设计，.正规表达式与有限自动机，.词法分析器自动生成。本章目标：.理解对词法分析器的任务，掌握词法分析器的设计；.掌握正规表达式与有限自动机；.掌握词法分析器的自动产生。本章重点：.词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。.掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。(1)非形式描述的语言正规式(2)正规式 NFA (非确定的有限自动机)3) NFA DFA (确定的有限自动机)4) DFA 最简 DFA本章难点(1)非形式描述的语言正规式(2)正规式

2、NFA (非确定的有限自动机)NFA DFA (确定的有限自动机)DFA 最简 DFA作业题一、单项选择题组卷方案，至少 15道).程序语言下面的单词符号中， 一般不需要超前搜索a.关键字 b. 标识符 c. 常数 d.算符和界符.在状态转换图的实现中， 一般对应一个循环语句a.不含回路的分叉结点b.含回路的状态结点c.终态结点d. 都不是.用了表示字母，d表示数字，=l , d,则定义标识符的正则表达式可以是： 。(a)ld * (b)ll * (c)l(l | d)* (d)ll * | d *.正规表达式(e |a|b)之表布的集合是 (a) e , ab, ba, aa, bb (b)

3、ab , ba, aa, bb(c)a , b, ab, aa, ba, bb (d) e, a, b, aa, bb, ab, ba.有限状态自动机可用五元组(Vt, Q, 8 , qo, Q)来描述，设有一有限状态自动机M的定义如下：Vt=0 , 1, Q=q0, q 1, q2, Q=qz, 6 的定义为：8 (q。，0) =q18 ( q1, 0) =q2M所对应的状态转换图为Sh图中T示开始状蠹.保承筹止状态.有限状态自动机可用五元组(Vt, Q, 8 , qo, Q)来描述，设有一有限状态自动机M的定义如下：V=0, 1, Q=qo, qi, q2, Q=qz, 6 的定义为：8

4、( q0, 0) =qi8 (qi, 0) =q26 ( q2, 1) =q26 ( q2, 0) =q2M所能接受的语言可以用正则表达式表示为。(0|1) *00(0|1) *(0|1) *000(0|1) *0.有限状态自动机可用五元组(Vt, Q, 8 , qc, Q)来描述，设有一有限状态自动机M的定义如下：V=0, 1 , Q=q。，q i, q2, Q=qz, 6 的定义为：8 ( q0, 0) =qi8 (qi, 0) =q26 ( q2, i) =q26 ( q2, 0) =q2M所能接受的语言为 。由 0 和 1 所组成的符号串的集合 以 0 为头符号和尾符号、由 0 和 1

5、 所组成的符号串的集合以两个0 结束的，由0 和 1 所组成的符号串的集合以两个0 开始的，由0 和 1 所组成的符号串的集合. 从接受语言的能力上来说，非确定型有穷自动机和 是等价的。i.正规式；ii.上下文无关文法；iii.确定性有穷自动机；i.左线性正规文法；ii .右线性正规文法；iii .确定性有穷自动机；i.正规式；ii.上下文无关文法；iii.正规文法；i .正规式；ii .确定性有穷自动机；iii.下推自动机；. 下面四个选项中， 关于编译过程中扫描器的任务的叙述， 是较为完整且正确的。组织源程序的输入； 按词法规则分割出单词， 识别其属性， 并转换成属性字的形式输出； 删除注

6、释； 删除空格和无用字符； 行计数、 列计数； 发现并定位词法错误； 建立符号表。按词法规则分割出单词， 识别其属性， 并转换成属性字的形式输出； 发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出。组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。.关于NFA的叙述中，下面 是不正确的。A. 有一个有穷字母表B.有多个初始状态C. 有多个终止状态D.有多个有

7、限状态.词法分析的理论基础是 。A.有穷自动机理论 B.图灵机理论C .图论 D.无穷自动机理论.设有两个状态S和T,如果从S出发能读出某个字 w而停于终态，那么从 T出发也能读 出同样的字而停于终态； 反之，果从T出发能读出某个字 w而停于终态，那么从S出发也能 读出同样的字而停于终态。则我们称状态S和状态T是。A.可区分的；B.等价的；C.多余的；D.无用的。.词法分析器的输出结果是 。A、单词自身值B、单词在符号表中的位置C单词的种别编码H单词的种别编码和自身值.编译过程中扫描器的任务包括 。组织源程序的输入按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出删除注解删除空格及无

8、用字符行计数、列计数发现并定位词法错误建立符号表a.b . c . d .下述正则表达式中 与(a*+b)*(c+d)等价(即有相同符号串集)。(x+y亦可写作x|y) a*(c+d)+b(c+d) a*(c+d)*+b(c+d)* a*(c+d)+b(c+d)(a+b)*c+(a+b)*d(a*+b)*c+(a*+b)*da. b. c. d. 16、正则式的“ * ”读作。a,并且 L 或者 c .连接 d .闭包.在状态转换图中，结点代表 ,用圆圈表示。a.输入缓冲区b.向前搜索c.状态d.字符串.与(a|b) *(a|b)等价的正规式是 。A. a *| b * B. (ab)*(a|

9、b) * C. (a|b)(a|b)* D. (a|b)*.无符号常数的识别和拼数工作通常都在 阶段完成。A .词法分析B .语法分析C .语义分析D .代码生成一.答案：1. b ; 2. b ; 3. c ; 4. d ; 5.；6.，7.；8. b ; 9.；10. B ; 11. A ;12. B ; 13. d ; 14. d ; 18. C ; 19. A二、填空题：（按照组卷方案，至少 15道）.词法分析器对扫描缓冲区进行扫描时一般用两个指示器;另一个。. 一个确定性有限自动机DFA M的化简是指：寻找一个状态数比M少的DFA M，使得。.词法分析器所的输出常表示成如下形式的二元

10、式：（ , ） 0. 一个状态转换图只包含有限个状态，其中有一个被认为是 ,而且实际上至少有 一个。.把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个 程序段。.词法分析阶段的任务式从左到右扫描 ,从而逐个识别。.如果一个种别只含有一个单词符号，那么，对于这个单词符号， 就可以完 全代表它自身了。.单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比 如，对于某个标识符，常将 作为 其属性值。.单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比 如，对于常数，常将 作为其属性值。.如果一个种别含有多个单词符号，那么，对于它

11、的每个单词符号，除了给出种别编码以外，还应给出有关。.如果,则认为这两个正规式等价。* . . . . . . . . . . . . . . . . . . . . . . .对于中的任何符号串，如果存在一条从初态结点到某一终态结点的通路，且，则称 被该自动机所接受（识别）。. 一个Lex源程序主要包括两部分，一部分是 ,另一部分是 。. 一个DFA可用一个矩阵表示，该矩阵的行表示 ,列表示 ,矩阵元素表 示。这个矩阵叫状态转换矩阵。.对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态i和当前所面临的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为：二.答案：1.指向

12、当前正在识别的单词符号的开始位置，用于向前搜索以寻找单词符号的终点；2. L（M尸L（M） ; 3.单词种别，单词符号的属性值；4.初态，终态；5.由while和if语句构成的；6.源程序，单词；7.种别编码；8.存放它的有关信息的符号表项的指针；9.存放它的常数表项的指针；10.单词符号的属性信息（属性值）；11.两个正规式所表示的正规集相同；12.这条通路上所有弧的标记符号连接起来形成的符号串等于；13.正规定义式，识别规则；14.状态，输入字符，转换函数（或 （s, a）的值；15.将搜索 器回退一个位置，并令下一个状态图开始工作。三、判断题:（按照组卷方案，至少 15道）. NFA M

13、的非确定性表现在它有多个终态。（）.有穷自动机接受的语言是正则语言。（）.若1和2是2上的正规式，则 rr 2也是。（）.设M是一个NFA并且L（M） = x, y, z,则M的状态数至少为4个。 （）.令2 = a, b,则2上所有以b为首的字符构成的正规集的正规式为b*（a|b） *。.对任何一个 NFA M 都存在一个 DFA M,使得L(M尸L(M).对一个右线性文法 G,必存在一个左线性文法G,使得L(G尸L(G),反之亦然。() TOC o 1-5 h z .对任意一个右线性文法G都存在一个NFA M满足L(G尸L(M)。().对任意一个右线性文法G都存在一个DFA M满足L(G尸

14、L(M)。().对任何正则表达式 r ,都存在一个 NFA M满足L(M)=L(r)。().对任何正则表达式 r ,都存在一个 DFA M满足L(M)=L(r)。(). 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(). 一个正规式只能对应一个有限状态自动机；().在词法分析的状态转换图中，有些结点是带星号的，这些结点肯定是终态结点。().适当设置扫描缓冲区的大小(比如容纳256个字符)可以保证单词符号不会被它的边界所打断。()四.答案：1. X; 2.; 3.;4. X; 5. X; 6.; 7.; 8.; 9.; 10.11.; 12X; 13. X; 14.;

15、15. X;四、名词解释:(按照组卷方案，至少 5道).状态转换图；.正规式(正规表达式、正则表达式)的形式化定义;.给出确定性有限状态自动机的形式化定义；.给出非确定性有限状态自动机的形式化定义；. DFA状态最小化。四.答案.状态转换图是一张有限方向图，用于识别(或接受)一定的字符串。在图中，结点代表状态，用圆圈表示；状态之间用箭弧连结；箭弧上的标记(字符)代 表在射出结点(即箭弧的始结点)状态下可能出现的字符或字符类。一张状态转换图只包含有限个状态(即有限个结点)，其中一个被认为是初态，而且实际上至少要有一个终态(用双圈表示)。.正规式是采用递归方式来定义的。(1)和都是正规式；(2)任

16、何aC , 2是上的一个正规式；(3)假定r和s都是 上的正规式，则r|s、r s、和r*也都是正规式。一个确定有限自动机(DFA M是一个五元式：M=(S, so, F),其中：S是一个有限集合，它的每一个元素称为一个状态；是一个有限字母表，它的每一个元素称为一个输入字符；是一个从SX 至ij S的单值部分映射。(s, a)=s,意思是：当前状态是 s,输入字符为a时，自动机将转入下一个状态 s。s称为s的后继状态；soCS,是自动机的惟一初态；F S,是一一个终态集合。一个非确定有限自动机(NFA M是一个五元式：M=(S, so, F),其中：S是一个有限集合，它的每一个元素称为一个状态

17、；是一个有限字母表，它的每一个元素称为一个输入字符；是一个从SX 到S的子集的映射。 (s , a尸s 1, s2,，sm,意思是：当前状态是s,输入字符为a时，自动机将转入的下一个状态可能是si,或者S2, ,或者Sm；soCS,是自动机的惟一初态;F S,是一一个终态集合。五、简答题：(按照组卷方案，至少 5道)1写出标识符(以字母打头，由字母和数字组成的符号串)的正则表达式。答：letter A B . Z a b . zdigit 01.9id letter(letter digit)*.词法分析器对程序语言的单词符号一般如何分类答：程序语言的单词符号一般可以分为下列五种：(1)关键字

18、：是有程序语言所定义的具有固定意义的标识符，有时也称保留字或基本字；(2)标识符：用来表示变量名、数组名和过程名等各种名字；(3)常数：一般有整型、实型、布尔型和文字型等各种类型，是程序执行过程中不变的量;(4)运算符：如+、*、/等各种进行算术逻辑运算的符号；(5)界符：如逗号、分号、括号等。.人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机3.先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序:羊空菜羊狼空羊；羊空狼羊菜空羊现给出一个 NFA: M=（S, Q, 0, 9 , 8）其中 2=羊，空，菜，狼, Q=0,

19、 1,2, 3, 4, 5, 6, 7, 8, 9,转形函数:8 （0 ,羊）=1 , 8 （1 ,空）=2 , 8 （2 ,菜）=3 , 8 （2 ,狼）=58 （3 ,羊）=4 , 8 （5 ,羊）=6 , 8 （4 ,狼）=7 , 8 （6 ,菜）=78 （7 ,空）=8 , 8 （8 ,羊）=9 4C语言无符号实数用正则表达式怎么定义答：digit 01.9digits digit（digit）*fraction . digitsexponentE （+-） digits ）num digits （ fraction |）（exponent|）分析下面各正规表达式所表木的语言。(00|

20、11)*(01|10)(00|11)*(01|10)(00|11)*)*答：（1 ） a | a C 0 , 1* ,a中有偶数个0和偶数个1,即由偶数个0和偶数个1构成的何谓扫描器扫描器的功能是什么答：扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。一般把词法分析器安排成一个子程序， 每当语法分析器需要一个单词符号时就调用这个子程序。 每一次调用， 词法分析器就从输入串中识别出一个单词符号， 把它交给语法分析器。词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车

21、符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义， 而注解部分几乎允许出现在程序中的任何地方。 它们不是程序的必要组成部分， 预处理时可以将其剔掉。 词法分析器一般会构造一个预处理子程序来处理上述任务。试简述有穷状态自动机与正则表达式的等价性概念。答：.汇上的非确定有限自动机M所能识别字的全体L(M)是汇上的一个正规集；同时，对于汇上的每个正规集V,存在一个汇上的确定有限自动机M使得V=L(M)。六、应用题：.有一个语言，它接收 2=0, 1上所有满足如下条件的字符串：每个 1都有。直接跟在 右边。(1 )给出该语言的正规式(2)画出接收该语言的 NFA(3 )把该

22、NFA转换成等价的 DFA(4 )对该DFA进行状态最小化解法1:(1)按题意相应的正规表达式是0 (0 | 10) 0或0 ( 100 )0。(2 )构造NFA为0*的NFA为：0 | 10 的 NFA为:(0 | 10)* 的 NFA为:的NFA为(给各个结点标上序号)0*(0 | 10)*0*(3 )用子集法确定化II 0I 10,1,3, 4, 5,6, 9, 13, 14, 15,172,7,1 6=1 , 2, 3, 4, 5, 6, 9, 13, 14, 15, 17 U 5 ,7,8,9, 13, 14,15, 17 U15 ,16, 17=1 , 2,3,4,5, 6, 7,

23、 8,9, 13, 14, 15,16, 17 10=10, 111 , 2, 3, 4, 5,6, 7, 8, 9, 13,14, 15, 16, 17 2 , 7 , 1 6,同上10同上10 , 11 1 2 =5 , 6, 8, 9, 12, 13, 14, 15, 175, 6, 8, 9, 12,13, 14, 15, 17 7 , 1 6 =5 , 6, 7, 8, 9, 13, 14, 15, 16, 1710旧态5, 6, 7, 8, 9,13, 14, 15, 16, 7 , 1 6 旧态10旧态令：0, 1, 3, 4, 5, 6, 9, 13, 14, 15, 17 =

24、 A;1 , 2, 3, 4, 5, 6, 7, 8, 9, 13, 14, 15, 16, 17 = B;10, 11 = G5 , 6, 8, 9, 12, 13, 14, 15, 17 = D;5 , 6, 7, 8, 9, 13, 14, 15, 16, 17 = E;画出DFA如图所示：(4 )对该DFA进行状态最小化=I(1) , I(2)=C , A, B, D, EI(1) =C不可再分；看 1出=伊，B, D, E:A, B, D, Ec=B, E,落入了 I(2);A, B, D, E1=C,落入了 I;所以，A,B, D, E是等价状态，不再分;因此，从A, B, D,

25、E中抽取一个状态作为代表，C不变，得到简化了的DFA如图所示:解法2:(2 )构造NFA为(3)用子集法确定化II 011S01X, 0,1, 3, Y0,1, 3, Y21230,1,3, Y0,1, 3, Y222321 , 3, Y/3431 , 3, Y1 , 3, Y244DFA 为:0(4)可最小化，终态组为 A, B, D,非终态组为C;A, B, D0 A, B, D,A, B, D1C,所以A, B, D为等价状态，可合并。.已知字母表=a , b上语言L = w|w 中a的个数是偶数。(1 )给出该语言的正规式(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 D

26、FA(4 )对该DFA进行状态最小化2解法1:(1) 语言L的正规式是:(a b a | b) 或 b (a b a b )(2)画出接收该语言的NFA(3) NFA转换成DFAII aI bSaB1 ,2, 3, 12, 134=4, 5, 6, 8, 914 =2, 3, 11, 12, 13,14ABC4, 5, 6, 8, 910 =2 , 3, 10, 11, 12,137=6, 7, 8, 9BDE2 , 3, 11, 12,13, 144=4, 5, 6, 8, 914 =2, 3, 11, 12, 13,14CBC2 , 3, 10, 11,12, 134=4, 5, 6, 8

27、, 914 =2, 3, 11, 12, 13,14DBC6, 7, 8, 910 =2 , 3, 10, 11, 12,137=6, 7, 8, 9EDE得到的DFA为:bb(4 )对该DFA进行状态最小化=I ，I= B , E , A, C, B , E a=D,落入 I 中； B ,I(i)= B , E 不必再分。. I =A, C, D a =B,落入 I(1)./2) = A, G D 不必再分。故，得到的接受该语言的最简DFA是：解法2D E b=E;落入I中；中；I(2) = A, C, D b=C,落入 I(2)中;)b(2)画出接收该语言的 NFA(3) NFA转换成DF

28、AII aI bSaB1，32=23=1, 3ABA23 = 1 , 32 =2BAB得到的DFA如下:(4 )对该DFA进行状态最小化无法再分。3.有一个语言，它接收 2=0, 1上的含奇数个1的所有串。(1 )给出该语言的正规式(2)画出接收该语言的 NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示：正则表达式为 0*1 (0|10 *1)*o4.已知N=0, 1上正则表达式为 0(0|1)*0 ,(1)该正则表达式所定义的语言是什么(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示： (1) 以 0

29、开头并且以 0 结尾的，由 0 和 1 组成的符号串。5已知2=0, 1上正则表达式为(0|1) *0(0|1)(0|1),(1)该正则表达式所定义的语言是什么(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示： (1) 由 0 和 1 组成的符号串，且从右边开始数第 3 位为 0。6已知 2=0, 1上正则表达式为 0*10*10*10*,(1)该正则表达式所定义的语言是什么(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示：(1)含3个1的由0和1组成的符号串。 a | a C 0,

30、 1+ ,且a中含有3个1 。7有一个语言，它接收2=a, b上所有满足如下条件的字符串：不含子串abb的由a和b组成的符号串的全体。(1)给出该语言的正规式(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示：正则表达式为：b*(a*|(ba) *)*。8已知2=0, 1上正则表达式为( |0)1 *)*,(1)该正则表达式所定义的语言是什么(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示： (1) 由 0 和 1 组成的符号串。9已知2=0, 1上正则表达式为(a*|b*)*,(1)该正则表达式所定义的语言是什么(2)画出接收该语言的NFA(3 )把该 NFA转换成等价的 DFA(4 )对该DFA进行状态最小化提示： (1) 所有由 a 和 b 组成的符号串。10.已知语言为2=a, b上的、由a和b组成的但是不以bb结束的所有符号串的集合。(