第三章词法分析.ppt

上传人：sccc

文档编号：5090383

上传时间：2023-06-03

格式：PPT

页数：101

大小：1.34MB

《第三章词法分析.ppt》由会员分享，可在线阅读，更多相关《第三章词法分析.ppt（101页珍藏版）》请在三一办公上搜索。

1、第三章词法分析,3.1 词法分析概述3.2 词法分析程序的设计 3.3 正规式与有限自动机3.4 词法分析程序的实现3.5 词法分析器的自动生成,2,2023/6/3,中南大学软件学院陈志刚,3.1 词法分析概述,一、词法分析程序的任务二、词法分析程序的功能三、词法分析程序的安排四、词法分析程序的实现方式五、词法分析程序的输出形式,3,2023/6/3,中南大学软件学院陈志刚,词法分析程序,词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍。输入：源程序字符串输出：等价的属性字序列（内部表示形式）,3.1 词法分析概述,4,2023/6/3,中南大学软件

2、学院陈志刚,一、词法分析程序的任务从左至右逐个字符地扫描源程序，产生一个个单词符号。把作为字符的源程序改造为单词符号串组成的中间程序，执行词法分析任务的程序称为词法分析器或称扫描器。,3.1 词法分析概述,5,2023/6/3,中南大学软件学院陈志刚,二、词法分析程序的功能,词法分析程序主要执行以下功能：读入源程序字符串，识别开具有独立含义的最小语法单位单词（符号）；把单词变换成长度统一的且为定长的属性字；其他功能：滤掉空格，跳过注释、换行符某些预加工处理,3.1 词法分析概述,6,2023/6/3,中南大学软件学院陈志刚,三、词法分析程序的安排,常常把词法分析程序作为独立的一遍或作为被

3、语法分析程序所调用的子程序。1、作为独立的一遍：语法分析前进行词法分析，把单词符号串形成中间文件存贮。,3.1 词法分析概述,7,2023/6/3,中南大学软件学院陈志刚,三、词法分析程序的安排,2、作为被语法分析器词用的子程序：,3.1 词法分析概述,8,2023/6/3,中南大学软件学院陈志刚,相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。,四、词法分析程序的实现方式,3.1 词法分析概述,9,2023/6/3,中南大学软件学

4、院陈志刚,相对独立方式,当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。,源程序,词法分析程序,语法分析程序,Token,get token,.,四、词法分析程序的实现方式,3.1 词法分析概述,10,2023/6/3,中南大学软件学院陈志刚,完全独立方式,采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性,源程序,词法分析程序,语法分析程序,属性字序列,.,四、词法分析程序的实现方式,3.1 词法分析概述,11,2023/6/3,中南大学软件学院陈志刚,单词-是程序语言的基本语法符号。如：基本字、标识符、常数、运算符、界符等。词法

5、分析器中单词的输出形式：（单词类别、单词内部码值）,五、词法分析程序的输出形式,3.1 词法分析概述,12,2023/6/3,中南大学软件学院陈志刚,词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值）单词种别：表示单词种类，常用整数编码，它是语法分析需要的单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。,五、词法分析程序的输出形式,3.1 词法分析概述,13,2023/6/3,中

6、南大学软件学院陈志刚,语言的单词符号,单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数。(个数不确定，按类型分类)运算符：如+、-、*、/、等。(个数确定，一符一类)界符：如，、；、（、）、:等。(个数确定,一符一类)注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。,五、词法分析程序的输出形式,3.1 词法分析概述,14,2023/6/3,中南大学软件学院陈志刚,例：若分类表为：试分析输入串：IF a10THEN b1:=c1*d1 ELSE b1:=5 经词

7、法分析后的输出。,五、词法分析程序的输出形式,3.1 词法分析概述,15,2023/6/3,中南大学软件学院陈志刚,解：输出的单词串为：,五、词法分析程序的输出形式,3.1 词法分析概述,16,2023/6/3,中南大学软件学院陈志刚,一、状态转换图,状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。,S,I,E,字母,数字,字母或数字,状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态,3.2 词法

