第4章词法分析优秀课件.ppt-淘文阁

资源描述

《第4章词法分析优秀课件.ppt》由会员分享，可在线阅读，更多相关《第4章词法分析优秀课件.ppt（147页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第4章章词法分析词法分析第1页，本讲稿共147页第第3章教学内容章教学内容词法分析的任务；单词，单词的分类，单词的输出形式单词的描述工具：正规文法；正规式；有穷自动机。词法分析程序的自动构造原理：正规式到有穷自动机的转换算法。如何设计和实现词法分析程序。第2页，本讲稿共147页一、词法分析的任务一、词法分析的任务人们要理解一篇文章或一句话，首先必须了解人们要理解一篇文章或一句话，首先必须了解这篇文章或这句话的结构，文章包含哪些段落，每这篇文章或这句话的结构，文章包含哪些段落，每个段落包含哪些句子，每个句子又包含哪些词。这个段落包含哪些句子，每个句子又包含哪些词。这些过程对于人来说没有什么

2、难度，但对于计算机来些过程对于人来说没有什么难度，但对于计算机来说就不同了，输入一段话或一个程序，计算机得到说就不同了，输入一段话或一个程序，计算机得到的只是一串符号，要对这段话或这段程序进行分析，的只是一串符号，要对这段话或这段程序进行分析，计算机首先必须知道这段话由哪些词组成，或这个计算机首先必须知道这段话由哪些词组成，或这个程序由哪些单词符号构成。这个过程就是词法分析。程序由哪些单词符号构成。这个过程就是词法分析。第3页，本讲稿共147页识别单词识别单词词法分析的任务是：从左到右逐个字符地对源程序进行扫描和分解，根据语言的词法规则识别出一个个的单词符号。词法分析是编译的基础。执行词法分析

3、的程序就是词法分析器(扫描器)，其功能是输入源程序，输出单词符号。第4页，本讲稿共147页词法分析程序的主要任务：扫描源程序，识别出单词其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，第5页，本讲稿共147页二、与语法分析程序的接口方式二、与语法分析程序的接口方式方式方式1：词法分析程序作为单独的程序，输：词法分析程序作为单独的程序，输入源程序，输出单词文件，提供给语法分入源程序，输出单词文件，提供给语法分析程序使用。析程序使用。方式方式2：词法分析程序作为语法分析程序的：词法分析程序作为语法分析程序的子程序，提供给语法分析程序调用，不产子程序，提供给语法分析程序调用

4、，不产生中间文件。生中间文件。第6页，本讲稿共147页字符串字符串表示的源表示的源程序程序词法分析词法分析程序程序字符语法分析语法分析程序程序取单词回送单词词法分析程序作为子程序词法分析程序作为子程序第7页，本讲稿共147页三、单词的分类三、单词的分类【单词】【单词】单词是语言中具有独立意义的最小语单词是语言中具有独立意义的最小语法单位，包括保留字、标识符、运算符、标法单位，包括保留字、标识符、运算符、标点符号和常量等。点符号和常量等。【例如】【例如】ab是表达式，不是单词。是表达式，不是单词。a,b是标识符，是运算符，都是单词。是标识符，是运算符，都是单词。第8页，本讲稿共147页程序设计

5、语言的单词符号一般可分成下列程序设计语言的单词符号一般可分成下列5种：种：关关键键字字(基基本本字字，保保留留字字)：具具有有固固定定意意义义的的标标识识符符，如如PASCAL语言中的语言中的begin,end,if和和while等。等。标标识识符符:用用来来表表示示各各种种名名字字，如如常常量量名名、变变量量名名和和过过程程名名等。等。常常数数:各各种种类类型型的的常常数数，如如25，3.1415，TRUE和和“ABC”等。等。运算符运算符:如如+，*，=j)i-;while(i=j)i-;经词法分析器处理后转换的单词序列为：经词法分析器处理后转换的单词序列为：while ,-(,-id i

6、d的种别码的种别码,指向指向i i的符号表项的指针的符号表项的指针 =的种别码的种别码,-,-id ),-id -,-;,-第14页，本讲稿共147页四、单词的三种描述工具四、单词的三种描述工具单词有三种描述工具：单词有三种描述工具：正规文法正规文法正规式正规式有穷自动机有穷自动机第15页，本讲稿共147页1.正规文法正规文法正规文法的形式：正规文法的形式：右线性文法：右线性文法：AaB或或Aa 其中，其中，A、B为单个的非终结符，为单个的非终结符，a为单个的终结为单个的终结符。符。第16页，本讲稿共147页标识符的文法标识符的文法PASCAL语言中的标识符是字母开头，后跟字母数字串。设l表示

