第三章词法分析.ppt_三一文库31doc.com

资源描述

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

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

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

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

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

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

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

7、试分析输入串：IF a10 THEN b1:=c1*d1 ELSE b1:=5 经词法分析后的输出。,五、词法分析程序的输出形式,3.1 词法分析概述,15,2019/4/7,中南大学软件学院陈志刚,解：输出的单词串为：,五、词法分析程序的输出形式,3.1 词法分析概述,16,2019/4/7,中南大学软件学院陈志刚,一、状态转换图,状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。,S,I,E,字母,数字,字母或数

8、字,状态都是非终结符号 S：开始状态 E：终止状态，用双圈表示 I：标识符状态,3.2 词法分析程序的设计,例1：,17,2019/4/7,中南大学软件学院陈志刚,一、状态转换图,例2：,例3：,18,2019/4/7,中南大学软件学院陈志刚,方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。例1：,二、状态转换图的实现,PROCEDURE Proc0; Getchar; case char of AZ : proc1; 09: proc2; otherwise error; end of case;,19,2019/4/7,中南大学软件学院陈志刚,为了描述方便，引入一

9、些标准过程（函数）与变量: 1.全程字符变量Char：存放最新读入的源程序字符； 2.字符串TOKEN：存放构成单词符号的字符串； 3.过程GETChar：读入一个源程序字符，放入Char中，搜索指针前移； 4.过程GETNBC：反复调用 GETChar，直接读入的 Char 为止； 5.过程CONCAT：把Char中字符连到TOKEN末尾去； 6.函数Letter/digit：判别Char中是否为字母/数字； 7.过程Return (c, val ); 8.过程Retract：搜索器指针回拔一个字符。,二、状态转换图的实现,20,2019/4/7,中南大学软件学院陈志刚,例2：,PROCE

10、DURE Pro0; BEGIN Getchar; IF char IN AZ then pro1 else error; END; Procedure pro1; begin getchar; while char IN AZ, og DO begin concat; getchar; End; pro2; End; procedure pro2; begin retract; return(101,TOKEN ); end;,21,2019/4/7,中南大学软件学院陈志刚,三、为正则文法构造状态转换图,什么是正则文法？（U:=T 或U:=WT）步骤如下：以S为开始状态作结点；把文法

11、中的每一个非终结符号作为状态结点；对于形如Q:=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q:=RT的规则引一条从状态R到Q的弧，弧上标记为T，其中R为非终结符号，T为终结符号。以识别符号为终止状态。,22,2019/4/7,中南大学软件学院陈志刚,构造状态转换图举例,例如：对于正则文法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,2019/4/7,中南大学软件学院陈志刚,四、应用状态转换图识别句子,如果x是

12、相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤如下: (1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止； (2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。,24,2019/4/7,中南大学软件学院陈志刚,应用状态转换图识别句子举例,例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|b,a,b,S,A,B,a,b,Z,b,a,a,a,

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

14、a b a b a a a,A,B,A,B,A,Z,Z,(a) 分析过程,(b) 语法树,27,2019/4/7,中南大学软件学院陈志刚,五、用状态转换图为正则语言构造正则文法,从上面状态转换图，可得到相应的正则文法： 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,2019/4/7,中南大学软件学院陈志刚,六、转换系统,定义：转换系统是具有下列三个特征的状态转换图，即 1) 开始状态S和终止状态Z 唯一; 2) 无弧进入S，也无弧自Z射出； 3

15、)可能存在标记为空串（）的弧。转换系统与状态转换图的区别：弧,S,S1,S2,Z,A,Z2,Z1,29,2019/4/7,中南大学软件学院陈志刚,一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、NFA和DFA的转换五、正规式和有限自动机的等价性六、DFA的化简,3.3 正规式与有限自动机,30,2019/4/7,中南大学软件学院陈志刚,一、基本概念 1.字母表：元素的非空有限集合。如=A, B, O 2.字符：字母表的一个元素称为一个字符（符号） 3. 上的字：上字符的有穷序列；例：=a,b,c 4.空字：不含任何字符的字 5.字的长

