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

编译原理与技术词法分析 (2)9/4/20241《编译原理与技术》讲义有限自动机¡有限自动机（Finite Automata－FA）是种更一般化的状态转换图分为NFA和DFA¡词法分析器自动生成：正规式 NFA DFA 词法程序 非确定有限自动机确定的有限自动机9/4/20242《编译原理与技术》讲义非确定有限自动机－NFA¡NFA Mn 是一个五元组 Mn =(, S, S0,F,)，其中：•－有限字母表（输入符号集）•S－有限状态集•S0－非空初态集合，S0S•F－终态集合，F S• －状态转换函数，－状态转换函数，S x S x  * *  2 2S S9/4/20243《编译原理与技术》讲义确定的有限自动机－DFA¡DFA Md 是一个五元组 Md =(, S, S0,F,)，其中: , S, S0,F 同NFA中的定义，而定义如下：  ：S x S x    S S ，， 为一单值映射函数为一单值映射函数9/4/20244《编译原理与技术》讲义有限自动机的表示¡1）状态转换图开始状态一般状态终态s(s,a)=ttas(s,)=tt9/4/20245《编译原理与技术》讲义有限自动机的表示¡2）状态转换矩阵（表） *状态(集)ab…Si{Sj}…Sj……(Si,a) = {Sj}9/4/20246《编译原理与技术》讲义有限自动机的表示¡e.g.7 NFA Mn =(, S, S0,F,)，其中： = { 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} 9/4/20247《编译原理与技术》讲义有限自动机的表示¡e.g.7 中NFA的状态转换图如下：S0S3S10,1000,1110,1S2S49/4/20248《编译原理与技术》讲义有限自动机的表示¡e.g.7 中NFA的状态转换矩阵（表）如下： *状态(集)01S0{S0, S3 }{S0, S1 }S1∅{S2}S2{S2}{S2}S3{S4}∅S4{S4}{S4}9/4/20249《编译原理与技术》讲义有限自动机识别的语言¡e.g.8 下面FA识别（接受）的串是什么？S0S1S201¡FA识别（接受）串∈* , 如果存在一个从FA的初态到某个终态的（状态）转换路径，该路径上所有标记的字符依次连接为。

¡FA M 所识别的语言 L(M)L(M) = { | M 识别 ∈* }9/4/202410《编译原理与技术》讲义有限自动机识别的语言¡e.g.9 下面DFA M识别的语言L(M)是什么？S2S101S0S3111000S109/4/202411《编译原理与技术》讲义有限自动机识别的语言¡e.g.9 L(M) = {含偶数个0和偶数个1的0,1串}S2S101S0S3111000S2S1S0S3偶数个“0”与偶数个“1”的0,1串偶数个“0”与奇数个“1”的0,1串奇数个“0”与偶数个“1”的0,1串奇数个“0”与奇数个“1”的0,1串9/4/202412《编译原理与技术》讲义有限自动机识别的语言¡e.g.10 下面DFA M识别的语言L(M)是什么？S2S1S00101019/4/202413《编译原理与技术》讲义有限自动机识别的语言¡e.g.10 L(M) = { 能被“3”整除的二进制数(串) }S2S1S0010101S2S1S0能被3整除被3整除…余1被3整除…余29/4/202414《编译原理与技术》讲义有限自动机识别的语言¡e.g.10 L(M) = { 能被“3”整除的二进制数(串) }二进制串 10010 , 即十进制18的识别过程：S2S1S001010输入串 100109/4/202415《编译原理与技术》讲义比较 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)，即两者识别正规语言能力相同（等价）9/4/202416《编译原理与技术》讲义比较 DFA 和 NFA（2）DFANFA容易实现－当输入串结束时（或不存在相应状态转换）时，若当前状态为终态即为接受“已读入”的串，否则拒绝。

