编译原理与技术词法分析 (2).ppt

资源描述

《编译原理与技术词法分析 (2).ppt》由会员分享，可在线阅读，更多相关《编译原理与技术词法分析 (2).ppt（65页珍藏版）》请在三一文库上搜索。

1、2019/10/27,编译原理与技术讲义,1,编译原理与技术,词法分析 (2),2019/10/27,编译原理与技术讲义,2,有限自动机,有限自动机（Finite AutomataFA）是种更一般化的状态转换图。分为NFA和DFA。词法分析器自动生成：正规式 NFA DFA 词法程序,非确定有限自动机,确定的有限自动机,2019/10/27,编译原理与技术讲义,3,非确定有限自动机NFA,NFA Mn 是一个五元组 Mn =(, S, S0,F,)，其中：有限字母表（输入符号集） S有限状态集 S0非空初态集合，S0S F终态集合，F S 状态转换函数，S x * 2S,2019/10

2、/27,编译原理与技术讲义,4,确定的有限自动机DFA,DFA Md 是一个五元组 Md =(, S, S0,F,)，其中: , S, S0,F 同NFA中的定义，而定义如下：：S x S ，为一单值映射函数。,2019/10/27,编译原理与技术讲义,5,有限自动机的表示,1）状态转换图,开始状态,一般状态,终态,s,(s,a)=t,t,a,s,(s,)=t,t,2019/10/27,编译原理与技术讲义,6,有限自动机的表示,2）状态转换矩阵（表）,(Si,a) = Sj,2019/10/27,编译原理与技术讲义,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/27,编译原理与技术讲义,8,有限自动机的表示,e.g.7 中NFA的状态转换图如下：,S0,S3,S1,0,1,0,0,0,1,1,1,0,1,S2,S4,2019/10/27,编译原理与技术讲义,9,有限自动机的表示,e.g.7 中NFA的状态转换矩阵（

4、表）如下：,2019/10/27,编译原理与技术讲义,10,有限自动机识别的语言,e.g.8 下面FA识别（接受）的串是什么？,S0,S1,S2,0,1,FA识别（接受）串* , 如果存在一个从FA的初态到某个终态的（状态）转换路径，该路径上所有标记的字符依次连接为。 FA M 所识别的语言 L(M) L(M) = | M 识别 * ,2019/10/27,编译原理与技术讲义,11,有限自动机识别的语言,e.g.9 下面DFA M识别的语言L(M)是什么？,2019/10/27,编译原理与技术讲义,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/27,编译原理与技术讲义,13,有限自动机识别的语言,e.g.10 下面DFA M识别的语言L(M)是什么？,S2,S1,S0,0,1,0,1,0,1,2019/10/27,编译原理与技术讲义,14,有限自动机识别的语言,e.g.10 L(M) = 能被“3”整除的二进制数(串) ,S2,S1,S0,能被3整除,被3整除余1,被3整除余2,2019/10/27,编译原理与技术讲义,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/27,编译原理与技术讲义,16,比较 DFA 和 NFA（1）,2019/10/27,编译原理与技术讲义,17,比较 DFA 和 NFA（2）,2019/10/27,编译原理与技术讲义,18,比较 DFA 和 NFA（3）,e.g.11 识别正规式（0|1）*01的DFA和NFA,2019/10/27,编译原理与技术讲义,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/27,编译原理与技术讲义,20,正规式与有限自动机,R= R1 | R2 （1）,Si,fi,Sj,fj,R1对应的NFA,Si为初态，fi为终态,R2对应的NFA,Sj为初态，fj为终态,2019/10/27,编译原理与技术讲义,21,正规式与有限自动机,R= R1 | R2 （2）,S0,Si,fi,Sj,fj,引入新的初态S0和(S0,)=Si和(S0,)=Sj,2019/10/27,编译原理与技术讲义,22,正规式与有限自动机,

8、R= R1 | R2 （3）,S0,f0,Si,fi,Sj,fj,引入新的终态f0和(fi,)=f0和(fj,)=f0,2019/10/27,编译原理与技术讲义,23,正规式与有限自动机,R= R1 R2 （1）,R1对应的NFA,Si为初态，fi为终态,R2对应的NFA,Sj为初态，fj为终态,2019/10/27,编译原理与技术讲义,24,正规式与有限自动机,R= R1 R2 （2）,S0,引入新的初态S0和(S0,)=Si,2019/10/27,编译原理与技术讲义,25,正规式与有限自动机,R= R1 R2 （3）,S0,引入新的状态转换(fi,)=Sj,2019/10/27,编译原理与

