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

编译原理作业集 第三章 词法分析

第三章 词法分析

本章要点

１．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。

本章目标：

１．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。

本章重点：

1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言 ? 正规式

（2）正规式 ? NFA（非确定的有限自动机） （3）NFA ? DFA（确定的有限自动机） （4）DFA ? 最简DFA 本章难点

（1） 非形式描述的语言 ? 正规式

（2） 正规式 ? NFA（非确定的有限自动机） （3） NFA ? DFA（确定的有限自动机） （4） DFA ? 最简DFA

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 1 -

编译原理作业集 第三章 词法分析

作业题 一、单项选择题

（按照组卷方案，至少15道）

1. 程序语言下面的单词符号中， 一般不需要超前搜索

a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中， 一般对应一个循环语句

a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字，?={l，d}，则定义标识符的正则表达式可以是： 。

(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，ba}

5. 有限状态自动机可用五元组（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）=q2 M所对应的状态转换图为 。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 2 -

编译原理作业集 第三章 词法分析

6. 有限状态自动机可用五元组（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）=q2

M所能接受的语言可以用正则表达式表示为 。

①(0|1)* ②00(0|1)* ③(0|1)*00 ④0(0|1)*0

7 . 有限状态自动机可用五元组（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）=q2 M所能接受的语言为 。

①由0和1所组成的符号串的集合

②以0为头符号和尾符号、由0和1所组成的符号串的集合 ③以两个0结束的，由0和1所组成的符号串的集合 ④以两个0开始的，由0和1所组成的符号串的集合

8. 从接受语言的能力上来说，非确定型有穷自动机和________是等价的。

a. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.确定性有穷自动机；

b. ⅰ.左线性正规文法；ⅱ.右线性正规文法；ⅲ.确定性有穷自动机； c. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.正规文法； d. ⅰ.正规式；ⅱ.确定性有穷自动机；ⅲ.下推自动机；

9. 下面四个选项中，关于编译过程中扫描器的任务的叙述，________是较为完整且正确的。 ①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表。 ②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。

③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出。

④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 3 -

编译原理作业集 第三章 词法分析

10. 关于NFA的叙述中，下面______是不正确的。

A.有一个有穷字母表 B.有多个初始状态 C.有多个终止状态 D.有多个有限状态 11. 词法分析的理论基础是 。

A.有穷自动机理论 B.图灵机理论 Ｃ.图论 Ｄ.无穷自动机理论

12. 设有两个状态S和T，如果从S出发能读出某个字w而停于终态，那么从T出发也能读出同样的字而停于终态；反之，果从T出发能读出某个字w而停于终态，那么从S出发也能读出同样的字而停于终态。则我们称状态S和状态T是 。

A. 可区分的；B. 等价的；C. 多余的；D. 无用的。 13. 词法分析器的输出结果是 。

A、单词自身值

B、单词在符号表中的位置 D、单词的种别编码和自身值

C、单词的种别编码

14. 编译过程中扫描器的任务包括______。

①组织源程序的输入

②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 ⑧删除注解

④删除空格及无用字符 ⑤行计数、列计数 ⑥发现并定位词法错误 ⑦建立符号表

a．②③④⑦ b．②③④⑥⑦ c．①②③④⑥⑦ d．①②③④⑤⑥⑦

15. 下述正则表达式中______与(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)*d

a.①③ b. ③④⑤ c.③ d.④⑤ 16、正则式的“*”读作______。

a，并且 L或者 c．连接 d．闭包

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 4 -

编译原理作业集 第三章 词法分析

17. 在状态转换图中，结点代表 ，用圆圈表示。 a.输入缓冲区 b.向前搜索 c.状态 d.字符串 18. 与(a|b)*(a|b)等价的正规式是 。

A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)* 19.无符号常数的识别和拼数工作通常都在 阶段完成。

Ａ．词法分析 Ｂ．语法分析 Ｃ．语义分析 Ｄ．代码生成

一．答案：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. 词法分析器所的输出常表示成如下形式的二元式：（______________，_________________）。 4. 一个状态转换图只包含有限个状态，其中有一个被认为是________，而且实际上至少有一个________。

5. 把状态转换图用程序实现时，对于含有回路的状态结点来说，可以让它对应一个_____________________________________程序段。