16、度： | 6.上字的全体： * 7.字的连接：字与字的连接记为,3.3 正规式与有限自动机,31,2019/4/7,中南大学软件学院陈志刚,一、基本概念 8.字的方幂：字的n次连接称为的n次方幂,记为 ,特别地 = 9.字的集合A与B的乘积：记作 ,其中 10. *子集的方幂： A=,A1=A, , 11.*子集的正则闭包： 12.*子集的闭包：,3.3 正规式与有限自动机,32,2019/4/7,中南大学软件学院陈志刚,正规式与正规集正规集是字母表上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。 1.和都是上的正规式，它们所表示的正规集分别为和 2.

17、任何a,a是上的正规式，它所表示的正规式为 3.假定u和v是正规式，它们所代表的正规集分别是L(u)和L(v)，则u|v, uv, u*都是上的正规式，它们所表示的正规集分别为L(u)L(v), L(u)L(v), L(u)* 仅由有限次使用上述三步而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集,33,2019/4/7,中南大学软件学院陈志刚,正规式与正规集优先级递增： |(或)，（直接），*,（正规式） , , *, （正规集）例1. =0, 1，则正规式有0, 1, , 1*,| 0 |, ，正规集有0, 1, , , 1*, 若两个正规式所表示的正规集相同，

18、则认为二者等价才是上的正规集,34,2019/4/7,中南大学软件学院陈志刚,正规式的性质： 1交换律：U|V=V|U 证：L(u|v)=L(u)L(v) = L(v)L(u)=L(v|u) 因此，u|v=v|u 2结合律：(u|v)|w=u|(v|w),(uv)w=u(vw) 3分配律：u(v|w)=uv|uw,(u|v)w=u(vw) 4 u=u=u 证：L(u)=L()L(u)=L(u)0 L(u)=L(u),35,2019/4/7,中南大学软件学院陈志刚,二、确定型有穷状态自动机,一个确定的有穷自动机（DFA）D是一个五元组：D=（K，M，S，F）其中 K：有穷非空的状态集合；：

19、有穷非空的输入符号字母表； M：转换函数，是在KK上的映像，即，如 M(ki,a)=kj,(kiK,kjK)就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态； SK是唯一的一个初态； F K是非空的终态集合。,36,2019/4/7,中南大学软件学院陈志刚,例1DFA M=(0, 1, 2, a, b,f,0, 2)，其中(s,a)=S,(s,b)=2,s=0,1, 2 注：一个DFA可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素Ms, a的值为(s, a)。例2,二、确定型有穷状态自动机,37,2019/4/7,中南大学软件

20、学院陈志刚,一个DFA M也可用一张状态转换图表示，DFA的每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入字符，若(s, a)=S，则从状态s画一条箭弧到S，弧上标记为a。对*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上标记连接成的字等于，则称可为DFA M所识别，或称DFA M可读出（或接受、识别）字。 DFA M识别的字的全体记为L(M)。,二、确定型有穷状态自动机,38,2019/4/7,中南大学软件学院陈志刚,如果一个DFA M的输入字母表为，则我们也称M是上的一个DFA。可以证明：上的一个子集是正规的，当且仅当存在上的DFA M，使得V=L（M）。

21、 DFA的确定性表现在映射：SS是一个单值函数。也就是说，对任何状态sS和输入符号a，(s, a)唯一地确定了下一状态。特别地，若DFA M的初态同时又是终态，改DFA M可识别空字。显然，若DFA M中字母表含n个字母，则任何一个状态顶多只有n条发出弧。,二、确定型有穷状态自动机,39,2019/4/7,中南大学软件学院陈志刚,从状态转换图构造有穷状态自动机,例如：从下面状态图构造DFA DFA 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

22、,S,A,B,a,b,Z,b,a,a,40,2019/4/7,中南大学软件学院陈志刚,运行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,2019/4/7,中南大学软件学院陈志刚,举例,如前例：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，

23、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,2019/4/7,中南大学软件学院陈志刚,正则集,正则集：L(D)，是一个DFA接受的字符串集合正则语言与正则集：L(G)=L(D) 最小状态自动机：状态个数最少，唯一如何减少自动机的状态数而不改变自动机所接受的语言呢？,43,2019/4/7,中南大学软件学院陈志刚,如何在计算机内表示映像？,映像M：含义？映像在计算机内的表示法：矩

