第3章-词法分析-编译原理-陈火旺.ppt

《第3章-词法分析-编译原理-陈火旺.ppt》由会员分享，可在线阅读，更多相关《第3章-词法分析-编译原理-陈火旺.ppt（107页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1v内容：内容：状态转换图、正规式和有限自动机、词法分析器的自动生成状态转换图、正规式和有限自动机、词法分析器的自动生成v掌握掌握:正规式、状态转换图，正规式、状态转换图，DFN的概念、的概念、NFA的概念，将的概念，将NFA转转 换为换为DFA、DFA的化简、正规式与有限自动机间的转换。的化简、正规式与有限自动机间的转换。v理解理解:正规文法与有穷自动机间的转换正规文法与有穷自动机间的转换 词法分析器的自动产生工具词法分析器的自动产生工具LEX 第第3章章 词法分析词法分析教学要求教学要求2本章在编译程序中的地位本章在编译程序中的地位表表格格管管理理词法分析器词法分析器语法分析器语法分析器语

2、义分析与中间代码产生语义分析与中间代码产生优化器优化器目标代码生成器目标代码生成器源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码出出错错处处理理3v执行词法分析的程序称为执行词法分析的程序称为又称为又称为词法分析器词法分析器或或扫描器扫描器.v词法分析的词法分析的任务任务：从左至右逐个地扫描源程：从左至右逐个地扫描源程序的字符串序的字符串,按照按照词法规则词法规则识别出一个个正识别出一个个正确的单词，并转换为相应的确的单词，并转换为相应的二元式二元式形式，交形式，交给语法分析使用。给语法分析使用。v把作为字符串的源程序改造成单词符号串的把作为字符串

3、的源程序改造成单词符号串的词法分析是编译的基础。词法分析是编译的基础。3.1 设计设计词法分析器词法分析器时应考虑的几个问题时应考虑的几个问题43.1.1 词法分析阶段的必要性词法分析阶段的必要性 v词法分析的工作纳入整个语法分析中一揽子地进行，原则上是词法分析的工作纳入整个语法分析中一揽子地进行，原则上是可行的。可行的。v在设计一个编译程序时，通常是把对源程序的结构分析分为词在设计一个编译程序时，通常是把对源程序的结构分析分为词法分析和语法分析两个相对独立的阶段来完成。法分析和语法分析两个相对独立的阶段来完成。第一，描述单词的结构比描述源程序的其它语法结构要简单第一，描述单词的结构比描述源程

4、序的其它语法结构要简单得多，仅使用得多，仅使用3 3型文法也就基本够用了。型文法也就基本够用了。第二，由于把词法分析和语法分析分开，可使编译程序各部第二，由于把词法分析和语法分析分开，可使编译程序各部分的功能更为单一，整个编译程序的结构也更加清晰，从而分的功能更为单一，整个编译程序的结构也更加清晰，从而有利于编译程序的编写和调整。有利于编译程序的编写和调整。v上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译程序的逻辑功能而言，而不一定指的是编译程序的执行流程。程序的逻辑功能而言，而不一定指的是编译程序的执行流程。53.1.2 词法分析

5、器的输出形式词法分析器的输出形式v词法分析器输出的单词常常表示为词法分析器输出的单词常常表示为二元式二元式形式形式 (单词种别单词种别,单词符号的属性值单词符号的属性值)单词种别提供给语法分析程序使用；单词符号的属性值提供给语义分析程序使用。具体的分类设计方法以方便语法分析程序使用为原则。63.1.2 词法分析器的输出形式词法分析器的输出形式v程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：关键字关键字(保留字或基本字保留字或基本字)：如：如 if,then,else,while,doif,then,else,while,do等等 标识符标识符：用来表示各种名字，如：用来表示各

6、种名字，如 x1x1常量常量：如：如 256256，3.143.14，true,true,abcabc 运算符运算符：如：如 、*、/等等等等分界符分界符：如：如 逗号，分号，冒号等逗号，分号，冒号等73.1.2 词法分析器的输出形式词法分析器的输出形式v单词种别单词种别:一个语言的单词符号如何分类、分为几类、如何一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词对编码主要取决于处理上的方便。通常，每种单词对应一个整数码。应一个整数码。注意：保留字、运算符和界符的个数确定，注意：保留字、运算符和界符的个数确定，标识符和常数的个数不确定。标识符和常数的个数不确定

