编译原理 二 词法分析PPT课件

1、.,1,第二章 词法分析,词法分析概述 词法分析程序的手工实现 正规表达式与有限自动机 词法分析程序的自动生成,.,2,2.1 词法分析器设计方法,词法分析是编译过程中的第一个阶段，其主要任务是：从左到右逐个字符地对源程序进行扫描，产生单词符号，通常用记号（token）表示。最后生成并输出一个单词符号序列，或直接将单词符号作为语法分析模块的输入。,源程序 （字符串形式）,输出单词序列 （记号形式）,词法分析,语法分析,token,token,getNextToken,.,3,问题：,1、什么是记号（单词符号）？ 2、记号如何描述？ 3、记号如何识别？,词法分析的其他作用： 1、当词法分析程序发

2、现标识符类型的单词时，要将其添加到符号表中； 2、过滤注释和空白等字符； 3、记录换行符的个数，为每个出错消息赋予一个行号，从而使编译器生成的错误信息与源程序的位置联系起来。,.,4,1、记号（token）及其描述,记号（单词符号）是程序语言的基本语法单位。 一般分为下面7种： 关键字（基本字） 标识符：常量、数组、变量、过程或函数名等。 常数：各种类型的常数 。 运算符：如+、-、*、/、等。 分界符：如，、；、（、） 等。 空白符：如空格符、换行符等。 注释,.,5,注意：一种语言的单词如何分 类、怎样编码， 主要取决于技术实现上的方便。,.,6,2、记号的识别,在词法分析中，可以用状态转

3、换图来识别单词。,例如,状态转换图是有限的有 向图，结点表示状 态，用圆圈表示；结 点之间可以用有向边 连接，有向边上可标 记字符。,.,7,q1,q2,q3,q0,例1：字符串100101的识别的过程,.,8,q2,q3,q0,q1,例1：字符串100101的识别的过程,.,9,q2,q0,q1,q3,例1：字符串100101的识别的过程,.,10,q2,q3,q0,q1,例1：字符串100101的识别的过程,.,11,q1,q2,q3,q0,例1：字符串100101的识别的过程,.,12,q1,q3,q0,q2,例1：字符串100101的识别的过程,.,13,q1,q0,q2,q3,例1：

4、字符串100101的识别的过程,.,14,q1,q2,q3,q0,例2：字符串00识别的过程,.,15,q1,q3,q0,q2,例2：字符串00识别的过程,.,16,q1,q2,q3,q0,例2：字符串00识别的过程,.,17,q1,q2,q3,q0,例3：字符串10101识别的过程,.,18,q2,q3,q0,q1,例3：字符串10101识别的过程,.,19,q2,q0,q1,q3,例3：字符串10101识别的过程,.,20,q1,q3,q0,q2,例3：字符串10101识别的过程,.,21,q1,q2,q3,q0,例3：字符串10101识别的过程,.,22,q2,q3,q0,q1,例3：字

5、符串10101识别的过程,.,23,状态转换图举例,例1：字符串必须以空格开始和结束，中间可以有0个或任意多个由az组成的字符串。,.,24,例2：Pascal语言中关系运算符识别的状态转换图。,.,25,例3：标识符识别的状态转换图。,.,26,例4：无符号整数的状态转换图。,.,27,2.2 一个简单的词法分析器示例,对于不含回路的分支状态，可以对应一个switch()语句或一组if-else语句。 对于含回路的状态，可以对应一条while语句。 终态一般对应一个return()语句。对于词法分析器，一般指返回给语法分析器。 以一个C语言子集为例。,单词符号,种别编码,助记符,内码值,wh

6、ile,if,else,switch,case,标识符,常数,+,-,*,=,=,=,;,1,2,3,4,5,6,7,8,9,10,11,11,11,12,13,while,if,else,switch,case,id,num,+,-,*,relop,relop,relop,=,;,-,-,-,-,-,num在符号表中的位置,-,-,-,LE,LT,EQ,-,-,id在符号表中的位置,2,0,1,字母,字母或数字,其它,3,4,5,6,数字,数字,其它,+,-,7,*,9,10,0 THEN 返回 (key,null) buildlist(token); 返回 (id，id的符号表入口指针)

