第3章词法分析

1、第三章 词法分析u3.1 词法分析概述u3.2 词法分析程序的设计 u3.3 正规式与有限自动机u3.4 词法分析程序的实现u3.5 词法分析器的自动生成22022-3-173.1 词法分析概述词法分析概述u一、词法分析程序的任务u二、词法分析程序的功能u三、词法分析程序的安排u四、词法分析程序的实现方式u五、词法分析程序的输出形式32022-3-17词法分析程序n词法分析是编译过程中的一个阶段，在语法分析前进行 ，也可以和语法分析结合在一起作为一遍。n输入：源程序字符串n输出：等价的属性字序列（内部表示形式）3.1 词法分析概述词法分析概述42022-3-17q一、词法分析程序的任务一、词法

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

3、.1 词法分析概述词法分析概述62022-3-17q三、词法分析程序的安排三、词法分析程序的安排n常常把词法分析程序作为独立的一遍或作为被语法分析程序所调用的子程序。n1、作为独立的一遍： 语法分析前进行词法分析，把单词符号串形成中间文件存贮。3.1 词法分析概述词法分析概述72022-3-17q三、词法分析程序的安排三、词法分析程序的安排n2、作为被语法分析器词用的子程序： 3.1 词法分析概述词法分析概述82022-3-17n相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。n完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入

4、整个源程序，它的输出作为语法分析程序的输入。q四、词法分析程序的实现方式四、词法分析程序的实现方式3.1 词法分析概述词法分析概述92022-3-17相对独立方式n当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。源程序词法分析程序语法分析程序Tokenget token.q四、词法分析程序的实现方式四、词法分析程序的实现方式3.1 词法分析概述词法分析概述102022-3-17完全独立方式n采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性提高编译效率增加编译系统的可移植性 源程序词法分析程序语法分析程序属性字序列属性字序列.q四、词法分析程序的实现方式四、词法分析程序的

5、实现方式3.1 词法分析概述词法分析概述112022-3-17n单词-是程序语言的基本语法符号。n如：基本字、标识符、常数、运算符、界符等。n词法分析器中单词的输出形式： （单词类别、单词内部码值） q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法分析概述122022-3-17n词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值）n单词种别：表示单词种类，常用整数编码，它是语法分析需要的n单词自身的值：是编译中其他阶段所需要的信息如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。如果一个种别含有多个单词符号，那么还应给出

6、该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法分析概述132022-3-17语言的单词符号n单词符号是程序语言的基本语法单位，一般分为下面5种：关键字（基本字）：（个数确定，可全体编为一类，也可一字一类)标识符：（个数不确定，作为一类）常数：各种类型的常数 。(个数不确定，按类型分类)运算符：如+、-、*、/、0THEN b1:=c1*d1 ELSE b1:=5 经词法分析后的输出。经词法分析后的输出。q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法

7、分析概述152022-3-17n解：输出的单词串为：解：输出的单词串为：q五、词法分析程序的输出形式五、词法分析程序的输出形式3.1 词法分析概述词法分析概述162022-3-17一、状态转换图n状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。n一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。 SIE字母字母数字数字字母或数字字母或数字状态都是非终结符号S：开始状态E：终止状态，用双圈表示I：标识符状态3.2 词法分析程序的设计词法分析程序的设计例例1：172022-

8、3-17一、状态转换图例例2：例例3：182022-3-17n方法：每个结点对应一段程序，前面状态结的程方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。序调用其后继结点的程序。n例例1：二、状态转换图的实现PROCEDURE Proc0;Getchar; case char of AZ : proc1; 09: proc2;otherwise error;end of case;192022-3-17q为了描述方便，引入一些标准过程（函数）与变量为了描述方便，引入一些标准过程（函数）与变量:n1.全程字符变量全程字符变量Char：存放最新读入的源程序字符；：存放最新读入的源程