7、。保留字：保留字：可全体视为一种，也可一字一种；可全体视为一种，也可一字一种；标识符：标识符：统归为一种；统归为一种；常数：常数：统归为一种统归为一种,或按整、实、布尔等再分；或按整、实、布尔等再分；运算符和界符：运算符和界符：一符一种，或统归为一种。一符一种，或统归为一种。83.1.2 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值 单词符号的属性是指单词符号的特征值。如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因而不需要属性值。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号

8、的属性值。93.1.2 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值标识符和常数标识符和常数 标识符的标识符的内部码内部码(如如ASCII码等等码等等)和和常数本身的值常数本身的值(二进制，逻辑值等二进制，逻辑值等)来表示。来表示。标识符的标识符的符号表入口地址符号表入口地址作为其单词符号的属性值作为其单词符号的属性值,常量在其常量在其常量表中的入口地址常量表中的入口地址作为其单词符号的属性作为其单词符号的属性值。值。每个基本字占一个单词种别，单词符号的属性值缺省每个基本字占一个单词种别，单词符号的属性值缺省。对于界符，运算符通常一个符号一个种别，单词符号的对于界

9、符，运算符通常一个符号一个种别，单词符号的属性值缺省属性值缺省例例:参见参见P42.P42.表表3.1 3.1 单词符号及种别编码单词符号及种别编码103.1.3 词法分析器作为独立子程序词法分析器作为独立子程序v词法分析可采用如下两种处理结构词法分析可采用如下两种处理结构：把词法分析程序作为主程序。将词法分析作为把词法分析程序作为主程序。将词法分析作为独立的一遍来完成独立的一遍来完成。把词法分析程序作为语法分析程序调用的子程把词法分析程序作为语法分析程序调用的子程序。序。v每当语法分析器需要一个单词符号时就调用这个子程每当语法分析器需要一个单词符号时就调用这个子程序。序。v每一次调用，词法分

10、析器从源程序字符串中识别出一每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析个单词符号，并把它的内部表示二元组交给语法分析器处理。器处理。113.1.4 源程序的输入源程序的输入、预处理预处理及及超前搜索超前搜索词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。输输入入串串一一般般放放在在一一个个输输入入缓缓冲冲区区中中。词词法法分分析析器器的的工工作作可可以以直直接接在在输输入入缓缓冲冲区区中中进进行行。但但在在许许多多情情况况下下，可可以以先先预预处处理理输输入入串串，识识别工作将更方便。（参见别工作将更方便。（参见

11、P40 图图3.1）123.1.4 源程序的输入源程序的输入、预处理预处理及及超前搜索超前搜索v预处理的原因预处理的原因 源程序中包含源程序中包含回车回车,换行换行,多余空白符多余空白符,注释行等编辑注释行等编辑字字符符,它们对程序逻辑功能无任何影响，它们对程序逻辑功能无任何影响，在词法分析之前在词法分析之前,首首先要剔除掉这些符号先要剔除掉这些符号,使得词法分析更为简单。使得词法分析更为简单。一行语句结束应配上一个特殊字符说明。一行语句结束应配上一个特殊字符说明。有些语言要识别标号区，区分标号语句，找出续行符连有些语言要识别标号区，区分标号语句，找出续行符连接成完整语句等。接成完整语句等。输

12、出源程序清单以便复核。输出源程序清单以便复核。v 预处理子程序任务预处理子程序任务 从输入缓冲区中读取源程序，预处理后送入扫描缓冲从输入缓冲区中读取源程序，预处理后送入扫描缓冲区。此时，扫描缓冲区的字符都是有效字符。区。此时，扫描缓冲区的字符都是有效字符。词法分析程序这时可以再对扫描缓冲区进行扫描。词法分析程序这时可以再对扫描缓冲区进行扫描。133.1.4 源程序的输入源程序的输入、预处理预处理及及超前搜索超前搜索v超前搜索超前搜索 对于有些语言，关键字不保护，关键字与用户自定义标对于有些语言，关键字不保护，关键字与用户自定义标识符间没有界符，要在上下文环境中识别单词，这时需要识符间没有界符，