8、它们可以由如下规则描述：无符号数d余留无符号数|.十进小数|e指数部分余留无符号数d余留无符号数|.十进小数|e指数部分|十进小数d余留十进小数余留十进小数e指数部分|d余留十进小数指数部分d余留整指数|s整指数整指数d余留整指数余留整指数d余留整指数|其中s表示正或负号(+，-)，d表示09中的任一数字。无符号实数的文法无符号实数的文法第19页，本讲稿共147页程序设计语言中的其它单词的文法非常简单：运算符+|-|*|/|=|界符，|；|(|)|其它的文法其它的文法第20页，本讲稿共147页2、正规式、正规式正规表达式（regular expression）是说明单词的模式(pattern)

9、的一种重要的表示法（记号），是定义正规集的工具。正规式也称正则表达式，也是表示正规集的数学工具。第21页，本讲稿共147页正规式的递归定义正规式的递归定义是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为；是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为；aVaVT T是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为aa；设设e e1 1和和e e2 2分别是表示的正规集分别是表示的正规集L(eL(e1 1)和和L(eL(e2 2)的正规式的正规式,则：则：a)a)e e1 1|e|e2 2是正规式是正规式,表示的正规集为表示的正规集为L(eL

10、(e1 1)L(e)L(e2 2););b)b)e e1 1e e2 2是正规式是正规式,表示的正规集为表示的正规集为 L(e L(e1 1)L(e)L(e2 2););c)c)e e1 1*是正规式是正规式,表示的正规集为表示的正规集为(L(e(L(e1 1)*。第22页，本讲稿共147页三种运算符规定运算符的优先顺序为：规定运算符的优先顺序为：*|。正规式定义中的正规式定义中的“|”读为读为“或或”（也（也有使用有使用“+”代替代替“|”的）；的）；“”读读为为“连接连接”；“*”读为读为“闭包闭包”（即，（即，任意有限次的自重复连接）。任意有限次的自重复连接）。连接符连接符“”一般可省略

11、不写。一般可省略不写。“*”、“”和和“|”都是左结合的。都是左结合的。第23页，本讲稿共147页示例示例=a，b 上的正规式和相应的正规集如下：正规式正规集a aabab=a,bab a b=ab(ab)(ab)a,ba,b=aa,ab,ba,bba a =,a,aa,任意个a的串 =a n|n 0ba b a =ba n|n 0a|ba a,b,ba,baa,baaa,第24页，本讲稿共147页示例示例正规式正规集(ab)a,b =,a,b,aa,ab 所有由a 和b组成的串(ab)abb 所有结尾是abb的任意a和b的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继

12、的b组成的串第25页，本讲稿共147页描述单词的正规式描述单词的正规式程序设计语言的单词都能用正规式来定义。Pascal语言的标识符的正规式为：字母(字母|数字)*或写作 l(l|d)*无符号整数的正规式为：d*d=d+=dd*无符号实数的正规式为：d*(dd*|)(e(+|-|)dd*|)运算符的正规式为：|*|/|(|)|第26页，本讲稿共147页正规式等价正规式等价若两个正规式e1和e2所表示的正规集相同,即L(e1)=L(e2),则e1和e2等价,记为e1=e2。e1=ab，e2=ba，显然等价；e1=b(ab),e2=(ba)b均为babababababab，等价；e1=(ab),

13、e2=(ab)均表示由a和b组成的任意的符号串，所以等价。第27页，本讲稿共147页正规式的性质正规式的性质设设r,s,t为正规式，正规式服从的代数规律有为正规式，正规式服从的代数规律有1.r s=s r“或或”服从交换律服从交换律2.r(s t)=(r s)t“或或”的可结合律的可结合律3.(rs)t=r(st)“连连接接”的的可可结结合合律律4.r(s t)=rs rt (s t)r=sr tr分配律分配律 5.r=r,r=r 是是“连连接接”的的恒恒等等元元素素零一律零一律6.r =r 的幂等律的幂等律第28页，本讲稿共147页3、有穷自动机、有穷自动机FA有穷自动机(也称有限自动机)

14、作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有有穷穷自自动动机机分分为为两两类类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。第29页，本讲稿共147页有穷自动机的模型有穷自动机的模型有穷自动机FA是具

15、有离散输入输出系统的数学模型。系统的状态概括了对过去输入处理情况的信息。系统只需要根据当前所处的状态和面临的输入就可以决定系统的后继行为。每当系统出来了当前的输入后，系统的内部状态也将发生变化。例如：电梯控制装置就是有穷系统的典型。第30页，本讲稿共147页19481948年，由神经物理学家年，由神经物理学家MeCulochMeCuloch和和PittsPitts首首先提出先提出FAFA模型。模型。a1a2a3a4 an#有有穷穷控控制制器器输入带输入带有穷控制器控制读头从左有穷控制器控制读头从左向右逐个扫描并读入输入向右逐个扫描并读入输入符号，并且根据控制器的符号，并且根据控制器的当前

16、状态和当前输入符号当前状态和当前输入符号控制转入下一个状态。控制转入下一个状态。读头读头第31页，本讲稿共147页接收方式接收方式FA在初始状态下开始读入第一个输入符。FA接收输入串：终态方式。若读头在输入带上最后一个符号时，恰好进入某个终止状态，则宣布接收该输入串；否则，不接收。第32页，本讲稿共147页确定的有穷自动机DFA【DFA定义】一个确定的有穷自动机(DFA)M是一个五元组：M=（S，f，s0，Z），其中：S是一个有穷状态集，它的每个元素称为一个状态；是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表；f是状态转换函数，是定义在SS上的单值单值映射，即若 f（

17、q1，a）=q2，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2，q2称作q1的后继状态；s0 S是唯一唯一的初态；Z S是一个终态集，终态也称可接受状态或结束状态。第33页，本讲稿共147页示例【例【例1】DFA M=(0,1,2,3,a,b,f,0,3)，其中：，其中：f（0,a)=1 f（0,b)=2 f（1,a)=3 f（1,b)=2 f（2,a)=1 f（2,b)=3 f（3,a)=3 f（3,b)=3第34页，本讲稿共147页状态转换矩阵DFA可以用一个矩阵表示可以用一个矩阵表示:行行:表示状态表示状态q;列列:表示输入字符表示输入字符a;矩矩阵阵元元素素：表表示示f(

18、q,a)的的值值,即即在在q状态下读入输入符a时应转换到的下一个状态。ab012132213333状态输入符第35页，本讲稿共147页状态转换图DFA也可以表示成一张（确定的）状态也可以表示成一张（确定的）状态转换图：转换图：结点：表示状态，用圆圈圈起来；结点：表示状态，用圆圈圈起来；箭弧箭弧：表示状态转移的方向；：表示状态转移的方向；f(q1,a)q2：状态状态初态初态终态终态 q1 q2a第36页，本讲稿共147页b0123aaaba，bbDFA：第37页，本讲稿共147页串串为为DFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存在，若存在一条从初态结点到某一终态

