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

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

2、® 最简DFA本章难点（1） 非形式描述的语言 « 正规式（2） 正规式 ® NFA（非确定的有限自动机）（3） NFA ® DFA（确定的有限自动机）（4） DFA ® 最简DFA作业题一、单项选择题（按照组卷方案，至少15道）1. 程序语言下面的单词符号中， 一般不需要超前搜索a. 关键字 b. 标识符 c. 常数 d. 算符和界符2. 在状态转换图的实现中， 一般对应一个循环语句a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是3. 用了表示字母，d表示数字，å=l，d，则定义标识符的正则表达式可以是

3、： 。(a)ld* (b)ll* (c)l(l | d)* (d)ll* | d*4. 正规表达式(|a|b)2表示的集合是 (a)，ab，ba，aa，bb (b)ab，ba，aa，bb(c)a，b，ab，aa，ba，bb (d)，a，b，aa，bb，ab，ba5. 有限状态自动机可用五元组（VT，Q，q0，Qf）来描述，设有一有限状态自动机M的定义如下：VT=0， 1，Q=q0， q1， q2，Qf=q2，的定义为：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所对应的状态转换图为 。6. 有限状态自动机可用五元组（VT，Q，q0，Qf）来描述，设有一有限状态自

4、动机M的定义如下：VT=0， 1，Q=q0， q1， q2，Qf=q2，的定义为：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所能接受的语言可以用正则表达式表示为 。(0|1)* 00(0|1)* (0|1)*00 0(0|1)*07 . 有限状态自动机可用五元组（VT，Q，q0，Qf）来描述，设有一有限状态自动机M的定义如下：VT=0， 1，Q=q0， q1， q2，Qf=q2，的定义为：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所能接受的语言为 。由0和1所组成的符号串的集合以0为头符号和尾符号、由0和1所组成的符号串的集合

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

6、法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出。组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。10. 关于NFA的叙述中，下面_是不正确的。 A.有一个有穷字母表 B.有多个初始状态 C.有多个终止状态 D.有多个有限状态11. 词法分析的理论基础是 。'#Q;#f,G6aA.有穷自动机理

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

8、误建立符号表a b c d15. 下述正则表达式中_与(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闭包17. 在状态转换图中，结点代表 ，用圆圈表示。 a.输入缓冲区 b.向前搜索 c.状态 d.字符串18. 与(a|b)*(a|b)等价的正规式是 。A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D.

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

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

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

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

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

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

15、；2. Ö；3. Ö；4. ×；5. ×；6. Ö；7. Ö；8. Ö；9. Ö；10. Ö；11. Ö；12×；13. ×；14. Ö；15. ×；四、名词解释：（按照组卷方案，至少5道）1. 状态转换图；2. 正规式（正规表达式、正则表达式）的形式化定义；3. 给出确定性有限状态自动机的形式化定义；4. 给出非确定性有限状态自动机的形式化定义；5. DFA状态最小化。四答案1. 状态转换图是一张有限方向图，用于识别（或接受）一定的字符串。在图中，结点代

16、表状态，用圆圈表示；状态之间用箭弧连结；箭弧上的标记（字符）代表在射出结点（即箭弧的始结点）状态下可能出现的字符或字符类。一张状态转换图只包含有限个状态（即有限个结点），其中一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。2. 正规式是采用递归方式来定义的。（1）e和Æ都是正规式；（2）任何aå，a是å上的一个正规式；（3）假定r和s都是å上的正规式，则r|s、r×s、和r*也都是正规式。3. 一个确定有限自动机（DFA）M是一个五元式：M=(S，å，d，s0，F)，其中：（1）S是一个有限集合，它的每一个元素称为一个状态

17、；（2）å是一个有限字母表，它的每一个元素称为一个输入字符；（3）d是一个从S×å到S的单值部分映射。d(s，a)=s'，意思是：当前状态是s，输入字符为a时，自动机将转入下一个状态s'。 s'称为s的后继状态；（4）s0S，是自动机的惟一初态；（5）FÍS，是一个终态集合。一个非确定有限自动机（NFA）M是一个五元式：M=(S，å，d，s0，F)，其中：（1）S是一个有限集合，它的每一个元素称为一个状态；（2）å是一个有限字母表，它的每一个元素称为一个输入字符；（3）d是一个从S×å到S的

18、子集的映射。d(s，a)=s1，s2，sm，意思是：当前状态是s，输入字符为a时，自动机将转入的下一个状态可能是s1，或者s2，或者sm； （4）s0S，是自动机的惟一初态；（5）FÍS，是一个终态集合。五、简答题：（按照组卷方案，至少5道）1 写出标识符（以字母打头，由字母和数字组成的符号串）的正则表达式。答：letter®A ½B ½. Z ½ a ½b ½. ½zdigit ®0 ½1 ½. ½9id ® letter(letter½digit)*2

19、. 词法分析器对程序语言的单词符号一般如何分类？答：程序语言的单词符号一般可以分为下列五种：（1）关键字：是有程序语言所定义的具有固定意义的标识符，有时也称保留字或基本字；（2）标识符：用来表示变量名、数组名和过程名等各种名字；（3）常数：一般有整型、实型、布尔型和文字型等各种类型，是程序执行过程中不变的量；（4）运算符：如、*、/等各种进行算术逻辑运算的符号；（5）界符：如逗号、分号、括号等。3. 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机？3. 先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：羊空菜羊狼空羊

20、；羊空狼羊菜空羊现给出一个NFA: M=(，Q，0，9，)其中=羊，空，菜，狼，Q=0，1，2，3，4，5，6，7，8，9，转形函数：(0，羊)=1，(1，空)=2，(2，菜)=3，(2，狼)=5(3，羊)=4，(5，羊)=6，(4，狼)=7，(6，菜)=7(7，空)=8，(8，羊)=94 C语言无符号实数用正则表达式怎么定义？答：digit ®0 ½1 ½. ½9digits ®digit(digit)*fraction ® . digits exponent ®E (+ ½- e½) digits )

