第4章词法分析精选文档.ppt

《第4章词法分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第4章词法分析精选文档.ppt（147页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

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

6、：while ,-(,-id id的种别码的种别码,指向指向i i的符号表项的指针的符号表项的指针 =的种别码的种别码,-,-id ),-id -,-;,-本讲稿第十四页，共一百四十七页四、单词的三种描述工具四、单词的三种描述工具单词有三种描述工具：单词有三种描述工具：正规文法正规文法正规式正规式有穷自动机有穷自动机本讲稿第十五页，共一百四十七页1.正规文法正规文法正规文法的形式：正规文法的形式：右线性文法：右线性文法：AaB或或Aa 其中，其中，A、B为单个的非终结符，为单个的非终结符，a为单个的终结为单个的终结符。符。本讲稿第十六页，共一百四十七页标识符的文法标识符的文法PASCAL语言中

7、的标识符是字母开头，后跟字母数字串。设l表示az中的任何一英文字母，d表示09中的任一数字。描述标识符的文法为：G11I:I lB|l BlB|dB|l|d注意：一般关键字（保留字）都是由字母构成，它是标注意：一般关键字（保留字）都是由字母构成，它是标识符集合的子集。识符集合的子集。本讲稿第十七页，共一百四十七页无符号整数的文法无符号整数的文法描述无符号整数的文法为：GD:D dD|d给出123的推导过程：D 1D 12D 123给出00123的推导过程：D 0D 00D 001D 0012D 00123描述整数的文法为：GN:N+D|D D dD|d本讲稿第十八页，共一百四十七页最复杂的一类

8、单词要属无符号实数了，比如25.55e+5和2.1，它们可以由如下规则描述：无符号数d余留无符号数|.十进小数|e指数部分余留无符号数d余留无符号数|.十进小数|e指数部分|十进小数d余留十进小数余留十进小数e指数部分|d余留十进小数指数部分d余留整指数|s整指数整指数d余留整指数余留整指数d余留整指数|其中s表示正或负号(+，-)，d表示09中的任一数字。无符号实数的文法无符号实数的文法本讲稿第十九页，共一百四十七页程序设计语言中的其它单词的文法非常简单：运算符+|-|*|/|=|界符，|；|(|)|其它的文法其它的文法本讲稿第二十页，共一百四十七页2、正规式、正规式正规表达式（regula

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