8、分析程序的设计,例1：,17,2023/6/3,中南大学软件学院陈志刚,一、状态转换图,例2：,例3：,18,2023/6/3,中南大学软件学院陈志刚,方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。例1：,二、状态转换图的实现,PROCEDURE Proc0;Getchar;case char of AZ:proc1;09:proc2;otherwise error;end of case;,19,2023/6/3,中南大学软件学院陈志刚,为了描述方便，引入一些标准过程（函数）与变量:1.全程字符变量Char：存放最新读入的源程序字符；2.字符串TOKEN：存放构成单

9、词符号的字符串；3.过程GETChar：读入一个源程序字符，放入Char中，搜索指针前移；4.过程GETNBC：反复调用 GETChar，直接读入的 Char 为止；5.过程CONCAT：把Char中字符连到TOKEN末尾去；6.函数Letter/digit：判别Char中是否为字母/数字；7.过程Return(c,val);8.过程Retract：搜索器指针回拔一个字符。,二、状态转换图的实现,20,2023/6/3,中南大学软件学院陈志刚,例2：,PROCEDURE Pro0;BEGIN Getchar;IF char IN A.Z then pro1 else error;END;Pr

10、ocedure pro1;begin getchar;while char IN A.Z,o.g DO begin concat;getchar;End;pro2;End;procedure pro2;begin retract;return(101,TOKEN);end;,21,2023/6/3,中南大学软件学院陈志刚,三、为正则文法构造状态转换图,什么是正则文法？（U:=T 或U:=WT）步骤如下：以S为开始状态作结点；把文法中的每一个非终结符号作为状态结点；对于形如Q:=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q:=RT的规则引一条从状态R到Q的弧，弧上标记为

11、T，其中R为非终结符号，T为终结符号。以识别符号为终止状态。,22,2023/6/3,中南大学软件学院陈志刚,构造状态转换图举例,例如：对于正则文法GZ：Z:=Za|Aa|Bb A:=Ba|a B:=Ab|b,S,A,B,a,b,S,A,B,a,Z,Z,a,S,A,B,a,b,Z,b,a,a,b,a,a,a,b,a,(1),(2),(3),23,2023/6/3,中南大学软件学院陈志刚,四、应用状态转换图识别句子,如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下:(1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止

12、；(2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。,24,2023/6/3,中南大学软件学院陈志刚,应用状态转换图识别句子举例,例如：对于正则文法GZ：Z:=Za|Aa|Bb A:=Ba|a B:=Ab|b,a,b,S,A,B,a,b,Z,b,a,a,a,b,S,A,B,a,b,Z,b,a,a,(1)识别字符串ababaaa,F,b,a,b,(2)识别字符串bababbb,25,2023/6/3,中南大学软件学院陈志刚,状态转换

13、图识别句子的实质,是一个规约过程，运用自底向上的识别算法：如：S A与A Z表示：a直接规约为A，Aa直接规约为Z。从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过程。,26,2023/6/3,中南大学软件学院陈志刚,对句子ababaaa的分析,步骤当前状态输入的其余部分 S ababaaa A babaaa B abaaa A baaa B aaa A aa Z a Z,a b a b a a a,A,B,A,B,A,Z,Z,(a)分析过程,(b)语法树,27,2023/6/3,中南大学软件学院陈志刚,五、用状态转换图为正则语言构造正则文法,从上面

14、状态转换图，可得到相应的正则文法：GZ:Z:=Cb C:=Bb|b B:=Ab A:=Ba|a,S,A,B,C,Z,a,b,b,b,b,a,例如：正则语言(ab)nb2|n0 基于其句子的一般形式，为其构造状态转换图：,28,2023/6/3,中南大学软件学院陈志刚,六、转换系统,定义：转换系统是具有下列三个特征的状态转换图，即 1)开始状态S和终止状态Z 唯一;2)无弧进入S，也无弧自Z射出；3)可能存在标记为空串（）的弧。转换系统与状态转换图的区别：弧,S,S1,S2,Z,A,Z2,Z1,29,2023/6/3,中南大学软件学院陈志刚,一、基本概念二、确定有穷状态自动机（DFA）三、非

15、确定有穷状态自动机（NFA）四、NFA和DFA的转换五、正规式和有限自动机的等价性六、DFA的化简,3.3 正规式与有限自动机,30,2023/6/3,中南大学软件学院陈志刚,一、基本概念1.字母表：元素的非空有限集合。如=A,B,O2.字符：字母表的一个元素称为一个字符（符号）3.上的字：上字符的有穷序列；例：=a,b,c4.空字：不含任何字符的字 5.字的长度：|6.上字的全体：*7.字的连接：字与字的连接记为,3.3 正规式与有限自动机,31,2023/6/3,中南大学软件学院陈志刚,一、基本概念8.字的方幂：字的n次连接称为的n次方幂,记为,特别地=9.字的集合A与B的乘积：记作,