19、结点的通一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符路，且这条通路上所有箭弧的标记符连接成的字符串等于连接成的字符串等于，则称，则称串串为为DFA M所识别所识别（读出或接受）。（读出或接受）。若若M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则为则为空字空字可为可为M所识别所识别。第38页，本讲稿共147页示例示例例1中串abaa的识别路径为：b0123aaaba，bb0a1b2a1a3第39页，本讲稿共147页扩充转换函数扩充转换函数f若有：f（q1，a1）=q2f（q2，a2）=q3f（q3，a3）=q4f（qn，an）=qn+1则可记为：f(q1，a

20、1 a2an)=qn1第40页，本讲稿共147页DFA M所能识别的语言集DFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若DFA M=（S，f，s0，Z），则有：L(M)|f(s0，)q，q Z 第41页，本讲稿共147页示例示例例1中的DFA M所识别的语言集L(M)为在a,b上所有含相继两个a或相继两个b的字符串。L(M)(a|b)*(aa|bb)(a|b)*b0123aaaba，bb第42页，本讲稿共147页标识符的标识符的DFA标识符e2f3的识别路径为：0e121f1310字母字母1字母或数字字母或数字中间状态第43页，本讲稿共147页无符号整数的无符号整数

21、的DFA无符号整数0123的识别路径为：0011121310数字数字1 数字数字第44页，本讲稿共147页无符号实数的无符号实数的DFA无符号实数3.8e+9的识别路径为：701346527dddddddee+7031.283e4+596第45页，本讲稿共147页不确定的有穷自动机NFA【NFA定义】不确定的有穷自动机NFA M是一个五元组：M=（S，f，S0，Z），其中：S是有穷状态集；是有穷输入字母表；f是状态转换函数，是定义在S2S上的多值映射，即若 f（q1，a）=q2，q3，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2和q3状态；S0 S是初态集；Z S是一个终态集。第