6. 词法分析阶段的任务式从左到右扫描 ，从而逐个识别 。 7. 如果一个种别只含有一个单词符号，那么，对于这个单词符号， 就可以完全代表它自身了。

8. 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比如，对于某个标识符，常将 作为其属性值。

9. 单词符号的属性值是指单词符号的特性或特征，其属性值则是反映特性或特征的值。比如，对于常数，常将 作为其属性值。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 5 -

编译原理作业集 第三章 词法分析

10. 如果一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以外，还应给出有关 。

11. 如果 ，则认为这两个正规式等价。

12. 对于?*中的任何符号串?，如果存在一条从初态结点到某一终态结点的通路，且 ，则称?被该自动机所接受（识别）。 13. 一个Lex源程序主要包括两部分，一部分是 ，另一部分是 。 14. 一个DFA可用一个矩阵表示，该矩阵的行表示 ，列表示 ，矩阵元素表示 。这个矩阵叫状态转换矩阵。

15. 对于词法分析程序来说，当程序到达“错误处理”时，意味着现行状态i和当前所面临的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应该为： 。

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

三、判断题：

（按照组卷方案，至少15道）

1．NFA M的非确定性表现在它有多个终态。 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. 对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。 ( ) 10. 对任何正则表达式r，都存在一个NFA M，满足L(M)=L(r)。 ( ) 11. 对任何正则表达式r，都存在一个DFA M，满足L(M)=L(r)。 ( )

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 6 -

编译原理作业集 第三章 词法分析

12．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ ） 13. 一个正规式只能对应一个有限状态自动机；

（ ）

14. 在词法分析的状态转换图中，有些结点是带星号的，这些结点肯定是终态结点。（ ） 15. 适当设置扫描缓冲区的大小（比如容纳256个字符）可以保证单词符号不会被它的边界所打断。 （ ） 四．答案：1. ×；2. ?；3. ?；4. ×；5. ×；6. ?；7. ?；8. ?；9. ?；10. ?；11. ?；12×；13. ×；14. ?；15. ×；

四、名词解释：

（按照组卷方案，至少5道） 1. 状态转换图；

2. 正规式（正规表达式、正则表达式）的形式化定义； 3. 给出确定性有限状态自动机的形式化定义； 4. 给出非确定性有限状态自动机的形式化定义； 5. DFA状态最小化。 四．答案

1. 状态转换图是一张有限方向图，用于识别（或接受）一定的字符串。

在图中，结点代表状态，用圆圈表示；状态之间用箭弧连结；箭弧上的标记（字符）代表在射出结点（即箭弧的始结点）状态下可能出现的字符或字符类。

一张状态转换图只包含有限个状态（即有限个结点），其中一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。 2. 正规式是采用递归方式来定义的。 （1）?和?都是正规式；

（2）任何a∈?，a是?上的一个正规式；

（3）假定r和s都是?上的正规式，则r|s、r?s、和r*也都是正规式。

3. 一个确定有限自动机（DFA）M是一个五元式：M=(S，?，?，s0，F)，其中：

（1）S是一个有限集合，它的每一个元素称为一个状态； （2）?是一个有限字母表，它的每一个元素称为一个输入字符；

（3）?是一个从S×?到S的单值部分映射。?(s，a)=s'，意思是：当前状态是s，输入字符为a时，自动机将转入下一个状态s'。 s'称为s的后继状态；

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 7 -

编译原理作业集 第三章 词法分析

（4）s0∈S，是自动机的惟一初态； （5）F?S，是一个终态集合。

一个非确定有限自动机（NFA）M是一个五元式：M=(S，?，?，s0，F)，其中：

（1）S是一个有限集合，它的每一个元素称为一个状态； （2）?是一个有限字母表，它的每一个元素称为一个输入字符；

（3）?是一个从S×?到S的子集的映射。?(s，a)={s1，s2，……，sm}，意思是：当前状态是s，输入字符为a时，自动机将转入的下一个状态可能是s1，或者s2，……，或者sm；

（4）s0∈S，是自动机的惟一初态； （5）F?S，是一个终态集合。

五、简答题：

（按照组卷方案，至少5道）

1 写出标识符（以字母打头，由字母和数字组成的符号串）的正则表达式。 答：