7、= : getchar(); IF character等于= THEN 返回 (relop，EQ) retract(); 返回 (= ，null),+ : 返回 (+,null) - : 返回 (-,null) * : 返回 (*,null) : getchar(); IF character等于= THEN 返回 (relop，LE) retract(); 返回 (relop，LT) ; : 返回 (;,null) 其它 : retract(); error(); END OF CASE,.,37,需要进一步考虑的问题 1、缓冲区预处理，超前搜索 2、关键字的处理，符号表的实现 3、符号表的

8、查找效率，算法的优化实现 4、词法错误处理,.,38,源程序的输入,在内存开辟缓冲区，将程序文本放进该缓冲区 预处理：删除无用字符等 词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。,起始指针,搜索指针,.,39,超前搜索,词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。,.,40,关键字的识别与查表算法,对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符

9、。 查找算法： 线性查找 折半查找 Hash函数,.,41,出错处理,对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。,.,42,正规表达式是一种适合描述符号串的表示法，可由它定义正规集。 正规集即为正规式所描述的串的集合。一般用L()表示。 采用正规表达式的原因： 词法规则简单，容易被理解； 从它容易构造高效识别程序； 可由正规表达式自动构造词法分析程序； 可用于其他各种信息流的处理。,2.3 正规表达式与有限自动机简介,.,43,1、正规表达式的定义,设为字母表，则的正规表达式按照下列规则递归地定义： 基本：(1) 都是上的正规式，表示为L()=；

10、(2)是上的正规式，表示为L()=； (3) 对于任何a ，a是上的一个正规式，表示为L(a)=a ； 归纳：(4) （递归定义）若r和s都是上的正规式，则 (r)是上的正规式，表示集合L( ( r ) )=L( r ) ； rs是上的正规式，表示集合L( r|s )=L( r ) L( s )； rs是上的正规式，表示集合L( rs )=L( r ) L( s )； r*是上的正规式，表示集合L(r* )=(L( r ) )*。,.,44,运算优先级 *高于“连接” “连接” 高于 | ( )指定优先关系,.,45,例： 令=a，b， 上的正规式和相应的正规集的例子有： 正规式 正规集 a

11、a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,aa, 任意个a的串,.,46,(ab) 表示正规集 ,a,b,aa,ab 所有由a和b组成的串 (ab)(aabb)(ab) 表示正规集上所有含有两个相继的a或两个相继的b组成的串,.,47,思考： 1、令=a，b，设R=a(a|b)*是上的正规式，试求其表示的正规集。 2、若=a，b， 则字符串集合S=anban|n0可以用正规式描述吗？,.,48,2、程序设计语言中的正规式实例,令=letter,digit，则上的正规式 r=letter(letter|digit)* 可以用来表示标识符。 令=d,.,e,

12、+,-，则上的正规式 r=d*(.dd*|)(e(+|-|)dd*|) 可以用来表示无符号浮点数。其中d表示digit, 即0-9数字。,.,49,3、正规表达式的等价,如果正规表达式r与s表示的正规集相同，即描述的字符串的集合相同，则称它们是等价的。记为: r=s,.,50,例：判断下述正规式之间是否等价。 1）(a|b)* 与 a*|b* 2）(ab)* 与 a*b* 3）(a|b)* 与 (a*b*)*,答：1）、2）不等价，3）等价,.,51,4、正规表达式的性质,设e、e1、e2、e3均为正规表达式，则 e|= |e=e e= e= (零正规表达式) e=e=e (同一律，单位正规表

13、达式) e1|e2=e2|e1 (交换律) e1|(e2|e3)= (e1|e2)|e3 e1(e2e3)=(e1e2)e3 (结合律) e1(e2|e3)= e1e2|e1e3 (e1|e2)e3= e1e3|e2e3 (分配律),2.1 完成下列选择题： (1) 词法分析器的输出结果是 。 a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。 a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等,(3) DFA M(见图2-

14、1)接受的字集为 。 a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d,.,54,状态转换图 确定有限状态自动机（DFA） 非确定有限状态自动机（NFA） NFA确定化为DFA DFA的化简,有限自动机（FA）,.,55,有限自动机是依据某些输入而改变状态的 机器或程序。可以用状态转换图来表示。 有限自动机是有向图这种通用结构的一个 实例，在动态数据结构和高级搜索方面有 许多应用。,序,.,56,1、状态转换图,有向图，结点表示状态，用圆圈表示； 结点