由于面临同样输入符号存在多重状态转换或存在转换的选择，实现较为复杂一般地，NFA接受串如果它在读完串后“能够能够””到达某终态识别相同正规集的DFA和NFA： DFA的规模（在状态数和状态转换上）一般比相应的NFA复杂（可以达到指数级）9/4/202417《编译原理与技术》讲义比较 DFA 和 NFA（3）¡e.g.11 识别正规式（0|1）*01的DFA和NFAS2S1S00011NFA :S2S1S0101100DFA :9/4/202418《编译原理与技术》讲义¡对于上正规式R，存在一个NFA M，使得L(M) = L(R) ，反之亦然Thopmson 方法：ü R= ü R=∅ü R=a∈正规式与有限自动机S0S1S0S1S0a只引入初态S0和终态S1，他们之间无状态转换9/4/202419《编译原理与技术》讲义正规式与有限自动机üR= R1 | R2 （1）SifiSjfjR1对应的NFA,Si为初态，fi为终态R2对应的NFA,Sj为初态，fj为终态9/4/202420《编译原理与技术》讲义正规式与有限自动机üR= R1 | R2 （2）S0SifiSjfj引入新的初态S0和(S0,)=Si和(S0,)=Sj9/4/202421《编译原理与技术》讲义正规式与有限自动机üR= R1 | R2 （3）S0f0SifiSjfj引入新的终态f0和(fi,)=f0和(fj,)=f09/4/202422《编译原理与技术》讲义正规式与有限自动机üR= R1 · R2 （1）SifiSjfjR1对应的NFA,Si为初态，fi为终态R2对应的NFA,Sj为初态，fj为终态9/4/202423《编译原理与技术》讲义正规式与有限自动机üR= R1 · R2 （2）SifiSjfjS0引入新的初态S0和(S0,)=Si9/4/202424《编译原理与技术》讲义正规式与有限自动机üR= R1 · R2 （3）SifiSjfjS0引入新的状态转换(fi,)=Sj9/4/202425《编译原理与技术》讲义正规式与有限自动机üR= R1 · R2 （4）SifiSjfjS0引入新的终态f0和状态转换(fj,)=f0f09/4/202426《编译原理与技术》讲义正规式与有限自动机üR= R1* （1） SifiR1对应的NFA,Si为初态，fi为终态9/4/202427《编译原理与技术》讲义正规式与有限自动机üR= R1* （2）SifiS0引入新的初态S0和(S0,)=Si9/4/202428《编译原理与技术》讲义正规式与有限自动机üR= R1* （3） SifiS0引入新的终态f0和状态转换(fi,)=f0f09/4/202429《编译原理与技术》讲义正规式与有限自动机üR= R1* （4） SifiS0引入新的状态转换(fi,)=Sif09/4/202430《编译原理与技术》讲义正规式与有限自动机üR= R1* （5）SifiS0引入新的状态转换(S0,)=f0f09/4/202431《编译原理与技术》讲义正规式与有限自动机üR= (R1) SifiR1对应的NFA，它也是(R1)对应的NFA9/4/202432《编译原理与技术》讲义¡e.g.12 构造（0|1）*01的对应的FA。

1）0• 0 1• 1 • 0 | 1 019/4/202433《编译原理与技术》讲义¡e.g.12 构造（0|1）*01的对应的FA2）• (0 | 1) 同 0 | 1• (0 | 1)*019/4/202434《编译原理与技术》讲义¡e.g.12 构造（0|1）*01的对应的FA3）• (0 | 1)* 00109/4/202435《编译原理与技术》讲义¡e.g.12 构造（0|1）*01的对应的FA4）• (0 | 1)* 0 100119/4/202436《编译原理与技术》讲义¡e.g.12 构造（0|1）*01的对应的FA5）R1R2|R301（）R4*R5R7·R9·R60R819/4/202437《编译原理与技术》讲义¡Thompson方法所构造的NFA的状态数和转换较多可以采用下面方法减少之：• R = R1 | R2R1R2• R = R1 R2R1R2• R = R1*R1• RRR19/4/202438《编译原理与技术》讲义¡e.g.13 构造（0|1）*01的对应的FA－简化版（0|1）* 0 11）(0|1)* 012）(0|1)*13）014）00 | 19/4/202439《编译原理与技术》讲义¡e.g.13 构造（0|1）*01的对应的FA－简化版14）00 | 115）0019/4/202440《编译原理与技术》讲义NFA的确定化（转换到DFA）¡子集构造法对NFA进行模拟。

