编译原理 第二章 词法分析ppt课件

.,1,第二章词法分析,词法分析概述词法分析程序的手工实现正规表达式与有限自动机词法分析程序的自动生成,.,2,2.1词法分析器设计方法,词法分析是编译过程中的第一个阶段，其主要任务是：从左到右逐个字符地对源程序进行扫描，产生单词符号，通常用记号（token）表示。最后生成并输出一个单词符号序列，或直接将单词符号作为语法分析模块的输入。,源程序（字符串形式）,输出单词序列（记号形式）,词法分析,语法分析,token,token,getNextToken,.,3,问题：,1、什么是记号（单词符号）？2、记号如何描述？3、记号如何识别？,词法分析的其他作用：1、当词法分析程序发现标识符类型的单词时，要将其添加到符号表中；2、过滤注释和空白等字符；3、记录换行符的个数，为每个出错消息赋予一个行号，从而使编译器生成的错误信息与源程序的位置联系起来。,.,4,1、记号（token）及其描述,记号（单词符号）是程序语言的基本语法单位。一般分为下面7种：关键字（基本字）标识符：常量、数组、变量、过程或函数名等。常数：各种类型的常数。运算符：如+、-、*、/、等。分界符：如，、；、（、）等。空白符：如空格符、换行符等。注释,.,5,注意：一种语言的单词如何分类、怎样编码，主要取决于技术实现上的方便。,.,6,2、记号的识别,在词法分析中，可以用状态转换图来识别单词。,例如,状态转换图是有限的有向图，结点表示状态，用圆圈表示；结点之间可以用有向边连接，有向边上可标记字符。,.,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：字符串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：字符串10101识别的过程,.,23,状态转换图举例,例1：字符串必须以空格开始和结束，中间可以有0个或任意多个由az组成的字符串。,.,24,例2：Pascal语言中关系运算符识别的状态转换图。,.,25,例3：标识符识别的状态转换图。,.,26,例4：无符号整数的状态转换图。,.,27,2.2一个简单的词法分析器示例,对于不含回路的分支状态，可以对应一个switch()语句或一组if-else语句。对于含回路的状态，可以对应一条while语句。终态一般对应一个return()语句。对于词法分析器，一般指返回给语法分析器。以一个C语言子集为例。,单词符号,种别编码,助记符,内码值,while,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,0THEN返回(key,null)buildlist(token);返回(id，id的符号表入口指针)=:getchar();IFcharacter等于=THEN返回(relop，EQ)retract();返回(=，null),+:返回(+,null)-:返回(-,null)*:返回(*,null):getchar();IFcharacter等于=THEN返回(relop，LE)retract();返回(relop，LT);:返回(;,null)其它:retract();error();ENDOFCASE,.,37,需要进一步考虑的问题1、缓冲区预处理，超前搜索2、关键字的处理，符号表的实现3、符号表的查找效率，算法的优化实现4、词法错误处理,.,38,源程序的输入,在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。,起始指针,搜索指针,.,39,超前搜索,词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。,.,40,关键字的识别与查表算法,对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数,.,41,出错处理,对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。,.,42,正规表达式是一种适合描述符号串的表示法，可由它定义正规集。正规集即为正规式所描述的串的集合。一般用L()表示。采用正规表达式的原因：词法规则简单，容易被理解；从它容易构造高效识别程序；可由正规表达式自动构造词法分析程序；可用于其他各种信息流的处理。,2.3正规表达式与有限自动机简介,.,43,1、正规表达式的定义,设为字母表，则的正规表达式按照下列规则递归地定义：基本：(1)都是上的正规式，表示为L()=；(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，上的正规式和相应的正规集的例子有：正规式正规集aaaba,babab(ab)(ab)aa,ab,ba,bba,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,+,-，则上的正规式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=ee=e=(零正规表达式)e=e=e(同一律，单位正规表达式)e1|e2=e2|e1(交换律)e1|(e2|e3)=(e1|e2)|e3e1(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)DFAM(见图2-1)接受的字集为。a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合c.含奇数个0的二进制数组成的集合d.含偶数个0的二进制数组成的集合【解答】(1)c(2)c(3)d,.,54,状态转换图确定有限状态自动机（DFA）非确定有限状态自动机（NFA）NFA确定化为DFADFA的化简,有限自动机（FA）,.,55,有限自动机是依据某些输入而改变状态的机器或程序。可以用状态转换图来表示。有限自动机是有向图这种通用结构的一个实例，在动态数据结构和高级搜索方面有许多应用。,序,.,56,1、状态转换图,有向图，结点表示状态，用圆圈表示；结点之间可以用有向边连接，有向边上标记影响状态改变的可能输入的字符；,.,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:ZK是非空的终态集合。,.,58,从状态转换图构造DFA,例：从下面状态图构造DFA。,DFAD=（S，Z，A，B，a，b，M，S，Z），其中M定义为：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=ZM（Z，a）=Z,.,59,例：构造一个识别语言(a|b)*ab的有限自动机。,从正规表达式构造有限自动机,状态,.,60,非确定有限状态自动机,一个非确定的有限自动机（NFA）D是一个五元组：N=（K，M，S，Z）其中K：有限非空的状态集合；：有穷非空的输入字母表；M：转换函数，是在K到K的子集所组成集合的映像，M(Ki,a)=K1,K2,.KnS:SK是非空的初态集合；Z:ZK是非空的终态集合.,.,61,DFA与NFA的区别,NFA还允许在状态转换图中输出边上标记为。,.,62,举例,与右图所示对应的有一个NFA，N=(S,A,B,Z,a,b,M,S,Z)其中M：M(S,a)=AM(S,b)=BM(A,a)=ZM(A,b)=BM(B,a)=A,BM(B,b)=ZM(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,一、由正规表达式构造等价的NFAM,1、由正规表达式R表示成如图所示的拓广转换图。,2、对正规式采用如下规则构造对应的NFAM。,3、逐步运用上述3个规则不断在1、的拓广转换图中增加新结点进行分解，直到每条有向边上仅标识有中的一个字母或为止，则NFAM构造完成。,.,66,例：对给定正规式b*(d|ad)(b|ab)+，构造其NFAM。,举例,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、状态子集的_闭包,若FAM有状态子集I，则其_闭包即_closure(I)为：（1）若SiI，则Si_closure(I)；（2）若SiI，则对从Si出发经过通路所能到达的任何状态Sj，都有Sj_closure(I)。,.,69,二、NFA的确定化,2、定义,对FAM的一个状态子集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_closure(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。,.,72,例：假设有一个NFAM如下，试用子集法对其进行确定化，形成等价的DFAM。,状态,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)=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,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的化简,2、化简(最小化)算法基本思想划分法将DFAM中的状态划分为互不相交的子集，每个子集内部的状态都等价；而在不同子集间的状态均不等价。,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中有不等价的状态，还要进一步划分。对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的任何一个子集，所以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,6f(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,由正规式构造有限自动机小结,正规式到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,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词法分析器的自动生成,用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言直接编写词法分析程序。利用自动生成工具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|zdigit0|1|2|9identifierletter(letter|digit)*integerdigit(digit)*2、识别规则正规式动作描述token1action1token2action2tokennactionn,/*声明部分*/%#include#include#include#defineWHILE1#defineDO2#defineIF3#defineELSE4#defineSWITCH5#defineID6#defineNUM7#definePLUS8#defineSUB9#defineSTAR10#defineRELOP11