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

资源描述

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

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

2、或一个程序，于计算机来说就不同了，输入一段话或一个程序，计算机得到的只是一串符号，要对这段话或这段计算机得到的只是一串符号，要对这段话或这段程序进行分析，计算机首先必需知道这段话由哪程序进行分析，计算机首先必需知道这段话由哪些词组成，或这个程序由哪些单词符号构成。这些词组成，或这个程序由哪些单词符号构成。这个过程就是词法分析。个过程就是词法分析。识别单词识别单词词法分析的任务是：从左到右逐个字符地对源程序进行扫描和分解，依据语言的词法规则识别出一个个的单词符号。词法分析是编译的基础。执行词法分析的程序就是词法分析器(扫描器)，其功能是输入源程序，输出单词符号。词法分析程序的主要任务：扫描源程序

3、，识别出单词其他任务：滤掉空格，跳过注释、换行符追踪换行标记，复制出错源程序，宏绽开，二、与语法分析程序的接口方式二、与语法分析程序的接口方式方式方式1：词法分析程序作为单独的程序，输：词法分析程序作为单独的程序，输入源程序，输出单词文件，供应应语法分入源程序，输出单词文件，供应应语法分析程序运用。析程序运用。方式方式2：词法分析程序作为语法分析程序的：词法分析程序作为语法分析程序的子程序，供应应语法分析程序调用，不产子程序，供应应语法分析程序调用，不产生中间文件。生中间文件。字符串字符串表示的源表示的源程序程序词法分析词法分析程序程序字符语法分析语法分析程序程序取单词回送单词词法分析程序作为

4、子程序词法分析程序作为子程序三、单词的分类三、单词的分类【单词】【单词】单词是语言中具有独立意义的最小语单词是语言中具有独立意义的最小语法单位，包括保留字、标识符、运算符、标法单位，包括保留字、标识符、运算符、标点符号和常量等。点符号和常量等。【例如】【例如】ab是表达式，不是单词。是表达式，不是单词。a,b是标识符，是运算符，都是单词。是标识符，是运算符，都是单词。程序设计语言的单词符号一般可分成下列程序设计语言的单词符号一般可分成下列5种：种：关关键键字字(基基本本字字，保保留留字字)：具具有有固固定定意意义义的的标标识识符，如符，如PASCAL语言中的语言中的begin,end,if和和

5、while等。等。标标识识符符:用用来来表表示示各各种种名名字字，如如常常量量名名、变变量量名名和过程名等。和过程名等。常常数数:各各种种类类型型的的常常数数，如如25，3.1415，TRUE和和“ABC”等。等。运算符运算符:如如+，*，=j)i-;while(i=j)i-;经词法分析器处理后转换的单词序列为：经词法分析器处理后转换的单词序列为：while ,-(,-id id的种别码的种别码,指向指向i i的符号表项的指针的符号表项的指针 =的种别码的种别码,-,-id ),-id -,-;,-四、单词的三种描述工具四、单词的三种描述工具单词有三种描述工具：单词有三种描述工具：正规文法正规

6、文法正规式正规式有穷自动机有穷自动机1.正规文法正规文法正规文法的形式：正规文法的形式：右线性文法：右线性文法：AaB或或Aa 其中，其中，A、B为单个的非终结符，为单个的非终结符，a为单个的终结为单个的终结符。符。标识符的文法标识符的文法PASCAL语言中的标识符是字母开头，后跟字母数字串。设l表示az中的任何一英文字母，d表示09中的任一数字。描述标识符的文法为：G11I:I lB|l BlB|dB|l|d留意：一般关键字（保留字）都是由字母构成，它是标识符集合的子集。无符号整数的文法无符号整数的文法描述无符号整数的文法为：GD:D dD|d给出123的推导过程：D 1D 12D 123给

