编译原理与技术.ppt

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

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

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

5、”与偶数个“1”的0,1串,偶数个“0”与奇数个“1”的0,1串,奇数个“0”与偶数个“1”的0,1串,奇数个“0”与奇数个“1”的0,1串,2020/8/21,编译原理与技术讲义,13,有限自动机识别的语言,e.g.10 下面DFA M识别的语言L(M)是什么？,S2,S1,S0,0,1,0,1,0,1,2020/8/21,编译原理与技术讲义,14,有限自动机识别的语言,e.g.10 L(M) = 能被“3”整除的二进制数(串) ,S2,S1,S0,能被3整除,被3整除余1,被3整除余2,2020/8/21,编译原理与技术讲义,15,有限自动机识别的语言,e.g.10 L(M) = 能被“3

6、”整除的二进制数(串) 二进制串 10010 , 即十进制18的识别过程：,S2,S1,S0,0,1,0,1,0,输入串 1,0,0,1,0,2020/8/21,编译原理与技术讲义,16,比较 DFA 和 NFA（1）,2020/8/21,编译原理与技术讲义,17,比较 DFA 和 NFA（2）,2020/8/21,编译原理与技术讲义,18,比较 DFA 和 NFA（3）,e.g.11 识别正规式（0|1）*01的DFA和NFA,2020/8/21,编译原理与技术讲义,19,对于上正规式R，存在一个NFA M，使得 L(M) = L(R) ，反之亦然。 Thopmson 方法： R= R= R

7、=a,正规式与有限自动机,S0,S1,S0,S1,S0,a,只引入初态S0和终态S1，他们之间无状态转换,2020/8/21,编译原理与技术讲义,20,正规式与有限自动机,R= R1 | R2 （1）,Si,fi,Sj,fj,R1对应的NFA,Si为初态，fi为终态,R2对应的NFA,Sj为初态，fj为终态,2020/8/21,编译原理与技术讲义,21,正规式与有限自动机,R= R1 | R2 （2）,S0,Si,fi,Sj,fj,引入新的初态S0和(S0,)=Si和(S0,)=Sj,2020/8/21,编译原理与技术讲义,22,正规式与有限自动机,R= R1 | R2 （3）,S0,f0,S

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

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

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

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

12、1 | R2,R1,R2,R = R1 R2,R1,R2,R = R1*,R1,R,R,R1,2020/8/21,编译原理与技术讲义,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,2020/8/21,编译原理与技术讲义,40,e.g.13 构造（0|1）*01的对应的FA简化版,1,4）,0,0 | 1,1,5）,0,0,1,2020/8/21,编译原理与技术讲义,41,NFA的确定化（转换到DFA）,子集构造法 对NFA进行模拟。NFA的转换表中每个条目是状态子集，而在

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

14、0) -closure(T) = 从状态集合T的每一个状态t出发，经过若干空转换（ 转换）所能到达的所有状态,2020/8/21,编译原理与技术讲义,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 ,2020/8/21,编译原理与技术讲义,44,初始时，DFA的状态集合Dstates中只有初态Sd0且未标记。 while ( Dstates中有未标记的状态 T ） do 标记

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

16、M。（续3）,2020/8/21,编译原理与技术讲义,49,e.g.14 确定化以下NFA M。（续4）,2020/8/21,编译原理与技术讲义,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不等价。,2020/8/21,编译原理与技术讲义,51,DFA的简化极小化,状态极小化将DFA的状态集合S划分成若干不相交状态子集，不同子集的状态间是可区别的，相同子集内的状态间等

17、价。取各个状态子集中的某一个状态为该子集代表，消除该子集中其他状态。 初始划分：终态集合 与 非终态集合 划分过程：如果s1,s2划分子集I，a ，有 (s1,a) 划分J ，(s2,a) 划分K ，则 划分I应进一步再划分成I1,I2 ,s1 I1,s2 I2,2020/8/21,编译原理与技术讲义,52,DFA的简化极小化,e.g.15 将下面的DFA M极小化 （1）,2020/8/21,编译原理与技术讲义,53,e.g.15 将下面的DFA M极小化 （2）,初始划分 I0=终态集合= 3，4，5，6 和I1=非终态集合= 0, 1, 2 ,考查 I1=0,1,2, 0a 1 , 1a

18、 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，此时划分过程结束！,2020/8/21,编译原理与技术讲义,54,e.g.15 将下面的DFA M极小化 （3）,最终划分 0 , 1 , 2 和 3，4，5，6

19、 /取状态3为代表,极小化的DFA如下：,2020/8/21,编译原理与技术讲义,55,词法分析器自动生成Lex,Lex 源程序,LEX,lex.yy.c yylex(),lex.yy.c yylex(),C编译器,可执行文件/a.out,可执行文件/a.out,输入串,单词记号,2020/8/21,编译原理与技术讲义,56,词法分析器自动生成Lex,Lex 源程序组成 定义段 规则段 用户程序段,2020/8/21,编译原理与技术讲义,57,词法分析器自动生成Lex,Lex 源程序组成定义段: % #include #include int count = 0; /* 任何形式的C声明 */ % 上述C声明、语句被拷贝到lex.yy.c文件中,2020/8/21,编译原理与技术讲义,58,词法分析器自动生成Lex,Lex 源程序组成 定义段: 正规定义 digit 0-9 number digit+,2020/8/21,编译原理与技术讲义,59,词法分析器自动生成Lex,Lex 源程序组成规则段 正规式 语义动作 number int n = atoi(yytext); printf(“%x”,