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

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

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

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

3、,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,2023/4/26,编译原理与技术讲义,8,有限自动机的表示,e.g.7 中NFA的状态转换图如下：,S0,S3,S1,0,1,0,0,0,1,1,1,0,1,S2,S4,2023/4/26,编译原理与技术讲义,9,有限自动机的表示,e.g.7 中NFA的状态转换矩阵（表）如下：,2023/4/26,编译原理与技术讲义,10,有限自动机识别的语言,e.g.8 下面FA识别（接受）的串是什么？,S0,S1,S2,0,1

4、,FA识别（接受）串*,如果存在一个从FA的初态到某个终态的（状态）转换路径，该路径上所有标记的字符依次连接为。FA M 所识别的语言 L(M)L(M)=|M 识别*,2023/4/26,编译原理与技术讲义,11,有限自动机识别的语言,e.g.9 下面DFA M识别的语言L(M)是什么？,2023/4/26,编译原理与技术讲义,12,有限自动机识别的语言,e.g.9 L(M)=含偶数个0和偶数个1的0,1串,S2,S1,S0,S3,偶数个“0”与偶数个“1”的0,1串,偶数个“0”与奇数个“1”的0,1串,奇数个“0”与偶数个“1”的0,1串,奇数个“0”与奇数个“1”的0,1串,2023/4

5、/26,编译原理与技术讲义,13,有限自动机识别的语言,e.g.10 下面DFA M识别的语言L(M)是什么？,S2,S1,S0,0,1,0,1,0,1,2023/4/26,编译原理与技术讲义,14,有限自动机识别的语言,e.g.10 L(M)=能被“3”整除的二进制数(串),S2,S1,S0,能被3整除,被3整除余1,被3整除余2,2023/4/26,编译原理与技术讲义,15,有限自动机识别的语言,e.g.10 L(M)=能被“3”整除的二进制数(串)二进制串 10010,即十进制18的识别过程：,S2,S1,S0,0,1,0,1,0,输入串 1,0,0,1,0,2023/4/26,编译原理

6、与技术讲义,16,比较 DFA 和 NFA（1）,2023/4/26,编译原理与技术讲义,17,比较 DFA 和 NFA（2）,2023/4/26,编译原理与技术讲义,18,比较 DFA 和 NFA（3）,e.g.11 识别正规式（0|1）*01的DFA和NFA,2023/4/26,编译原理与技术讲义,19,对于上正规式R，存在一个NFA M，使得L(M)=L(R)，反之亦然。Thopmson 方法：R=R=R=a,正规式与有限自动机,S0,S1,S0,S1,S0,a,只引入初态S0和终态S1，他们之间无状态转换,2023/4/26,编译原理与技术讲义,20,正规式与有限自动机,R=R1|R2

7、（1）,Si,fi,Sj,fj,R1对应的NFA,Si为初态，fi为终态,R2对应的NFA,Sj为初态，fj为终态,2023/4/26,编译原理与技术讲义,21,正规式与有限自动机,R=R1|R2（2）,S0,Si,fi,Sj,fj,引入新的初态S0和(S0,)=Si和(S0,)=Sj,2023/4/26,编译原理与技术讲义,22,正规式与有限自动机,R=R1|R2（3）,S0,f0,Si,fi,Sj,fj,引入新的终态f0和(fi,)=f0和(fj,)=f0,2023/4/26,编译原理与技术讲义,23,正规式与有限自动机,R=R1 R2（1）,R1对应的NFA,Si为初态，fi为终态,R2

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

9、译原理与技术讲义,28,正规式与有限自动机,R=R1*（2）,S0,引入新的初态S0和(S0,)=Si,2023/4/26,编译原理与技术讲义,29,正规式与有限自动机,R=R1*（3）,Si,fi,S0,引入新的终态f0和状态转换(fi,)=f0,f0,2023/4/26,编译原理与技术讲义,30,正规式与有限自动机,R=R1*（4）,Si,fi,S0,引入新的状态转换(fi,)=Si,f0,2023/4/26,编译原理与技术讲义,31,正规式与有限自动机,R=R1*（5）,Si,fi,S0,引入新的状态转换(S0,)=f0,f0,2023/4/26,编译原理与技术讲义,32,正规式与有限自

10、动机,R=(R1),R1对应的NFA，它也是(R1)对应的NFA,2023/4/26,编译原理与技术讲义,33,e.g.12 构造（0|1）*01的对应的FA。（1）,0,0,1,1,0|1,0,1,2023/4/26,编译原理与技术讲义,34,e.g.12 构造（0|1）*01的对应的FA。（2）,(0|1)同 0|1,(0|1)*,0,1,2023/4/26,编译原理与技术讲义,35,e.g.12 构造（0|1）*01的对应的FA。（3）,(0|1)*0,0,1,0,2023/4/26,编译原理与技术讲义,36,e.g.12 构造（0|1）*01的对应的FA。（4）,(0|1)*0 1,2

