编译原理与技术 词法分析 (2).ppt
《编译原理与技术 词法分析 (2).ppt》由会员分享,可在线阅读,更多相关《编译原理与技术 词法分析 (2).ppt(65页珍藏版)》请在三一文库上搜索。
1、2019/10/26,编译原理与技术讲义,1,编译原理与技术,词法分析 (2),2019/10/26,编译原理与技术讲义,2,有限自动机,有限自动机(Finite AutomataFA)是种更一般化的状态转换图。分为NFA和DFA。 词法分析器自动生成: 正规式 NFA DFA 词法程序,非确定有限自动机,确定的有限自动机,2019/10/26,编译原理与技术讲义,3,非确定有限自动机NFA,NFA Mn 是一个五元组 Mn =(, S, S0,F,), 其中: 有限字母表(输入符号集) S有限状态集 S0非空初态集合,S0S F终态集合,F S 状态转换函数,S x * 2S,2019/10
2、/26,编译原理与技术讲义,4,确定的有限自动机DFA,DFA Md 是一个五元组 Md =(, S, S0,F,), 其中: , S, S0,F 同NFA中的定义,而定义如下: :S x S , 为一单值映射函数。,2019/10/26,编译原理与技术讲义,5,有限自动机的表示,1)状态转换图,开始状态,一般状态,终态,s,(s,a)=t,t,a,s,(s,)=t,t,2019/10/26,编译原理与技术讲义,6,有限自动机的表示,2)状态转换矩阵(表),(Si,a) = Sj,2019/10/26,编译原理与技术讲义,7,有限自动机的表示,e.g.7 NFA Mn =(, S, S0,F,
3、),其中: = 0,1 , S = S0, S1 , S2 , S3 , S4 ,F=S2 , S4 (S0,0)= S0, S3 (S0,1)= S0, S1 (S1,0)= (S1,1)= S2 (S2,0)= S2 (S2,1)= S2 (S3,0)= S4 (S3,1)= (S4,0)= S4 (S4,1)= S4,2019/10/26,编译原理与技术讲义,8,有限自动机的表示,e.g.7 中NFA的状态转换图如下:,S0,S3,S1,0,1,0,0,0,1,1,1,0,1,S2,S4,2019/10/26,编译原理与技术讲义,9,有限自动机的表示,e.g.7 中NFA的状态转换矩阵(
4、表)如下:,2019/10/26,编译原理与技术讲义,10,有限自动机识别的语言,e.g.8 下面FA识别(接受)的串是什么?,S0,S1,S2,0,1,FA识别(接受)串* , 如果存在一个从FA的初态到某个终态的(状态)转换路径,该路径上所有标记的字符依次连接为。 FA M 所识别的语言 L(M) L(M) = | M 识别 * ,2019/10/26,编译原理与技术讲义,11,有限自动机识别的语言,e.g.9 下面DFA M识别的语言L(M)是什么?,2019/10/26,编译原理与技术讲义,12,有限自动机识别的语言,e.g.9 L(M) = 含偶数个0和偶数个1的0,1串,S2,S1
5、,S0,S3,偶数个“0”与偶数个“1”的0,1串,偶数个“0”与奇数个“1”的0,1串,奇数个“0”与偶数个“1”的0,1串,奇数个“0”与奇数个“1”的0,1串,2019/10/26,编译原理与技术讲义,13,有限自动机识别的语言,e.g.10 下面DFA M识别的语言L(M)是什么?,S2,S1,S0,0,1,0,1,0,1,2019/10/26,编译原理与技术讲义,14,有限自动机识别的语言,e.g.10 L(M) = 能被“3”整除的二进制数(串) ,S2,S1,S0,能被3整除,被3整除余1,被3整除余2,2019/10/26,编译原理与技术讲义,15,有限自动机识别的语言,e.g
6、.10 L(M) = 能被“3”整除的二进制数(串) 二进制串 10010 , 即十进制18的识别过程:,S2,S1,S0,0,1,0,1,0,输入串 1,0,0,1,0,2019/10/26,编译原理与技术讲义,16,比较 DFA 和 NFA(1),2019/10/26,编译原理与技术讲义,17,比较 DFA 和 NFA(2),2019/10/26,编译原理与技术讲义,18,比较 DFA 和 NFA(3),e.g.11 识别正规式(0|1)*01的DFA和NFA,2019/10/26,编译原理与技术讲义,19,对于上正规式R,存在一个NFA M,使得 L(M) = L(R) ,反之亦然。 T
7、hopmson 方法: R= R= R=a,正规式与有限自动机,S0,S1,S0,S1,S0,a,只引入初态S0和终态S1,他们之间无状态转换,2019/10/26,编译原理与技术讲义,20,正规式与有限自动机,R= R1 | R2 (1),Si,fi,Sj,fj,R1对应的NFA,Si为初态,fi为终态,R2对应的NFA,Sj为初态,fj为终态,2019/10/26,编译原理与技术讲义,21,正规式与有限自动机,R= R1 | R2 (2),S0,Si,fi,Sj,fj,引入新的初态S0和(S0,)=Si和(S0,)=Sj,2019/10/26,编译原理与技术讲义,22,正规式与有限自动机,
8、R= R1 | R2 (3),S0,f0,Si,fi,Sj,fj,引入新的终态f0和(fi,)=f0和(fj,)=f0,2019/10/26,编译原理与技术讲义,23,正规式与有限自动机,R= R1 R2 (1),R1对应的NFA,Si为初态,fi为终态,R2对应的NFA,Sj为初态,fj为终态,2019/10/26,编译原理与技术讲义,24,正规式与有限自动机,R= R1 R2 (2),S0,引入新的初态S0和(S0,)=Si,2019/10/26,编译原理与技术讲义,25,正规式与有限自动机,R= R1 R2 (3),S0,引入新的状态转换(fi,)=Sj,2019/10/26,编译原理与
9、技术讲义,26,正规式与有限自动机,R= R1 R2 (4),Sj,fj,S0,引入新的终态f0和状态转换(fj,)=f0,f0,2019/10/26,编译原理与技术讲义,27,正规式与有限自动机,R= R1* (1),R1对应的NFA,Si为初态,fi为终态,2019/10/26,编译原理与技术讲义,28,正规式与有限自动机,R= R1* (2),S0,引入新的初态S0和(S0,)=Si,2019/10/26,编译原理与技术讲义,29,正规式与有限自动机,R= R1* (3),Si,fi,S0,引入新的终态f0和状态转换(fi,)=f0,f0,2019/10/26,编译原理与技术讲义,30,
10、正规式与有限自动机,R= R1* (4),Si,fi,S0,引入新的状态转换(fi,)=Si,f0,2019/10/26,编译原理与技术讲义,31,正规式与有限自动机,R= R1* (5),Si,fi,S0,引入新的状态转换(S0,)=f0,f0,2019/10/26,编译原理与技术讲义,32,正规式与有限自动机,R= (R1),R1对应的NFA,它也是(R1)对应的NFA,2019/10/26,编译原理与技术讲义,33,e.g.12 构造(0|1)*01的对应的FA。(1),0,0,1,1,0 | 1,0,1,2019/10/26,编译原理与技术讲义,34,e.g.12 构造(0|1)*01
11、的对应的FA。(2),(0 | 1) 同 0 | 1,(0 | 1)*,0,1,2019/10/26,编译原理与技术讲义,35,e.g.12 构造(0|1)*01的对应的FA。(3),(0 | 1)* 0,0,1,0,2019/10/26,编译原理与技术讲义,36,e.g.12 构造(0|1)*01的对应的FA。(4),(0 | 1)* 0 1,2019/10/26,编译原理与技术讲义,37,e.g.12 构造(0|1)*01的对应的FA。(5),R1,R2,|,R3,0,1,(,),R4,*,R5,R7,R9,R6,0,R8,1,2019/10/26,编译原理与技术讲义,38,Thompso
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理与技术 词法分析 2 编译 原理 技术 词法 分析
链接地址:https://www.31doc.com/p-4191766.html