22、46页，本讲稿共147页示例【例【例2】NFA M=(1,2,3,a,b,f,1,3,2)，其中：，其中：f(1,a)=3 f(1,b)=1,2 f(2,a)=f(2,b)=3 f(3,a)=f（3,b)=2状态转换矩阵为：状态转换矩阵为：ab131,22332状态输入符第47页，本讲稿共147页NFA的状态转换图1a32bbbb第48页，本讲稿共147页串串为为NFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存在一，若存在一条从初态结点到某一终态结点的通路，条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成且这条通路上所有箭弧的标记符连接成的字符串

23、等于的字符串等于，则称，则称串串为为NFA M所所识别识别（读出或接受）。（读出或接受）。第49页，本讲稿共147页示例示例例2中串bab的识别路径为：1b1a3b21a32bbbb第50页，本讲稿共147页NFA M所能识别的语言集NFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若NFA M=（S，f，S0，Z），则有：L(M)|f(q1，)q2，q1 S0,q2 Z 第51页，本讲稿共147页示例示例例2中的NFA M所识别的语言集为:L(M)b*(b|ab)(bb)*1a32bbbb第52页，本讲稿共147页讨论注意注意DFA与与NFA的异同点。的异同点。DFA

24、是是NFA的特例。的特例。对于每个对于每个NFA M都一定存在一个都一定存在一个DFA M，使，使L(M)=L(M)。即：对每个即：对每个NFA M存在着与之等价的存在着与之等价的DFA M。与某一与某一NFA等价的等价的DFA不唯一。不唯一。第53页，本讲稿共147页标识符的标识符的NFAI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母字母数字IB,FBB,F B,FF第54页，本讲稿共147页标识符的标识符的NFA标识符e2f3的识别路径为：IeB2BfB3FI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母第55页，本讲稿共147页五、词法分析器的自动生成原理五

25、、词法分析器的自动生成原理正规式NFA转换DFA确定化化简最小DFA第56页，本讲稿共147页1.1.正规式 NFA对于上的一个正规式r，可以构造一个上的NFA M，使得L(M)=L(r)。转换第57页，本讲稿共147页构造方法构造方法引进初始结点X和终态结点Y，把正规式r表示成拓广转换图，如下所示：分析正规式r的语法结构，使用如下规则为r中的每个基本符号构造NFA。Xr Y第58页，本讲稿共147页转换规则转换规则(a)对于正规式，所构造的NFA为：(b)对于正规式，所构造的NFA为：(c)对于正规式a，a，所构造的NFA为：X Y X Y Xa Y第59页，本讲稿共147页若r是由上的正

