《第3章-词法分析-编译原理-陈火旺优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第3章-词法分析-编译原理-陈火旺优秀PPT.ppt（107页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1v内容：内容：v 状态转换图、正规式和有限自动机、词法分析器的状态转换图、正规式和有限自动机、词法分析器的自动生成自动生成v驾驭驾驭:v 正规式、状态转换图，正规式、状态转换图，DFN的概念、的概念、NFA的概念，的概念，将将NFA转转 v 换为换为DFA、DFA的化简、正规式与有限自动机间的的化简、正规式与有限自动机间的转换。转换。v理解理解:v 正规文法与有穷自动机间的转换正规文法与有穷自动机间的转换v 词法分析器的自动产生工具词法分析器的自动产生工具LEX v v 第第3章章 词法分析词法分析教学要求教学要求2本章在编译程序中的地位本章在编译程序中的地位表表格格管管理理词法分析器词法分
2、析器语法分析器语法分析器语义分析与中间代码产生语义分析与中间代码产生优化器优化器目标代码生成器目标代码生成器源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码出出错错处处理理3v执行词法分析的程序称为又称为词法分析器执行词法分析的程序称为又称为词法分析器或扫描器或扫描器.v词法分析的任务：从左至右逐个地扫描源程词法分析的任务：从左至右逐个地扫描源程序的字符串序的字符串,依据词法规则识别出一个个正依据词法规则识别出一个个正确的单词，并转换为相应的二元式形式，交确的单词，并转换为相应的二元式形式，交给语法分析运用。给语法分析运用。v把作为字符串的源程序改造
3、成单词符号串的把作为字符串的源程序改造成单词符号串的词法分析是编译的基础。词法分析是编译的基础。3.1 设计设计词法分析器词法分析器时应考虑的几个问题时应考虑的几个问题43.1.1 词法分析阶段的必要性词法分析阶段的必要性 v词法分析的工作纳入整个语法分析中一揽子地进行，原则上是词法分析的工作纳入整个语法分析中一揽子地进行，原则上是可行的。可行的。v在设计一个编译程序时，通常是把对源程序的结构分析分为词在设计一个编译程序时，通常是把对源程序的结构分析分为词法分析和语法分析两个相对独立的阶段来完成。法分析和语法分析两个相对独立的阶段来完成。v第一，描述单词的结构比描述源程序的其它语法结构要简洁得
4、第一，描述单词的结构比描述源程序的其它语法结构要简洁得多，仅运用多，仅运用3型文法也就基本够用了。型文法也就基本够用了。v其次，由于把词法分析和语法分析分开，可使编译程序各部分其次，由于把词法分析和语法分析分开，可使编译程序各部分的功能更为单一，整个编译程序的结构也更加清晰，从而有利的功能更为单一，整个编译程序的结构也更加清晰，从而有利于编译程序的编写和调整。于编译程序的编写和调整。v上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译程序的逻辑功能而言，而不确定指的是编译程序的执行流程。程序的逻辑功能而言，而不确定指的是编译程序的执行流
5、程。53.1.2 词法分析器的输出形式词法分析器的输出形式v词法分析器输出的单词常常表示为二元式形式词法分析器输出的单词常常表示为二元式形式 v (单词种别单词种别,单词符号的属性值单词符号的属性值)v单词种别供应应语法分析程序运用；单词种别供应应语法分析程序运用；v单词符号的属性值供应应语义分析程序运用。单词符号的属性值供应应语义分析程序运用。v具体的分类设计方法以便利语法分析程序运用为原具体的分类设计方法以便利语法分析程序运用为原则。则。63.1.2 词法分析器的输出形式词法分析器的输出形式v程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：关键字关键字(保留字或基本字保留字
6、或基本字)：如：如 if,then,else,while,doif,then,else,while,do等等 标识符标识符：用来表示各种名字，如：用来表示各种名字，如 x1x1常量常量：如：如 256256，3.143.14，true,true,abcabc 运算符运算符：如：如 、*、/等等等等分界符分界符：如：如 逗号，分号，冒号等逗号，分号，冒号等73.1.2 词法分析器的输出形式词法分析器的输出形式v单词种别单词种别:v 一个语言的单词符号如何分类、分为几一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的便利。通常，每类、如何编码主要取决于处理上的便利。通常，每种单词对应
7、一个整数码。种单词对应一个整数码。v 留意：保留字、运算符和界符的个数确定，留意：保留字、运算符和界符的个数确定，v 标识符和常数的个数不确定。标识符和常数的个数不确定。v 保留字：可全体视为一种，也可一字一种；保留字：可全体视为一种，也可一字一种；v 标识符：统归为一种；标识符：统归为一种；v 常数：统归为一种常数：统归为一种,或按整、实、布尔等再分；或按整、实、布尔等再分；v 运算符和界符：一符一种，或统归为一种。运算符和界符：一符一种，或统归为一种。83.1.2 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值v 单词符号的属性是指单词符号的特征值单词符号的属性
8、是指单词符号的特征值。v假如一个种别只含有一个单词符号，那么对于这个单假如一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因而不须要词符号，种别编码就完全代表它自身了，因而不须要属性值。属性值。v若一个种别含有多个单词符号，那么，对于它的每个若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单单词符号，除了给出种别编码之外，还应给出有关单词符号的属性值。词符号的属性值。93.1.2 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值标识符和常数标识符和常数 标识符的标识符的内部码内部码(如如ASCII
9、码等等码等等)和和常数本身的值常数本身的值(二进制，逻辑值等二进制，逻辑值等)来表示。来表示。标识符的标识符的符号表入口地址符号表入口地址作为其单词符号的属性值作为其单词符号的属性值,常量在其常量在其常量表中的入口地址常量表中的入口地址作为其单词符号的属性作为其单词符号的属性值。值。每个基本字占一个单词种别，单词符号的属性值缺省每个基本字占一个单词种别，单词符号的属性值缺省。对于界符，运算符通常一个符号一个种别，单词符号的对于界符，运算符通常一个符号一个种别，单词符号的属性值缺省属性值缺省例例:参见参见P42.P42.表表3.1 3.1 单词符号及种别编码单词符号及种别编码103.1.3 词法
10、分析器作为独立子程序词法分析器作为独立子程序v词法分析可接受如下两种处理结构：词法分析可接受如下两种处理结构：v把词法分析程序作为主程序。将词法分析作为独立把词法分析程序作为主程序。将词法分析作为独立的一遍来完成。的一遍来完成。v把词法分析程序作为语法分析程序调用的子程序。把词法分析程序作为语法分析程序调用的子程序。v每当语法分析器须要一个单词符号时就调用这个子每当语法分析器须要一个单词符号时就调用这个子程序。程序。v每一次调用，词法分析器从源程序字符串中识别出每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法一个单词符号，并把它的内部表示二元组交给语法分
11、析器处理。分析器处理。113.1.4 源程序的输入、预处理及源程序的输入、预处理及超前搜寻超前搜寻词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。输输入入串串一一般般放放在在一一个个输输入入缓缓冲冲区区中中。词词法法分分析析器器的的工工作作可可以以干干脆脆在在输输入入缓缓冲冲区区中中进进行行。但但在在很很多多状状况况下下，可可以以先先预预处处理理输输入入串串，识识别工作将更便利。（参见别工作将更便利。（参见P40 图图3.1）123.1.4 源程序的输入、预处理及源程序的输入、预处理及超前搜寻超前搜寻v预处理的缘由预处理的缘由v 源程序中包含回车源程序中包含回车
12、,换行换行,多余空白符多余空白符,注释行等注释行等编辑字符编辑字符,它们对程序逻辑功能无任何影响，它们对程序逻辑功能无任何影响，在词在词法分析之前法分析之前,首先要剔除掉这些符号首先要剔除掉这些符号,使得词法分析使得词法分析更为简洁。更为简洁。v 一行语句结束应配上一个特殊字符说明。一行语句结束应配上一个特殊字符说明。v 有些语言要识别标号区，区分标号语句，找有些语言要识别标号区，区分标号语句，找出续行符连接成完整语句等。出续行符连接成完整语句等。v 输出源程序清单以便复核。输出源程序清单以便复核。v 预处理子程序任务预处理子程序任务v 从输入缓冲区中读取源程序，预处理后送入从输入缓冲区中读取
13、源程序，预处理后送入扫描缓冲区。此时，扫描缓冲区的字符都是有效字扫描缓冲区。此时，扫描缓冲区的字符都是有效字符。符。v 词法分析程序这时可以再对扫描缓冲区进行词法分析程序这时可以再对扫描缓冲区进行扫描。扫描。133.1.4 源程序的输入、预处理及源程序的输入、预处理及超前搜寻超前搜寻v超前搜寻超前搜寻v 对于有些语言，关键字不爱护，关键字与用户对于有些语言，关键字不爱护，关键字与用户自定义标识符间没有界符，要在上下文环境中识别自定义标识符间没有界符，要在上下文环境中识别单词，这时须要超前搜寻方法来识别关键字。单词，这时须要超前搜寻方法来识别关键字。v 例如：例如：FORTRAN语言：语言：v
14、1.DO10K=1，50 v 2.DO10K=1.50v扫描缓冲区的结构扫描缓冲区的结构 (自学自学)16词法分析程序设计词法分析程序设计v 设计方法：设计方法：写出该语言的词法规则；写出该语言的词法规则；把词法规则转换为相应的把词法规则转换为相应的状态转换图状态转换图；把各转换图的初态连在一起，构成识别该把各转换图的初态连在一起，构成识别该 语言的语言的自动机自动机；(4)(4)设计扫描器设计扫描器 173.2 正规文法和有限自动机正规文法和有限自动机v 这节介绍这节介绍词法规则词法规则的形式表示的形式表示(正规式正规式),从从正规式正规式向有限自动机的转化向有限自动机的转化.正规式正规式有
15、限自动机有限自动机词法分析器词法分析器控制程序控制程序自动生成器自动生成器转化转化合成合成183.2.1 正规文法、正规集与正规式正规文法、正规集与正规式v正规文法：正规文法：是是chomsky3型文法。型文法。例如：标识符这种单词可以用下面的规则描述例如：标识符这种单词可以用下面的规则描述|（|）表示随意字母，表示随意字母，表示随意数字表示随意数字注：正规文法描述是注：正规文法描述是正规集正规集的文法，可用于描述程序设计的文法，可用于描述程序设计语言的语法部分语言的语法部分。19v 对于一个正规文法的语言提炼出一个简洁的公式，用这个式对于一个正规文法的语言提炼出一个简洁的公式，用这个式子来对
16、它进行子来对它进行形式化的表示形式化的表示，这个式子叫，这个式子叫正规式正规式。v正规式：正规式：也称也称正则表达式正则表达式,是说明是说明单词的模式单词的模式的一种重要的的一种重要的表示法（记号）；是定义正规集的数学工具；用来描述单词表示法（记号）；是定义正规集的数学工具；用来描述单词符号。符号。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集注：正规集是集合，可有穷也可无穷。注：正规集是集合，可有穷也可无穷。可通过正规式来形式化表示。可通过正规式来形式化表示。v 正规集：正规集：由正规文法产生的语言所构成的集合。由正规文法产生的语言所构成的集合。203.2.1 正规文法、正规式
17、与正规集正规文法、正规式与正规集下面以标识符为例说明下面以标识符为例说明正规式正规式与与正规集正规集:标识符标识符标识符标识符是以字母开头的字母数字串。是以字母开头的字母数字串。若用若用L L表示字母表示字母,用用D D表示数字表示数字,则标识符可表示为则标识符可表示为:L(L|D):L(L|D)*其中并置表示两者的其中并置表示两者的连接连接,|,|表示两者选一表示两者选一,*,*表示零次或多次引用。表示零次或多次引用。L(L|D)L(L|D)*为为标识符的正规式标识符的正规式，该正规式表示的集合为该正规式表示的集合为标识符的正规集标识符的正规集。21v下面是正规式和它所定义的正规集的递归定义
18、。下面是正规式和它所定义的正规集的递归定义。v 1),是是 上的正规式上的正规式,所表示的正规集为所表示的正规集为 ,;v 2)若若 a,则则 a 为正规式为正规式,所表示的正规集为所表示的正规集为 a;v 3)设设U,V 为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 L(U),L(V);v 则则 U|V为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 L(U)L(V);v UV为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 L(U)L(V);v V*为为 上的正规式上的正规式,所表示的正规集为所表示的正规集为 (L(V)*;v 4)仅当有限次运用上述
19、三步骤而定义的表达式仅当有限次运用上述三步骤而定义的表达式,才是才是 上的正规式上的正规式,而这些正规式所表示的字集才是而这些正规式所表示的字集才是上的正规集。上的正规集。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集或运算或运算连接积连接积22说明：说明：1上的一个字指的是由上的一个字指的是由中字符构成的一个有穷序列中字符构成的一个有穷序列;不包含任何字符的序列称为空字（不包含任何字符的序列称为空字（）。）。*表示表示上全部字的全体上全部字的全体,包括空字（包括空字（）。）。例如例如,若若=a,b 则则*=,a,b,aa,ab,ba,bb,aaa,2 表示不含任何元素的空集表示
20、不含任何元素的空集。留意留意、和和的区分：的区分：表示不包含任何字符的序列表示不包含任何字符的序列,它是正规集中的一个元素；它是正规集中的一个元素；表示不含任何字的集合表示不含任何字的集合,它是一个空的正规集；它是一个空的正规集；表示由空字组成的集合。表示由空字组成的集合。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集233 3 运用括号可变更运算符的运算次序。运用括号可变更运算符的运算次序。若若规规定定*优优先先于于,优优先先于于|,|,则则在在不不混混淆淆状状况况下下,可可省省 去括号。去括号。4 R4 R自身的自身的n n次连接记为次连接记为 Rn=RRR Rn=RRR5
21、R0=,5 R0=,R*=R0R1R2R3,R*R*=R0R1R2R3,R*为为R R的闭包的闭包 R+=RR*,R+=RR*,称称R+R+是是R R的正闭包。的正闭包。闭闭包包R*R*中中的的每每个个字字都都是是由由R R中中的的字字经经过过有有限限次次连连接接而而成成的。的。6 6 对于正规式对于正规式R R和和S,S,若它们表示的正规集若它们表示的正规集L(R)=L(S),L(R)=L(S),则称则称R R和和S S等价等价,记为记为R=SR=S。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集24v 正规式具有下列性质：正规式具有下列性质：v (1)交换律：交换律：R|S=
22、S|R v (2)结合律：结合律：R|(S|T)=(R|S)|T,R(ST)=(RS)T v (3)安排律：安排律：R(S|T)=RS|RT,(R|S)T=RT|STv (4)同一律：同一律：R=R=R3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集例例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
23、)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,aab,aba,abb,aaaa,上全部以上全部以a为首的字为首的字25 例例3.2 3.2 推断下述正规式之间是否等价：推断下述正规式之间是否等价：(1)b(ab)*(1)b(ab)*与与(ba)*b (2)(ab)*(ba)*b (2)(ab)*与与a*b*a*b*解解:(1)b(ab)*:(1)b(ab)*对应的正规集是对应的正规集是b b后面出现随意多
24、个后面出现随意多个abab对对 L(b(ab)*)=b,bab,babab,L(b(ab)*)=b,bab,babab,(ba)*b (ba)*b对应的正规集是对应的正规集是b b前面可出现随意个前面可出现随意个baba对对L(ba)*b)=b,bab,babab,L(ba)*b)=b,bab,babab,因此两者等价。因此两者等价。正规式正规式b(ab)*b(ab)*及及(ba)*b(ba)*b都描述以都描述以b b开头且其后跟以零个或随意开头且其后跟以零个或随意多个多个abab所组成的字符串等。故我们说两个正规式等价，所组成的字符串等。故我们说两个正规式等价，(2)(ab)*(2)(ab)
25、*对应的正规集以随意个对应的正规集以随意个abab对出现，即对出现，即 ababab,ababab,而而a*b*a*b*对应的正规集则是随意个对应的正规集则是随意个a a后接随意个后接随意个b,b,即即aabb,aabb,因此两者不等价。因此两者不等价。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,b
26、a,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 =abn n|n0|n027v通过这一节的学习，要求能依据给出的简洁正规式，通过这一节的学习，要求能依据给出的简洁正规式，会写出其表示的正规集。会写出其表示的正规集。v例例3.4 令令=a,b,其正规式和正规集如下：其正规式和正规集如下：v 正规式正规式 正规集正规集v 1.ba*v 2.a(a|b)*v 3.(a|b)*(aa|bb)(a|b)*上
27、全部以上全部以b为为首后跟着随意多个首后跟着随意多个a的字。的字。上全部以上全部以a为为首的字。首的字。上全部含有两个相上全部含有两个相继继的的a或或两个相两个相继继的的b 的字。的字。28例例3.5:令令=A,B,0,1,则：则：正规式正规式 正规集正规集1.(A|B)(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.
28、2.1 正规文法、正规式与正规集正规文法、正规式与正规集v 三个概念之间的关系：三个概念之间的关系：v 一个正规语言可以用正规文法来定义，也可一个正规语言可以用正规文法来定义，也可以用正规式来定义，有些正规语言很简洁用文法定以用正规式来定义，有些正规语言很简洁用文法定义，有些则用正规式定义更简洁。义，有些则用正规式定义更简洁。v 一个正规语言是一个集合（正规集），那么这一个正规语言是一个集合（正规集），那么这个集合可以用正规文法来定义，也可以用正规式来个集合可以用正规文法来定义，也可以用正规式来定义。定义。303.2.2 有限自动机有限自动机v有限自动机（有限自动机（Finite Automa
29、ta FA）v是一种识别装置，它能精确地识别正规集。是一种识别装置，它能精确地识别正规集。它为词法分析程序的构造供应了方法和工具。它为词法分析程序的构造供应了方法和工具。v 是一种具有离散输入输出系统的数学模型。是一种具有离散输入输出系统的数学模型。它具有有限数目的内部状态，系统可以依据它具有有限数目的内部状态，系统可以依据当前所处的状态和面临的输入字符确定系统当前所处的状态和面临的输入字符确定系统的后继行为。其当前状态概括了过去处理的的后继行为。其当前状态概括了过去处理的信息。信息。313.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带注：状态分为初始状态、中间状
30、态和终止状态。注：状态分为初始状态、中间状态和终止状态。终止状态可以有若干个，而初始状态一般只有一个。终止状态可以有若干个，而初始状态一般只有一个。状态变换状态变换 z e d c b a有限状态控制器有限状态控制器读头读头323.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带状态状态:初态初态 z e d c b a有限状态控制器有限状态控制器读头读头 z e d c b a有限状态控制器有限状态控制器读头读头状态状态:中间中间333.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带状态状态:终态终态 z e d c b a有限状态控制器
31、有限状态控制器读头读头 z e d c b a有限状态控制器有限状态控制器读头读头状态状态:非终非终态态注：读头全部读完，且此时状态为终态，则说明此输入串正确。注：读头全部读完，且此时状态为终态，则说明此输入串正确。注：读头全部读完，而此时状态不是终态，则说明此输入串错误。注：读头全部读完，而此时状态不是终态，则说明此输入串错误。状态的变换和符号的读入用一个图形结构来表示。（状态的变换和符号的读入用一个图形结构来表示。（状态转换图状态转换图）343.2.3 状态转换图状态转换图 P41 v状态转换图：状态转换图是一张有限方向图，只包含状态转换图：状态转换图是一张有限方向图，只包含有限个状态，即
32、有限个结点。有限个状态，即有限个结点。P41v 1.结点代表状态，用圆圈表示结点代表状态，用圆圈表示v 2.终止状态用双圈表示终止状态用双圈表示v 3.初始状态前标记符号初始状态前标记符号“”来表示（可省）来表示（可省）v 4.状态之间用箭弧连结，箭弧上的标记代表在射出状态之间用箭弧连结，箭弧上的标记代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或结点（即箭弧始结点）状态下可能出现的输入字符或字符类，箭弧标记表示状态转换的条件。字符类，箭弧标记表示状态转换的条件。v 5.状态图有一个初态，多个终态。状态图有一个初态，多个终态。v 6.状态转换图可识别确定的字符串（单词）。状态转换图可识
33、别确定的字符串（单词）。v 7.状态转换图用于表示单词结构状态转换图用于表示单词结构,从状态转换图的初从状态转换图的初态到终态间态到终态间,每条路径上字符的连接每条路径上字符的连接,就构成了该状态就构成了该状态图的合法单词。图的合法单词。35例例3.6 P41 3.6 P41 图图3.2(a)3.2(a)表示：表示：在状态在状态1 1下，若输入字符为下，若输入字符为X X，则读进，则读进X X，并转换到，并转换到状态状态2 2。若输入字符为若输入字符为Y Y，则读进，则读进Y Y，并转换到状态，并转换到状态3 3。若输入字符非若输入字符非X X和非和非Y Y，则此转换图不工作。，则此转换图不工
34、作。231Y YX X36例例3.7 P41 3.7 P41 图图3.2(b)3.2(b)表示：识别标识符的状态转换图如下表示：识别标识符的状态转换图如下:其中状态其中状态0 0为初态，为初态，2 2为终态；为终态；识别标识符的过程是：从初态识别标识符的过程是：从初态0 0起先，若在状态起先，若在状态0 0下输入字符下输入字符为字母，则读进它，并转换到状态为字母，则读进它，并转换到状态1 1。在状态在状态1 1之下，若输入字符为字母或数字，则读进它，并重之下，若输入字符为字母或数字，则读进它，并重新进入状态新进入状态1 1。始终重复这个过程直到发觉输入字符不再是字母或数字时始终重复这个过程直到
35、发觉输入字符不再是字母或数字时（这个字符已经被读进）进入状态（这个字符已经被读进）进入状态2 2；状态状态2 2是终态，意味着到此已识别出一个标识符；是终态，意味着到此已识别出一个标识符；终态上打个星号表示单词尾部多跟一个字符终态上打个星号表示单词尾部多跟一个字符,应当去掉。应当去掉。若在状态若在状态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)初态初态00终态终态7 7之之间随意一个路径都间随意一个路径都表示一个实数。表示一个实数。小数形式的实数：小数形式的实数：指
37、数形式的实数：指数形式的实数：该转换图可以识别下面形式的一些实数该转换图可以识别下面形式的一些实数:123.,.123,123E3,123.456,123.45e2,.123E+10,123.456E-3 等等39状态转换图识别字符串状态转换图识别字符串:综合例综合例v一个特别重要的事实是，大多数程序语言的单词符一个特别重要的事实是，大多数程序语言的单词符号都可以用状态转换图予以识别。号都可以用状态转换图予以识别。v作为一个综合例子，教材作为一个综合例子，教材P42-P46.P42-P46.构造了一个识别构造了一个识别某个简洁语言的全部单词符号的状态转换图，并给某个简洁语言的全部单词符号的状态
38、转换图，并给出了对应的词法分析程序。出了对应的词法分析程序。v希望同学们好好读一下。为完成的试验希望同学们好好读一下。为完成的试验-设计并设计并实现一个小语言的词法分析程序实现一个小语言的词法分析程序,可以以这个例子可以以这个例子做参考。做参考。40识别简洁语言单词符号的转换图识别简洁语言单词符号的转换图v参见P43.图3.37非非*+312字母字母0*非字母与数字非字母与数字字母或数字字母或数字=数字数字数字数字空白空白*4*非数字非数字568*9*13其它其它2态：识别标识态：识别标识符和关键字符和关键字4态：识别整常数态：识别整常数8态：识别态：识别*9态：识别态：识别*13态：识别错误
39、态：识别错误5态：识别态：识别=6态：识别态：识别+41v状态转换图简洁用程序实现状态转换图简洁用程序实现:v 即简洁由转换图编写词法分析程序。即简洁由转换图编写词法分析程序。v最简洁的方法是让每个状态结点对应一小段程序。最简洁的方法是让每个状态结点对应一小段程序。v 依据画出的识别单词的状态转换图构造词法分析依据画出的识别单词的状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态的程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的限制程序模拟状态转换图的工作；词法分析程序的限制程序模拟状态转换图的状态转换。状态转换。3.2.4 状态转换图的实现状态转换图的实现 (自
40、学自学)49 本节内容及关系本节内容及关系正规表达正规表达式式E用用正规集正规集L(E)表示表示,值集值集正规文法正规文法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确定有限自
41、动机（确定有限自动机（DFA）(Deterministic FA)一个确定有限自动机一个确定有限自动机(DFA M)是一个五元式是一个五元式:DFA M=(S,s0,F)注：这里注：这里确定确定的含义，就是状态转换关系的含义，就是状态转换关系是一个函数，即对是一个函数，即对于给定的于给定的当前状态当前状态s和当前读入的字符和当前读入的字符a有有唯一确定唯一确定的的下一状下一状态态s。1.S 1.S 是有限是有限状态集状态集；2.2.是一个有穷字母表是一个有穷字母表,每个元素为一每个元素为一字符字符；3.s3.s0 0S,S,是是唯一唯一的的初态初态;4.F4.F S,S,是是终态集终态集（可空
42、）。（可空）。5.5.是一个是一个单值单值映射函数映射函数,(s,a)=s,(s,a)=s，指明若当前的状，指明若当前的状态为态为s s，而输入，而输入字符为字符为a a时，则下一个状态是时，则下一个状态是s s；533.2.5 确定有限自动机确定有限自动机vDFA表示表示 状态转换矩阵状态转换矩阵 状态转换图状态转换图DFADFA的映射关系可以用一个矩阵表示：的映射关系可以用一个矩阵表示：该矩阵的该矩阵的行行表示表示状态状态列列表示输入表示输入字符字符，矩阵元素表示，矩阵元素表示(s,a)(s,a)的值的值该矩阵称为该矩阵称为状态转换矩阵或状态转换表状态转换矩阵或状态转换表54例如例如3.1
43、0 3.10 P48 P48 DFA M=(0,1,2,3,a,b,0,3)DFA M=(0,1,2,3,a,b,0,3)其中其中为为:(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、别字：v 对于对于*中的任何一个字中的任何一个字，若存在一条从初，若存在一条从初态结点到某一终态结点的通路，且这条通路上全部态结点到某一终态结点的通路，且这条通路上全部箭弧的标记符连接成的字等于箭弧的标记符连接成的字等于，则称，则称 为为DFA MDFA M所所识别。识别。v例例:P48:P48 图图3.53.5的的DFADFA识别字识别字abbab,abbab,因为存在路径因为存在路径 012333012333；但不接受字；但不接受字ababa,ababa,因为不存在识别路径。因为不存在识别路径。a,ba0123abbab56DFA识别字、语言识别字、语言L(M)vDFADFA识别空字识别空
45、字 若若M M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则称空字则称空字 可以为可以为DFA MDFA M所识别。所识别。v例例:图图3.53.5的的DFADFA不识别空字不识别空字。vDFA MDFA M所能识别的字的全体记为所能识别的字的全体记为L(M)L(M)。v例：例：P48 P48 图图3.53.5的的DFA MDFA M识别的字的全体识别的字的全体v L(M)=L(M)=上全部含有相继两个上全部含有相继两个a a或相继两个或相继两个b b的字的字 a,ba0123abbab57DFA：练习：练习1设有设有 DFA M=(0,1,2,a,b,DFA M=(0,1,2,a
46、,b,0,1,2),0,1,2)其中：其中：（0,a)=2;0,a)=2;（0,b)=10,b)=1 （1,a)=;1,a)=;（1,b)=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
47、是一有限状态集是一有限状态集;2.2.是一个有穷字母表是一个有穷字母表,每个元素为一字符每个元素为一字符;3.3.F F S,S,是是终态集终态集。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如如:一
48、个一个NFAMNFAM也可用状态图表示。也可用状态图表示。3.2.6 非确定有限自动机非确定有限自动机a0bba,ba|b123a60假定假定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.1
50、1 DFA M=(s3.11 DFA M=(s0 0,s,s1 1,s,s2 2,a,b,s,a,b,s0 0,s,s2 2),),且且(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 s