8、；|(|)|其它的文法其它的文法2、正规式、正规式正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。正规式也称正则表达式，也是表示正规集的数学工具。正规式的递归定义正规式的递归定义是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为；是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为；aVaVT T是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为aa；设设e e1 1和和e e2 2分别是表示的正规集分别是表示的正规集L(eL(e1 1)和和L(eL(e2 2)的正的

9、正规式规式,则：则：a)a)e e1 1|e|e2 2是正规式是正规式,表示的正规集为表示的正规集为L(eL(e1 1)L(e)L(e2 2););b)b)e e1 1ee2 2是正规式是正规式,表示的正规集为表示的正规集为 L(eL(e1 1)L(e)L(e2 2););c)c)e e1 1*是正规式是正规式,表示的正规集为表示的正规集为(L(e(L(e1 1)*。三种运算符规定运算符的优先依次为：规定运算符的优先依次为：*|。正规式定义中的正规式定义中的“|”读为读为“或或”（也（也有运用有运用“+”代替代替“|”的）；的）；“”读读为为“连接连接”；“*”读为读为“闭包闭包”（即，（即，

10、随意有限次的自重复连接）。随意有限次的自重复连接）。连接符连接符“”一般可省略不写。一般可省略不写。“*”、“”和和“|”都是左结合的。都是左结合的。示例示例=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 全部结尾是abb的随意a和b的串(ab)(aabb)(ab)上全部含

11、有两个相继的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，明显等价；e1=b(ab),e2=(ba)b均为babababababab，等价；e1=(ab),e2=(ab)均表示由a和

12、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 的幂等律的幂等律 3、有穷自动机、有穷自动机FA有穷自动机(也称有限自动机)作为一种识别装置，它能精确地识别正规集，即识别正规文法所定义的语言和正规式所表

13、示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造找寻特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。有穷自动机的模型有穷自动机的模型有穷自动机FA是具有离散输入输出系统的数学模型。系统的状态概括了对过去输入处理状况的信息。系统只须要依据当前所处的状态和面临的输入就可以确定系统的后继行为。每当系统出来了

14、当前的输入后，系统的内部状态也将发生变更。例如：电梯限制装置就是有穷系统的典型。19481948年，由神经物理学家年，由神经物理学家MeCulochMeCuloch和和PittsPitts首先提出首先提出FAFA模型。模型。有有穷穷控控制制器器输入带输入带有穷限制器限制读头从左有穷限制器限制读头从左向右逐个扫描并读入输入向右逐个扫描并读入输入符号，并且依据限制器的符号，并且依据限制器的当前状态和当前输入符号当前状态和当前输入符号限制转入下一个状态。限制转入下一个状态。读头读头接收方式接收方式FA在初始状态下起先读入第一个输入符。FA接收输入串：终态方式。若读头在输入带上最终一个符号时，恰

15、好进入某个终止状态，则宣布接收该输入串；否则，不接收。确定的有穷自动机DFA【DFA定义】一个确定的有穷自动机(DFA)M是一个五元组：M=（S，f，s0，Z），其中：S是一个有穷状态集，它的每个元素称为一个状态；是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表；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)，其中：，

16、其中：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状态转换矩阵DFA可以用一个矩阵表示可以用一个矩阵表示:行行:表示状态表示状态q;列列:表示输入字符表示输入字符a;矩矩阵阵元元素素：表表示示f(q,a)的的值值,即即在在q状态下读入输入符a时应转换到的下一个状态。状态输入符状态转换图DFA也可以表示成一张（确定的）状态也可以表示成一张（确定的）状态转换图：转换图：结点：表示状态，用圆圈圈起来；结点：表示状态，用圆圈圈起来；箭弧箭弧：表示状态转移的方向；：表示状态转移的方向；f(q1,a)q2：状

17、态状态初态初态终态终态 q1 q2ab0123aaaba，bbDFA：串串为为DFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存，若存在一条从初态结点到某一终态结点在一条从初态结点到某一终态结点的通路，且这条通路上全部箭弧的的通路，且这条通路上全部箭弧的标记符连接成的字符串等于标记符连接成的字符串等于，则称，则称串串为为DFA M所识别（读出或接受）。所识别（读出或接受）。若若M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则为空字则为空字可为可为M所识别。所识别。示例示例例1中串abaa的识别路径为：b0123aaaba，bb0a1b2a1a3扩充转换

18、函数扩充转换函数f若有：f（q1，a1）=q2f（q2，a2）=q3f（q3，a3）=q4f（qn，an）=qn+1则可记为：f(q1，a1 a2an)=qn1DFA 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标识符的标识符的DFA标识符e2f3的识别路径为：0e121f1310字母字母1字母或数字字母或

19、数字中间状态无符号整数的无符号整数的DFA无符号整数0123的识别路径为：0011121310数字数字1 数字数字无符号实数的无符号实数的DFA无符号实数3.8e+9的识别路径为：701346527dddddddee+7031.283e4+596不确定的有穷自动机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是一个终态集。示例【例【例2】NF

20、A 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状态转换矩阵为：状态转换矩阵为：状态输入符NFA的状态转换图1a32bbbb串串为为NFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存，若存在一条从初态结点到某一终态结点在一条从初态结点到某一终态结点的通路，且这条通路上全部箭弧的的通路，且这条通路上全部箭弧的标记符连接成的字符串等于标记符连接成的字符串等于，则称，则称串串为为NFA M所识别（读出或接受）。所识别（读出或接受）。示例示例例2中串bab的识

21、别路径为：1b1a3b21a32bbbbNFA M所能识别的语言集NFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若NFA M=（S，f，S0，Z），则有：L(M)|f(q1，)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等价的等价的

22、DFA不唯一。不唯一。标识符的标识符的NFAI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母标识符的标识符的NFA标识符e2f3的识别路径为：IeB2BfB3FI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母五、词法分析器的自动生成原理五、词法分析器的自动生成原理正规式NFA转换DFA确定化化简最小DFA1.1.正规式 NFA对于上的一个正规式r，可以构造一个上的NFA M，使得L(M)=L(r)。转换构造方法构造方法引进初始结点X和终态结点Y，把正规式r表示成拓广转换图，如下所示：分析正规式r的语法结构，运用如下规则为r中的每个基本符号构造NFA。Xr Y转换规则

23、转换规则(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整个转换过程中，可用X表示初态，Y表示终态，全部新结点均接受不同的名字标记，可依次用1、2、3等。示例示例【例3】构造正规式r1 01*的NFA。X01*Y X0 Y 11*X0 11 Y 2

24、2.NFA DFA从NFA的矩阵表示中可以看出，表项通常是多个状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。DFA运用它的状态去记录在NFA读入一个输入符号后可能达到的全部状态。确定化方法：状态子集法。确定化状态子集状态子集【状态子集【状态子集I的的-闭包：闭包：-CLOSURE(I)】a)若若qI，则，则q-CLOSURE（I）；）；b)若若qI，那么从，那么从q动身经随意条动身经随意条弧而能弧而能到达的任何状态到达的任何状态q都属于都属于_CLOSURE（I）；）；【状态子集【状态子集Ia=_CLOSUR

25、E(J)】a，I是状态子集，是状态子集，J是那些可从是那些可从I中的某一状中的某一状态结点动身经过一条态结点动身经过一条a弧而到达的状态结弧而到达的状态结点的全体。点的全体。示例示例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。4Y32615XaaaabbbbNFA确定化为确定化为DFA:状态子集法状

26、态子集法从从NFA M=(S,f,S0,Z)构造等价的构造等价的DFA M(K,f,k0,F)的基本方法是：的基本方法是：1.求求DFA的初态的初态k0 -closure(NFA的初态的初态)-closure(X)X，5，12.求求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中；如此接着，直至

27、不中；如此接着，直至不再产生新的状态为止。即可得到再产生新的状态为止。即可得到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的方法求其它的状态。的方法求其它的状态。示例示例对状态对状态5，3，1求其求其Ia，Ib子集：子集：f(5

28、，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中。中。如此接着，将此过程用状态转换矩阵记录下如此接着，将此过程用状态转换矩阵记录下来：来：示例示例 I Ia Ib X,5,1 5,3,1 5,4,1 5,3,1 5,3,1,2,6,Y 5,4,

29、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 2 1 5 3 3 4 4 6 5 5 6 5 6 3 4 如何确定如何确定DFA的终态集的终态集包含原NFA的终态的子集都是DFA的终态。例如：3，4，5，

30、6均是终态。所得所得DFA如下：如下：3521460baaaaabbbbbaab3.DFA的化简的化简确定有穷自动机M的化简是指：找寻一个状态数比DFA M少的DFA M，使得L(M)L(M)。一个有穷自动机是化简了的，即是它没有多余状态，并且它的状态中没有两个是相互等价的。一个有穷自动机可以通过消退多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。多余状态多余状态所谓有穷自动机的多余状态，是指这样的状态：从有穷自动机的初态动身，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。等价和可区分的等价和可区分的等价：假如有穷自动机DFA M的两个状态s和t能够识别同样的符

31、号串，则称状态s和t等价。可区分的：假如有穷自动机DFA M的两个状态s和t不等价，则称这两个状态是可区分的。【例如】终态与非终态是可区分的。DFADFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFADFA最小状态最小状态DFA的含义的含义:没有多余状态没有多余状态(死状态死状态)没有两个状态是相互等价（不行区分）没有两个状态是相互等价（不行区分）两个状态两个状态s和和t可区分：不满足可区分：不满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s动身读入某个动身读入某个a a和从和从 t动身读入某个动身读入某个a到达的状态等价。到达的状态等价。DFA的最小化过程：

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

33、aabbbbbaab示例示例DFA的状态集的状态集k0，1，2，3，4，5，61.首先把首先把M的状态的状态K分为两组：分为两组：终态集终态集K1=3，4，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 所以状

34、态所以状态3，4，5，6均等价，因此均等价，因此K1不能再分割。不能再分割。探讨非终态集探讨非终态集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

35、应一分为二：应一分为二：K2210 K2222所以所以K分为四组分为四组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为：为：Y34bba21Xab2.NFA确定化为DFA：初态-closure(X)X，1，2重命名为：重命名为：状态输入符DFA的状态转换图为：的状态转换图为：4

36、2ab310abbaabba3.DFA的化简：的化简：DFA的状态集的状态集K0，1，2，3，41)首先把状态首先把状态K分为可区分的两组状态集：分为可区分的两组状态集：终态集终态集K1=4非终态集非终态集K2=0，1，2，32)探讨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=33)探讨K21=0，1，2能否分割：0，1，2a 1而 0，2b 2 K21 1b 3 K22所以可分割为K211=0，2 K212=14)探讨K211=0，2能否分割：0，2a 1 0，2b 2所