26、规式r1，r2为复合而成的正规式，则按如下转换规则进行转换：(a)对正规式r1 r2，所构造的NFA如下：(b)对正规式r1|r2，所构造的NFA如下：Xr1 Y 1r2 Xr1 Yr2第60页，本讲稿共147页(c)对正规式r1*，所构造的NFA如下：r1 X Y 1第61页，本讲稿共147页整个转换过程中，可用X表示初态，Y表示终态，所有新结点均采用不同的名字标记，可依次用1、2、3等。第62页，本讲稿共147页示例示例【例3】构造正规式r1 01*的NFA。X01*Y X0 Y 11*X0 11 Y 2 第63页，本讲稿共147页2.NFA DFA从NFA的矩阵表示中可以看出，表项通常是

27、多个状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每的每一个状态对应一个状态对应NFA的一组状态。的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。确定化方法：状态子集法。确定化第64页，本讲稿共147页状态子集状态子集【状态子集状态子集I I的的-闭包：闭包：-CLOSURE(I)-CLOSURE(I)】a a)若若q qI I，则，则q q-CLOSURE-CLOSURE（I I）；）；b)b)若若q qI I，那那么么从从q q出出发发经经任任意意条条弧弧而而能能到到达达的的任任何何状状态态

28、 qq都都属属于于_CLOSURE_CLOSURE（I I）；）；【状态子集【状态子集I Ia a=_CLOSURE(J)=_CLOSURE(J)】a a，I是状态子集，是状态子集，J J是那些可从是那些可从I I中的某一状中的某一状态结点出发经过一条态结点出发经过一条a a弧而到达的状态结弧而到达的状态结点的全体。点的全体。第65页，本讲稿共147页示例示例I=1,-closure(I)=1,2；Ia 1 a 5,6,2,3,8,4,7;I=5,-closure(I)=5,6,2；Ia 5 a 3,8;1,2a=-closure(5,3,4)=2,3,4,5,6,7,8；12534687

29、aaa第66页，本讲稿共147页示例示例【例【例4】画出正规式：】画出正规式：（a|b)*(aa|bb)(a|b)*对应的对应的NFA。4Y32615Xaaaabbbb第67页，本讲稿共147页NFA确定化为确定化为DFA:状态子集法状态子集法从从NFA M=(S,f,S0,Z)构造等价的构造等价的DFA M(K,f,k0,F)的基本方法是：的基本方法是：1.求求DFA的初态的初态k0 -closure(NFA的初态的初态)-closure(X)X，5，1第68页，本讲稿共147页2.求求DFA M 的状态集的状态集K中的其它状态以及中的其它状态以及状态转换函数状态转换函数f,用求用求Ia，I

30、b的方法：的方法：设设I k0 f(k0，a)Ia k0 af(k0，b)Ib k0 b因为因为a,b,所以只需求所以只需求Ia，Ib即可。即可。子集子集Ia，Ib求出后得到一个新状态就添加求出后得到一个新状态就添加到到DFA的状态集的状态集K中；如此继续，直至不中；如此继续，直至不再产生新的状态为止。即可得到再产生新的状态为止。即可得到DFA的的全部状态全部状态K和状态转换函数和状态转换函数f。第69页，本讲稿共147页示例示例对初态对初态k0求其求其Ia，Ib子集：子集：f(k0，a)Ia X，5，1 a 5，3，1 f(k0，b)Ib X，5，1 b 5，4，1所得所得5，3，1与与5，

31、4，1均是异于均是异于k0的新状态，的新状态，因此将它们加入因此将它们加入DFA的状态集的状态集K中。中。再继续对新状态再继续对新状态5，3，1 与与5，4，1利用求利用求Ia，Ib的方法求其它的状态。的方法求其它的状态。第70页，本讲稿共147页示例示例对状态对状态5，3，1求其求其Ia，Ib子集：子集：f(5，3，1，a)5，3，1 a 5，3，1，2，6，Y f(5，3，1，b)5，3，1 b 5，4，1所得所得5，3，1，2，6，Y 加入加入DFA的状的状态集态集K中。中。第71页，本讲稿共147页示例示例对状态对状态5，4，1求其求其Ia，Ib子集：子集：f(5，4，1，a)5，4，