13、要在上下文环境中识别单词，这时需要超前搜索方法来识别关键字。超前搜索方法来识别关键字。例如：例如：FORTRANFORTRAN语言：语言：1.1.DO10K=1DO10K=1，50 50 2.2.DO10K=1.50DO10K=1.50v扫描缓冲区的结构扫描缓冲区的结构 (自学自学)16词法分析程序设计词法分析程序设计v 设计方法：设计方法：写出该语言的词法规则；写出该语言的词法规则；把词法规则转换为相应的把词法规则转换为相应的状态转换图状态转换图；把各转换图的初态连在一起，构成识别该把各转换图的初态连在一起，构成识别该 语言的语言的自动机自动机；(4)(4)设计扫描器设计扫描器 173.2

14、正规文法和有限自动机正规文法和有限自动机v 这节介绍这节介绍词法规则词法规则的形式表示的形式表示(正规式正规式),从从正规式正规式向有限自动机的转化向有限自动机的转化.正规式正规式有限自动机有限自动机词法分析器词法分析器控制程序控制程序自动生成器自动生成器转化转化合成合成183.2.1 正规文法、正规集与正规式正规文法、正规集与正规式v正规文法：正规文法：是是chomsky3型文法。型文法。例如：标识符这种单词可以用下面的规则描述例如：标识符这种单词可以用下面的规则描述|（|）表示任意字母，表示任意字母，表示任意数字表示任意数字注：正规文法描述是注：正规文法描述是正规集正规集的文法，可用于描述

15、程序设计的文法，可用于描述程序设计语言的语法部分语言的语法部分。19v 对于一个正规文法的语言提炼出一个简洁的公式，用这个式对于一个正规文法的语言提炼出一个简洁的公式，用这个式子来对它进行子来对它进行形式化的表示形式化的表示，这个式子叫，这个式子叫正规式正规式。v正规式：正规式：也称也称正则表达式正则表达式,是说明是说明单词的模式单词的模式的一种重要的的一种重要的表示法（记号）；是定义正规集的数学工具；用来描述单词表示法（记号）；是定义正规集的数学工具；用来描述单词符号。符号。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集注：正规集是集合，可有穷也可无穷。注：正规集是集合，可有穷

16、也可无穷。可通过正规式来形式化表示。可通过正规式来形式化表示。v 正规集：正规集：由正规文法产生的语言所构成的集合。由正规文法产生的语言所构成的集合。203.2.1 正规文法、正规式与正规集正规文法、正规式与正规集下面以标识符为例说明下面以标识符为例说明正规式正规式与与正规集正规集:标识符标识符标识符标识符是以字母开头的字母数字串。是以字母开头的字母数字串。若用若用L L表示字母表示字母,用用D D表示数字表示数字,则标识符可表示为则标识符可表示为:L(L|D):L(L|D)*其中并置表示两者的其中并置表示两者的连接连接,|,|表示两者选一表示两者选一,*,*表示零次或多次引用。表示零次或多次

17、引用。L(L|D)L(L|D)*为为标识符的正规式标识符的正规式，该正规式表示的集合为该正规式表示的集合为标识符的正规集标识符的正规集。21v下面是正规式和它所定义的正规集的递归定义。下面是正规式和它所定义的正规集的递归定义。1),是是 上的正规式上的正规式,所表示的正规集为所表示的正规集为 ,;2)若若 a,则则 a 为正规式为正规式,所表示的正规集为所表示的正规集为 a;3)设设U,V 为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 L(U),L(V);则则 U|V为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 L(U)L(V);UV为为 上的正规式上的正规式,

18、所表示的正规集为所表示的正规集为 L(U)L(V);V*为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 (L(V)*;4)仅当有限次使用上述三步骤而定义的表达式仅当有限次使用上述三步骤而定义的表达式,才是才是 上的正上的正规式规式,而这些而这些正规式所表示的字集才是正规式所表示的字集才是上的正规集。上的正规集。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集或运算或运算连接积连接积22说明：说明：11上的一个上的一个字字指的是由指的是由中中字符构成的一个有穷序列字符构成的一个有穷序列;不包含任何字符的序列称为空字（不包含任何字符的序列称为空字（）。）。*表示表示上所有

19、字的全体上所有字的全体,包括空字（包括空字（）。）。例如例如,若若=a,b=a,b 则则*=,a,b,aa,ab,ba,bb,aaa,=,a,b,aa,ab,ba,bb,aaa,2 2 表示不含任何元素的空集表示不含任何元素的空集 。注意注意、和和的区别：的区别：表示不包含任何字符的序列表示不包含任何字符的序列,它是正规集中的一个元素；它是正规集中的一个元素；表示不含任何字的集合表示不含任何字的集合,它是一个空的正规集；它是一个空的正规集；表示由空字组成的集合。表示由空字组成的集合。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集233 3 使用括号可改变运算符的运算次序。使用括号

