第3讲-词法分析-ii

《第3讲-词法分析-ii》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理和技术本讲纲要词法概念的复习词法记号的识别有限自动机定义DFA构建方法词法单元词法记号词法单元词法记号模式用模式语言描述正规式，是描述词法记号的一种最为常见的模式语言正规式正规式，又称正则表达式，RegularExpressionPascal里面的标识符模式正规式表示letterA

2、B

3、…

4、Z

5、a

6、b

7、…

8、zdigit0

9、1

10、…

11、9idletter(letter

12、digit)*怎么用语言来描述Pascal的标识符模式？Pascal标识符模式的自然语言描述：首字符必须是字母，由字母或数字组成的字符串C语言的标识符模式模式的

13、非形式描述首字符必须是_或者字母，由_、字母或数字组成的字符串请仿照Pascal标识符的例子，写出C语言的标识符的正规式表示本讲纲要词法概念的复习词法记号的识别有限自动机定义DFA构建方法词法记号的识别词法记号的识别等同于对字符串的匹配过程这个匹配过程可以基于有限状态机来完成简单的正则式d->a01a正则式d->ab02a1b正则式d->a

14、b01ab正规式d->a*0a自动机的定义正规式d->a?字符a出现一次或者0次01a练习正规式d->a(a

15、b)*请画出它的状态转换图01aab本讲纲要词法概念的复习词法记号的识别有限自动机定义

16、DFA构建方法DFA确定的有限自动机（简称DFA)数学形式定义DFA是这样一个数学模型，包括状态集合S输入字母表转换函数move:SS唯一的初态sS终态集合FS01a问题请构造(a

17、b)*ab的DFA?这个，基本上很难！怎么办？下面，先引入一个新概念…NFA不确定的有限自动机（简称NFA）数学形式定义DFA是这样一个数学模型，包括状态集合S输入字母表转换函数move:S({})P(S)唯一的初态sS终态集合FSNFA例识别aa*

18、bb*的NFA12开始a0abb34NFA(a

19、b)*ab的NFA12开始

20、a0abb(a

21、b)*ab的DFA12开始a0abbab状态转移表状态迁移动作，从开始状态到目标状态输入符号ab0{0,1}{0}1{2}212开始a0abb输入符号ab0{1}{0}1{1}{2}2{1}{0}12开始a0abbabDFA与NFA的区别1.NFA中允许转换边，而DFA中不允许2.NFA中move(s,a)可能是一个多元集合，而DFA中move(s,a)最多有一个元素本讲纲要词法概念的复习词法记号的识别有限自动机定义DFA构建方法DFAorNFA在机器上实现字符串识别过程基于DFA?还是基于NFA?NFA更贴近

22、于人们对正规式的认识DFA因为每次状态转换都是确定性的，即从当前状态s与当前字符a，可以转换到唯一的目标状态s’DFA构建方法1直接从自然语言描述，进行DFA的构建适合场景：从自然语言描述不能够得到一个简单的正规式号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始4方法：1、列出全部可能的状态2、从各个状态出发，构造边及输入字符记号例：识别={0,1}上能被能5整除的二进制数0123开始40号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始410号外：从语言

23、到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始4100号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始41001号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始410010号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始4100101号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始41001010号外：从语言到确定的有限自动机例：识别={0,1}

24、上能被能5整除的二进制数0123开始410010101号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始4100101010号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始41001010101号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数0123开始41001010101号外：从语言到确定的有限自动机本讲小结DFA,NFA的概念DFA的构建方法1自然语言描述=>DFA