NFA的转换表中每个条目是状态子集，而在DFA中则为单一的状态NFA到DFA的转换的一般想法是，让DFA中的每个状态代表NFA中的状态子集DFA用它的状态去记住NFA在读入每个输入符号后能到达的所有状态的集合，即在DFA在读了符号a1a2…an后到达代表NFA状态子集T的状态，而这个子集T是从NFA开始状态沿着标记有a1a2…an的路径所能到达的所有状态的集合9/4/202441《编译原理与技术》讲义NFA的确定化（转换到DFA）¡子集构造法ØDFA的“状态”Sd是NFA的非空状态子集，Sd2SØDFA的初态Sd0－包括原NFA初态S0及其经转换能到达的所有状态，即 Sd0 = { S0，u | S0 * u }＝  -closure({S0})  -closure(T) = { 从状态集合T的每一个状态t出发，经过若干空转换（ 转换）所能到达的所有状态}9/4/202442《编译原理与技术》讲义NFA的确定化（转换到DFA）¡子集构造法ØDFA状态转换函数d : Sd1 a Sd2 ， Sd2 = { t，u | s a t , s∈Sd1 ， t * u } =  -closure( { t | s a t , s∈Sd1 } )ØDFA的终态F－{ 含有原NFA终态的Sd }9/4/202443《编译原理与技术》讲义 初始时，DFA的状态集合Dstates中只有初态Sd0且未标记。