20、可改变运算符的运算次序。若若规规定定*优优先先于于,优优先先于于|,|,则则在在不不混混淆淆情情况况下下,可可省省 去括号。去括号。4 R4 R自身的自身的n n次连接记为次连接记为 R Rn n=RR=RRR R5 R5 R0 0=,=,R R*=R=R0 0RR1 1RR2 2RR3 3,R,R*为为R R的闭包的闭包 R R+=RR=RR*,称称R R+是是R R的正闭包。的正闭包。闭闭包包R R*中中的的每每个个字字都都是是由由R R中中的的字字经经过过有有限限次次连连接接而而成成的。的。6 6 对于正规式对于正规式R R和和S,S,若它们表示的正规集若它们表示的正规集L(R)=L(S

21、),L(R)=L(S),则称则称R R和和S S等价等价,记为记为R=SR=S。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集24v 正规式具有下列性质：正规式具有下列性质：(1)(1)交换律：交换律：R|S=S|R R|S=S|R (2)(2)结合律：结合律：R|(S|T)=(R|S)|T,R(ST)=(RS)T R|(S|T)=(R|S)|T,R(ST)=(RS)T (3)(3)分配律：分配律：R(S|T)=RS|RT,(R|S)T=RT|STR(S|T)=RS|RT,(R|S)T=RT|ST (4)(4)同一律：同一律：R=R=RR=R=R3.2.1 正规文法、正规式与正规