10、e|e2 2是正规式是正规式,表示的正规集为表示的正规集为L(eL(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)*。本讲稿第二十二页，共一百四十七页三种运算符规定运算符的优先顺序为：规定运算符的优先顺序为：*|。正规式定义中的正规式定义中的“|”读为读为“或或”（也（也有使用有使用“+”代替代替“|”的）；的）；“”读读为为“连接连接”；“*”读为读为“闭包闭包”（即，（即，任意有

11、限次的自重复连接）。任意有限次的自重复连接）。连接符连接符“”一般可省略不写。一般可省略不写。“*”、“”和和“|”都是左结合的。都是左结合的。本讲稿第二十三页，共一百四十七页示例示例=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,本讲稿第二十四页，共一百四十七页示例示例 正规式 正规集(ab)a,b =,a,b,aa,ab 所有由a 和b组成的串(ab)abb 所有结尾是

12、abb的任意a和b的串(ab)(aabb)(ab)上所有含有两个相继 的a或两个相继的b组成 的串本讲稿第二十五页，共一百四十七页描述单词的正规式描述单词的正规式程序设计语言的单词都能用正规式来定义。Pascal语言的标识符的正规式为：字母(字母|数字)*或写作 l(l|d)*无符号整数的正规式为：d*d=d+=dd*无符号实数的正规式为：d*(dd*|)(e(+|-|)dd*|)运算符的正规式为：|*|/|(|)|本讲稿第二十六页，共一百四十七页正规式等价正规式等价若两个正规式e1和e2所表示的正规集相同,即L(e1)=L(e2),则e1和e2等价,记为e1=e2。e1=ab，e2=ba，显

13、然等价；e1=b(ab),e2=(ba)b均为babababababab，等价；e1=(ab),e2=(ab)均表示由a和b组成的任意的符号串，所以等价。本讲稿第二十七页，共一百四十七页正规式的性质正规式的性质设设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

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

15、，确定的有穷自动机的化简等算法。本讲稿第二十九页，共一百四十七页有穷自动机的模型有穷自动机的模型有穷自动机FA是具有离散输入输出系统的数学模型。系统的状态概括了对过去输入处理情况的信息。系统只需要根据当前所处的状态和面临的输入就可以决定系统的后继行为。每当系统出来了当前的输入后，系统的内部状态也将发生变化。例如：电梯控制装置就是有穷系统的典型。本讲稿第三十页，共一百四十七页19481948年，由神经物理学家年，由神经物理学家MeCulochMeCuloch和和PittsPitts首先提出首先提出FAFA模型。模型。a1a2a3a4 an#有有 穷穷控控 制制 器器输入带输入带有穷控制器控制读头

16、从左有穷控制器控制读头从左向右逐个扫描并读入输入向右逐个扫描并读入输入符号，并且根据控制器的符号，并且根据控制器的当前状态和当前输入符号当前状态和当前输入符号控制转入下一个状态。控制转入下一个状态。读头读头本讲稿第三十一页，共一百四十七页接收方式接收方式FA在初始状态下开始读入第一个输入符。FA接收输入串：终态方式。若读头在输入带上最后一个符号时，恰好进入某个终止状态，则宣布接收该输入串；否则，不接收。本讲稿第三十二页，共一百四十七页确定的有穷自动机DFA【DFA定义】一个确定的有穷自动机(DFA)M是一个五元组：M=（S，f，s0，Z），其中：S是一个有穷状态集，它的每个元素称为一个状态；是

17、一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表；f是状态转换函数，是定义在SS上的单值单值映射，即若 f（q1，a）=q2，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2，q2称作q1的后继状态；s0 S是唯一唯一的初态；Z S是一个终态集，终态也称可接受状态或结束状态。本讲稿第三十三页，共一百四十七页示例【例【例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本讲稿第三十四页，共一百四十七页状态

18、转换矩阵DFA可以用一个矩阵表示可以用一个矩阵表示:行行:表示状态表示状态q;列列:表示输入字符表示输入字符a;矩矩阵阵元元素素：表表示示f(q,a)的的值值,即即在在q状态下读入输入符a时应转换到的下一个状态。ab012132213333状态输入符本讲稿第三十五页，共一百四十七页状态转换图DFA也可以表示成一张（确定的）状态也可以表示成一张（确定的）状态转换图：转换图：结点：表示状态，用圆圈圈起来；结点：表示状态，用圆圈圈起来；箭弧箭弧：表示状态转移的方向；：表示状态转移的方向；f(q1,a)q2：状态状态初态初态终态终态 q1 q2a本讲稿第三十六页，共一百四十七页b0123aaaba，b

19、bDFA：本讲稿第三十七页，共一百四十七页串串 为为DFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存在，若存在一条从初态结点到某一终态结点的通一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符路，且这条通路上所有箭弧的标记符连接成的字符串等于连接成的字符串等于，则称，则称串串 为为DFA M所识别所识别（读出或接受）。（读出或接受）。若若M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则为则为空字空字 可为可为M所识别所识别。本讲稿第三十八页，共一百四十七页示例示例例1中串abaa的识别路径为：b0123aaaba，bb0a1b2a1a3本讲稿

20、第三十九页，共一百四十七页扩充转换函数扩充转换函数f若有：f（q1，a1）=q2f（q2，a2）=q3f（q3，a3）=q4f（qn，an）=qn+1则可记为：f(q1，a1 a2an)=qn1本讲稿第四十页，共一百四十七页DFA M所能识别的语言集DFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若DFA M=（S，f，s0，Z），则有：L(M)|f(s0，)q，q Z 本讲稿第四十一页，共一百四十七页示例示例例1中的DFA M所识别的语言集L(M)为在a,b上所有含相继两个a或相继两个b的字符串。L(M)(a|b)*(aa|bb)(a|b)*b0123aaaba，bb

21、本讲稿第四十二页，共一百四十七页标识符的标识符的DFA标识符e2f3的识别路径为：0e121f1310字母字母1字母或数字字母或数字中间状态本讲稿第四十三页，共一百四十七页无符号整数的无符号整数的DFA无符号整数0123的识别路径为：0011121310数字数字1 数字数字本讲稿第四十四页，共一百四十七页无符号实数的无符号实数的DFA无符号实数3.8e+9的识别路径为：701346527dddddddee+7031.283e4+596本讲稿第四十五页，共一百四十七页不确定的有穷自动机NFA【NFA定义】不确定的有穷自动机NFA M是一个五元组：M=（S，f，S0，Z），其中：S是有穷状态集；是

22、有穷输入字母表；f是状态转换函数，是定义在S2S上的多值映射，即若 f（q1，a）=q2，q3，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2和q3状态；S0 S是初态集；Z S是一个终态集。本讲稿第四十六页，共一百四十七页示例【例【例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状态输入符本讲稿第四十七页，共一百四十七页NFA的状态转换图1a32bbbb本讲稿第四十八页，共一百四十七页串串 为为NFA

23、M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存在，若存在一条从初态结点到某一终态结点的通路，一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成且这条通路上所有箭弧的标记符连接成的字符串等于的字符串等于，则称，则称串串 为为NFA M所所识别识别（读出或接受）。（读出或接受）。本讲稿第四十九页，共一百四十七页示例示例例2中串bab的识别路径为：1b1a3b21a32bbbb本讲稿第五十页，共一百四十七页NFA M所能识别的语言集NFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若NFA M=（S，f，S0，Z），则有：L(M)|f(q

24、1，)q2，q1 S0,q2 Z 本讲稿第五十一页，共一百四十七页示例示例例2中的NFA M所识别的语言集为:L(M)b*(b|ab)(bb)*1a32bbbb本讲稿第五十二页，共一百四十七页讨论注意注意DFA与与NFA的异同点。的异同点。DFA是是NFA的特例。的特例。对于每个对于每个NFA M都一定存在一个都一定存在一个DFA M，使，使L(M)=L(M)。即：对每个即：对每个NFA M存在着与之等价的存在着与之等价的DFA M。与某一与某一NFA等价的等价的DFA不唯一。不唯一。本讲稿第五十三页，共一百四十七页标识符的标识符的NFAI字母字母B字母或数字字母或数字F字母或数字字母或数字字

25、母字母字母数字IB,FBB,FB,FF本讲稿第五十四页，共一百四十七页标识符的标识符的NFA标识符e2f3的识别路径为：IeB2BfB3FI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母本讲稿第五十五页，共一百四十七页五、词法分析器的自动生成原理五、词法分析器的自动生成原理正规式NFA转换DFA确定化化简最小DFA本讲稿第五十六页，共一百四十七页1.1.正规式 NFA对于上的一个正规式r，可以构造一个上的NFA M，使得L(M)=L(r)。转换本讲稿第五十七页，共一百四十七页构造方法构造方法引进初始结点X和终态结点Y，把正规式r表示成拓广转换图，如下所示：分析正规式r的语法结构，

26、使用如下规则为r中的每个基本符号构造NFA。Xr Y本讲稿第五十八页，共一百四十七页转换规则转换规则(a)对于正规式，所构造的NFA为：(b)对于正规式，所构造的NFA为：(c)对于正规式a，a，所构造的NFA为：X Y X Y Xa Y本讲稿第五十九页，共一百四十七页 若r是由上的正规式r1，r2为复合而成的正规式，则按如下转换规则进行转换：(a)对正规式r1 r2，所构造的NFA如下：(b)对正规式r1|r2，所构造的NFA如下：Xr1 Y 1r2 Xr1 Yr2本讲稿第六十页，共一百四十七页(c)对正规式r1*，所构造的NFA如下：r1 X Y 1本讲稿第六十一页，共一百四十七页整个转换

27、过程中，可用X表示初态，Y表示终态，所有新结点均采用不同的名字标记，可依次用1、2、3等。本讲稿第六十二页，共一百四十七页示例示例【例3】构造正规式r1 01*的NFA。X01*Y X0 Y 11*X0 11 Y 2 本讲稿第六十三页，共一百四十七页2.NFA DFA从NFA的矩阵表示中可以看出，表项通常是多个状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每的每一个状态对应一个状态对应NFA的一组状态。的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。确定化方法：状态子集法。确定化本讲稿第六十四页，共一百四十

28、七页状态子集状态子集【状态子集状态子集I I的的-闭包：闭包：-CLOSURE(I)-CLOSURE(I)】a a)若若q qI I，则，则q q-CLOSURE-CLOSURE（I I）；）；b)b)若若q qI I，那那么么从从q q出出发发经经任任意意条条弧弧而而能能到到 达达 的的 任任 何何 状状 态态 qq都都 属属 于于_CLOSURE_CLOSURE（I I）；）；【状态子集【状态子集I Ia a=_CLOSURE(J)=_CLOSURE(J)】a a，I是状态子集，是状态子集，J J是那些可从是那些可从I I中的某一状中的某一状态结点出发经过一条态结点出发经过一条a a弧而到

