编译原理与技术.ppt

《编译原理与技术.ppt》由会员分享，可在线阅读，更多相关《编译原理与技术.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、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 12/28/20227编译原理与技术讲义有限自动机的表示e.g.7 中NFA的状态转换图如下：S0S3S10,1000,1110,1S2S412/28/20228编译原理与技术讲义有限自动机的表示e.g.7 中NFA的状态转换矩阵（表）如下：*状态(集)01S0S0,S3 S0,S1 S1S2S2S2S2S3S4S4S4S412/28/20229编译原理与技术讲义有限自动机识别的语言e.g.8 下面FA识别（接受）的串是什么

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

5、1串奇数个“0”与奇数个“1”的0,1串12/28/202212编译原理与技术讲义有限自动机识别的语言e.g.10 下面DFA M识别的语言L(M)是什么？S2S1S001010112/28/202213编译原理与技术讲义有限自动机识别的语言e.g.10 L(M)=能被“3”整除的二进制数(串)S2S1S0010101S2S1S0能被3整除被3整除余1被3整除余212/28/202214编译原理与技术讲义有限自动机识别的语言e.g.10 L(M)=能被“3”整除的二进制数(串)二进制串 10010,即十进制18的识别过程：S2S1S001010输入串 1001012/28/202215编译原理

6、与技术讲义比较 DFA 和 NFA（1）DFANFA：S x S x S S ：S x S x 2 2S S 没有 转换有 转换对*，DFA的“识别”路径唯一且完全由确定对*的“识别”路径可能存在多条不同的路径对于正规式R，均有DFA Md和NFA Mn，使得L(Md)=L(Mn)=L(R)，即两者识别正规语言能力相同（等价）12/28/202216编译原理与技术讲义比较 DFA 和 NFA（2）DFANFA容易实现当输入串结束时（或不存在相应状态转换）时，若当前状态为终态即为接受“已读入”的串，否则拒绝。由于面临同样输入符号存在多重状态转换或存在转换的选择，实现较为复杂。一般地，NFA接受串

7、如果它在读完串后“能够能够”到达某终态。识别相同正规集的DFA和NFA：DFA的规模（在状态数和状态转换上）一般比相应的NFA复杂（可以达到指数级）12/28/202217编译原理与技术讲义比较 DFA 和 NFA（3）e.g.11 识别正规式（0|1）*01的DFA和NFAS2S1S00011NFA:S2S1S0101100DFA:12/28/202218编译原理与技术讲义对于上正规式R，存在一个NFA M，使得L(M)=L(R)，反之亦然。Thopmson 方法：R=R=R=a正规式与有限自动机S0S1S0S1S0a只引入初态S0和终态S1，他们之间无状态转换12/28/202219编译原

8、理与技术讲义正规式与有限自动机R=R1|R2 （1）SifiSjfjR1对应的NFA,Si为初态，fi为终态R2对应的NFA,Sj为初态，fj为终态12/28/202220编译原理与技术讲义正规式与有限自动机R=R1|R2 （2）S0SifiSjfj引入新的初态S0和(S0,)=Si和(S0,)=Sj12/28/202221编译原理与技术讲义正规式与有限自动机R=R1|R2（3）S0f0SifiSjfj引入新的终态f0和(fi,)=f0和(fj,)=f012/28/202222编译原理与技术讲义正规式与有限自动机R=R1 R2（1）SifiSjfjR1对应的NFA,Si为初态，fi为终态R2对

9、应的NFA,Sj为初态，fj为终态12/28/202223编译原理与技术讲义正规式与有限自动机R=R1 R2（2）SifiSjfjS0引入新的初态S0和(S0,)=Si12/28/202224编译原理与技术讲义正规式与有限自动机R=R1 R2（3）SifiSjfjS0引入新的状态转换(fi,)=Sj12/28/202225编译原理与技术讲义正规式与有限自动机R=R1 R2（4）SifiSjfjS0引入新的终态f0和状态转换(fj,)=f0f012/28/202226编译原理与技术讲义正规式与有限自动机R=R1*（1）SifiR1对应的NFA,Si为初态，fi为终态12/28/202227编译原

10、理与技术讲义正规式与有限自动机R=R1*（2）SifiS0引入新的初态S0和(S0,)=Si12/28/202228编译原理与技术讲义正规式与有限自动机R=R1*（3）SifiS0引入新的终态f0和状态转换(fi,)=f0f012/28/202229编译原理与技术讲义正规式与有限自动机R=R1*（4）SifiS0引入新的状态转换(fi,)=Sif012/28/202230编译原理与技术讲义正规式与有限自动机R=R1*（5）SifiS0引入新的状态转换(S0,)=f0f012/28/202231编译原理与技术讲义正规式与有限自动机R=(R1)SifiR1对应的NFA，它也是(R1)对应的NFA1

11、2/28/202232编译原理与技术讲义e.g.12 构造（0|1）*01的对应的FA。（1）0 0 1 1 0|1 0112/28/202233编译原理与技术讲义e.g.12 构造（0|1）*01的对应的FA。（2）(0|1)同 0|1(0|1)*0112/28/202234编译原理与技术讲义e.g.12 构造（0|1）*01的对应的FA。（3）(0|1)*001012/28/202235编译原理与技术讲义e.g.12 构造（0|1）*01的对应的FA。（4）(0|1)*0 1001112/28/202236编译原理与技术讲义e.g.12 构造（0|1）*01的对应的FA。（5）R1R2|R