16、其中10.*子集的方幂：A=,A1=A,11.*子集的正则闭包：12.*子集的闭包：,3.3 正规式与有限自动机,32,2023/6/3,中南大学软件学院陈志刚,正规式与正规集正规集是字母表上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。1.和都是上的正规式，它们所表示的正规集分别为和2.任何a,a是上的正规式，它所表示的正规式为3.假定u和v是正规式，它们所代表的正规集分别是L(u)和L(v)，则u|v,uv,u*都是上的正规式，它们所表示的正规集分别为L(u)L(v),L(u)L(v),L(u)*仅由有限次使用上述三步而定义的表达式才是上的正规式，仅由这些

17、正规式所表示的字集才是上的正规集,33,2023/6/3,中南大学软件学院陈志刚,正规式与正规集优先级递增：|(或)，（直接），*,（正规式）,*,（正规集）例1.=0,1，则正规式有0,1,1*,|0|,，正规集有0,1,1*,若两个正规式所表示的正规集相同，则认为二者等价才是上的正规集,34,2023/6/3,中南大学软件学院陈志刚,正规式的性质：1交换律：U|V=V|U 证：L(u|v)=L(u)L(v)=L(v)L(u)=L(v|u)因此，u|v=v|u2结合律：(u|v)|w=u|(v|w),(uv)w=u(vw)3分配律：u(v|w)=uv|uw,(u|v)w=u(vw)4u=

18、u=u 证：L(u)=L()L(u)=L(u)0 L(u)=L(u),35,2023/6/3,中南大学软件学院陈志刚,二、确定型有穷状态自动机,一个确定的有穷自动机（DFA）D是一个五元组：D=（K，M，S，F）其中 K：有穷非空的状态集合；：有穷非空的输入符号字母表；M：转换函数，是在KK上的映像，即，如 M(ki,a)=kj,(kiK,kjK)就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；SK是唯一的一个初态；F K是非空的终态集合。,36,2023/6/3,中南大学软件学院陈志刚,例1DFA M=(0,1,2,a,b,f,0,2)，

19、其中(s,a)=S,(s,b)=2,s=0,1,2注：一个DFA可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素Ms,a的值为(s,a)。例2,二、确定型有穷状态自动机,37,2023/6/3,中南大学软件学院陈志刚,一个DFA M也可用一张状态转换图表示，DFA的每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入字符，若(s,a)=S，则从状态s画一条箭弧到S，弧上标记为a。对*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上标记连接成的字等于，则称可为DFA M所识别，或称DFA M可读出（或接受、识别）字。DFA M识别的字的全体记为L(M)。,二、

20、确定型有穷状态自动机,38,2023/6/3,中南大学软件学院陈志刚,如果一个DFA M的输入字母表为，则我们也称M是上的一个DFA。可以证明：上的一个子集是正规的，当且仅当存在上的DFA M，使得V=L（M）。DFA的确定性表现在映射：SS是一个单值函数。也就是说，对任何状态sS和输入符号a，(s,a)唯一地确定了下一状态。特别地，若DFA M的初态同时又是终态，改DFA M可识别空字。显然，若DFA M中字母表含n个字母，则任何一个状态顶多只有n条发出弧。,二、确定型有穷状态自动机,39,2023/6/3,中南大学软件学院陈志刚,从状态转换图构造有穷状态自动机,例如：从下面状态图构造D

21、FADFA D=（S，Z，A，B，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 M（B，b）=Z M（Z，a）=Z,a,b,S,A,B,a,b,Z,b,a,a,40,2023/6/3,中南大学软件学院陈志刚,运行DFA与识别一个字符串,扩充的映像M定义：M(R,)=R M(R,Tt)=M(M(R,T),t)，其中t*，T以上两个式子的含义是什么？定义：对于某DFA D=（K,M,S,F），如果M(S，t)=P,PF，则称符号串t可被DFA D所接受。运行一个DFA的过程：识别一个符号串是否被接受,41,2023/6