29、达的状态结弧而到达的状态结点的全体。点的全体。本讲稿第六十五页，共一百四十七页示例示例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；12534687aaa本讲稿第六十六页，共一百四十七页示例示例【例【例4】画出正规式：】画出正规式：（a|b)*(aa|bb)(a|b)*对应的对应的NFA。4Y32615Xaaaabbbb本讲稿第六十七页，共一百四十七页NFA确定化为确定化为DFA:状态子集法状态子集法从从NFA M=(S,f

30、,S0,Z)构造等价的构造等价的DFA M(K,f,k0,F)的基本方法是：的基本方法是：1.求求DFA的初态的初态k0 -closure(NFA的初态的初态)-closure(X)X，5，1本讲稿第六十八页，共一百四十七页2.求求DFA M 的状态集的状态集K中的其它状态以及中的其它状态以及状态转换函数状态转换函数f,用求用求Ia，Ib的方法：的方法：设设I k0 f(k0，a)Ia k0 af(k0，b)Ib k0 b因为因为a,b,所以只需求所以只需求Ia，Ib即可。即可。子集子集Ia，Ib求出后得到一个新状态就添加求出后得到一个新状态就添加到到DFA的状态集的状态集K中；如此继续，直至

31、不中；如此继续，直至不再产生新的状态为止。即可得到再产生新的状态为止。即可得到DFA的的全部状态全部状态K和状态转换函数和状态转换函数f。本讲稿第六十九页，共一百四十七页示例示例对初态对初态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，4，1均是异于均是异于k0的新状态，的新状态，因此将它们加入因此将它们加入DFA的状态集的状态集K中。中。再继续对新状态再继续对新状态5，3，1 与与5，4，1利用求利用求Ia，Ib的方法求其它的状态。的方法求其它的状态。本讲稿第七十页，共一百四十七页示例

