本节书摘来自华章出版社《编译与反编译技术》一书中的第2章，第2.6节本章小结，作者庞建民，陶红伟，刘晓楠，岳峰，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.6 本章小结
词法分析是编译过程的第一个阶段，是编译过程的基础，它负责对源程序进行扫描，按照源程序的构词规则识别出一个个单词符号。本章主要讨论了词法分析器的手工实现、自动实现以及相关的理论知识。
首先，对词法分析的实现进行了需求分析，给出了词法分析器的功能。探讨了实现词法分析器的关键技术，介绍了一种基于状态转换图的词法分析器的手工实现，该方法首先将描述源语言单词符号结构的正规文法或者正规式转化为状态转换图，然后手工把这种状态转换图翻译为识别单词符号的程序。
接下来讨论了词法分析器的自动生成，介绍了与之相关的确定的有穷自动机、非确定的有穷自动机的概念以及两者之间的等价性转化，并讨论了确定的有穷自动机的化简，与此同时，还给出了正规式与有穷自动机之间的等价性转化方法。最后，介绍了一个词法分析器自动生成工具LEX。
习题
- 用自然语言描述下列正规式所表示的语言。
（1）0( 0 | 1)*0
（2）( (ε | 0) 1 )
（3）(0 | 1) * 0( 0 | 1) (0 | 1 )
（4）0101010
（5）(A | B | C |…| Z)(a | b | c |…| z)*
（6）(aa | b)(bb | a)
- 写出下列各语言的正规式。
（1） 处于“/ ”和“/”之间的串构成的注释，注释中没有“*/”，除非它们出现在双引号中。
（2）所有不含子串“011”的由0和1构成的符号串的全体。
（3）所有含子串“011”的由0和1构成的符号串的全体。
（4）以a开头和结尾的所有小写字母串。
（5）所有表示偶数的数字串。
- 正规式(ab)a与正规式a(ba)是否等价？请说明理由。
- 设有正规文法G(Z)：
Z→0A
A→0A | 0B
B→1A |ε
试给出该文法生成语言的正规式。
- 将正规式r = (a | b)(aa)*(a | b)转换成与之等价的正规文法。
- 画出用来识别如下三个关键字的状态转换图：
STEP STRING SWITCH - 设有右线性文法G(S)：
S→aB
B→aB| bS| a
试构造与之相对应的状态转换图。
- 已知描述八进制数的正规式如下：
0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*
试给出识别八进制数的状态图。
- 一个人带着一只狼、一只山羊和一棵白菜来到一条河的岸边，想要过河到对岸去，此时，岸边只有一条船，其大小恰好能装下人和其余三件东西中的一件，也即，人每次只能将随行中的一件物品带到对岸。但是若人将狼和山羊留在同一岸上而无人照看的话，狼就会将羊吃掉；类似的，如果人把山羊和白菜留在同一岸而无人照看，山羊也会把白菜吃掉。请用状态转换图作为工具，描述人可以采取的所有乘船渡河方案，并从中找出使得羊和白菜都不被吃掉的方案。
- 已知有语言L={w | w∈(0，1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0}，试构造接受该语言的确定的有穷自动机。
- 设有L(G)={a2n+1b2ma2p+1∣n≥0，p≥0，m≥1}。
（1）给出描述该语言的正规式。
（2）构造识别该语言的确定的有穷自动机。
- 试构造识别语言r=(a | b)*abb的非确定的有穷自动机N，使L(N)=L(r)。
- 已知正规式((a|b)|aa)b和正规式(a|b)*b。
（1）试用有穷自动机的等价性证明这两个正规式是等价的。
（2）分别给出与这两个正规式相对应的正规文法。
- 设M=({x，y}，{a，b}，δ，x，{y})为一非确定的有穷自动机，其δ定义如下：
δ(x, a)={x, y} δ{x, b}={y}
δ(y, a)=? δ{y, b}={x, y}
试构造与之等价的确定的有穷自动机D，并对所构造的自动机进行极小化。
- 已知一有穷自动机的状态转换图如图2-30所示，试求该自动机所识别语言的正规式。
- 为下列正规式构造极小化的DFA。
（1）(a|b)*a(a|b)
（2）(a|b)*a(a|b (a|b)
（3）(a|b)*a(a|b)(a|b)(a|b)