9、序字符；n2.字符串字符串TOKEN：存放构成单词符号的字符串；：存放构成单词符号的字符串；n3.过程过程GETChar：读入一个源程序字符，放入：读入一个源程序字符，放入Char中，中，搜索指针前移；搜索指针前移；n4.过程过程GETNBC：反复调用：反复调用 GETChar，直接读入的，直接读入的 Char 为止；为止；n5.过程过程CONCAT：把：把Char中字符连到中字符连到TOKEN末尾去；末尾去；n6.函数函数Letter/digit：判别：判别Char中是否为字母中是否为字母/数数字；字；n7.过程过程Return (c, val );n8.过程过程Retract：搜索器指针回

10、拔一个字符。：搜索器指针回拔一个字符。 二、状态转换图的实现202022-3-17n例例2：PROCEDURE Pro0;BEGIN Getchar;IF char IN A.Z then pro1 else error;END;Procedure 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;212022-3-17三、为正则文法构造状态转换图n什么是正则文法？（U:=T 或

11、U:=WT）n步骤如下：以S为开始状态作结点；把文法中的每一个非终结符号作为状态结点；对于形如Q:=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q:=RT的规则引一条从状态R到Q的弧，弧上标记为T，其中R为非终结符号，T为终结符号。以识别符号为终止状态。222022-3-17构造状态转换图举例n例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)232022-3-17四、应用状态转换图识别句子n如果x是相应文法的句子便必须能从开始状态出发，顺着弧的方向行进到终止状态。其步骤

12、如下: (1)从开始状态开始，以它作为当前状态，并从x的最左字符开始重复步骤2，直到到达x的右端为止； (2)扫描x的下一字符，在当前状态射出的各个弧中找出标记有该字符的弧，并沿此弧前进，以达到的状态作为下一当前状态。n步骤2存在的两种可能：可能找不到一条弧的标记与当前字符相同；总能找到一个弧，其标记与当前字符相同。242022-3-17应用状态转换图识别句子举例n例如：对于正则文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|babSABabZbaaabSABabZbaa(1)识别字符串ababaaaFba,b(2)识别字符串bababbb252022-3-17状态转换图识别句

13、子的实质n是一个规约过程，运用自底向上的识别算法：如： S A与A Z表示：a直接规约为A，Aa直接规约为Z。n从开始状态S出发逐步到达终止状态Z的过程，也是从终结符号串出发，规约到非终结符号的过程。aa262022-3-17对句子ababaaa的分析步骤 当前状态 输入的其余部分n S ababaaan A babaaan B abaaan A baaan B aaan A aan Z a1 Za b a b a a aABABAZZ(a) 分析过程分析过程(b) 语法树语法树272022-3-17五、用状态转换图为正则语言构造正则文法n从上面状态转换图，可得到相应的正则文法： GZ: Z:

14、=Cb C:=Bb|b B:=Ab A:=Ba|aSABCZabbbban例如：正则语言(ab)nb2|n0 基于其句子的一般形式，为其构造状态转换图：282022-3-17六、转换系统n定义：转换系统是具有下列三个特征的状态转换图，即 1) 开始状态S和终止状态Z 唯一; 2) 无弧进入S，也无弧自Z射出； 3)可能存在标记为空串（）的弧。n转换系统与状态转换图的区别： 弧SS1S2ZAZ2Z1292022-3-17u一、基本概念u二、确定有穷状态自动机（DFA）u三、非确定有穷状态自动机（NFA）u四、NFA和DFA的转换u五、正规式和有限自动机的等价性u六、DFA的化简3.3 正规式与有

15、限自动机正规式与有限自动机302022-3-17q一、基本概念一、基本概念n1.字母表字母表： 元素的非空有限集合。如元素的非空有限集合。如=A, B, On2.字符：字符： 字母表字母表的一个元素称为一个字符（符号）的一个元素称为一个字符（符号）n3. 上的字：上的字： 上字符的有穷序列；例：上字符的有穷序列；例：=a,b,cn4.空字空字： 不含任何字符的字不含任何字符的字 n5.字的长度：字的长度： |n6.上字的全体：上字的全体： *n7.字的连接：字的连接： 字字与字与字的连接记为的连接记为3.3 正规式与有限自动机正规式与有限自动机312022-3-17q一、基本概念一、基本概念n