22、集正规文法、正规式与正规集例例3.1=a,b,R=a(a3.1=a,b,R=a(a|b)b)*是是上正规式上正规式,试求试求R R表示的正规集。表示的正规集。解解:L(R)=L(a(a:L(R)=L(a(a|b)b)*)=L(a)L(a)=L(a)L(a|b)b)*)=L(a)(L(a =L(a)(L(a|b)b)*=L(a)(L(a)L(b)=L(a)(L(a)L(b)*=a(ab)=a(ab)*=aa,b=aa,b*=a,a,b,aa,ab,ba,bb,aaa,=a,a,b,aa,ab,ba,bb,aaa,=a,aa,ab,aaa,aab,aba,abb,aaaa,=a,aa,ab,aaa

23、,aab,aba,abb,aaaa,上所有以上所有以a为首的字为首的字25 例例3.2 3.2 判断下述正规式之间是否等价：判断下述正规式之间是否等价：(1)b(ab)(1)b(ab)*与与(ba)(ba)*b (2)(ab)b (2)(ab)*与与a a*b b*解解:(1):(1)b(ab)b(ab)*对应的正规集是对应的正规集是b b后面出现任意多个后面出现任意多个abab对对 L(b(ab)L(b(ab)*)=b,bab,babab,)=b,bab,babab,(ba)(ba)*b b对应的正规集是对应的正规集是b b前面可出现任意个前面可出现任意个baba对对L(L(ba)(ba)*

24、b)=b)=b,bab,babab,b,bab,babab,因此两者等价因此两者等价。正规式正规式b(ab)b(ab)*及及(ba)(ba)*b b都描述以都描述以b b开头且其后跟以零个或任意开头且其后跟以零个或任意多个多个abab所组成的字符串等。故我们说两个正规式等价，所组成的字符串等。故我们说两个正规式等价，(2)(ab)(2)(ab)*对应的正规集以任意个对应的正规集以任意个abab对出现，即对出现，即 abababababab,而而a a*b b*对应的正规集则是任意个对应的正规集则是任意个a a后接任意个后接任意个b,b,即即a aababb,b,因此两者不等价。因此两者不等价。

25、26例例3.3:3.3:设设 =a,ba,b,则则正规式和正规集正规式和正规集:a a b b (a(a b)(ab)(a b)b)a a*(a(a b)b)*aa abab*a,ba,b aa,ab,ba,bbaa,ab,ba,bb ,a,aa,aaa,aaaa,a,aa,aaa,aaaa,=a=an n|n0|n0 ,a,b,aa,ab,ba,bb,aaa,aab,abb,a,b,aa,ab,ba,bb,aaa,aab,abb,bab,bba,bbb.bab,bba,bbb.=a,b=a,b*a,ab,abb,abbb,abbbb,.a,ab,abb,abbb,abbbb,.=ab =ab

26、n n|n0|n027v通过这一节的学习，要求能根据给出的简单正规式，通过这一节的学习，要求能根据给出的简单正规式，会写出其表示的正规集。会写出其表示的正规集。例例3.4 令令=a,b,其正规式和正规集如下：其正规式和正规集如下：正规式正规式 正规集正规集 1.ba*2.a(a|b)*3.(a|b)*(aa|bb)(a|b)*上所有以上所有以b为首后跟着任意多个为首后跟着任意多个a的字。的字。上所有以上所有以a为首的字。为首的字。上所有含有两个相继的上所有含有两个相继的a或或两个相继的两个相继的b 的字。的字。28例例3.5:令令=A,B,0,1,则：则：正规式正规式 正规集正规集1.(A|B

27、)(A|B|0|1)*2.(0|1)(0|1)*3.问问:正规式正规式,0,110,0|1,1*表示的正规表示的正规集是集是?答答:正规集分别是正规集分别是,0,110,0,1,1,11,111,=1*=1n|n0。上的上的“标识符标识符”的全体的全体 =A,B.A,B,0,1*上上“数数”的全体的全体=0,1.0,1*293.2.1 正规文法、正规式与正规集正规文法、正规式与正规集v 三个概念之间的关系：三个概念之间的关系：一个正规语言可以用正规文法来定义，也可以用正规一个正规语言可以用正规文法来定义，也可以用正规式来定义，有些正规语言很容易用文法定义，有些则用正式来定义，有些正规语言很容易

28、用文法定义，有些则用正规式定义更容易。规式定义更容易。一个正规语言是一个集合（正规集），那么这个集合一个正规语言是一个集合（正规集），那么这个集合可以用正规文法来定义，也可以用正规式来定义。可以用正规文法来定义，也可以用正规式来定义。303.2.2 有限自动机有限自动机v有限自动机（有限自动机（Finite Automata FA）是一种识别装置，它能准确地识别正规集。它是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具为词法分析程序的构造提供了方法和工具。是一种具有离散输入输出系统的数学模型。它是一种具有离散输入输出系统的数学模型。它具有有限数目的内部状态，系统可以

29、根据当前具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继所处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去处理的信息。行为。其当前状态概括了过去处理的信息。313.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带注：状态分为初始状态、中间状态和终止状态。注：状态分为初始状态、中间状态和终止状态。终止状态可以有若干个，而初始状态一般只有一个。终止状态可以有若干个，而初始状态一般只有一个。状态变换状态变换 z e d c b a有限状态控制器有限状态控制器读头读头323.2.2 有限自动机有限自动机v有限自动机模型：有限自动

30、机模型：输入带输入带状态状态:初态初态 z e d c b a有限状态控制器有限状态控制器读头读头 z e d c b a有限状态控制器有限状态控制器读头读头状态状态:中间中间333.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带状态状态:终态终态 z e d c b a有限状态控制器有限状态控制器读头读头 z e d c b a有限状态控制器有限状态控制器读头读头状态状态:非终非终态态注：读头全部读完，且此时状态为终态，则说明此输入串正确。注：读头全部读完，且此时状态为终态，则说明此输入串正确。注：读头全部读完，而此时状态不是终态，则说明此输入串错误。注：读头全部

31、读完，而此时状态不是终态，则说明此输入串错误。状态的变换和符号的读入用一个图形结构来表示。（状态的变换和符号的读入用一个图形结构来表示。（状态转换图状态转换图）343.2.3 状态转换图状态转换图 P41 v状态转换图：状态转换图：状态转换图是一张有限方向图，只包含有限状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。个状态，即有限个结点。P41P41 1.1.结点代表结点代表状态状态，用，用圆圈圆圈表示表示 2.2.终止状态终止状态用用双圈双圈表示表示 3.3.初始状态初始状态前标记符号前标记符号“”来表示（可省）来表示（可省）4.4.状态之间用状态之间用箭弧箭弧连结，箭弧上的连结

32、，箭弧上的标记标记代表在射出结点（即代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类，箭弧标箭弧始结点）状态下可能出现的输入字符或字符类，箭弧标记表示记表示状态转换的条件状态转换的条件。5.5.状态图有状态图有一个初态，多个终态一个初态，多个终态。6.6.状态转换图可识别一定的状态转换图可识别一定的字符串字符串（单词）。（单词）。7.7.状态转换图用于表示单词结构状态转换图用于表示单词结构,从状态转换图的初态到终态从状态转换图的初态到终态间间,每条路径上字符的连接每条路径上字符的连接,就构成了该状态图的合法单词。就构成了该状态图的合法单词。35例例3.6 P41 3.6 P41

33、图图3.2(a)3.2(a)表示：表示：在状态在状态1 1下，若输入字符为下，若输入字符为X X，则读进，则读进X X，并转换到，并转换到状态状态2 2。若输入字符为若输入字符为Y Y，则读进，则读进Y Y，并转换到状态，并转换到状态3 3。若输入字符非若输入字符非X X和非和非Y Y，则此转换图不工作。，则此转换图不工作。231Y YX X36例例3.7 P41 3.7 P41 图图3.2(b)3.2(b)表示：识别标识符的状态转换图如下表示：识别标识符的状态转换图如下:其中状态其中状态0 0为初态，为初态，2 2为终态；为终态；识别标识符的过程是：从初态识别标识符的过程是：从初态0 0开始

34、，若在状态开始，若在状态0 0下输入字下输入字符为字母，则读进它，并转换到状态符为字母，则读进它，并转换到状态1 1。在状态在状态1 1之下，若输入字符为字母或数字，则读进它，并之下，若输入字符为字母或数字，则读进它，并重新进入状态重新进入状态1 1。一直重复这个过程直到发现输入字符不再是字母或数字时一直重复这个过程直到发现输入字符不再是字母或数字时（这个字符已经被读进）进入状态（这个字符已经被读进）进入状态2 2；状态状态2 2是终态，意味着到此已识别出一个标识符；是终态，意味着到此已识别出一个标识符；终态上打个星号表示单词尾部多跟一个字符终态上打个星号表示单词尾部多跟一个字符,应该去掉。应

35、该去掉。若在状态若在状态0 0时输入的字符不为时输入的字符不为“字母字母”，则意味着这个转，则意味着这个转换图不工作。换图不工作。012 2(b)字母字母字母或数字字母或数字其它其它*37(c)012 2数字数字数字数字其它其它*例例3.8 P41 3.8 P41 图图3.2(c)3.2(c)表示：识别无符号整数的状态转表示：识别无符号整数的状态转换图如下：换图如下：在在状状态态转转换换图图中中,到到达达单单词词符符号号的的终终态态时时即即给给出出相相应应的的单单词词编编码码。若若到到达达终终态态时时多多读读入入了了一一个个符符号号,则则识识别别出出该该单单词词后后再再将将多多读读入入的的那那

36、个个符符号号退退回回。对对此此类类情情况况的的处处理理方方法是在终态上以法是在终态上以*作为标识。作为标识。38例例3.9 P41 3.9 P41 图图3.2(d)3.2(d)表示：识别实数的状态转换表示：识别实数的状态转换图如下：图如下：01数字数字数字数字其它其它*23456数字数字数字数字 数字数字E或或e+或或-数字数字E或或e其它其它数字数字7(d)初态初态0 0终态终态7 7之之间任意一个路径都间任意一个路径都表示一个实数。表示一个实数。小数形式的实数：小数形式的实数：指数形式的实数：指数形式的实数：该转换图可以识别下面形式的一些实数该转换图可以识别下面形式的一些实数:123.,.

37、123,123E3,123.456,123.45e2,.123E+10,123.456E-3 等等39状态转换图识别字符串状态转换图识别字符串:综合例综合例v一个非常重要的事实是，一个非常重要的事实是，大多数程序语言的单词符大多数程序语言的单词符号都可以用状态转换图予以识别号都可以用状态转换图予以识别。v作为一个综合例子，作为一个综合例子，教材教材P42-P46.P42-P46.构造了一个识别构造了一个识别某个简单语言的所有单词符号的状态转换图，并给某个简单语言的所有单词符号的状态转换图，并给出了对应的词法分析程序。出了对应的词法分析程序。v希望同学们好好读一下。为完成的实验希望同学们好好读一

38、下。为完成的实验 -设计并设计并实现一个小语言的词法分析程序实现一个小语言的词法分析程序,可以以这个例子可以以这个例子做参考。做参考。40识别简单语言单词符号的转换图识别简单语言单词符号的转换图v参见P43.图3.37非非*+312字母字母0*非字母与数字非字母与数字字母或数字字母或数字=数字数字数字数字空白空白*4*非数字非数字568*9*13其它其它2态：识别标识态：识别标识符和关键字符和关键字4态：识别整常数态：识别整常数8态：识别态：识别*9态：识别态：识别*13态：识别错误态：识别错误5态：识别态：识别=6态：识别态：识别+41v状态转换图容易用程序实现状态转换图容易用程序实现:即容

39、易由转换图编写词法分析程序。即容易由转换图编写词法分析程序。v最简单的办法是让每个状态结点对应一小段程序最简单的办法是让每个状态结点对应一小段程序。根据画出的识别单词的状态转换图构造词法分根据画出的识别单词的状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的工作；词法分析程序的控制程序模拟状态转换图的状态转换。的状态转换。3.2.4 状态转换图的实现状态转换图的实现 (自学自学)49 本节内容及关系本节内容及关系正规表达正规表达式式E用用正规集正规集L(E)表示表示,值集值集正规文法正规文法

40、G正规语言正规语言L(G)用用产生产生单词符号结单词符号结构的描述构的描述词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现有限自动机有限自动机 FA M状态转换图状态转换图单词符号集单词符号集L(M)形式化形式化识别识别,接受接受三者相同三者相同等价等价等价等价等价等价50 作业：作业：P64 8(1)(2)9(1)51(b)012 20|10其它其它*0|1012 2(a)字母字母 字母字母其它其它*数字数字523.2.5 确定有限自动机确定有限自动机v确定有限自动机（确定有限自动机（DFA）(Deterministic FA)一个确定有限自动机一个确定有限自动机(DFA M)是一个

41、五元式是一个五元式:DFA M=(S,s0,F)注：这里注：这里确定确定的含义，就是状态转换关系的含义，就是状态转换关系是一个函数，即对是一个函数，即对于给定的于给定的当前状态当前状态s和当前读入的字符和当前读入的字符a有有唯一确定唯一确定的的下一状下一状态态s。1.S 1.S 是有限是有限状态集状态集；2.2.是一个有穷字母表是一个有穷字母表,每个元素为一每个元素为一字符字符；3.s3.s0 0S,S,是是唯一唯一的的初态初态;4.F4.F S,S,是是终态集终态集（可空）。（可空）。5.5.是一个是一个单值单值映射函数映射函数,(s,a)=s,(s,a)=s，指明若当前的状，指明若当前的状

42、态为态为s s，而输入，而输入字符为字符为a a时，则下一个状态是时，则下一个状态是s s；533.2.5 确定有限自动机确定有限自动机vDFA表示表示 状态转换矩阵状态转换矩阵 状态转换图状态转换图DFADFA的映射关系可以用一个矩阵表示：的映射关系可以用一个矩阵表示：该矩阵的该矩阵的行行表示表示状态状态列列表示输入表示输入字符字符，矩阵元素表示，矩阵元素表示(s,a)(s,a)的值的值该矩阵称为该矩阵称为状态转换矩阵或状态转换表状态转换矩阵或状态转换表54例如例如3.10 3.10 P48 P48 DFA M=(0,1,2,3,a,b,0,3)DFA M=(0,1,2,3,a,b,0,3)

43、其中其中为为:(0,a)=1 (1,a)=3 (2,a)=1 (3,a)=3:(0,a)=1 (1,a)=3 (2,a)=1 (3,a)=3 (0,b)=2 (1,b)=2 (2,b)=3 (3,b)=3 (0,b)=2 (1,b)=2 (2,b)=3 (3,b)=3 状态转换矩阵状态转换矩阵可表示为可表示为:状态图状态图可表示为可表示为:ab012132213333状状态态字字 符符a012abbaabb355DFA识别识别(读出读出,接受接受)字字vDFADFA识别字识别字：对于对于*中的任何一个字中的任何一个字，若存在一条从初态，若存在一条从初态结点到某一终态结点的结点到某一终态结点的通

44、路通路，且这条通路上所有箭且这条通路上所有箭弧的标记符连接成的字等于弧的标记符连接成的字等于，则称，则称 为为DFA MDFA M所识所识别。别。例例:P48:P48 图图3.53.5的的DFADFA识别字识别字abbab,abbab,因为存在路因为存在路径径 012333012333；但不接受字；但不接受字ababa,ababa,因为不存在识别因为不存在识别路径。路径。a,ba0123abbab56DFA识别字、语言识别字、语言L(M)vDFADFA识别空字识别空字 若若M M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则称空字则称空字 可以为可以为DFA MDFA M所识别。所

45、识别。例例:图图3.53.5的的DFADFA不识别空字不识别空字。vDFA MDFA M所能识别的字的全体记为所能识别的字的全体记为L(M)L(M)。例：例：P48 P48 图图3.53.5的的DFA MDFA M识别的字的全体识别的字的全体 L(M)=L(M)=上所有含有相继两个上所有含有相继两个a a或相继两个或相继两个b b的字的字 a,ba0123abbab57DFA：练习：练习1设有设有 DFA M=(0,1,2,a,b,DFA M=(0,1,2,a,b,0,1,2),0,1,2)其中：其中：（0,a)=2;0,a)=2;（0,b)=10,b)=1 （1,a)=;1,a)=;（1,b