15、之间可以用有向边连接，有向边上 标记影响状态改变的可能输入的字符；,.,57,2、确定的有限状态自动机,一个确定的有限自动机（DFA）D是一个五元组 D=（K，M，S，Z），其中 K：有限非空的状态集合； ：有穷非空的输入符号字母表； M：转换函数，是在KK上的映像，即: 如M（ki，a）=kj，（kiK，kjK） 意味着，当前状态为ki，输入符为a时，将转换为下一个状 态kj，我们把kj称作ki的一个后继状态； S: SK是唯一的一个初态； Z: Z K是非空的终态集合。,.,58,从状态转换图构造DFA,例：从下面状态图构造DFA。,DFA D=（S，Z，A，B，a，b，M，S，Z）， 其

16、中M定义为： M（S，a）=A M（S，b）=B M（A，a）=Z M（A，b）=B M（B，a）=A M（B，b）=Z M（Z，a）=Z,.,59,例：构造一个识别语言(a|b)*ab 的有限自动机。,从正规表达式构造有限自动机,状 态,.,60,非确定有限状态自动机,一个非确定的有限自动机（NFA）D是一个五元组：N=（K，M，S，Z）其中 K：有限非空的状态集合； ：有穷非空的输入字母表； M：转换函数，是在K到K的子集所组成集合的映像， M(Ki, a)=K1,K2,.Kn S: SK是非空的初态集合； Z: ZK是非空的终态集合.,.,61,DFA与NFA的区别,NFA还允许在状态转