16、8.字的方幂：字字的方幂：字的的n次连接称为次连接称为的的n次方幂次方幂,记记为为 ,特别地特别地 =n9.字的集合字的集合A与与B的乘积：的乘积： 记作记作 ,其中其中n10. *子集的方幂：子集的方幂： A=,A1=A, ,n11.*子集的正则闭包：子集的正则闭包：n12.*子集的闭包：子集的闭包：3.3 正规式与有限自动机正规式与有限自动机n0322022-3-17q正规式与正规集正规式与正规集n正规集是字母表正规集是字母表上的一个特殊字集，通常我们借助正上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。规式来描述它。关于正规式与正规集的定义是递归的。n1.

17、和和都是都是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为和和n2.任何任何a,a是是上的正规式，它所表示的正规式为上的正规式，它所表示的正规式为n3.假定假定u和和v是正规式，它们所代表的正规集分别是是正规式，它们所代表的正规集分别是L(u)和和L(v)，则，则u|v, uv, u*都是都是上的正规式，它上的正规式，它们所表示的正规集分别为们所表示的正规集分别为L(u)L(v), L(u)L(v), L(u)*n仅由有限次使用上述三步而定义的表达式才是仅由有限次使用上述三步而定义的表达式才是上的正上的正规式，仅由这些正规式所表示的字集才是规式，仅由这些正规式所表示的

18、字集才是上的正规集上的正规集332022-3-17q正规式与正规集正规式与正规集n优先级递增：优先级递增： |(或或)，（连接），（连接），*,（正规式）（正规式） , , *, （正规集）（正规集）n例例1. =0, 1，则正规式有，则正规式有0, 1, , 1*,，正规集有正规集有0, 1, , , 1*, n若两个正规式所表示的正规集相同，则认为二者若两个正规式所表示的正规集相同，则认为二者等价才是等价才是上的正规集上的正规集342022-3-17q正规式的性质：正规式的性质：n1交换律：交换律：U|V=V|U 证：证：L(u|v)=L(u)L(v) = L(v)L(u)=L(v|u)

19、因此，因此，u|v=v|un2结合律：结合律：(u|v)|w=u|(v|w),(uv)w=u(vw)n3分配律：分配律：u(v|w)=uv|uw,(u|v)w=u(vw)n4u=u=u 证：证：L(u)=L()L(u)=L(u)0 L(u)=L(u) 352022-3-17二、确定型有穷状态自动机q一个确定的有穷自动机（DFA）D是一个五元组：M=（S，S0，F）其中 S：有穷非空的状态集合；：有穷非空的输入符号字母表； ：转换函数，是在SS上的映像，即，如 (s,a)=s,(sS,sS)就意味着，当前状态为s，输入符为a时，将转换为下一个状态s，我们把s称作s的一个后继状态； S0S是唯一的

20、一个初态； F S是非空的终态集合。362022-3-17n例例1DFA M=(0, 1, 2, a, b,f,0, 2)，其中，其中(s,a)=S,(s,b)=S,s=0,1, 2n注：一个注：一个DFA可表示为一个状态转换矩阵，行表示可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素状态，列表示输入字符，矩阵元素Ms, a的值的值为为(s, a)。n例例2二、确定型有穷状态自动机372022-3-17n一个一个DFA M也可用一张状态转换图表示，也可用一张状态转换图表示，DFA的的每个状态对于状态转换图的一个接点，图中箭弧每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入