46、)=21,b)=2 （2,a)=2;2,a)=2;（2,b)=22,b)=2问问：该：该DFADFA有几个状态？几个输入字符？初态？终有几个状态？几个输入字符？初态？终态？画出其转换图。态？画出其转换图。n解解：有有0 0，1 1，2 2共共三三个个状状态态。0 0为为初初态态，1 1和和2 2为为终终态态。输入字符为输入字符为a,ba,b两个。两个。其状态转换图如其状态转换图如:a,ba012bb583.2.6 非确定有限自动机非确定有限自动机1.1.S S是一有限状态集是一有限状态集;2.2.是一个有穷字母表是一个有穷字母表,每个元素为一字符每个元素为一字符;3.3.F F S,S,是是终

47、态集终态集。4.4.S S0 0 S,S,是是初态集初态集;5.5.是一个是一个多值多值映射函数映射函数,S S*2s 其含义为其含义为:在状态在状态S S,输入输入字字时时,将转换到下一状态集将转换到下一状态集2s。一个非确定有限自动机一个非确定有限自动机(NFA M)是一个五元式是一个五元式:NFA M=(S,S0,F)而而DFA是字符是字符注：非确定主要是指后继状态可有多个。注：非确定主要是指后继状态可有多个。DFA是是NFA的特例。的特例。59如如:一个一个NFAMNFAM也可用状态图表示。也可用状态图表示。3.2.6 非确定有限自动机非确定有限自动机a0bba,ba|b123a60假