32、1 a 5，3，1 f(5，4，1，b)5，4，1 b 5，4，1，2，6，Y所得所得5，4，1，2，6，Y 加入加入DFA的状的状态集态集K中。中。如此继续，将此过程用状态转换矩阵记录如此继续，将此过程用状态转换矩阵记录下来：下来：第72页，本讲稿共147页示例示例 I Ia Ib X,5,1 5,3,1 5,4,1 5,3,1 5,3,1,2,6,Y 5,4,1 5,4,1 5,3,1 5,4,1,2,6,Y5,3,1,2,6,Y 5,3,1,2,6,Y 5,4,1,6,Y5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,4,1,6,Y 5,3,1,6,Y 5,4,1,

33、2,6,Y 5,3,1,6,Y 5,3,1,2,6,Y 5,4,1,6,Y第73页，本讲稿共147页示示例例对上面的表中的状态子集重新命名后的状态转换矩阵对上面的表中的状态子集重新命名后的状态转换矩阵 a b 0 1 2 1 3 2 2 1 5 3 3 4 4 6 5 5 6 5 6 3 4 第74页，本讲稿共147页如何确定如何确定DFA的终态集的终态集包含原NFA的终态的子集都是DFA的终态。例如：3，4，5，6均是终态。第75页，本讲稿共147页所得所得DFA如下：如下：3521460baaaaabbbbbaab第76页，本讲稿共147页3.DFA的化简的化简确定有穷自动机M的化简是指：

34、寻找一个状态数比DFA M少的DFA M，使得L(M)L(M)。一个有穷自动机是化简了的，即是它没有多余状态，并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。第77页，本讲稿共147页多余状态多余状态所谓有穷自动机的多余状态，是指这样的状态：从有穷自动机的初态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。第78页，本讲稿共147页等价和可区别的等价和可区别的等价：如果有穷自动机DFA M的两个状态s和t能够识别同样的符号串，则称状态s和t等价。可区别的：如果有穷自动机DFA M的两个状态s和t不

35、等价，则称这两个状态是可区别的。【例如】终态与非终态是可区别的。第79页，本讲稿共147页 DFADFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFADFA最小状态最小状态DFA的含义的含义:没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状态s和和t可区别：不满足可区别：不满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s出发读入某个出发读入某个a a和从和从 t出发出发读入某个读入某个a到达的状态等价。到达的状态等价。第80页，本讲稿共147页DFA的最小化过程：分割法的最小化过程：分割

36、法确定有限自动机确定有限自动机M的化简的过程也就是的化简的过程也就是其状态最少化过程：其状态最少化过程：一个一个 DFA M的状态最少化过程是指将的状态最少化过程是指将 M的状态集分割成一些不相交的子集，使的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。个代表，同时消去其它等价状态。第81页，本讲稿共147页例如：将前面所得的例如：将前面所得的DFA化简化简3521460baa

37、aaabbbbbaab第82页，本讲稿共147页示例示例DFA的状态集的状态集k0，1，2，3，4，5，61.首先把首先把M的状态的状态K分为两组：分为两组：终态集终态集K1=3，4，5，6非终态集非终态集K2=0，1，2显然显然K1与与K2不等价。不等价。第83页，本讲稿共147页2.然后，试图然后，试图K1，K2在中寻找一个子集和在中寻找一个子集和一个输入符号使得这个子集中的状态可一个输入符号使得这个子集中的状态可区别的；若可区别，则再分割；继续，区别的；若可区别，则再分割；继续，一直到不能再分割为止。一直到不能再分割为止。讨论终态集讨论终态集K1=3，4，5，6 是否可分割：是否可分割：

38、3，4，5，6a K1 3，4，5，6b K1 所以状态所以状态3，4，5，6均等价，因此均等价，因此K1不能再分割。不能再分割。第84页，本讲稿共147页讨论非终态集讨论非终态集K2=0，1，2 是否可分割：是否可分割：0，1，2a 1，3 它既不属于它既不属于K20，1，2，也不属于，也不属于K13，4，5，6，因此应将其一分为二。，因此应将其一分为二。0，2a 1 1a 3 由于由于1态经态经a弧到达弧到达3态，而且状态态，而且状态0，2经经a弧到达弧到达1态，所以将态，所以将1状态分出来，形成状态分出来，形成 K211 K220，2第85页，本讲稿共147页再讨论再讨论K22=0，2