21、字符，若上的标记为输入字符，若(s, a)=S，则从状，则从状态态s画一条箭弧到画一条箭弧到S，弧上标记为，弧上标记为a。n对对*中的任何字中的任何字，若存在一条从初态到某一终，若存在一条从初态到某一终态的道路，且这条路上所有弧上标记连接成的字态的道路，且这条路上所有弧上标记连接成的字等于等于，则称，则称可为可为DFA M所识别，或称所识别，或称DFA M可可读出（或接受、识别）字读出（或接受、识别）字。nDFA M识别的字的全体记为识别的字的全体记为L(M)。二、确定型有穷状态自动机382022-3-17n如果一个如果一个DFA M的输入字母表为的输入字母表为，则我们也称，则我们也称M是是上

22、的一个上的一个DFA。可以证明：。可以证明：上的一个子集是正规的，上的一个子集是正规的，当且仅当存在当且仅当存在上的上的DFA M，使得，使得V=L（M）。）。nDFA的确定性表现在映射的确定性表现在映射：SS是一个单值函数。是一个单值函数。也就是说，对任何状态也就是说，对任何状态sS和输入符号和输入符号a，(s, a)唯一地确定了下一状态。唯一地确定了下一状态。n特别地，若特别地，若DFA M的初态同时又是终态，改的初态同时又是终态，改DFA M可识别空字可识别空字。n显然，若显然，若DFA M中字母表中字母表含含n个字母，则任何一个个字母，则任何一个状态顶多只有状态顶多只有n条发出弧。条发

23、出弧。 二、确定型有穷状态自动机392022-3-17从状态转换图构造有穷状态自动机n例如：从下面状态图构造DFAnDFA D=（S，Z，A，B，a，b，S，Z） 其中定义为： （S，a）=A （S，b）=B （A，a）=Z （A，b）=B （B，a）=A （B，b）=Z （Z，a）=ZabSABabZbaa402022-3-17运行DFA与识别一个字符串n扩充的映像定义： (R, )=R (R, Tt)=(R, T), t)，其中t*， Tn以上两个式子的含义是什么？n定义： 对于某DFA D=（K,S,F），如果(S，t)=P, PF，则称符号串t可被DFA D所接受。n运行一个DFA的过

24、程：识别一个符号串是否被接受412022-3-17举例n如前例：DFA D=（S，Z，A，B，a，b，S，Z） （S，a）=A （S，b）=B （A，a）=Z （A，b）=B （B，a）=A （B，b）=Z （Z，a）=Z 则：(S, ababaa)=(S,a), babaa) =(A,babaa)= (A,b), abaa)= (B,abaa)=(A,baa)= (B,aa)=(A,a)= Z 422022-3-17正则集n正则集：L(D)，是一个DFA接受的字符串集合n正则语言与正则集：L(G)=L(D)n最小状态自动机：状态个数最少，唯一n如何减少自动机的状态数而不改变自动机所接受的语言

25、呢？432022-3-17如何在计算机内表示映像？n映像：含义？n映像在计算机内的表示法：矩阵表示法表结构表示法442022-3-17DFA 的矩阵表示法字符字符状态状态abSABabZbaa矩阵行代表状态，列代表输入字符，矩阵行代表状态，列代表输入字符，矩阵元素是映像得到的新状态。矩阵元素是映像得到的新状态。452022-3-17表结构表示法状态名状态名射出的弧数射出的弧数标记标记1指向的下一状态指向的下一状态1标记标记K指向的下一状态指向的下一状态k对每一个状态结点而言对每一个状态结点而言若某结点有若某结点有K个射出的弧，个射出的弧，则相应表长为则相应表长为2k+2462022-3-17引

26、入n(R,T)是K到K的单值函数，即唯一确定下一状态n如果在当前状态下，同一个输入字符确定的下一状态不止一个呢？如 V:=UT W:=UTUWVTTabSABabZbaaaan例如：文法G3.2: Z:=Za|Aa|Bb A:=Ba|Za|a B:=Ab|Ba|b三、非确定有穷状态自动机472022-3-17一个非确定的有穷自动机（NFA）D是一个五元组：N=（S，S0，F）其中S：有穷非空的状态集合；：有穷非空的输入字母表；：转换函数，是在S到S的子集所组成集合的映像， (R, T)=Q1,Q2,.QnS0S是非空的初态集合；FS是非空的终态集合.三、非确定有穷状态自动机482022-3-1