32、示例对状态对状态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中。中。本讲稿第七十一页，共一百四十七页示例示例对状态对状态5，4，1求其求其Ia，Ib子集：子集：f(5，4，1，a)5，4，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中。中。如此继续，将此过程用状态转换矩阵记录如此继续，将此过程用状态转换矩阵记录下来：下来：本讲稿第七十

33、二页，共一百四十七页示例示例 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,2,6,Y 5,3,1,6,Y 5,3,1,2,6,Y 5,4,1,6,Y本讲稿第七十三页，共一百四十七页示示例例对上面的表中的状态子集重新命名后的状态转换矩阵对上面的表中的状态子集重新命名后的状态转换矩阵 a b 0 1 2 1 3 2

34、2 1 5 3 3 4 4 6 5 5 6 5 6 3 4 本讲稿第七十四页，共一百四十七页如何确定如何确定DFA的终态集的终态集包含原NFA的终态的子集都是DFA的终态。例如：3，4，5，6均是终态。本讲稿第七十五页，共一百四十七页所得所得DFA如下：如下：3521460baaaaabbbbbaab本讲稿第七十六页，共一百四十七页3.DFA的化简的化简确定有穷自动机M的化简是指：寻找一个状态数比DFA M少的DFA M，使得L(M)L(M)。一个有穷自动机是化简了的，即是它没有多余状态，并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之