22、/3,中南大学软件学院陈志刚,举例,如前例：DFA D=（S，Z，A，B，a，b，M，S，Z）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 则：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z,42,2023/6/3,中南大学软件学院陈志刚,正则集,正则集：L(D)，是一个DFA接受的字符串集合正则语言与正则集：L(G)=L(D)最小状态自动机：状态个数最少，唯一如何减少自动机的状态

23、数而不改变自动机所接受的语言呢？,43,2023/6/3,中南大学软件学院陈志刚,如何在计算机内表示映像？,映像M：含义？映像在计算机内的表示法：矩阵表示法表结构表示法,44,2023/6/3,中南大学软件学院陈志刚,DFA 的矩阵表示法,a,b,S,A,B,a,b,Z,b,a,a,矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。,45,2023/6/3,中南大学软件学院陈志刚,表结构表示法,对每一个状态结点而言若某结点有K个射出的弧，则相应表长为2k+2,46,2023/6/3,中南大学软件学院陈志刚,引入,M(R,T)是K到K的单值函数，即唯一确定下一状态如果在当前状态

24、下，同一个输入字符确定的下一状态不止一个呢？如 V:=UT W:=UT,U,W,V,T,T,a,b,S,A,B,a,b,Z,b,a,a,a,a,例如：文法G3.2:Z:=Za|Aa|Bb A:=Ba|Za|a B:=Ab|Ba|b,三、非确定有穷状态自动机,47,2023/6/3,中南大学软件学院陈志刚,一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，M，S，F）其中K：有穷非空的状态集合；：有穷非空的输入字母表；M：转换函数，是在K到K的子集所组成集合的映像，M(R,T)=Q1,Q2,.QnSK是非空的初态集合；FK是非空的终态集合.,三、非确定有穷状态自动机,48,2023/6

25、/3,中南大学软件学院陈志刚,DFA与NFA的区别,49,2023/6/3,中南大学软件学院陈志刚,举例,前述文法G3.2对应的自动机NFA N=(S,A,B,Z,a,b,M,S,Z)其中M：M(S,a)=A M(S,b)=BM(A,a)=Z M(A,b)=BM(B,a)=A,B M(B,b)=ZM(Z,a)=A,Z,a,b,S,A,B,a,b,Z,b,a,a,a,a,50,2023/6/3,中南大学软件学院陈志刚,扩充映像,定义：M(R,)=R R为任意的状态 M(R,Tt)=M(Q1,t)M(Q2,t)M(Qn,t)其中t*，T，M(R,T)=Q1,Q2,.Qn M(R,Tt)=M(

26、Q1,Q2,Qn,t)=M(Qi,t),51,2023/6/3,中南大学软件学院陈志刚,举例(字符串被NFA所接受),对于输入字符串babbabb，运行G3.2的NFA,52,2023/6/3,中南大学软件学院陈志刚,运行NFA,运行NFA：识别一个字符串是否被NFA所接受，是否能达到终态集合中的某个状态实质：用自底向上方法识别句子状态转换的下一状态不唯一，如何解决？,53,2023/6/3,中南大学软件学院陈志刚,单状态,M(R,T)=Q1,Q2,Qn 变为M(R,T)=Q1,Q2,Qn（单状态）表示当前状态为R输入字符T时，下一状态可能是这些状态中的某一状态。,54,2023/6/3

27、,中南大学软件学院陈志刚,怎样把NFA变为DFA?,定理3.6 NFA N=(K,M,S,F)对应DFA N=(K,M,S,F)其中K是有穷非空状态集合，由k的一切子集组成；用Q1,Q2,Qm表示K的元素，QiKM(R1,R2,Ri,T)=Q1,Q2,.QjS=S1,S2,SnF=Sj,Sk,Sl|Sj,Sk,SlK,Sj,Sk,SlF 则 L(N)=L(N),四、NFA与DFA的转换,55,2023/6/3,中南大学软件学院陈志刚,举例,例:为NFA N=(S,A,B,Z,a,b,M,S,Z)构造DFA.设它对应的DFA N=(K,a,b,M,S,F),a,b,S,A,B,a,b,Z,b