37、以不行分割，0状态与2状态等价，不再分割。所以最终将状态集K分割为0，2，1，3，4，一共四组。最终，令状态最终，令状态0代表代表0，2。把原来到达。把原来到达2的弧都导入的弧都导入0，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。4ab310abaabb示例示例【例【例6】标识符的正规式】标识符的正规式r为为l(l|d)*1.由正规式由正规式r构造构造NFA为：为：Y1Xl2ld2.NFA确定化为DFA：初态-closure(X)X重命名为：重命名为：状态输入符DFA的状态转换图为：的状态转换图为：2d0ll1l，d3.DFA的化简：的化简：DFA的状态集的状态集K0，

38、1，21)首先把状态首先把状态K分为可区分的两组状态集：分为可区分的两组状态集：终态集终态集K1=1，2 非终态集非终态集K2=02)探讨K1=1，2能否分割：1，2a 2 1，2b 2所以不行分割，1状态与2状态等价，不再分割。所以最终将状态集K分割为0，1，2，一共两组。最终，令状态最终，令状态1代表代表1，2。把原来到达。把原来到达2的弧都导入的弧都导入1，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。0l1l，d六、正规文法六、正规文法有穷自动机有穷自动机对于正规文法G和有穷自动机FA M，假如L(G)=L(M),则称G和M等价。转换右线性文法的转换方法右线性文