27、7DFA与NFA的区别DFANFA开始状态开始状态唯一唯一一个或多个一个或多个映像映像单个状态单个状态状态集合状态集合492022-3-17举例n前述文法G3.2对应的自动机NFA N=(S,A,B,Z,a,b,S,Z) 其中：(S,a)=A (S,b)=B(A,a)=Z (A,b)=B(B,a)=A,B (B,b)=Z(Z,a)=A,ZabSABabZbaaaa502022-3-17扩充映像n定义： (R, )=R R为任意的状态 (R,Tt)=(Q1,t)(Q2,t)(Qn,t) 其中t*，T， (R, T)=Q1,Q2,.Qn (R, Tt)=(Q1,Q2,Qn, t)=(Qi,t)51

28、2022-3-17举例(字符串被NFA所接受)n对于输入字符串babbabb，运行G3.2的NFA步骤步骤当前状态当前状态输入的其余部分输入的其余部分可能的后继可能的后继 选择选择1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ522022-3-17运行NFAn运行NFA：识别一个字符串是否被NFA所接受，是否能达到终态集合中的某个状态n实质：用自底向上方法识别句子n状态转换的下一状态不唯一，如何解决？532022-3-17单状态n(R,T)=Q1,Q2,Qn 变为(R,T)=Q1,Q2,Qn （单状态） 表示当前状态为R