24、阵表示法表结构表示法,44,2019/4/7,中南大学软件学院陈志刚,DFA 的矩阵表示法,a,b,S,A,B,a,b,Z,b,a,a,矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。,45,2019/4/7,中南大学软件学院陈志刚,表结构表示法,对每一个状态结点而言若某结点有K个射出的弧，则相应表长为2k+2,46,2019/4/7,中南大学软件学院陈志刚,引入,M(R,T)是K到K的单值函数，即唯一确定下一状态如果在当前状态下，同一个输入字符确定的下一状态不止一个呢？如 V:=UT W:=UT,U,W,V,T,T,a,b,S,A,B,a,b,Z,b,a,a,a,

25、a,例如：文法G3.2: Z:=Za|Aa|Bb A:=Ba|Za|a B:=Ab|Ba|b,三、非确定有穷状态自动机,47,2019/4/7,中南大学软件学院陈志刚,一个非确定的有穷自动机（NFA）D是一个五元组：N=（K，M，S，F）其中 K：有穷非空的状态集合；：有穷非空的输入字母表； M：转换函数，是在K到K的子集所组成集合的映像， M(R, T)=Q1,Q2,.Qn SK是非空的初态集合； FK是非空的终态集合.,三、非确定有穷状态自动机,48,2019/4/7,中南大学软件学院陈志刚,DFA与NFA的区别,49,2019/4/7,中南大学软件学院陈志刚,举例,前述文法G3.2

26、对应的自动机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,S,A,B,a,b,Z,b,a,a,a,a,50,2019/4/7,中南大学软件学院陈志刚,扩充映像,定义： 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(Q1,Q2,Qn, t)=M(Qi,t),51,2019/4/7,中南大学软件学院陈志刚,举例(字符

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

28、, S, F) 对应 DFA N=(K, , M, S, F) 其中 K是有穷非空状态集合，由k的一切子集组成；用Q1,Q2,Qm表示K的元素， QiK M(R1,R2,Ri,T)= Q1,Q2,.Qj S=S1, S2, , Sn F=Sj, Sk, , Sl|Sj, Sk, , SlK, Sj, Sk, , SlF 则 L(N)=L(N),四、NFA与DFA的转换,55,2019/4/7,中南大学软件学院陈志刚,举例,例: 为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,

29、b,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)=BZ K=S,A,B,Z,AB,AZ, BZ,ABZ M(AZ,a)=AZ M(AZ,b)=B M(BZ,a)=ABZ M(BZ,b)=Z M(ABZ,a)=ABZ M(ABZ,b)=BZ,56,2019/4/7,中南大学软件学院陈志刚,举例（续1）,a,b,S,A,B,a,b,Z,b,a,a,a,a,根据左边状态转换矩阵，可以得到DFA

30、N的状态集合（表的左列状态），即 K=S,A,b,Z,AB,AZ,BZ,ABZ,57,2019/4/7,中南大学软件学院陈志刚,举例（续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,2019/4/7,中南大学软件学院陈志刚,1上NFA M所能识别的字的全体是上的一个正规集证明：设转换图中每条弧上

31、可用一个正规式作标记，让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,2019/4/7,中南大学软件学院陈志刚,消结规则为,五、正规式和有限自动机的等价性,60,2019/4/7,中南大学软件学院陈志刚,例1.消结点,五、正规式和有限自动机的等价性,例2.消结点,61,2019/4/7,中南大学软件学院陈志

32、刚,2对于上的每个正规集V，存在一个上的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,2019/4/7,中南大学软件学院陈志刚,具体方法：构造如下转换图：逐步分解，便可得到一个NFA M，有L(u)=V=L(M)。例1 第二步，把NFA M确定化为DFA M，得证。,五、正规式和有限自动机的等价性,63,2019/4/7