28、,a,a,a,a,K=S M(S,a)=A M(S,b)=B K=S,A,B M(A,a)=Z M(A,b)=B M(B,a)=AB M(B,b)=Z K=S,A,B,Z,AB M(Z,a)=AZ M(Z,b)=M(AB,a)=ABZ M(AB,b)=BZK=S,A,B,Z,AB,AZ,BZ,ABZM(AZ,a)=AZ M(AZ,b)=B M(BZ,a)=ABZ M(BZ,b)=ZM(ABZ,a)=ABZM(ABZ,b)=BZ,56,2023/6/3,中南大学软件学院陈志刚,举例（续1）,a,b,S,A,B,a,b,Z,b,a,a,a,a,根据左边状态转换矩阵，可以得到DFA N的状态集合（

29、表的左列状态），即K=S,A,b,Z,AB,AZ,BZ,ABZ,57,2023/6/3,中南大学软件学院陈志刚,举例（续2）,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,根据上面状态转换矩阵，同时可以得到N的映像函数，根据该映像可以画出它的状态转换图（如下）。终态集合中的元素为：由新映像得到的状态、且这些状态包含原NFA N的终态集合中的状态。,58,2023/6/3,中南大学软件学院陈志刚,1上NFA M所能识别的字的全体是上的一个正规集证明：设转换图中每条弧上可用一个正规式作标记，

30、让NFA M的转换图中加进两节点X和Y，形成新的NFA M，从X画弧指向原NFA M的所有初态，从原NFA M的所有终态画弧指向Y，显然L(M)=L(M)然后，对NFA M消结，直至只剩下X、Y两个结点为止，符上标记为一正规式。所以，NFA M识别的为一正规式；NFA M识别的是一正规集。,五、正规式和有限自动机的等价性,59,2023/6/3,中南大学软件学院陈志刚,消结规则为,五、正规式和有限自动机的等价性,60,2023/6/3,中南大学软件学院陈志刚,例1.消结点,五、正规式和有限自动机的等价性,例2.消结点,61,2023/6/3,中南大学软件学院陈志刚,2对于上的每个正规集V

31、，存在一个上的DFA M，使得V=L(M)。证明：第一步，用替代办法构造一个NFA M，使V=L(M)，因为正规集V可用正规式u来描述，而u由一系列单个字符连接而成，故可用下述方法分解之：,五、正规式和有限自动机的等价性,S,Z,e1e2,S,Z,e1,e2,S,Z,e1|e2,S,Z,e,S,Z,S,Z,e1,e2,e,62,2023/6/3,中南大学软件学院陈志刚,具体方法：构造如下转换图：逐步分解，便可得到一个NFA M，有L(u)=V=L(M)。例1第二步，把NFA M确定化为DFA M，得证。,五、正规式和有限自动机的等价性,63,2023/6/3,中南大学软件学院陈志刚,举例,

32、例：正则表达式(A|B)A|B|0|1的转换系统的构造过程如下：,S,Z,(A|B)A|B|0|1,S,Z,(A|B),A|B|0|1,S,Z,A,B,A|B|0|1,S,Z,A,B,1,0,A,B,64,2023/6/3,中南大学软件学院陈志刚,概念1.假设I是NFA M的状态集的一个子集，我们定义-CLOSURE(I)为（I的-闭包）。（1）若SI，则S-CLOSURE(I)（2）若SI，则从s出发经过任意条弧而达到的状态s，有s-CLOSURE(I)例1.,五、正规式和有限自动机的等价性,若I=1,3，则-CLOSURE(I)=1,3,2,8,65,2023/6/3,中南大学软件学院

33、陈志刚,概念2.假定I是M的状态子集，a是中的字符，定义Ia=-CLOSURE(J),其中J是I中任意状态出发（跳过前面任意多条弧），经过一条a弧而能达到的状态结的全体。例2同例1 DFA，Ia=5,6,2利用概念1和概念2，便可把NFA确定化。,五、正规式和有限自动机的等价性,66,2023/6/3,中南大学软件学院陈志刚,五、正规式和有限自动机的等价性,令，构造一张如下的表，此表第0列为状态子集I，第1至m列分别为状态子集，设第一行第0列为-CLOSURE(X),，其中X为NFA M的初态，求出第一个的，如果某个Iai(i=1,m)未曾在第0列中列出，则把Iai补入状态子集集合I中，即列