11、023/4/26,编译原理与技术讲义,37,e.g.12 构造（0|1）*01的对应的FA。（5）,R1,R2,|,R3,0,1,（,）,R4,*,R5,R7,R9,R6,0,R8,1,2023/4/26,编译原理与技术讲义,38,Thompson方法所构造的NFA的状态数和转换较多。可以采用下面方法减少之：,R=R1|R2,R1,R2,R=R1 R2,R1,R2,R=R1*,R1,R,R,R1,2023/4/26,编译原理与技术讲义,39,e.g.13 构造（0|1）*01的对应的FA简化版,（0|1）*0 1,1）,(0|1)*0,1,2）,(0|1)*,1,3）,0,1,4）,0,0|1

12、,2023/4/26,编译原理与技术讲义,40,e.g.13 构造（0|1）*01的对应的FA简化版,1,4）,0,0|1,1,5）,0,0,1,2023/4/26,编译原理与技术讲义,41,NFA的确定化（转换到DFA）,子集构造法对NFA进行模拟。NFA的转换表中每个条目是状态子集，而在DFA中则为单一的状态。NFA到DFA的转换的一般想法是，让DFA中的每个状态代表NFA中的状态子集。DFA用它的状态去记住NFA在读入每个输入符号后能到达的所有状态的集合，即在DFA在读了符号a1a2an后到达代表NFA状态子集T的状态，而这个子集T是从NFA开始状态沿着标记有a1a2an的路径所能到达的

13、所有状态的集合。,2023/4/26,编译原理与技术讲义,42,NFA的确定化（转换到DFA）,子集构造法DFA的“状态”Sd是NFA的非空状态子集，Sd2SDFA的初态Sd0包括原NFA初态S0及其经转换能到达的所有状态，即 Sd0=S0，u|S0*u-closure(S0)-closure(T)=从状态集合T的每一个状态t出发，经过若干空转换（转换）所能到达的所有状态,2023/4/26,编译原理与技术讲义,43,NFA的确定化（转换到DFA）,子集构造法DFA状态转换函数d:Sd1 a Sd2，Sd2=t，u|s a t,sSd1，t*u=-closure(t|s a t,sSd1)DF

14、A的终态F 含有原NFA终态的Sd,2023/4/26,编译原理与技术讲义,44,初始时，DFA的状态集合Dstates中只有初态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；,2023/4/26,编译原理与技术讲义,45,NFA的确定化,e.g.14 确定化以下NFA M。,2023/4/26,编译原理与技术讲义,46,e.g.14 确定化以下NFA M。

15、（续1）,2023/4/26,编译原理与技术讲义,47,e.g.14 确定化以下NFA M。（续2）,2023/4/26,编译原理与技术讲义,48,e.g.14 确定化以下NFA M。（续3）,2023/4/26,编译原理与技术讲义,49,e.g.14 确定化以下NFA M。（续4）,2023/4/26,编译原理与技术讲义,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不等价。

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

17、FA M极小化（2）,初始划分 I0=终态集合=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，此时划分过程结束！,2023/4/26,编译原理与技术讲义,54,e.g.15 将下

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

19、count=0;/*任何形式的C声明*/%上述C声明、语句被拷贝到lex.yy.c文件中,2023/4/26,编译原理与技术讲义,58,词法分析器自动生成Lex,Lex 源程序组成定义段:正规定义digit 0-9number digit+,2023/4/26,编译原理与技术讲义,59,词法分析器自动生成Lex,Lex 源程序组成规则段正规式 语义动作 number int n=atoi(yytext);printf(“%x”,n);/*语义动作合法的C语句*/语义动作(C 语句)被拷贝到yylex()中当正规式匹配时其相应的语义动作即被执行,2023/4/26,编译原理与技术讲义,60,词法

20、分析器自动生成Lex,Lex 源程序组成用户程序段包含用户自定义的C函数，此段可空。如：main()int yywrap()yylex();return 0;return 1;,2023/4/26,编译原理与技术讲义,61,%#include#include int count=0;/*任何形式的C声明*/%digit 0-9number digit+,%number int n=atoi(yytext);printf(“%x”,n);/*语义动作合法的C语句*/%main()yylex();return 0;int yywrap()return 1;,e.g.16 一个lex例子程序,2023/4/26,编译原理与技术讲义,62,Lex 中元字符约定（1）,2023/4/26,编译原理与技术讲义,63,Lex 中元字符约定（2）,2023/4/26,编译原理与技术讲义,64,Lex 内部名字,2023/4/26,编译原理与技术讲义,65,词法分析器自动生成Lex,Lex中二义性规则的处理选择最长规则进行匹配，如 和=输入串与两个（或两个以上）规则匹配时，选择在规则段中位置靠前（首先出现）的规则进行匹配。如，关键字规则靠前而（普通）标识符规则在后。,