21、num ® digits ( fraction | e ) (exponent | e )5. 分析下面各正规表达式所表示的语言。(1) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答：(1) |0，1*，中有偶数个0和偶数个1，即由偶数个0和偶数个1构成的串。6. 何谓扫描器？扫描器的功能是什么？答：扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别

22、出一个单词符号，把它交给语法分析器。词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处理子程序来处理上述任务。7. 试简述有穷状态自动机与正则表达式的等价性概念。答：上的非确定有限自动机M所能识别字的全体L(M)是上的一个正规集；同时，对于上的每个正规集V，存在一个上的确定有限自动机M，使得V=L(M)。六、应用题：1. 有一个语言，它接收=0，1上

23、所有满足如下条件的字符串：每个1都有0直接跟在右边。（）给出该语言的正规式（）画出接收该语言的NFA（）把该NFA转换成等价的DFA（）对该DFA进行状态最小化解法1：（）按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0*。（）构造NFA为0*的NFA为：0 | 10的NFA为：(0 | 10)*的NFA为：0*(0 | 10)*0*的NFA为（给各个结点标上序号）（）用子集法确定化II0I10，1，3，4，5，6，9，13，14，15，17=1，2，3，4，5，6，9，13，14，15，175，7，8，9，13，14，15，1715，16，171，2，3，4，5，6

24、，7，8，9，13，14，15，16，17=10，111，2，3，4，5，6，7，8，9，13，14，15，16，17，同上同上10，115，6，8，9，12，13，14，15，17Æ5，6，8，9，12，13，14，15，175，6，7，8，9，13，14，15，16，17旧态5，6，7，8，9，13，14，15，16，17旧态旧态令：0，1，3，4，5，6，9，13，14，15，17A；1，2，3，4，5，6，7，8，9，13，14，15，16，17B；10，11C；5，6，8，9，12，13，14，15，17D；5，6，7，8，9，13，14，15，16，17E；画出DFA如图

25、所示：（）对该DFA进行状态最小化PI(1)，I(2)C，A，B，D，EI(1)C不可再分；看I(2)A，B，D，E：A，B，D，E0B，E，落入了I(2)；A，B，D，E1C，落入了I(1)；所以，A，B，D，E是等价状态，不再分；因此，从A，B，D，E中抽取一个状态作为代表，C不变，得到简化了的DFA如图所示：解法2：（）构造NFA为（3）用子集法确定化II0I1S01X，0，1，3，Y0，1，3，Y21，3，Y0，1，3，Y0，1，3，Y1，3，Y1，3，Y22/212342244333DFA为：（）可最小化，终态组为A，B，D，非终态组为C；A，B，D0A，B，D，A，B，D1C，所以

26、A，B，D为等价状态，可合并。2. 已知字母表S = a， b上语言L = w | w中a的个数是偶数。（）给出该语言的正规式（）画出接收该语言的NFA（）把该NFA转换成等价的DFA（）对该DFA进行状态最小化2解法1：（） 语言L的正规式是：(a b*a | b)* 或 b*(a b*a b*)* （）画出接收该语言的NFA（3）NFA转换成DFAIIaIbSaB1，2，3，12，13=4，5，6，8，92，3，11，12，13，14ABC4，5，6，8，92，3，10，11，12，136，7，8，9BDE2，3，11，12，13，14=4，5，6，8，92，3，11，12，13，14CB

27、C2，3，10，11，12，13=4，5，6，8，92，3，11，12，13，14DBC6，7，8，92，3，10，11，12，136，7，8，9EDE得到的DFA为：（）对该DFA进行状态最小化PI(1)，I(2) B，E ，A，C，D B，E aD，落入I(2)中； B，E bE；落入I(1)中；I(1) B，E 不必再分。I(2)A，C，D aB，落入I(1)中；I(2)A，C，D bC，落入I(2)中；I(2)A，C，D 不必再分。故，得到的接受该语言的最简DFA是：解法2（）画出接收该语言的NFA（3）NFA转换成DFAIIaIbSaB1，3=21，3ABA21，3=2BAB得到的D

28、FA如下：（）对该DFA进行状态最小化无法再分。3. 有一个语言，它接收=0，1上的含奇数个1的所有串。（）给出该语言的正规式（）画出接收该语言的NFA（）把该NFA转换成等价的DFA（）对该DFA进行状态最小化提示：正则表达式为0*1 (0|10*1)*。4. 已知=0，1上正则表达式为0(0|1)*0，（）该正则表达式所定义的语言是什么？（）画出接收该语言的NFA（）把该NFA转换成等价的DFA（）对该DFA进行状态最小化提示：(1) 以0开头并且以0结尾的，由0和1组成的符号串。5已知=0，1上正则表达式为(0|1)*0(0|1)(0|1)，（）该正则表达式所定义的语言是什么？（）画出接

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