35、等价的有穷自动机。本讲稿第七十七页，共一百四十七页多余状态多余状态所谓有穷自动机的多余状态，是指这样的状态：从有穷自动机的初态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。本讲稿第七十八页，共一百四十七页等价和可区别的等价和可区别的等价：如果有穷自动机DFA M的两个状态s和t能够识别同样的符号串，则称状态s和t等价。可区别的：如果有穷自动机DFA M的两个状态s和t不等价，则称这两个状态是可区别的。【例如】终态与非终态是可区别的。本讲稿第七十九页，共一百四十七页 DFADFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFADFA最小状态最小状态DFA的含义的含义

36、:没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状态s和和t可区别：不满足可区别：不满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s出发读入某个出发读入某个a a和从和从 t出发出发读入某个读入某个a到达的状态等价。到达的状态等价。本讲稿第八十页，共一百四十七页DFA的最小化过程：分割法的最小化过程：分割法确定有限自动机确定有限自动机M的化简的过程也就是的化简的过程也就是其状态最少化过程：其状态最少化过程：一个一个 DFA M的状态最少化过程是指将的状态最少化过程是指将 M的状态集分割成一些不相

37、交的子集，使的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。个代表，同时消去其它等价状态。本讲稿第八十一页，共一百四十七页例如：将前面所得的例如：将前面所得的DFA化简化简3521460baaaaabbbbbaab本讲稿第八十二页，共一百四十七页示例示例DFA的状态集的状态集k0，1，2，3，4，5，61.首先把首先把M的状态的状态K分为两组：分为两组：终态集终态集K1=3，4

38、，5，6非终态集非终态集K2=0，1，2显然显然K1与与K2不等价。不等价。本讲稿第八十三页，共一百四十七页2.然后，试图然后，试图K1，K2在中寻找一个子集和在中寻找一个子集和一个输入符号使得这个子集中的状态可一个输入符号使得这个子集中的状态可区别的；若可区别，则再分割；继续，区别的；若可区别，则再分割；继续，一直到不能再分割为止。一直到不能再分割为止。讨论终态集讨论终态集K1=3，4，5，6 是否可分割：是否可分割：3，4，5，6a K1 3，4，5，6b K1 所以状态所以状态3，4，5，6均等价，因此均等价，因此K1不能再分割。不能再分割。本讲稿第八十四页，共一百四十七页讨论非终态集讨

39、论非终态集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本讲稿第八十五页，共一百四十七页再讨论再讨论K22=0，2 是否可分割：是否可分割：0，2b 2，5 而它未包括在而它未包括在K1，K21与与K22中，故中，故0，2应一分为二：应一分为二：K2210 K2222所以所以K分

40、为四组分为四组3，4，5，6，0，1，2。每个组都不可再分。每个组都不可再分。本讲稿第八十六页，共一百四十七页3.最后，令状态最后，令状态3代表代表3，4，5，6。把原。把原来到达来到达4，5，6的弧都导入的弧都导入3，并删除，并删除4，5，6状态。即可得到化简后的状态。即可得到化简后的DFA。3210aaabbb,ba本讲稿第八十七页，共一百四十七页示例示例【例【例5】正规式】正规式r(a|b)*abb1.由正规式由正规式r构造构造NFA为：为：Y34bba21Xab本讲稿第八十八页，共一百四十七页2.NFA确定化为DFA：初态-closure(X)X，1，2IIaIb初态X,1,2X,1,