9、技术讲义,26,正规式与有限自动机,R= R1 R2 （4）,Sj,fj,S0,引入新的终态f0和状态转换(fj,)=f0,f0,2019/10/27,编译原理与技术讲义,27,正规式与有限自动机,R= R1* （1）,R1对应的NFA,Si为初态，fi为终态,2019/10/27,编译原理与技术讲义,28,正规式与有限自动机,R= R1* （2）,S0,引入新的初态S0和(S0,)=Si,2019/10/27,编译原理与技术讲义,29,正规式与有限自动机,R= R1* （3）,Si,fi,S0,引入新的终态f0和状态转换(fi,)=f0,f0,2019/10/27,编译原理与技术讲义,30,

10、正规式与有限自动机,R= R1* （4）,Si,fi,S0,引入新的状态转换(fi,)=Si,f0,2019/10/27,编译原理与技术讲义,31,正规式与有限自动机,R= R1* （5）,Si,fi,S0,引入新的状态转换(S0,)=f0,f0,2019/10/27,编译原理与技术讲义,32,正规式与有限自动机,R= (R1),R1对应的NFA，它也是(R1)对应的NFA,2019/10/27,编译原理与技术讲义,33,e.g.12 构造（0|1）*01的对应的FA。（1）,0,0,1,1,0 | 1,0,1,2019/10/27,编译原理与技术讲义,34,e.g.12 构造（0|1）*01

13、到DFA）,子集构造法对NFA进行模拟。NFA的转换表中每个条目是状态子集，而在DFA中则为单一的状态。NFA到DFA的转换的一般想法是，让DFA中的每个状态代表NFA中的状态子集。DFA用它的状态去记住NFA在读入每个输入符号后能到达的所有状态的集合，即在DFA在读了符号a1a2an后到达代表NFA状态子集T的状态，而这个子集T是从NFA开始状态沿着标记有a1a2an的路径所能到达的所有状态的集合。,2019/10/27,编译原理与技术讲义,42,NFA的确定化（转换到DFA）,子集构造法 DFA的“状态”Sd是NFA的非空状态子集，Sd2S DFA的初态Sd0包括原NFA初态S0及其经转

14、换能到达的所有状态，即 Sd0 = S0，u | S0 * u -closure(S0) -closure(T) = 从状态集合T的每一个状态t出发，经过若干空转换（转换）所能到达的所有状态,2019/10/27,编译原理与技术讲义,43,NFA的确定化（转换到DFA）,子集构造法 DFA状态转换函数d : Sd1 a Sd2 ， Sd2 = t，u | s a t , sSd1 ， t * u = -closure( t | s a t , sSd1 ) DFA的终态F 含有原NFA终态的Sd ,2019/10/27,编译原理与技术讲义,44,初始时，DFA的状态集合Dstates中只有初