33、,中南大学软件学院陈志刚,举例,例：正则表达式(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,2019/4/7,中南大学软件学院陈志刚,概念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,

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

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

37、始状态：A 终止状态：B,71,2019/4/7,中南大学软件学院陈志刚,前例续,NFA 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,2019/4/7,中南大学软件学院陈志刚,正则表达式的值与有穷自动机所接受的语言,定理3.11：上的NFA A所接受

39、),74,2019/4/7,中南大学软件学院陈志刚,字符串W把状态P和状态Q区别开：等价状态：无法区别开的两个状态基本思想：把状态集划分成互不相交的子集，使子集中的状态是等价的化简DFA的算法步骤：划分状态集合并状态:取每组状态中的代表状态，删去其他等价状态若有死状态或不可达状态，则把它们删去。死状态：无法达到终止状态的非终止状态不可达状态：不能从开始状态达到它的那些状态,六、DFA的化简,75,2019/4/7,中南大学软件学院陈志刚,举例,划分状态集为4和 0,1,2,3 对于0,1,2,3和输入字符a和b: M(0,a)=1 M(1,a)=1 M(2,a)=1 M(3

40、,a)=1 M(0,b)=2 M(1,b)=3 M(2,b)=2 M(3,b)=4 只有状态3在输入为b时映像的后继状态不在0,1,2,3中，因此该状态集划分为3和0,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,2019/4/7,中南大学软件学院陈志刚,举例（续1）,对于划分结果4, 3, 1, 0,2，把0,2合并为一个状态，其状态转换图如

41、图：,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,2019/4/7,中南大学软件学院陈志刚,构造词法分析程序的方法,用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。利用自动生成工具LEX自动生成词法分析程序。,3.4 词法分析程序的实现,78,2019/4/7,中南大学软件学院陈志刚,词法分析程序实现中要考虑的问题,确定实现词法分析程序的执行方式确定属性字的结构缓冲区预处理，超前搜索, 关键字的处理，符号表的实现查找效率，算法的优化实现词法错误处

42、理,3.4 词法分析程序的实现,79,2019/4/7,中南大学软件学院陈志刚,属性字,词法分析程序对说明部分不做语义处理。词法分析程序输出属性字一般采用下面的形式：（符号类，符号值）属性字是符号的机内表示，有统一固定的长度,3.4 词法分析程序的实现,80,2019/4/7,中南大学软件学院陈志刚,源程序的输入,在内存开辟缓冲区，将程序文本放进该缓冲区预处理：删除无用字符等词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。,起始指针,搜索指针,3.4 词法分析程序的实现,81,20

43、19/4/7,中南大学软件学院陈志刚,超前搜索,词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。,3.4 词法分析程序的实现,82,2019/4/7,中南大学软件学院陈志刚,关键字的识别与查表算法,对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。查找算法：线性查找折半查找 Hash函数,3.4 词法分析程序的实现,83,2019/4/7,中南大学软件学院陈志刚,出错处理,对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的

44、）单词进行出错处理。,3.4 词法分析程序的实现,84,2019/4/7,中南大学软件学院陈志刚,使用状态图设计词法分析程序,多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被状态图识别。使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段相应的子程序。,3.4 词法分析程序的实现,85,2019/4/7,中南大学软件学院陈志刚,2,0,1,字母,字母|数字,其它,3,4,5,6

45、,数字,数字,其它,+,-,7,8,*,/,9,10,11,13,=,:,;,16,17,其它,13,=,举例,86,2019/4/7,中南大学软件学院陈志刚,本节讨论：用正规式描述单词符号，并研究如何从正规产生识别这些单词符号的词法分析程序。,3.5 词法分析器的自动生成,87,2019/4/7,中南大学软件学院陈志刚,一、LEX语言,一个LEX语言程序经过编译后得到的结果程序，其作用相当于一个DFA，可用来识别和产生单词也就是说其功能即为一个词法分析器。,88,2019/4/7,中南大学软件学院陈志刚,一个LEX源程序包括两部分：辅助定义式和识别规则 1、辅助定义式 D1R1 DnRn 其中Ri为正规式，只允许出现上字符D1,Di-1；Di为这个正规式Ri的简名例1LetterA|B|Z Digit 0|1|9 Id Letter(Letter|Digit)*,. . .,89,2019/4/7,中南大学软件学院陈志刚,2.识别规则 P1A1 . . . PmAm 其中，Pi称为词形，为正规式(D1,Dm) Ai称为词形Pi的动作（程序）显然：一个LEX源程序产生的词法分析器只能识别形如Pi的单词。,90,2019/4/7,中南大学软件学院陈志刚,二、LEX的实现,LEX编译程序的目的是把一个LEX程序改造为一个词法分析

展开阅读全文