第05讲词法分析IVdfa化简lex习题

1、1正规式正规式状态转换图状态转换图温故而知新203NFA4NFA=DFA 理论依据 根据有限自动机理论，设L为一个有不确定的有限自动机接受的集合，则存在一个接受L的确定的有限自动机 怎样进行NFA到DFA的转化 子集构造法5本讲纲要 子集构造法 DFA化简 Lex 习题6NFA=DFA 子集构造法12a开始开始0abb7NFA=DFA 子集构造法12a开始开始0abb00, 1aba0, 2bab819开始开始 0ab ab6782345 919开始开始 0ab ab6782345 BD开始开始aAabbabCba10BD开始开始aAabbabCba111212开始开始a0abbab19开始开

2、始 0ab ab6782345 12开始开始a0abbBD开始开始aAabbabCba13本讲纲要 子集构造法 DFA化简 Lex 习题14 15 判断依据：16BD开始开始aAabbabCba17 DFA化简的途径 根据状态是否可以区分根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的 依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系18BD开始开始aAabbaa, bCbaEbBD开始开始aAabbabCba1912开始开始a0abbabBD开始开始aAabbabCba20本讲纲要 子集构造法 DFA化简 补充

3、 Lex 习题2112开始开始a0abbab2212开始开始a0abbab2312开始开始a0abbab2412开始开始a0abbab2512开始开始a0abbab2612开始开始a0abbab2712开始开始a0abbab2812开始开始a0abbab2912开始开始a0abbab30基于DFA构建识别程序 建立状态转移表建立状态转移表 每一步状态转换通过查表得到下一步状态转每一步状态转换通过查表得到下一步状态转换目标换目标31Program Assignment 编写识别 的程序 基于DFA，用状态转移表格来做 状态转移表的数据结构定义自选3233本讲纲要 子集构造法 Lex34 Lex编

4、译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.ca.outa.out输入流输入流记号序列记号序列3536 37383940用 Lex 定义常规表达式 .匹配任意字符，除了匹配任意字符，除了n-指范围指范围A-Za-z0-9$行的结尾行的结尾 模式可能出现的次数，例如模式可能出现的次数，例如A1,3表示可表示可能出现能出现1次或次或3次次否定否定,操作符操作符只能出现在左中括号后的第只能出现在左中括号后的第一个字符位置处一个字符位置处abc * | ?+等等常用的闭包，逻辑或等操作常用的闭包，逻辑或等操作4142434445. 匹配任意字符，除了 n46 简单

5、的例子简单的例子 删除输入中每行结尾处所有空白符删除输入中每行结尾处所有空白符 % t+$ ; 如果要将字符串中的空格或者制表符转换为单个如果要将字符串中的空格或者制表符转换为单个空格，需要增加一条规则：空格，需要增加一条规则：% t+$ ; t+ printf(“ ”);4748 hello world wo ai tian an men hello world i love# of lines = 3, # of chars = 4949源程序源程序字符流字符流顺顺序序组组合合词法词法单元单元词法词法记号记号模模式式非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组组合合串

6、串语言语言集集合合集集合合字母表字母表名名字字连接连接 指数指数和和 LUM连接连接 LM闭包闭包 L*正闭包正闭包 L+ +状态状态转换转换图图Lex50本讲纲要 第二章 习题51520123aabbabbbstart45aaa, b53012bbbb4aastart最简最简DFA5455用状态转换图表示接收(a|b)*aa 的DFA 最简单的句子是最简单的句子是aa 开始aa01256用状态转换图表示接收用状态转换图表示接收(a|b)*aa 的的DFA 因为在第一个因为在第一个a前可以有若干个前可以有若干个b，因此状态，因此状态0有到自身的有到自身的b转换。在最后两个字符都是转换。在最后两

7、个字符都是a的串的末尾添加若干个的串的末尾添加若干个a，能够保持串的这个性质能够保持串的这个性质 。57识别注释的DFA 58第二章 习题 1.书p36 2.3解： 首尾均为0的二进制串 0，1组成的二进制串，包括空串 倒数第3位为0的二进制串 包含且仅包含3个1的二进制串 1的个数和0的个数均为偶数的二进制串59巩固与提高312011110000开始开始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1602021-10-1361消除状态1：3201110110100start002021-10-1362消除状态2：3011|0010|0101|10start00|112021-10-1363

8、消除状态3：011|00(10|01)(00|11)*(01|10)startqf(00|11)|(10|01)(00|11)*(01|10)*即：start64。 11000011010011000011100110651100001101001100001110011066由偶数个0和奇数个1构成的所有0和1的串 在上一题的基础上给出： even_0_even_1 ( 00 | 11 | (01|10) (00|11)* (01|10) )*67由偶数个0和奇数个1构成的所有0和1的串 对于偶数个0和奇数个1构成的串，其第一个字符可能是0或1。 如果是1，那么剩下的部分一定是偶数个0和偶数

9、个1（即1 even_0_even_1）。 如果是0，那么经过若干个偶数个0或偶数个1，一定会出现一个01或10，才能保证0的个数是偶数，1的个数是奇数。若串还没有结束，剩余部分一定是偶数个0和偶数个1。68由偶数个0和奇数个1构成的所有0和1的串 答案 even_0_even_1 (00 | 11 | (01|10) (00|11)* (01|10) )* even_0_odd_1 1 even_0_even_1 | 0 even_0_even_1 (01|10) even_0_even_16970DFA化简举例 化简下面的DFA71DFA化简举例 化简下面的DFA72DFA化简举例 化简下面的DFA73DFA化简举例 化简下面的DFA74DFA化简举例 化简结果(去除死状态后)7512开始开始x0yyx11,2开始开始x0yyxx能被3整除的二进制数761(10*1)|(01*0)*10* 有限状态自动机是可以转化为正则表达式的。上面的这个自动机转化起来非常容易。我们可以先试着用自然语言叙述一下。首先，每个二进制数第一位必然为 “1”。到达状态1后，我们可以随意地、任意多次地在状态1周围绕圈圈，最终回到状态1。临近末尾，我们再读到一个“1”返回状态0，这之后随便读