12、301（）R4*R5R7R9R60R8112/28/202237编译原理与技术讲义Thompson方法所构造的NFA的状态数和转换较多。可以采用下面方法减少之：R=R1|R2R1R2 R=R1 R2R1R2 R=R1*R1 RRR112/28/202238编译原理与技术讲义e.g.13 构造（0|1）*01的对应的FA简化版（0|1）*0 11）(0|1)*012）(0|1)*13）014）00|112/28/202239编译原理与技术讲义e.g.13 构造（0|1）*01的对应的FA简化版14）00|115）00112/28/202240编译原理与技术讲义NFA的确定化（转换到DFA）子集构

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

14、0，u|S0*u -closure(S0)-closure(T)=从状态集合T的每一个状态t出发，经过若干空转换（转换）所能到达的所有状态12/28/202242编译原理与技术讲义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 12/28/202243编译原理与技术讲义 初始时，DFA的状态集合Dstates中只有初态Sd0且未标记。while(Dstates中有未标记的状态 T）do 标记 T；for 每个输入符号 a do

15、U=-closure(s|NFA状态转换函数(t,a)=s,tT)if U 不在 Dstates中 则将其加入Dstates且未加标记；记下DFA状态转换函数d（T，a）U；12/28/202244编译原理与技术讲义NFA的确定化e.g.14 确定化以下NFA M。X13ba2y6ba45aabb12/28/202245编译原理与技术讲义e.g.14 确定化以下NFA M。（续1）状态Sdabd:Sd1 a Sd2d:Sd1 b Sd2Sd0=x,3,13,4,13,5,13,4,13,2,4,1,6,y3,5,13,5,13,4,13,2,5,1,6,y3,2,4,1,6,y3,2,4,6,

16、1,y3,5,6,1,y3,2,5,1,6,y3,4,6,1,y3,2,5,6,1,y12/28/202246编译原理与技术讲义e.g.14 确定化以下NFA M。（续2）状态Sdabd:Sd1 a Sd2d:Sd1 b Sd23,5,6,1,y3,6,4,1,y3,2,6,5,1,y3,4,6,1,y3,2,6,4,1,y3,6,5,1,y12/28/202247编译原理与技术讲义e.g.14 确定化以下NFA M。（续3）x,3,1 3,4,1 3,5,13,2,4,1,6,y3,2,5,1,6,y3,5,6,1,y3,4,6,1,yabaabababbabab12/28/202248编译

17、原理与技术讲义e.g.14 确定化以下NFA M。（续4）0123456abaabababbabab12/28/202249编译原理与技术讲义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不等价。12/28/202250编译原理与技术讲义DFA的简化极小化状态极小化将DFA的状态集合S划分成若干不相交状态子集，不同子集的状态间是可区别的，相同子集内的状态间等价。取各个状态子集中的某一个

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

19、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，此时划分过程结束！12/28/202253编译原理与技术讲义e.g.15 将下面的DFA M极小化 （3）最终划分 0 ,1 ,2 和 3，4，5，6 /取状态3为代表极小化的DFA如下：30a12bababa,b12/28/202254编译原理与技术讲义

20、词法分析器自动生成LexLex 源程序LEXlex.yy.cyylex()lex.yy.cyylex()C编译器可执行文件/a.out可执行文件/a.out输入串单词记号12/28/202255编译原理与技术讲义词法分析器自动生成LexLex 源程序组成定义段规则段用户程序段12/28/202256编译原理与技术讲义词法分析器自动生成LexLex 源程序组成定义段:%#include#include int count=0;/*任何形式的C声明 */%上述上述C声明、语句被拷贝到声明、语句被拷贝到lex.yy.c文件中文件中12/28/202257编译原理与技术讲义词法分析器自动生成LexLe

21、x 源程序组成定义段:正规定义digit 0-9number digit+12/28/202258编译原理与技术讲义词法分析器自动生成LexLex 源程序组成规则段正规式 语义动作 number int n=atoi(yytext);printf(“%x”,n);/*语义动作合法的C语句*/语义动作语义动作(C 语句语句)被拷贝到被拷贝到yylex()中中当正规式匹配时其相应的语义动作即被执行当正规式匹配时其相应的语义动作即被执行12/28/202259编译原理与技术讲义词法分析器自动生成LexLex 源程序组成用户程序段包含用户自定义的C函数，此段可空。如：main()int yywrap(

22、)yylex();return 0;return 1;12/28/202260编译原理与技术讲义%#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例子程序12/28/202261编译原理与技术讲义Lex 中元字符约定（1）名称含义a字符a“a”字符a,无论a是否为元字符 n t b ”转义符，

23、用来表示回车，,tab制表,退格，引号”a*a的零次或多次重复(零闭包)a+a的一次或多次重复(正闭包)a?a的零次或一次（可选）abc同正规式 a|b|ca-d表示范围，a,b,c,d中的一个12/28/202262编译原理与技术讲义Lex 中元字符约定（2）名称含义a-d同 abcdab除了a或b外的任一字符.除了 n 外的任一字符 xxx 名字xxx表示正规式（正规定义）|“或”运算符()a a$a出现在行首（行尾）a/ba后面跟着b12/28/202263编译原理与技术讲义Lex 内部名字名称含义lex.yy.cLex的输出文件名yylex()Lex词法扫描函数yytext yylen

24、g跟规则匹配的字符串、串长yyinLex输入文件变量(缺省stdin)yyoutLex输出文件变量(缺省stdout)inputLex缓冲的输入例程yywrap()遇到输入（文件）结束符EOF时Lex调用。通常由用户自定义为return 1;以表示正常返回ECHOLex缺省动作将yytext打印到yyout12/28/202264编译原理与技术讲义词法分析器自动生成LexLex中二义性规则的处理选择最长规则进行匹配，如 和=输入串与两个（或两个以上）规则匹配时，选择在规则段中位置靠前（首先出现）的规则进行匹配。如，关键字规则靠前而（普通）标识符规则在后。12/28/202265编译原理与技术讲义