41、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本讲稿第八十九页，共一百四十七页重命名为：重命名为：ab012113212314412状态输入符本讲稿第九十页，共一百四十七页DFA的状态转换图为：的状态转换图为：42ab310abbaabba本讲稿第九十一页，共一百四十七页3.DFA的化简：的化简：DFA的状态集的状态集K0，1，2，3，41)首先把状态首先把状态K分为可区别的两组状态集：分为可区别的两组状态集：终态集终态集K1=4非终态集非终态集K2=0，1，2，3本讲稿第九十二页，共一

42、百四十七页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本讲稿第九十三页，共一百四十七页3)讨论K21=0，1，2能否分割：能否分割：0，1，2a 1而 0，2b 2 K21 1b 3 K22所以可分割为K211=0，2 K212=1本讲稿第九十四页，共一百四十七页4)讨论讨论K211=0，2能否分割：能否分割：0，2a 1 0，2b 2所以不可分割，所以不可分割，0状态与状态与2状态等价，不状态等价，不再分割。再分割。所以最终将状态集所以最终将状态集K分

43、割为分割为0，2，1，3，4，一共四组。，一共四组。本讲稿第九十五页，共一百四十七页最后，令状态最后，令状态0代表代表0，2。把原来到达。把原来到达2的弧都导入的弧都导入0，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。4ab310abaabb本讲稿第九十六页，共一百四十七页示例示例【例【例6】标识符的正规式】标识符的正规式r为为l(l|d)*1.由正规式由正规式r构造构造NFA为：为：Y1Xl2ld本讲稿第九十七页，共一百四十七页2.NFA确定化为DFA：初态-closure(X)XIIlId初态XX l=1,2,YXd=终态终态1,2,Y2,Y2,Y终态终态2,Y2,

44、Y2,Y本讲稿第九十八页，共一百四十七页重命名为：重命名为：ld01122222状态输入符本讲稿第九十九页，共一百四十七页DFA的状态转换图为：的状态转换图为：2d0ll1l，d本讲稿第一百页，共一百四十七页3.DFA的化简：的化简：DFA的状态集的状态集K0，1，21)首先把状态首先把状态K分为可区别的两组状态集：分为可区别的两组状态集：终态集终态集K1=1，2 非终态集非终态集K2=0本讲稿第一百零一页，共一百四十七页2)讨论K1=1，2能否分割：能否分割：1，2a 2 1，2b 2所以不可分割，所以不可分割，1状态与状态与2状态等价，不状态等价，不再分割。再分割。所以最终将状态集所以最终

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

46、态转换函数f由以下规则定义：1.P中形如AaB的产生式，则有f(A,a)=B;2.P中形如Aa的产生式，则有f(A,a)=F;3.对VT中的每个a，都有f(F,a)=。本讲稿第一百零五页，共一百四十七页示例示例【例7】描述标识符的右线性文法为：G11I:I lB|l BlB|dB|l|d本讲稿第一百零六页，共一百四十七页转换为转换为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 lB 可得可得 f(B，l)B 由由B dB

47、可得可得 f(B，d)B 由由B l 可得可得 f(B，l)F由由B d 可得可得 f(B，d)F 本讲稿第一百零七页，共一百四十七页用状态转换图表示为：用状态转换图表示为：FIlBl，dldl本讲稿第一百零八页，共一百四十七页初态-closure(I)IIIlId初态II l=B,FId=终态终态B,FB,FB,F将此将此NFA确定化为确定化为DFA本讲稿第一百零九页，共一百四十七页重命名为：重命名为：ld01111状态输入符0l1l，dDFA即为：即为：本讲稿第一百一十页，共一百四十七页上述上述DFA已经是最小的已经是最小的DFA，不需要，不需要再化简。再化简。因为如果要进行化简，则首先要

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

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

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