17、换图中输出边上标记为。,.,62,举例,与右图所示对应的有一个NFA ，N=(S,A,B,Z,a,b,M,S,Z) 其中M： M(S,a)=A M(S,b)=B M(A,a)=Z M(A,b)=B M(B,a)=A,B M(B,b)=Z M(Z,a)=A,Z,a,b,a,a,a,a,状态不唯一！,对于输入字符串babbabb，运行该NFA,a,.,64,2.4 正规表达式到有限自动机的构造,A为有限状态自动机，e为正规表达式，则存在 L(A)=L(e)，即正规表达式与有限自动机之间具有等价性。,任何两个有限自动机M和M，若它们识别的语言相同(L(M)=L(M)，则称M和M等价。,.,65,一、

18、由正规表达式构造等价的NFA M,1、由正规表达式R表示成如图所示的拓广转换图。,2、对正规式采用如下规则构造对应的NFA M。,3、逐步运用上述3个规则不断在1、的拓广转换图中增加新结点进行分解，直到每条有向边上仅标识有中的一个字母或为止，则NFA M构造完成。,.,66,例：对给定正规式b*(d|ad)(b|ab)+， 构造其NFA M。,举例,b*(d|ad)(b|ab)+改写为 b*(d|ad)(b|ab) (b|ab)*,.,67,b,d,b,a,d,a,b,b,a,b,.,68,二、NFA的确定化,1、状态子集的_闭包,若FA M有状态子集I，则其_闭包即_closure(I)为：

19、 （1）若Si I，则Si _closure(I)； （2）若Si I，则对从Si出发经过通路所能到达的任何状态Sj，都有Sj _closure(I)。,.,69,二、NFA的确定化,2、定义,对FA M的一个状态子集I，若a是中的一个字符，则给出定义： Ia=_closure(J)； 其中，J是所有那些可以从I中的某一状态出发经过有向边a而能到达的状态集。,.,70,例：已知一状态转换图如下所示，假定 I=_closure1，试求从状态I出发经过一条有向边a而能到达的: （1）状态集J； （2）_closure(J)。,1,5,6,2,3,8,4,7,a,a,a,J=5,3,4 _closu

20、re(J)=5,3,4, 6,2,8,7,.,71,二、NFA的确定化,3、用子集构造法将NFA确定化为DFA （1）构造一张转换表，其第一列为状态子集I，对不同的a(a)在表中单设一列Ia。 （2）表的第一行第一列其状态子集I为_closure(I0)，其中I0为初始状态。 （3）根据第一列中的I为每一个a求Ia并记入对应的Ia列中，如果此列不同于第一列已存在的所有状态子集I，则将其顺序列入空行中的第一列。 （4）重复步骤（3）直至每个I及a均已求得Ia，并且无新的状态子集加入第一列时为止；此过程可在有限步后终止。 （5）重新命名第一列的每一个状态子集，形成新的状态转换表，即得到等价的DFA

21、。,.,72,例：假设有一个NFA M如下，试用子集法对其进行确定化，形成等价的DFA M。,状态,Ia,Ib,I0=_closure(0) =0, 1, 2, 4, 7,_closure(I0a)= _closure(3,8)= 1, 2, 3, 4, 6, 7, 8,I1 =,_closure(I0b)= _closure(5)= 1, 2, 4, 5, 6, 7,I2 =,状态,Ia,Ib,I0=0, 1, 2, 4, 7,_closure(I0a)= _closure(3,8)= 1, 2, 3, 4, 6, 7, 8,I1 =,_closure(I0b)= _closure(5)=

22、1, 2, 4, 5, 6, 7,I2 =,I1 =1, 2, 3, 4, 6, 7, 8,_closure(3,8)= 1, 2, 3, 4, 6, 7, 8,I1 =,_closure(5,9)= 1, 2, 4, 5, 6, 7,9,I3 =,I2 =1, 2, 4, 5, 6, 7,I3 =1, 2, 4, 5, 6, 7,9,_closure(3,8)= 1, 2, 3, 4, 6, 7, 8,I1 =,_closure(5)= 1, 2, 4, 5, 6, 7,I2 =,_closure(3,8)= 1, 2, 3, 4, 6, 7, 8,I1 =,_closure(5)= 1,

23、2, 4, 5, 6, 7,I2 =,状态,识别语言 (a|b)*ab 的自动机,I1,I3,开始,a,I0,a,b,b,a,b,I2,b,a,将其确定化后 与上图比较, 两者识别的 字符串集合 相同吗?,.,77,练习,将右图所示的NFA 用子集构 造法确定化为DFA。,a,b,a,a,.,78,a,b,a,a,.,79,S,B,AB,ABZ,A,Z,BZ,AZ,b,b,b,b,b,b,b,a,a,a,a,a,a,a,a,开始状态:S,终止状态:Z,AZ,BZ,ABZ,根据上面状态转换矩阵，可以得到确定化后DFA的映像函数，根据该映像可以画出它的状态转换图如下：,.,80,三、DFA的化简,

24、2、化简(最小化)算法基本思想划分法 将DFA M 中的状态划分为互不相交的子集，每个子集内部的状态都等价；而在不同子集间的状态均不等价。,1、化简的前提条件：两个DFA接受的语言必须相同。,3、状态的等价,.,81,4、化简算法 （1）把状态集S划分为终态集和非终态集： 0I01,I02，I01属于非终态集,I02属于终态集。 因为终态能识别，而非终态不能，所以它们是可区别的； （2）假定经过k次划分后： kIk0,Ik1Ikm。这m个子集内部还是否可以划分？ 任取一个子集Iki=s1,s2,sk,若存在某读入字符a，使f(Iki,a)的结果不是全部包含在k的某个子集中，则说明Iki中有不等

25、价的状态，还要进一步划分。 对k中所有子集都进行测试，以完成一次划分。,三、DFA的化简,.,82,（3）重复步骤（2），直到子集个数不再增加为止。 （4）对每个子集任取一状态为代表。若该子集包含原有的初态，则相应代表状态就是最小化后M的初态；同样，若该子集包含原有的终态，则相应代表状态就是最小化后M的终态。,.,83,例：设有一DFA 的状态转换图如下，试化简之。,0,1,2,3,5,4,6,a,a,a,a,a,a,a,b,b,b,b,b,b,b,.,84,解： 把M的状态分为两组：终态集，非终态集 00,1,2,3,4,5,6 考察非终态集： f(0,1,2,a)=1,3 不属于0的任何一

26、个子集，所以 0，1，2要分开 得到：11，0,2，3,4,5,6 再看：f(0,2,a)=1属于1的子集 f(0,2,b)=2,5不属于1的任何子集，所以0,2要分开 得到： 2=1，0，2，3,4,5,6,.,85,解： （续） 考察终态集： f(3,4,5,6,a)=3,6包含于2的子集3,4,5,6 f(3,4,5,6,b)=4,5包含于2的子集3,4,5,6 所以3,4,5,6不可再划分 整个划分为4个组： 21,0,2,3,4,5,6 令状态3代表3,4,5,6，把原来到达状态4，5，6的弧都导入3，并删除4，5，6。得：,即为化简了的DFA。,a,b,.,87,由正规式构造有限自

27、动机小结,正规式到NFA（Thompson构造法） NFA到DFA（子集构造法） DFA到最小DFA（Hopcroft算法）,.,88,练习： 有正规式(a|b)*(aa|bb)(a|b)*，试为其构 造最简的DFA。,.,89,1、由正规表达式构造NFA,.,90,2、利用子集构造法将NFA确定化为DFA,状态,Ia,Ib, x,3,1,3,4,1,3,5,1,3,4,1,3,5,1,状态,Ia,Ib, x,3,1,3,4,1,3,5,1,3,4,1,3,5,1,3,2,4,1,6,y,3,5,1,3,2,4,1,6,y,3,4,1,3,2,5,1,6,y,3,2,5,1,6,y,3,2,4

28、,6,1,y,3,5,6,1,y,状态,Ia,Ib, x,3,1,3,4,1,3,5,1,3,4,1,3,5,1,3,2,4,1,6,y,3,5,1,3,2,4,1,6,y,3,4,1,3,2,5,1,6,y,3,2,5,1,6,y,3,2,4,6,1,y,3,5,6,1,y,3,5,6,1,y,3,4,6,1,y,3,2,5,6,1,y,3,4,6,1,y,3,6,4,1,y,3,2,6,5,1,y,3,2,6,4,1,y,3,6,5,1,y,.,96,即为化简了的DFA。,采用划分法可以使其简化为:,3、DFA的化简,.,97,2.5 词法分析器的自动生成,用手工方式，即根据识别语言单词的

29、状态转换图，使用某种高级语言直接编写词法分析程序。 利用自动生成工具LEX自动生成词法分析程序。,.,98,LEX的实现过程,Lex源程序,Lex.yy.c,Lex编译器,词法分析器L,Lex.yy.c,C编译器,Token序列,词法分析器L,输入流,.,99,Lex的源程序结构,声明部分 (正规定义式) % 转换规则 (识别规则) % 辅助过程 （用户子程序）,% 常量定义 % 正规定义,.,100,1、正规定义式 letterA|B|C|Z|a|b|c|z digit0|1|2|9 identifierletter(letter|digit)* integerdigit(digit)* 2、识别规则 正规式 动作描述 token1 action1 token2 action2 tokenn actionn,/*声明部分*/ % #include #include #include #define WHILE 1 #define DO 2 #define IF 3 #define ELSE 4 #define SWITCH 5 #define ID 6 #define NUM 7 #define PLUS 8 #define SUB 9 #define STAR 10 #define RELOP 11 #define EQ 12 #define SEMI 13 #d