第04讲-词法分析-III.ppt

《第04讲-词法分析-III.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、词法分析器记号（token）流源代码词法分析器工作原理：源程序字符流顺序组合词法单元词法记号模式非形式化描述形式化描述正规式字母组合串语言集合集合字母表名字温故而知新1正规式正规式：按照一组定义规则，由较简单的正规式构成的，每个正规式r表示一个语言L(r).定义规则说明L(r)是怎样以各种方式从r的子正规式所表示的语言组合而成。正规式用来表示简单的语言，叫做正规集。正规式是用于说明词法单元如何对应到词法记号的模式。与非形式化的描述相比，正规式更具形式化，更加精确。词法记号的描述与识别2回顾正规式词法记号的识别3正规式计算机实现状态

2、转换图？有限自动机不确定有限自动机确定有限自动机等价有限自动机4有限自动机识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。状态转换图（有限自动机）识别器确定/不确定有限自动机——时空权衡问题确定有限自动机：快，空间大5本讲纲要有限自动机定义DFA构建方法子集构造法6DFA确定的有限自动机（简称DFA)数学形式定义DFA是这样一个数学模型，包括状态集合S输入字母表转换函数move:SS唯一的初态sS终态集合FS01a7问题请构造(a

3、b)*ab的DFA?这个，基本上很难！怎么办？

4、下面，先引入一个新概念…8NFA不确定的有限自动机（简称NFA）数学形式定义DFA是这样一个数学模型，包括状态集合S输入字母表转换函数move:S({})P(S)唯一的初态sS终态集合FS缺点：1、输入字符包括2、一个状态对于某个字符，可能有多条输出边912开始a0abb34NFA例识别aa*

5、bb*的NFA10NFA(a

6、b)*ab的NFA12开始a0abb11(a

7、b)*ab的DFA12开始a0abbab12DFA与NFA的区别1.NFA中允许转换边，而DFA中不允许2.NFA中move(s,a)可能是

8、一个多元集合，而DFA中move(s,a)最多有一个元素13状态转移表(a

9、b)*ab状态迁移动作，从开始状态到目标状态输入符号ab0{0,1}{0}1{2}212开始a0abb输入符号ab0{1}{0}1{1}{2}2{1}{0}12开始a0abbab优点：快速定位缺点：字母表过大或大部分转换状态为空集时浪费空间14本讲纲要有限自动机定义DFA构建方法子集构造法15DFAorNFA在机器上实现字符串识别过程基于DFA?还是基于NFA?NFA更贴近于人们对正规式的认识DFA因为每次状态转换都是确定性的，即从当前状态s与当前字

10、符a，可以转换到唯一的目标状态s’16DFA构建方法1直接从自然语言描述，进行DFA的构建适合场景：从自然语言描述不能够得到一个简单的正规式170123开始4方法：1、列出全部可能的状态2、从各个状态出发，构造边及输入字符记号号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数180123开始41001010101号外：从语言到确定的有限自动机例：识别={0,1}上能被能5整除的二进制数19本讲纲要有限自动机定义DFA构建途径1：自然语言描述=>DFA途径2：正规式=>DFA途径3：正规式=>NFA=>D

11、FA子集构造法20途径1:自然语言描述=>DFA构建识别能被5整除的二进制数的DFA练习题：构建识别下列描述DFA偶数个0，偶数个1的01串C语言的注释/*…*/作为课后思考题，课后可以把解题过程以及答案发到我的邮箱，会作为最终平时成绩的一个参考，习题课时对这两个问题进行讨论21本讲纲要有限自动机定义DFA构建途径1：自然语言描述=>DFA途径2：正规式=>DFA途径3：正规式=>NFA=>DFA子集构造法22途径2:正则表达式=>DFA顾名思义，就是从词法模式的正规式表示，直接得到能够识别相应模式的DFA23示例1:关系运算符的

12、识别正则式relop<

13、<=

14、=

15、<>

16、>

17、>=0开始1<2=return(relop,LE)3>return(relop,NE)4otherreturn(relop,LT)=5return(relop,LT)=7return(relop,GE)6>8otherreturn(relop,GT)**24示例2：Pascal标识符的识别正规式idletter(letter

18、digit)*9开始1011letterLetter或digitother25无符号数的转换图开始1912131415161718digitdigitdigit

19、digitdigitdigitother.E+/Edigitotherotherreturn(install_num())*numdigit+(.digit+)?(E(+

20、)?digit+)?2.2词法记号的描述与识别26空白的转换图deli