while ( Dstates中有未标记的状态 T ） do{ 标记 T； for 每个输入符号 a do { U =  -closure( { s | NFA状态转换函数(t,a)=s, tT} ) if U 不在 Dstates中 则将其加入Dstates且未加标记； 记下DFA状态转换函数d（T，a）＝ U ； } }9/4/202444《编译原理与技术》讲义NFA的确定化¡e.g.14 确定化以下NFA MX13ba2y6ba45aabb9/4/202445《编译原理与技术》讲义¡e.g.14 确定化以下NFA M续1） 状态Sdabd : Sd1 a Sd2d : Sd1 b Sd2Sd0={ x,3,1}{3,4,1}{3,5,1}{3,4,1}{3,2,4,1,6,y}{3,5,1}{3,5,1}{3,4,1}{3,2,5,1,6,y}{3,2,4,1,6,y}{3,2,4,6,1,y}{3,5,6,1,y}{3,2,5,1,6,y}{3,4,6,1,y}{3,2,5,6,1,y}9/4/202446《编译原理与技术》讲义¡e.g.14 确定化以下NFA M。

续2） 状态Sdabd : Sd1 a Sd2d : Sd1 b Sd2{3,5,6,1,y}{3,6,4,1,y}{3,2,6,5,1,y}{3,4,6,1,y}{3,2,6,4,1,y}{3,6,5,1,y}9/4/202447《编译原理与技术》讲义¡e.g.14 确定化以下NFA M续3）{ x,3,1}{ 3,4,1}{ 3,5,1}{3,2,4,1,6,y}{3,2,5,1,6,y}{3,5,6,1,y}{3,4,6,1,y}abaabababbabab9/4/202448《编译原理与技术》讲义¡e.g.14 确定化以下NFA M续4）0123456abaabababbabab9/4/202449《编译原理与技术》讲义DFA的简化－极小化¡DFA M 极小化 DFA M’，其中L(M)=L(M’)，且DFA M’是和DFA M等价（识别语言相同）的DFA中状态数最少的¡状态s1和s2是等价的，如果s1  f1 且 s2  f2，f1，f2∈F，∈* ¡状态t1和t2是可区分的，如果t1和t2不等价9/4/202450《编译原理与技术》讲义DFA的简化－极小化¡状态极小化－将DFA的状态集合S划分成若干不相交状态子集，不同子集的状态间是可区别的，相同子集内的状态间等价。

取各个状态子集中的某一个状态为该子集代表，消除该子集中其他状态¡初始划分：终态集合 与 非终态集合¡划分过程：如果s1,s2∈划分子集I，a ∈，有(s1,a) ∈ 划分J ，(s2,a) ∈ 划分K ，则 划分I应进一步再划分成I1,I2 ,s1∈ I1,s2∈ I29/4/202451《编译原理与技术》讲义DFA的简化－极小化¡e.g.15 将下面的DFA M极小化 （1）0123456abaabababbabab9/4/202452《编译原理与技术》讲义¡e.g.15 将下面的DFA M极小化 （2）•初始划分 I0=终态集合= { 3，4，5，6 } 和I1=非终态集合={ 0, 1, 2 }•考查 I1={0,1,2}, 0a 1 , 1a 3 , 2a 1 ，I1需再划分成I2={0,2}和I3={1}，此时划分为: I0, I2 和 I3 即{3,4,5,6}, {0,2} 和{1}•考查 I2, 0b 2 , 2b 4，I2需再划分成I4={0}和I5={2}，此时划分为: I0, I4, I5 和 I3 即{3,4,5,6}, {0}, {2} 和 {1}•考查I0={3,4,5,6}, 3a 3 , 4a 6 , 5a 6 , 6a 3 3b 5 , 4b 4 , 5b 4 , 6b 5 ，不需要划分I0，此时划分过程结束！9/4/202453《编译原理与技术》讲义¡e.g.15 将下面的DFA M极小化 （3）•最终划分 { 0 } , { 1 } , { 2 } 和 { 3，4，5，6 } //取状态3为代表•极小化的DFA如下： 30a12bababa, b9/4/202454《编译原理与技术》讲义词法分析器自动生成－LexLex 源程序LEXlex.yy.cyylex()lex.yy.cyylex()C编译器可执行文件/a.out可执行文件/a.out输入串单词记号9/4/202455《编译原理与技术》讲义词法分析器自动生成－Lex¡Lex 源程序组成定义段％％规则段％％用户程序段9/4/202456《编译原理与技术》讲义词法分析器自动生成－Lex¡Lex 源程序组成－定义段:①%{#include #include int count = 0;/* 任何形式的C声明 */%}上述上述C声明、语句被拷贝到声明、语句被拷贝到lex.yy.c文件中文件中9/4/202457《编译原理与技术》讲义词法分析器自动生成－Lex¡Lex 源程序组成定义段:②正规定义digit [0-9]number {digit}+ 9/4/202458《编译原理与技术》讲义词法分析器自动生成－Lex¡Lex 源程序组成－规则段ü正规式{ 语义动作 }{number}{ int n = atoi(yytext); printf(“%x”, n); /* 语义动作－合法的C语句 */}ü语义动作语义动作(C 语句语句)被拷贝到被拷贝到yylex()中中ü当正规式匹配时其相应的语义动作即被执行当正规式匹配时其相应的语义动作即被执行9/4/202459《编译原理与技术》讲义词法分析器自动生成－Lex¡Lex 源程序组成用户程序段－包含用户自定义的C函数，此段可空。

如：main() int yywrap(){ yylex(); {return 0; return 1;} }9/4/202460《编译原理与技术》讲义%{#include #include int count = 0;/*任何形式的C声明 */%}digit [0-9]number {digit}+%%{number} { int n = atoi(yytext); printf(“%x”, n); /*语义动作－合法的C语句 */ }%%main() { yylex(); return 0; }int yywrap() { return 1; }e.g.16 一个lex例子程序9/4/202461《编译原理与技术》讲义Lex 中元字符约定（1）名称含义a字符a“a”字符a,无论a是否为元字符 \n \\ \t \b \”转义符\，用来表示回车，\,tab制表,退格，引号”a* a的零次或多次重复(零闭包)a+ a的一次或多次重复(正闭包)a? a的零次或一次（可选）[abc]同正规式 a | b | c[a-d]表示范围，a,b,c,d中的一个9/4/202462《编译原理与技术》讲义Lex 中元字符约定 （2）名称含义[a-d]同 [abcd][^ab]除了a或b外的任一字符.除了 \n 外的任一字符{ xxx }名字xxx表示正规式（正规定义）|“或” 运算符( ) < >^a a$a出现在行首（行尾）a / ba后面跟着b9/4/202463《编译原理与技术》讲义Lex 内部名字名称含义lex.yy.cLex的输出文件名yylex()Lex词法扫描函数yytext yyleng跟规则匹配的字符串、串长yyinLex输入文件变量(缺省stdin)yyoutLex输出文件变量(缺省stdout)inputLex缓冲的输入例程yywrap()遇到输入（文件）结束符EOF时Lex调用。

通常由用户自定义为{return 1;}以表示正常返回ECHOLex缺省动作将yytext打印到yyout9/4/202464《编译原理与技术》讲义词法分析器自动生成－Lex¡Lex中二义性规则的处理ü选择最长规则进行匹配，如 > 和 >=ü输入串与两个（或两个以上）规则匹配时，选择在规则段中位置靠前（首先出现）的规则进行匹配如，关键字规则靠前而（普通）标识符规则在后9/4/202465《编译原理与技术》讲义。