39、是否可分割：是否可分割：0，2b 2，5 而它未包括在而它未包括在K1，K21与与K22中，故中，故0，2应一分为二：应一分为二：K2210 K2222所以所以K分为四组分为四组3，4，5，6，0，1，2。每个组都不可再分。每个组都不可再分。第86页，本讲稿共147页3.最后，令状态最后，令状态3代表代表3，4，5，6。把原。把原来到达来到达4，5，6的弧都导入的弧都导入3，并删除，并删除4，5，6状态。即可得到化简后的状态。即可得到化简后的DFA。3210aaabbb,ba第87页，本讲稿共147页示例示例【例【例5】正规式】正规式r(a|b)*abb1.由正规式由正规式r构造构造NFA为：

40、为：Y34bba21Xab第88页，本讲稿共147页2.NFA确定化为DFA：初态-closure(X)X，1，2IIaIb初态X,1,2X,1,2 a=1,2,3X,1,2b=1,21,2,31,2,31,2,41,21,2,31,21,2,41,2,31,2,Y终态终态1,2,Y1,2,31,2第89页，本讲稿共147页重命名为：重命名为：ab012113212314412状态输入符第90页，本讲稿共147页DFA的状态转换图为：的状态转换图为：42ab310abbaabba第91页，本讲稿共147页3.DFA的化简：的化简：DFA的状态集的状态集K0，1，2，3，41)首先把状态首先把状

41、态K分为可区别的两组状态集：分为可区别的两组状态集：终态集终态集K1=4非终态集非终态集K2=0，1，2，3第92页，本讲稿共147页2)讨论K2=0，1，2，3能否分割：能否分割：0，1，2，3a 1 0，1，2，3b 2，3，4而 3b 4 K1 0，1，2b 2，3 K2所以可分割为K21=0，1，2 K22=3第93页，本讲稿共147页3)讨论K21=0，1，2能否分割：能否分割：0，1，2a 1而 0，2b 2 K21 1b 3 K22所以可分割为K211=0，2 K212=1第94页，本讲稿共147页4)讨论讨论K211=0，2能否分割：能否分割：0，2a 1 0，2b 2所以不可

42、分割，所以不可分割，0状态与状态与2状态等价，不状态等价，不再分割。再分割。所以最终将状态集所以最终将状态集K分割为分割为0，2，1，3，4，一共四组。，一共四组。第95页，本讲稿共147页最后，令状态最后，令状态0代表代表0，2。把原来到达。把原来到达2的弧都导入的弧都导入0，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。4ab310abaabb第96页，本讲稿共147页示例示例【例【例6】标识符的正规式】标识符的正规式r为为l(l|d)*1.由正规式由正规式r构造构造NFA为：为：Y1Xl2ld第97页，本讲稿共147页2.NFA确定化为DFA：初态-closure(

43、X)XIIlId初态XX l=1,2,YXd=终态终态1,2,Y2,Y2,Y终态终态2,Y2,Y2,Y第98页，本讲稿共147页重命名为：重命名为：ld01122222状态输入符第99页，本讲稿共147页DFA的状态转换图为：的状态转换图为：2d0ll1l，d第100页，本讲稿共147页3.DFA的化简：的化简：DFA的状态集的状态集K0，1，21)首先把状态首先把状态K分为可区别的两组状态集：分为可区别的两组状态集：终态集终态集K1=1，2 非终态集非终态集K2=0第101页，本讲稿共147页2)讨论K1=1，2能否分割：能否分割：1，2a 2 1，2b 2所以不可分割，所以不可分割，1状态