39、法的转换方法引入一个终态F。设右线性文法G(VN,VT,P,S),则相应的自动机为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)=。示例示例【例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 由由

40、B lB 可得可得 f(B，l)B 由由B dB 可得可得 f(B，d)B 由由B l 可得可得 f(B，l)F由由B d 可得可得 f(B，d)F 用状态转换图表示为：用状态转换图表示为：FIlBl，dldl初态-closure(I)I将此将此NFA确定化为确定化为DFA重命名为：重命名为：状态输入符0l1l，dDFA即为：即为：上述上述DFA已经是最小的已经是最小的DFA，不须，不须要再化简。要再化简。因为假如要进行化简，则首先要把因为假如要进行化简，则首先要把DFA的状态集分为可区分的两组状的状态集分为可区分的两组状态集：态集：终态集终态集K1=1非终态集非终态集K2=0而它们无法再分割

41、，所以不须要化而它们无法再分割，所以不须要化简，此简，此DFA即是最简即是最简DFA。七、设计词法分析程序七、设计词法分析程序设计词法分析程序的途径有两种:一种是手工编写：干脆依据词法规则编写程序。一种是自动生成：利用词法自动生成工具产生词法分析程序，依据的原理就是将正规表达式转换成等价的有限自动机，要分三步：正规式NFA转换DFA确定化化简最小DFA1.利用利用DFA设计词法分析器设计词法分析器为了构造词法分析器，要探讨构词法，每种单词类的结构模式以及识别它的数学模型有限自动机FA。它的模拟程序可以作为词法分析器的限制程序。正规式用于说明(描述)单词的结构特别简洁便利。而把一个正规式编译(或

42、称转换)为一个NFA进而转换为相应的DFA，这个DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序。识识别别某某语语言言单单词词的的状状态态转转换换图图实现状态转换图的方法实现状态转换图的方法依据画出的状态转换图（识别单词的）构造词法分析程序：每个状态对应一小段程序，完成到达此状态的工作；词法分析程序的限制程序模拟状态转换图的状态转换。一般规则一般规则1.对于不含回路的分叉结点，对应多分支语句：IKJM字母数字分叉结点I对应四分支程序段：GetChar();if(Isletter()状态J对应的程序段else if(Isdigit()状态K对应的程序段else i

43、f(ch+)状态M的对应程序段else 错误处理遇到“错误处理”：现行状态I和当前所面临的输入串不匹配。一般规则一般规则2.对于含回路的状态结点,对应循环语句：IJ字母或数字其它含回路的结点I对应while循环语句：GetChar();while (Isletter()or Isdigit()相应处理GetChar();状态J对应的程序段一般规则一般规则3.终态结点对应一个形如return(code,value)的语句(即单词的二元组输出形式)：遇到“非符号”：表示多读入一个字符，输入指针应回退一格。如下图所示。I非J 识识别别某某语语言言单单词词的的状状态态转转换换图图构造上述语言的词法分析

44、器,明显对应多分支语句：scaner()token=NULL;GetChar();if(Isletter(ch)识别标识符的程序段else if(Isdigit(ch)状态整数的程序段else switch(ch)case+:return(+的种别码，)；break;case-:return(-的种别码，)；break;case;:return(;的种别码，)；break;default:error();break;/*调用出错处理程序*/标识符与保留字的识别标识符与保留字的识别当首符是字母时，起先识别标识符或保留字，边读入下一个输入符边拼法标识符，直至读入非字母数字止。但是多读入一个字符，输

45、入指针(列计数)应回退一格。推断是否为保留字：查保留字表若查到则为保留字，输出保留字的二元组形式；若查不到则为用户定义的标识符，输出标识符的二元组形式。除此之外，还要考虑是否有符号表。运用下面的全局变量和过程运用下面的全局变量和过程1.Character 2.Token3.Getchar 4.getbc5.Concatenation6.isletter,isdigit7.Reserve 8.Retract9.buildlist10.return相应算法相应算法If(Isletter(ch)while (Isletter(ch)|Isdigit(ch)concat();/*拼标识符*/GetCh

46、ar();retract();/*输入指针回退一格*/creserve();/*查保留字表*/If(c!=10)return(保留字的种别,token);else return(标识符的种别,token);整数的识别整数的识别当首符是数字时，起先识别整数，边读入下一个输入符边拼数，直至读入非数字止。但是多读入一个字符，输入指针(列计数)应回退一格。拼数：要考虑是否将字符串形式的数转换为十进制数或二进制数。输出整数的二元组形式。相应算法相应算法If(Isdigit(ch)while (Isdigit(ch)concat();/*拼数*/GetChar();retract();/*输入指针回退一格

47、*/return(整数的种别,转换为二进制数);留意留意在识别标识符的过程中，要拼法出来，并和保留字区分开来；在识别常数的过程中，要把它转换成机器码表示以作为属性值。其它单词的识别其它单词的识别运算符与界符的识别特别简洁：对于单个单词：读入何种单个单词，就干脆识别，并且输出其二元组形式。例如：，。对于复合单词：须要拼复合单词，例如对两个字符组成的算符：=、=、=等单词，须要多读入一个字符，来推断它是否为复合单词。若是单个单词，此时输入指针(列计数)应回退一格。若是复合单词，就输出其二元组形式。示例示例【例如】：=case:GetChar();if(ch=)return(:=的种别，)；retr

48、act();return(:的种别，)；break；case :GetChar();if(ch=)return()return(的种别，)；retract();return(=0&bufi=48&bufi=65&bufi=97&bufi=a&bufi=A&bufi=Z)利用高级语言供应的函数：推断字母：isalpha(ch)推断数字：isdigit(ch)推断字母或数字：isalnum(ch)如何推断一个符号是字母或数字如何推断一个符号是字母或数字拼单词拼单词满足某种条件，就将输入符拼到单词变量中：tokenj=bufi;i+;j+;识别整数示例识别整数示例if(isdigit(bufi)to

49、kenj=bufi;i+;j+;while(1)if(isdigit(bufi)tokenj=bufi;i+;j+;else tokenj=0;break;将此整数串转换为二进制整数;输出整数的二元组;查符号表示例查符号表示例依次查表法依次查表法for(legth=0;legth 符号表的长度;legth+)if(!strcmp(token,keywordlegth)break;if(legth=符号表的长度)输出标识符的二元组;else 输出保留字的二元组;错误处理错误处理词法分析阶段的错误通常有：非法字符：指程序语言字母表以外的字符。例如数非法字符。单词拼错：例如whilf，9a88，85

50、.98.633。字符串常数或注解不封闭：例如/*，dsf。变量说明重复：例如real a；integer a。其它应用其它应用词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序的自动构造工具也广泛应用于很多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。本章小结本章小结1词法分析的任务。词法分析的任务。2单词的概念与单词的分类以及输出方式。单词的概念与单词的分类以及输出方式。3弄懂一些重要的概

展开阅读全文