34、于第0列新的一行。重复上述各步，直至所有行的Iai(i=1,m)均在第0列I中出现过为止。这种循环必将在有限步内中止。（因为S是有限状态集，所以S中状态的组合数也是有限的）,67,2023/6/3,中南大学软件学院陈志刚,显然，这张表可以看成一个状态转换表，也就是说可把I中每个子集看成一个状态，而状态转换表唯一地刻划了一个DFA M，其初态为该表的第1行第0列，含有原NFA M终态的子集为新的终态。（证毕）推论：一个子集是正规的，当且仅当它可由一个DFA（或NFA）所识别。,五、正规式和有限自动机的等价性,68,2023/6/3,中南大学软件学院陈志刚,例：设计一个DFA M，它识别二进制

36、 N=(A,C,D,E,a,b,M,A,C,D,A,C,D)M:M(A,a)=C,E M(A,b)=E M(C,a)=C M(D,a)=E M(D,b)=E M(E,a)=D,A,B,D,C,a,a,E,a,b,A,C,a,a,a,b,(e),(f),D,a,E,a,b,开始状态：A,B终止状态：B,C,D,开始状态：A,C,D终止状态：A,C,D,72,2023/6/3,中南大学软件学院陈志刚,正则表达式的值与有穷自动机所接受的语言,定理3.11：上的NFA A所接受的字符串集合L(A)是上的某个正则表达式e的值，即L(A)=|e|。例:NFA N相应的状态转换图为图(a)，则N所接受的语

38、互不相交的子集，使子集中的状态是等价的化简DFA的算法步骤：划分状态集合并状态:取每组状态中的代表状态，删去其他等价状态若有死状态或不可达状态，则把它们删去。死状态：无法达到终止状态的非终止状态不可达状态：不能从开始状态达到它的那些状态,六、DFA的化简,75,2023/6/3,中南大学软件学院陈志刚,举例,划分状态集为4和 0,1,2,3对于0,1,2,3和输入字符a和b:M(0,a)=1 M(1,a)=1M(2,a)=1 M(3,a)=1M(0,b)=2 M(1,b)=3M(2,b)=2 M(3,b)=4只有状态3在输入为b时映像的后继状态不在0,1,2,3中，因此该状态集划分为3和0,

39、1,2对于0,1,2:状态1在输入为b时的后继状态不在0,1,2中，因此划分为1和0,2,0,2,3,1,4,b,b,b,b,b,a,a,a,a,a,对于0,2:对于相同输入字符，该子集中每一状态映像得到的后继状态都相同，因此不再可划分最后划分为：4 3 1 0,2,六、DFA的化简,76,2023/6/3,中南大学软件学院陈志刚,举例（续1）,对于划分结果4,3,1,0,2，把0,2合并为一个状态，其状态转换图如图：,0,2,1,3,a,a,a,a,b,b,b,0,2,3,1,4,b,b,b,b,b,a,a,a,a,a,b,六、DFA的化简,77,2023/6/3,中南大学软件学院陈志刚

40、,构造词法分析程序的方法,用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。利用自动生成工具LEX自动生成词法分析程序。,3.4 词法分析程序的实现,78,2023/6/3,中南大学软件学院陈志刚,词法分析程序实现中要考虑的问题,确定实现词法分析程序的执行方式确定属性字的结构缓冲区预处理，超前搜索,关键字的处理，符号表的实现查找效率，算法的优化实现词法错误处理,3.4 词法分析程序的实现,79,2023/6/3,中南大学软件学院陈志刚,属性字,词法分析程序对说明部分不做语义处理。词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）属性字

41、是符号的机内表示，有统一固定的长度,3.4 词法分析程序的实现,80,2023/6/3,中南大学软件学院陈志刚,源程序的输入,在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。,起始指针,搜索指针,3.4 词法分析程序的实现,81,2023/6/3,中南大学软件学院陈志刚,超前搜索,词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。,3.4 词法分析程序的

42、实现,82,2023/6/3,中南大学软件学院陈志刚,关键字的识别与查表算法,对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找Hash函数,3.4 词法分析程序的实现,83,2023/6/3,中南大学软件学院陈志刚,出错处理,对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。,3.4 词法分析程序的实现,84,2023/6/3,中南大学软件学院陈志刚,使用状态图设计词法分析程序,多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都

43、可以被状态图识别。使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。,3.4 词法分析程序的实现,85,2023/6/3,中南大学软件学院陈志刚,2,0,1,字母,字母|数字,其它,3,4,5,6,数字,数字,其它,+,-,7,8,*,/,9,10,11,13,=,:,;,16,17,其它,13,=,举例,86,2023/6/3,中南大学软件学院陈志刚,本节讨论：用正规式描述单词符号，并研究如何从正规产生识别