48、定假定DFADFA有有m m个状态、个状态、n n个输入符个输入符,则状态转换图含则状态转换图含m m个状态个状态,每个状态最多有每个状态最多有n n条输出边与其它状态相连条输出边与其它状态相连,每条边用每条边用中中一个一个字符字符作标记，整个图含作标记，整个图含一个初态一个初态和若干个终态。和若干个终态。假定假定NFANFA有有m m个状态、个状态、n n个输入字个输入字,则状态转换图含则状态转换图含m m个状态个状态,每个状态最多有每个状态最多有n n条输出边与其它状态相连条输出边与其它状态相连,每条边用每条边用*中中一个字一个字作标记，整个图含作标记，整个图含若干个初态若干个初态和若干个

49、终态。和若干个终态。NFANFA的状态转换函数的状态转换函数是一是一多值多值函数，即函数，即(s(si i,)=,)=某些某些状态的集合状态的集合，它表示由当前状态和当前输入字符不能唯，它表示由当前状态和当前输入字符不能唯一确定下一状态，即允许同一状态对同一输入字可有不同一确定下一状态，即允许同一状态对同一输入字可有不同输出边；而输出边；而DFADFA的状态转换函数的状态转换函数是一个是一个单值单值函数。函数。NFA和和DFA的主要区别的主要区别61例例3.11 DFA M=(s3.11 DFA M=(s0 0,s,s1 1,s,s2 2,a,b,s,a,b,s0 0,s,s2 2),),且且

50、 (s(s0 0,a)=s,a)=s1 1,(s,(s0 0,b)=s,b)=s2 2,(s,(s1 1,a)=s,a)=s1 1 (s (s1 1,b)=s,b)=s2 2,(s,(s2 2,a)=s,a)=s2 2,(s,(s2 2,b)=s,b)=s1 1 试给出试给出M M的状态转换图与状态转换矩阵。的状态转换图与状态转换矩阵。解：状态转换图：解：状态转换图：状态转换矩阵：状态转换矩阵：字符字符状态状态abs0s1s2s1s1s2s2s2s1as12 s2s0abbab62例例3.12 3.12 NFA M=(sNFA M=(s0 0,s,s1 1,s,s2 2,a,b,s,a,b,s