29、输入字符T时，下一状态可能是这些状态中的某一状态。542022-3-17怎样把NFA变为DFA?n定理3.6 NFA N=(K, , , S0, F) 对应DFA N=(K, , , S, F) 其中K是有穷非空状态集合，由k的一切子集组成；用Q1,Q2,Q表示K的元素， QiK(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的转换552022-3-17举例n例: 为NFA N=(S,A,B,Z, a,b, , S, Z)构造DFA. 设它对

30、应的DFA N=(K, a,b, , S, F)abSABabZbaaaanK=S (S,a)=A (S,b)=B K=S,A,B (A,a)=Z (A,b)=B (B,a)=AB (B,b)=Z K=S,A,B,Z,AB (Z,a)=AZ (Z,b)= (AB,a)=ABZ (AB,b)=BZK=S,A,B,Z,AB,AZ, BZ,ABZ(AZ,a)=AZ (AZ,b)=B (BZ,a)=ABZ (BZ,b)=Z(ABZ,a)=ABZ(ABZ,b)=BZ562022-3-17举例（续1） 输入输入状态状态abSABAZBBABZZAZABABZBZAZAZBBZABZZABZABZBZabS

31、ABabZbaaaa根据左边状态转根据左边状态转换矩阵，可以得换矩阵，可以得到到DFA N的状态的状态集合（表的左列集合（表的左列状态），即状态），即K=S,A,b,Z,AB,AZ,BZ,ABZ572022-3-17举例（续2）SBABABZAZBZAZbbbbbbbaaaaaaaa开始状态开始状态:S终止状态终止状态:Z,AZ,BZ,ABZl 根据上面状态转换矩阵，同时可以得到根据上面状态转换矩阵，同时可以得到N的映像函数，根的映像函数，根据该映像可以画出它的状态转换图（如下）。据该映像可以画出它的状态转换图（如下）。l 终态集合中的元素为：由新映像得到的状态、终态集合中的元素为：由新映像得

32、到的状态、 且这些状态且这些状态包含原包含原NFA N的终态集合中的状态。的终态集合中的状态。582022-3-17q1上上NFA M所能识别的字的全体是所能识别的字的全体是上的一个上的一个正规集正规集n证明：设转换图中每条弧上可用一个正规式作标证明：设转换图中每条弧上可用一个正规式作标记，让记，让NFA M的转换图中加进两节点的转换图中加进两节点X和和Y，形成，形成新的新的NFA M，从，从X画画弧指向原弧指向原NFA M的所有初的所有初态，从原态，从原NFA M的所有终态画的所有终态画弧指向弧指向Y，显然，显然L(M)=L(M) 然后，对然后，对NFA M消结，直至只剩下消结，直至只剩下X

33、、Y两两个结点为止，符上标记为一正规式。个结点为止，符上标记为一正规式。 所以，所以，NFA M识别的为一正规式；识别的为一正规式；NFA M识别的是一正规集。识别的是一正规集。 五、正规式和有限自动机的等价性592022-3-17q消结规则为消结规则为五、正规式和有限自动机的等价性602022-3-17q例例1.消结点消结点五、正规式和有限自动机的等价性q例例2.消结点消结点612022-3-17n2对于对于上的每个正规集上的每个正规集V，存在一个，存在一个上的上的DFA M，使得，使得V=L(M)。n证明：第一步，用替代办法构造一个证明：第一步，用替代办法构造一个NFA M，使使V=L(M

34、)，因为正规集，因为正规集V可用正规式可用正规式u来描述，来描述，而而u由一系列单个字符连接而成，故可用下述方由一系列单个字符连接而成，故可用下述方法分解之：法分解之：五、正规式和有限自动机的等价性SZe1e2SZe1e2SZe1|e2SZeSZ SZe1e2e622022-3-17n具体方法：构造如下转换图：具体方法：构造如下转换图： 逐步分解，便可得到一个逐步分解，便可得到一个NFA M，有，有L(u)=V=L(M)。n例例1n第二步，把第二步，把NFA M确定化为确定化为DFA M，得证。，得证。五、正规式和有限自动机的等价性632022-3-17举例n例：正则表达式(A|B)A|B|0

35、|1的转换系统的构造过程如下：SZ(A|B)A|B|0|1SZ(A|B)A|B|0|1SZAB A|B|0|1SZAB 10AB642022-3-17n概念概念1. 假设假设I是是NFA M的状态集的一个子集，的状态集的一个子集，我们定义我们定义-CLOSURE(I)为（为（I的的-闭包）。闭包）。n（1）若）若SI，则，则S-CLOSURE(I)n（2）若）若SI ，则从，则从s出发经过任意条出发经过任意条弧而达弧而达到的状态到的状态s，有，有s-CLOSURE(I)n例例1.五、正规式和有限自动机的等价性若若I=1, 3，则，则-CLOSURE(I) =1, 3, 2, 8652022-3

36、-17n概念概念2. 假定假定I是是M的状态子集，的状态子集，a是是中的中的字符，定义字符，定义Ia= -CLOSURE(J),其中其中J是是I中任意状态出发（跳过前面任意多条中任意状态出发（跳过前面任意多条弧），弧），经过一条经过一条a弧而能达到的状态结的全体。弧而能达到的状态结的全体。n例例2同例同例1 DFA， Ia=5,6,2n利用概念利用概念1和概念和概念2，便可把，便可把NFA确定化。确定化。五、正规式和有限自动机的等价性662022-3-17五、正规式和有限自动机的等价性n令令 ，构造一张如下的表，此表第，构造一张如下的表，此表第0列为状态子集列为状态子集I，第，第1至至m列分别

37、为状态子列分别为状态子集集 ，设第一行第，设第一行第0列为列为-CLOSURE(X),，其中，其中X为为NFA M的初态，求出的初态，求出第一个的第一个的 ，如果某个，如果某个Iai(i=1,m)未曾在第未曾在第0列中列出，则把列中列出，则把Iai补入状态子集集合补入状态子集集合I中，即列于第中，即列于第0列新的一行。列新的一行。n重复上述各步，直至所有行的重复上述各步，直至所有行的Iai(i=1,m)均均在第在第0列列I中出现过为止。这种循环必将在有限步中出现过为止。这种循环必将在有限步内中止。（因为内中止。（因为S是有限状态集，所以是有限状态集，所以S中状态的中状态的组合数也是有限的）组合

38、数也是有限的） 672022-3-17n显然，这张表可以看成一个状态转换表，显然，这张表可以看成一个状态转换表，也就是说可把也就是说可把I中每个子集看成一个状态，中每个子集看成一个状态，而状态转换表唯一地刻划了一个而状态转换表唯一地刻划了一个DFA M，其初态为该表的第其初态为该表的第1行第行第0列，含有原列，含有原NFA M终态的子集为新的终态。（证毕）终态的子集为新的终态。（证毕）n推论：一个子集是正规的，当且仅当它可推论：一个子集是正规的，当且仅当它可由一个由一个DFA（或（或NFA）所识别。）所识别。五、正规式和有限自动机的等价性682022-3-17n例：设计一个例：设计一个DFA

39、M，它识别二进制偶数（不以，它识别二进制偶数（不以0开头的无符号数）开头的无符号数）n解：解：n1写出正规式写出正规式 1（1|0）* 0 n2画出画出NFA M 细化为：细化为：3. 确定化为确定化为DFA M五、正规式和有限自动机的等价性692022-3-17五、正规式和有限自动机的等价性或：或：702022-3-17举例n正则表达式a|(a|b)a的相应转换系统与状态转换图的构造过程。ABa|(a|b)aAB(a|b)aaABDCa(a|b)a ABDCaa Eab(a)(b)(c)(d)开始状态：开始状态：A终止状态：终止状态：B712022-3-17前例续nNFA N = (A,C,

40、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)=DABDCaa EabACaaa b(e)(f)DaEab开始状态：开始状态：A, B终止状态：终止状态：B, C, D开始状态：开始状态：A, C, D终止状态：终止状态：A, C, D722022-3-17正则表达式的值与有穷自动机所接受的语言n定理3.11：上的NFA A所接受的字符串集合L(A)是上的某个正则表达式e的值，即L(A)=|e|。n例: NFA N相应的状态转换图为图(a)，则N所接受的语言为合成所得到的正则

41、表达式 (aa|bb)|(ab|ba)aa|bb(ab|ba) 的值。ZTab, baab, baaa, bbaa, bb(a)ZTab|baab|baaa|bbaa|bbXY (b)732022-3-17前例续n正则表达式与有穷状态自动机是等价的。Zaa|bbXY (ab|ba)aa|bb(ab|ba)XY(d)(c)(aa|bb)|(ab|ba)aa|bb(ab|ba)742022-3-17n字符串W把状态P和状态Q区别开：n等价状态：无法区别开的两个状态n基本思想：把状态集划分成互不相交的子集，使子集中的状态是等价的n化简DFA的算法步骤：划分状态集合并状态:取每组状态中的代表状态，删去

42、其他等价状态若有死状态或不可达状态，则把它们删去。n死状态：无法达到终止状态的非终止状态n不可达状态：不能从开始状态达到它的那些状态六、DFA的化简752022-3-17举例n划分状态集为4和 0,1,2,3n对于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,1,2n对于0,1,2:状态1在输入为b时的后继状态不在0,1,2中，因此划分为1和0,202314bbbbbaaaaan对于对于0,

43、2:对于相同输对于相同输入字符，该子集中每一状入字符，该子集中每一状态映像得到的后继状态都态映像得到的后继状态都相同，因此不再可划分相同，因此不再可划分n最后划分为：最后划分为： 4 3 1 0,2 六、DFA的化简762022-3-17举例（续1）n对于划分结果4, 3, 1, 0,2，把0,2合并为一个状态，其状态转换图如图：0213aaaabbb02314bbbbbaaaaab六、DFA的化简772022-3-17构造词法分析程序的方法n用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如，C语言直接编写词法分析程序。n利用自动生成工具LEX自动生成词法分析程序。3.4 词

44、法分析程序的实现词法分析程序的实现782022-3-17词法分析程序实现中要考虑的问题n确定实现词法分析程序的执行方式n确定属性字的结构n缓冲区预处理，超前搜索,n关键字的处理，符号表的实现n查找效率，算法的优化实现n词法错误处理3.4 词法分析程序的实现词法分析程序的实现792022-3-17属性字n词法分析程序对说明部分不做语义处理。n词法分析程序输出属性字一般采用下面的形式： （符号类，符号值）n属性字是符号的机内表示，有统一固定的长度3.4 词法分析程序的实现词法分析程序的实现802022-3-17源程序的输入n在内存开辟缓冲区，将程序文本放进该缓冲区n预处理：删除无用字符等n词法分析

45、程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。起始指针起始指针搜索指针搜索指针3.4 词法分析程序的实现词法分析程序的实现812022-3-17超前搜索n词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。3.4 词法分析程序的实现词法分析程序的实现822022-3-17关键字的识别与查表算法n对于关键字，先把它们当成标识符，然后去查关键字表。若在表中查到，则为关键字，获取相应的类别码；否则，认为是标识符。n查找算法：线性查找

46、折半查找Hash函数3.4 词法分析程序的实现词法分析程序的实现832022-3-17出错处理n对定义外的（如，对首字符不是字母的，不是数字的，不是运算符和分界符的）单词进行出错处理。3.4 词法分析程序的实现词法分析程序的实现842022-3-17使用状态图设计词法分析程序n多数语言的词法规则可用正则文法和正则表达式来描述。正则文法或正则表达式定义的语言都可以被状态图识别。n使用状态图设计词法分析程序的步骤如下：对程序设计语言的单词按类构造相应的状态图。（这里把关键字与标识符作为一类）合并各类单词的状态图，增加一个出错处理终态，构成一个识别该语言所有单词的状态转换图对状态图的每一个终点编一段

47、相应的子程序。3.4 词法分析程序的实现词法分析程序的实现852022-3-17201字母字母|数字其它3456数字数字其它+-78*/9101113:;1617其它13=举例举例862022-3-17n本节讨论：本节讨论： 用正规式描述单词符号，并研究如何用正规式描述单词符号，并研究如何从正规产生识别这些单词符号的词法分析从正规产生识别这些单词符号的词法分析程序。程序。3.5 词法分析器的自动生成词法分析器的自动生成872022-3-17一、一、LEX语言语言n一个一个LEX语言程序经过编译后得到的结果程序，语言程序经过编译后得到的结果程序，其作用相当于一个其作用相当于一个DFA，可用来识别

48、和产生单词，可用来识别和产生单词也就是说其功能即为一个词法分析器。也就是说其功能即为一个词法分析器。 882022-3-17n一个一个LEX源程序包括两部分：辅助定义式和识别规则源程序包括两部分：辅助定义式和识别规则n1、辅助定义式、辅助定义式 D1R1 DnRn 其中其中Ri为正规式，只允许出现为正规式，只允许出现上字符上字符D1,Di-1；Di为这个正规式为这个正规式Ri的简名的简名n例例1LetterA|B|Z Digit 0|1|9 Id Letter(Letter|Digit)*. . . .892022-3-17n2.识别规则识别规则 P1A1 . . . PmAmn其中，其中，P

49、i称为词形，为正规式称为词形，为正规式(D1,Dm) Ai称为词形称为词形Pi的动作（程序）的动作（程序）n显然：一个显然：一个LEX源程序产生的词法分析器只能识源程序产生的词法分析器只能识别形如别形如Pi的单词。的单词。902022-3-17二、二、LEX的实现的实现nLEX编译程序的目的是把一个编译程序的目的是把一个LEX程序改造为一个词程序改造为一个词法分析器法分析器L，这个词法分析器，这个词法分析器L将象自动机一样工作。将象自动机一样工作。n1词法分析器词法分析器L的工作方法的工作方法 L逐个地扫描输入串的每个字符，寻找一个最大逐个地扫描输入串的每个字符，寻找一个最大的子串匹配某个的子串匹配某个Pi（即：当输入串已匹配某个词形（即：当输入串已匹配某个词形时，并不立即返回，而是沿着此道路继续前进，直时，