44、这些单词符号的词法分析程序。,3.5 词法分析器的自动生成,87,2023/6/3,中南大学软件学院陈志刚,一、LEX语言,一个LEX语言程序经过编译后得到的结果程序，其作用相当于一个DFA，可用来识别和产生单词也就是说其功能即为一个词法分析器。,88,2023/6/3,中南大学软件学院陈志刚,一个LEX源程序包括两部分：辅助定义式和识别规则1、辅助定义式 D1R1 DnRn 其中Ri为正规式，只允许出现上字符D1,Di-1；Di为这个正规式Ri的简名例1LetterA|B|Z Digit 0|1|9 Id Letter(Letter|Digit)*,.,89,2023/6/3,中南大学软

45、件学院陈志刚,2.识别规则 P1A1.PmAm其中，Pi称为词形，为正规式(D1,Dm)Ai称为词形Pi的动作（程序）显然：一个LEX源程序产生的词法分析器只能识别形如Pi的单词。,90,2023/6/3,中南大学软件学院陈志刚,二、LEX的实现,LEX编译程序的目的是把一个LEX程序改造为一个词法分析器L，这个词法分析器L将象自动机一样工作。1词法分析器L的工作方法 L逐个地扫描输入串的每个字符，寻找一个最大的子串匹配某个Pi（即：当输入串已匹配某个词形时，并不立即返回，而是沿着此道路继续前进，直至不能前进为止，逐个字符地逆向搜索，找到第一个逆向搜索到的匹配词形），把这个子串放入TOKE

46、N中，然后L调用动作子程序Ai（如果有二义，前面位置的词形优先），当Ai工作完后，L就把所得的单词符号（种别，内部码值）返回语法分析程序。下次调用L，接着往下分析。,91,2023/6/3,中南大学软件学院陈志刚,2.LEX程序的编译过程（1）对每条识别规则Pi构造一个NFA Mi;（2）引入一个新的初态X，从X画弧到每一个NFA Mi的初态，构造出一个NFA M;（3）把NFA M改造为DFA M，这个DFA M就是能识别所有形如Pi词形的词法分析器。这样我们就可用程序实现之，即编制出词法分析程序L。,92,2023/6/3,中南大学软件学院陈志刚,实例1,编写程序，实现下述LEX源程序

47、的功能辅助定义：(1)digit0|1|.|9(2)letterA|B|.|Z 识别规则:(1)digit(digit)*Return(4,val)(2)letter(letter|digit)*Return(5.Token)(3)*Return(6,_)(4)*Return(7,_),93,2023/6/3,中南大学软件学院陈志刚,解：1、各识别规则的NFA为：,94,2023/6/3,中南大学软件学院陈志刚,2、加入新初态X，构成NFA M整体,95,2023/6/3,中南大学软件学院陈志刚,3、确定化为DFA M,96,2023/6/3,中南大学软件学院陈志刚,4、写出实现其功

48、能的程序,PROGRAM LEX(input,output)BEGIN TOKEN:=;getchar;CASE char OF 0.9:while char IN0.9DO BEGIN TOKEN:=TOKEN+char;getchar END;retract;IF VAL(token,value)THEN return(4,value);A.Z:while char INA.Z,0.9DO BEGIN TOKEN:=TOKEN+char;getchar END;retract;Return(5,token);*:getchar;IF char=*THEN Return(7,-)ELSE r

49、etract;Return(6,-)ELSE:ERROR;ENDof case;END;,97,2023/6/3,中南大学软件学院陈志刚,本章小结,词法分析概况状态转换图确定型有穷状态自动机非确定型有穷状态自动机正则表达式词法分析程序的实现词法分析器的自动生成,98,2023/6/3,中南大学软件学院陈志刚,基本要求,了解词法分析程序的功能和实质。明确DFA与NFA的区别，掌握把NFA变为DFA的方法；熟练掌握把正则文法变为状态转换图以及写出有穷状态自动机的方法。掌握词法分析程序的基本实现方法。,99,2023/6/3,中南大学软件学院陈志刚,习题课,100,2023/6/3,中南大学软件学院陈志刚,101,2023/6/3,中南大学软件学院陈志刚,