15、态Sd0且未标记。 while ( Dstates中有未标记的状态 T ） do 标记 T； for 每个输入符号 a do U = -closure( s | NFA状态转换函数(t,a)=s, tT ) if U 不在 Dstates中则将其加入Dstates且未加标记；记下DFA状态转换函数d（T，a） U ； ,2019/10/27,编译原理与技术讲义,45,NFA的确定化,e.g.14 确定化以下NFA M。,2019/10/27,编译原理与技术讲义,46,e.g.14 确定化以下NFA M。（续1）,2019/10/27,编译原理与技术讲义,47,e.g.14 确定化以下NFA

16、 M。（续2）,2019/10/27,编译原理与技术讲义,48,e.g.14 确定化以下NFA M。（续3）,2019/10/27,编译原理与技术讲义,49,e.g.14 确定化以下NFA M。（续4）,2019/10/27,编译原理与技术讲义,50,DFA的简化极小化,DFA M 极小化 DFA M，其中L(M)=L(M)，且DFA M是和DFA M等价（识别语言相同）的DFA中状态数最少的。状态s1和s2是等价的，如果 s1 f1 且 s2 f2，f1，f2F，* 。状态t1和t2是可区分的，如果t1和t2不等价。,2019/10/27,编译原理与技术讲义,51,DFA的简化极小化,状

17、态极小化将DFA的状态集合S划分成若干不相交状态子集，不同子集的状态间是可区别的，相同子集内的状态间等价。取各个状态子集中的某一个状态为该子集代表，消除该子集中其他状态。初始划分：终态集合与非终态集合划分过程：如果s1,s2划分子集I，a ，有 (s1,a) 划分J ，(s2,a) 划分K ，则划分I应进一步再划分成I1,I2 ,s1 I1,s2 I2,2019/10/27,编译原理与技术讲义,52,DFA的简化极小化,e.g.15 将下面的DFA M极小化（1）,2019/10/27,编译原理与技术讲义,53,e.g.15 将下面的DFA M极小化（2）,初始划分 I0=终态集

18、合= 3，4，5，6 和I1=非终态集合= 0, 1, 2 ,考查 I1=0,1,2, 0a 1 , 1a 3 , 2a 1 ，I1需再划分成I2=0,2和I3=1，此时划分为: I0, I2 和 I3 即3,4,5,6, 0,2 和1,考查 I2, 0b 2 , 2b 4，I2需再划分成I4=0和I5=2，此时划分为: I0, I4, I5 和 I3 即3,4,5,6, 0, 2 和 1,考查I0=3,4,5,6, 3a 3 , 4a 6 , 5a 6 , 6a 3 3b 5 , 4b 4 , 5b 4 , 6b 5 ，不需要划分I0，此时划分过程结束！,2019/10/27,编译原理与技术

19、讲义,54,e.g.15 将下面的DFA M极小化（3）,最终划分 0 , 1 , 2 和 3，4，5，6 /取状态3为代表,极小化的DFA如下：,2019/10/27,编译原理与技术讲义,55,词法分析器自动生成Lex,Lex 源程序,LEX,lex.yy.c yylex(),lex.yy.c yylex(),C编译器,可执行文件/a.out,可执行文件/a.out,输入串,单词记号,2019/10/27,编译原理与技术讲义,56,词法分析器自动生成Lex,Lex 源程序组成定义段规则段用户程序段,2019/10/27,编译原理与技术讲义,57,词法分析器自动生成Lex,Lex 源程

20、序组成定义段: % #include #include int count = 0; /* 任何形式的C声明 */ % 上述C声明、语句被拷贝到lex.yy.c文件中,2019/10/27,编译原理与技术讲义,58,词法分析器自动生成Lex,Lex 源程序组成定义段: 正规定义 digit 0-9 number digit+,2019/10/27,编译原理与技术讲义,59,词法分析器自动生成Lex,Lex 源程序组成规则段正规式语义动作 number int n = atoi(yytext); printf(“%x”, n); /* 语义动作合法的C语句 */ 语义动作(C 语句)被拷贝

21、到yylex()中当正规式匹配时其相应的语义动作即被执行,2019/10/27,编译原理与技术讲义,60,词法分析器自动生成Lex,Lex 源程序组成用户程序段包含用户自定义的C函数，此段可空。如： main() int yywrap() yylex(); return 0; return 1; ,2019/10/27,编译原理与技术讲义,61,% #include #include int count = 0; /*任何形式的C声明 */ % digit 0-9 number digit+,% number int n = atoi(yytext); printf(“%x”, n); /

22、*语义动作合法的C语句 */ % main() yylex(); return 0; int yywrap() return 1; ,e.g.16 一个lex例子程序,2019/10/27,编译原理与技术讲义,62,Lex 中元字符约定（1）,2019/10/27,编译原理与技术讲义,63,Lex 中元字符约定（2）,2019/10/27,编译原理与技术讲义,64,Lex 内部名字,2019/10/27,编译原理与技术讲义,65,词法分析器自动生成Lex,Lex中二义性规则的处理选择最长规则进行匹配，如和 = 输入串与两个（或两个以上）规则匹配时，选择在规则段中位置靠前（首先出现）的规则进行匹配。如，关键字规则靠前而（普通）标识符规则在后。,

展开阅读全文

编译原理与技术 词法分析 (2).ppt

编译原理与技术词法分析 (2).ppt