44、与状态与2状态等价，不状态等价，不再分割。再分割。所以最终将状态集所以最终将状态集K分割为分割为0，1，2，一共两组。，一共两组。第102页，本讲稿共147页最后，令状态最后，令状态1代表代表1，2。把原来到达。把原来到达2的弧都导入的弧都导入1，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。0l1l，d第103页，本讲稿共147页六、正规文法六、正规文法有穷自动机有穷自动机对于正规文法G和有穷自动机FA M，如果L(G)=L(M),则称G和M等价。转换第104页，本讲稿共147页右线性文法的转换方法右线性文法的转换方法引入一个终态F。设右线性文法G(VN,VT,P,S

45、),则相应的自动机为M(VN F,VT,f,S,F)。状态转换函数f由以下规则定义：1.P中形如AaB的产生式，则有f(A,a)=B;2.P中形如Aa的产生式，则有f(A,a)=F;3.对VT中的每个a，都有f(F,a)=。第105页，本讲稿共147页示例示例【例7】描述标识符的右线性文法为：G11I:I lB|l BlB|dB|l|d第106页，本讲稿共147页转换为转换为NFA引入一个终态引入一个终态F，则相应的，则相应的NFA为：为：M(I,B,F,l,d,f,I,F),其中其中f可确定为：可确定为：由由I lB 可得可得 f(I，l)B 由由I l 可得可得 f(I，l)F 由由B l

46、B 可得可得 f(B，l)B 由由B dB 可得可得 f(B，d)B 由由B l 可得可得 f(B，l)F由由B d 可得可得 f(B，d)F 第107页，本讲稿共147页用状态转换图表示为：用状态转换图表示为：FIlBl，dldl第108页，本讲稿共147页初态-closure(I)IIIlId初态II l=B,FId=终态终态B,FB,FB,F将此将此NFA确定化为确定化为DFA第109页，本讲稿共147页重命名为：重命名为：ld01111状态输入符0l1l，dDFA即为：即为：第110页，本讲稿共147页上述上述DFA已经是最小的已经是最小的DFA，不需要，不需要再化简。再化简。因为如果

47、要进行化简，则首先要把因为如果要进行化简，则首先要把DFA的状态集分为可区别的两组状态集：的状态集分为可区别的两组状态集：终态集终态集K1=1非终态集非终态集K2=0而它们无法再分割，所以不需要化简，而它们无法再分割，所以不需要化简，此此DFA即是最简即是最简DFA。第111页，本讲稿共147页七、设计词法分析程序七、设计词法分析程序设计词法分析程序的途径有两种:一种是手工编写：直接依据词法规则编写程序。一种是自动生成：利用词法自动生成工具产生词法分析程序，依据的原理就是将正规表达式转换成等价的有限自动机，要分三步：正规式NFA转换DFA确定化化简最小DFA第112页，本讲稿共147页1.利用

48、利用DFA设计词法分析器设计词法分析器为了构造词法分析器，要研究构词法，每种单词类的结构模式以及识别它的数学模型有限自动机FA。它的模拟程序可以作为词法分析器的控制程序。正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序。第113页，本讲稿共147页识识别别某某语语言言单单词词的的状状态态转转换换图图第114页，本讲稿共147页实现状态转换图的方法实现状态转换图的方法根据画出的状态转换图（识别单词的）构造词法分析程序：每个状态对应一小段程序，完成到

49、达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。第115页，本讲稿共147页一般规则一般规则1.对于不含回路的分叉结点，对应多分支语句：IKJM字母数字第116页，本讲稿共147页分叉结点I对应四分支程序段：GetChar();if(Isletter()状态J对应的程序段else if(Isdigit()状态K对应的程序段else if(ch+)状态M的对应程序段else 错误处理遇到“错误处理”：现行状态I和当前所面临的输入串不匹配。第117页，本讲稿共147页一般规则一般规则2.对于含回路的状态结点,对应循环语句：IJ字母或数字其它第118页，本讲稿共147页含回路的结点I

50、对应while循环语句：GetChar();while (Isletter()or Isdigit()相应处理GetChar();状态J对应的程序段第119页，本讲稿共147页一般规则一般规则3.终态结点对应一个形如return(code,value)的语句(即单词的二元组输出形式)：遇到“非符号”：表示多读入一个字符，输入指针应回退一格。如下图所示。I非J第120页，本讲稿共147页识识别别某某语语言言单单词词的的状状态态转转换换图图第121页，本讲稿共147页构造上述语言的词法分析器,显然对应多分支语句：scaner()token=NULL;GetChar();if(Isletter(c

展开阅读全文