letter?A ?B ?... Z ? a ?b ?... ?z digit ?0 ?1 ?... ?9 id ? letter(letter?digit)*

2. 词法分析器对程序语言的单词符号一般如何分类？ 答：程序语言的单词符号一般可以分为下列五种：

（1）关键字：是有程序语言所定义的具有固定意义的标识符，有时也称保留字或基本字； （2）标识符：用来表示变量名、数组名和过程名等各种名字；

（3）常数：一般有整型、实型、布尔型和文字型等各种类型，是程序执行过程中不变的量； （4）运算符：如＋、－、*、/等各种进行算术逻辑运算的符号； （5）界符：如逗号、分号、括号等。

3. 人运狼、羊、菜过河，一次运一件，不让羊吃掉菜，也不让狼吃掉羊，画出渡河的状态转换图。可否将其抽象为一个有限自动机？

3. 先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序： ①羊空菜羊狼空羊；②羊空狼羊菜空羊

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 8 -

编译原理作业集 第三章 词法分析

现给出一个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，羊)=9

4 C语言无符号实数用正则表达式怎么定义？ 答：

digit ?0 ?1 ?... ?9 digits ?digit(digit)* fraction ? . digits

exponent ?E (+ ?- ??) digits )

num ? digits ( fraction | ? ) (exponent | ? ) 5. 分析下面各正规表达式所表示的语言。 (1) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

答：(1) {α|α∈{0，1}*，α中有偶数个0和偶数个1}，即由偶数个0和偶数个1构成的串。

6. 何谓扫描器？扫描器的功能是什么？

答：扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号，供语法分析器使用。

一般把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。 词法分析器工作的第一步是输入源程序文本。输入串中一般都包含一些没有意义的字符，如：空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义，而注解部分几乎允许出现在程序中的任何地方。它们不是程序的必要组成部分，预处理时可以将其剔掉。词法分析器一般会构造一个预处理子程序来处理上述任务。

7. 试简述有穷状态自动机与正则表达式的等价性概念。

答：．∑上的非确定有限自动机M所能识别字的全体L(M)是∑上的一个正规集；同时，对于∑上的每个正规集V，存在一个∑上的确定有限自动机M，使得V=L(M)。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 9 -

编译原理作业集 第三章 词法分析

六、应用题：

1. 有一个语言，它接收Σ={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

（１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 解法1：

（１）按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0*。 （２）构造NFA为 0*的NFA为：

? ? 0 ? ?

0 | 10的NFA为：

? 0 ? ? 1 ? 0 ?

(0 | 10)*的NFA为：

? ? ? 0 ? ? ? 1 ? 0 ? ?

0*(0 | 10)*0*的NFA为（给各个结点标上序号）

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 10 -

编译原理作业集 第三章 词法分析

I Ia Ib S {1，3} ————{2}={2} ————{3}＝{1，3} A {2} ————{3}＝{1，3} ————{2}={2} B 得到的DFA如下：

b b start a A a B

（４）对该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)， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

a B B A A B - 16 -

编译原理作业集 第三章 词法分析

（４）对该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结束的所有符号串的集合。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 17 -

编译原理作业集 第三章 词法分析

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化

提示：(1) (a|b)*a(a|b|ε)。All the strings of a’s and b’s that end with a, ab or aa. Or： All the strings of a’s and b’s that do not end with bb.。

11已知Σ={a，b}上正则表达式为(aa|b)*(a|bb)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化 提示：（1）All the strings of a’s and b’s that can be divided into two substings, where in the left substring, the even number of consecutive a’s are separated by b’s while in the right substring, the even number of consecutive b’ are separated by a’s.

12. 已知语言为Σ={0，1}上所有由0和1组成的二进制数串的集合，这些串从数值上可以看作是4的倍数。

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：(0|1)*00。

13已知语言为Σ={0，1}上所有由0和1组成的二进制串的集合，这些串都是以0打头以0结尾的。

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：0(0|1)*0。

14. 已知Σ={0，1}上正则表达式为1(0|1)*101， （１）该正则表达式所定义的语言是什么？

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 18 -

编译原理作业集 第三章 词法分析

（２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

15已知Σ={a，b}上正则表达式为(a|b)*abb(a|b)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 19 -

本文来源：https://www.bwwdw.com/article/x0c5.html