自动机理论-词法分析-PPT课件.ppt

1、第二章 词法分析词法分析概述词法分析概述正则表达式正则表达式自动机理论自动机理论 词法分析器的设计与实现词法分析器的设计与实现3 3 有限自动机有限自动机确定有限自动机确定有限自动机DFADFA非确定有限自动机非确定有限自动机NFANFANFANFA到到DFADFA的转换的转换DFADFA的化简的化简2345待机待选择冲调待取不足投币投币选择恰当/金额充足付咖啡/找零钱取咖啡/取零钱金额不足超时退款退款超时3.13.1 确定有限自动机确定有限自动机定义定义1 1：一个确定有限自动机一个确定有限自动机DFADFA为一个五元为一个五元组组( ( ,S,S,f f,s,s0 0,Z),Z)，其中：，

2、其中： 是有穷字母表，每个元素称为一个输入字是有穷字母表，每个元素称为一个输入字符；符；S S是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；f f是在是在 S SS S上的单值转换函数；上的单值转换函数；s s0 0 S S是唯一的一个初始状态；是唯一的一个初始状态；Z Z S S，是终止状态集，又称为接受状态集。，是终止状态集，又称为接受状态集。6701234ccefgdbaab03.1.13.1.1 DFADFA实例实例1 13.1.13.1.1 DFADFA实例实例2 2DFA M=(a, b, S, U, V, Q, f, S, DFA M=(a, b

3、, S, U, V, Q, f, S, Q)Q)，其中，其中f f定义为：定义为：f (S, a)=Uf (S, a)=Uf (V, a)=Uf (V, a)=Uf (S, b)=Vf (S, b)=Vf (V, b)=Qf (V, b)=Qf (U, a)=Qf (U, a)=Qf (Q, a)=Qf (Q, a)=Qf (U, b)=Vf (U, b)=Vf (Q, b)=Qf (Q, b)=Q83.1.23.1.2 DFADFA的两种表示方式的两种表示方式状态转换图状态转换图结点表示状态，转换边表示转换函数，边的结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。

4、箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。标识出初始状态和终止状态。状态转换矩阵状态转换矩阵可用二维数组描述。标识出初始状态和终止可用二维数组描述。标识出初始状态和终止状态。若状态。若DFADFA中有中有 f (Sf (SI I, a)=S, a)=SJ J，则：，则： Trans (Trans (S SI I，a)a) S SJ J93.1.33.1.3 DFADFA接受的字符串接受的字符串定义定义2 2：对于对于 * *中的任何字符串中的任何字符串t,t,若存在一条若存在一条从初始结点到某一终止结点的路径，且这从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连

5、接成的字符串等条路上所有弧的标记符连接成的字符串等于于t,t,则称则称t t为为DFA MDFA M所所接受（识别）的字符接受（识别）的字符串串。DFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M)L(M)称为称为M M所能接受（识别）的所能接受（识别）的语言语言。10思考思考 试用自动机描述银行试用自动机描述银行ATMATM机的状态转换。机的状态转换。 确定有限自动机名字中的确定有限自动机名字中的“确定确定”二字含二字含义、用途、局限？义、用途、局限？113.1.43.1.4 DFADFA的确定性的确定性 初始状态初始状态唯一唯一。 转换函数转换函数f:Sf:

6、SS S是一个是一个单值单值函数，也就函数，也就是说，对任何状态是说，对任何状态s s S,S,和输入符号和输入符号 a a, , f(s,a) f(s,a) 唯一地确定了下一个状态。即转换唯一地确定了下一个状态。即转换函数至多确定一个状态。函数至多确定一个状态。 没有空边没有空边，即不接受任何输入就进行状态，即不接受任何输入就进行状态转换（没有输入为转换（没有输入为 ，有时用，有时用 表示的边）。表示的边）。123.1.5 DFA3.1.5 DFA的局限的局限133.23.2 非确定有限自动机非确定有限自动机定义定义3 3：一个非确定有限自动机一个非确定有限自动机(NFA)A(NFA)A是一

7、个是一个五元组五元组A=(A=( ,SS, f, S,SS, f, S0 0,TS).,TS).其中其中 是字母表是字母表SSSS是状态集是状态集f f是转换函数是转换函数 f: SS f: SS ( ( ) ) 2 2SSSSS S0 0是初始状态集是初始状态集TSTS是终止状态集是终止状态集143.2.13.2.1 NFANFA接受的字符串接受的字符串定义定义4 4：设设A A是一个是一个NFANFA，A= (A= ( ,SS, f, S,SS, f, S0 0,TS),TS)则定义则定义L(A)L(A)为从任意初始状态到任意终止状为从任意初始状态到任意终止状态所接受的字符串集合。态所接受

8、的字符串集合。 L(A)=L(A)= |s|s0 0 s, ss, s0 0 S S0 0 ss TSTS 一个一个NFANFA的例子的例子SPZ00,1111153.2.23.2.2 等价和等价和NFANFA的确定化转换的确定化转换 自动机等价自动机等价设设A A1 1和和A A2 2是同一个字母表上的自动机，如果是同一个字母表上的自动机，如果有有L(AL(A1 1)=L(A)=L(A2 2) )，则称，则称A A1 1和和A A2 2等价。等价。 NFANFA到到DFADFA的转换（确定化）的转换（确定化）定理：对于每一个非确定自动机定理：对于每一个非确定自动机A A，存在一，存在一个确定

9、自动机个确定自动机AA，使得，使得L(A)=L(A)L(A)=L(A)。163.2.2.13.2.2.1 NFANFA的一种确定性方法的一种确定性方法 子集法子集法已知已知 NFA: A=(NFA: A=( , S, f, S, S, f, S0 0, Z), Z)构造构造 DFA: A=(DFA: A=( , S, f, S, S, f, S0 0, Z), Z)1.1.令令AA的的初始状态初始状态为为S S0 0=S=S1 1,S,S2 2,S,Sk k,其中其中S S1 1SSk k是是A A的的全部初始状态。全部初始状态。2.2.若若X=SX=S1 1,S,Sm m 是是AA的一个状态

10、，的一个状态，a a则定义则定义f(X,a)=f(Sf(X,a)=f(S1 1,a),a) f(Sf(S2 2,a),a) f(Sf(Sm m,a)=Q,a)=Q，将，将Q Q加入加入SS，重复该过程，直到重复该过程，直到SS收敛。收敛。3.3.若若Y=SY=S1 1,S,Sn n 是是AA的一个状态的一个状态, ,且存在一个且存在一个S Si i是是A A的终的终止状态，则令止状态，则令Y Y为为AA的的终止状态终止状态。17NFANFA确定化实例确定化实例18132564带带“空空”边的自动机边的自动机19012spaceD+-.D4D3闭包？！闭包？！ 在数学中，一个集合被称为在某个运算

11、下在数学中，一个集合被称为在某个运算下闭合闭合，如果在这个集合的成员上的运算生，如果在这个集合的成员上的运算生成这个集合的成员。如自然数之与减法。成这个集合的成员。如自然数之与减法。 当一个集合当一个集合S S不闭合在某个运算下的时候，不闭合在某个运算下的时候，我们通常可以找到包含我们通常可以找到包含S S的最小的闭合集合的最小的闭合集合。这个最小闭合集合被称为。这个最小闭合集合被称为S S的的( (关于这个关于这个运算的运算的) )闭包闭包。如在自然数集的减法下的闭。如在自然数集的减法下的闭包，是整数集。包，是整数集。203.2.2.23.2.2.2 带空边的带空边的NFANFA的确定化的确

12、定化定义定义5 5：设设I I是是NFANFA的状态集的子集，则的状态集的子集，则I I的的 闭闭包包为：为： _CLOSURE(I)=I_CLOSURE(I)=I q|f(p, q|f(p, )=q,)=q, p p_CLOSURE(I)_CLOSURE(I)定义定义6 6：设设I I是是NFANFA状态集的子集，则状态集的子集，则I Ia a= = _CLOSURE(J)_CLOSURE(J)，J=q|f(p,a)=q,J=q|f(p,a)=q, p p II21 修改后的子集法修改后的子集法已知已知 A A：NFA, NFA, 构造构造 A A:DFA:DFA1.1.令令AA的初始状态为

13、的初始状态为I I0 0= _CLOSURE(_CLOSURE(S S1 1,S,S2 2,S,Sk k),),其中其中S S1 1SSk k是是A A的的全部初始状态。全部初始状态。2.2.若若I=SI=S1 1,S,Sm m 是是AA的一个状态，的一个状态，a a则定义则定义f(I, a)=If(I, a)=Ia a将将I Ia a加入加入SS，重复该过程，直到，重复该过程，直到SS收敛。收敛。3.3.若若I=SI=S1 1,S,Sn n 是是AA的一个状态的一个状态, ,且存在一个且存在一个S Si i是是A A的终止状态，则令的终止状态，则令II为为AA的终止状态。的终止状态。22 带

14、空边的带空边的NFANFA确定化的例子确定化的例子23I I0 0=1,2=1,2I I1 1=I=I0a0a=2,4,5,6,7=2,4,5,6,7I I2 2=I=I0b0b=3,8=3,8I I3 3=I=I1a1a=I I4 4=I=I1b1b=3,8,9=3,8,9I I5 5=I=I2a2a=9=9I I6 6=I=I2b2b=I I7 7=I=I4a4a=9=I=9=I5 5I I8 8=I=I4b4b=24DFA M=DFA M=( (, , I I0 0,I,I1 1,I,I2 2,I,I4 4,I,I5 5, f(I f(I0 0,a)=I,a)=I1 1, f(I f(I

15、0 0,b)=I,b)=I2 2, f(I f(I1 1,b)=I,b)=I4 4, f(I f(I2 2,a)=I,a)=I5 5, f(I f(I4 4,a)=I,a)=I5 5, I I0 0, , I I1 1,I,I4 4,I,I5 5)3.33.3 DFADFA化简（极小化）化简（极小化） 状态等价：状态等价：对对DFADFA中的两个状态中的两个状态S S1 1和和S S2 2，如，如果将它们看作是初始状态，所接受的符号果将它们看作是初始状态，所接受的符号串相同，则定义串相同，则定义S S1 1和和S S2 2是等价的。是等价的。 无关状态：无关状态：从有限自动机的开始状态开始，从

16、有限自动机的开始状态开始，任何输入序列都不能到达的状态。任何输入序列都不能到达的状态。 最小最小DFADFA：如果如果DFADFA中没有无关状态，也没中没有无关状态，也没有彼此等价的状态，则称该自动机是最小有彼此等价的状态，则称该自动机是最小的。的。253.3.13.3.1 状态分离法状态分离法1.1. 将将DFADFA的所有状态的所有状态K K按终态和非终态划分成两个子集按终态和非终态划分成两个子集Z Z与与K-ZK-Z，构成初始化分，记作：，构成初始化分，记作： =Z, K-Z=Z, K-Z。2.2. 设当前的划分设当前的划分 中已经含有中已经含有m m个子集个子集: : =I=I1 1,

17、I,I2 2,I,Im m 对于每一个子集对于每一个子集I Ii i=S=Si1i1,S,Si2i2,S,Sinin 及每一个及每一个a a，设，设I Ii in n=f(I=f(Ii i,a)=f(S,a)=f(Si1i1,a),a) f(Sf(Si2i2,a),a) f(Sf(Sinin,a),a)若若I Ii in n中的状态分别落在中的状态分别落在 中中p p个不同的子集，则根据转移状个不同的子集，则根据转移状态相同与否将态相同与否将I Ii i分为分为p p个子集得到新的划分个子集得到新的划分 newnew。3.3. 若若 newnew , , 则将则将 newnew作为作为 重复重

18、复2 2，直到，直到 不能划分。不能划分。4.4. 将最后所得到的划分将最后所得到的划分 中的每个子集看成一个状态，对中的每个子集看成一个状态，对边作相应修改，确定开始状态和结束状态。边作相应修改，确定开始状态和结束状态。263.3.23.3.2 DFADFA化简化简 例例1 127思考：将如下思考：将如下DFADFA化简化简28 aCDBAEFSbaaaaabbbbbabF29SBAC,D,E,Fbabbaaa,bC,D,E,F3.43.4 正则表达式与正则表达式与FAFA等价等价定理：定理：对任一确定有限自动机对任一确定有限自动机A A，存在一正，存在一正 则表达式则表达式e,e,使得使得

19、L(A)=L(e),L(A)=L(e),反之亦然。反之亦然。关系图：关系图：30DFA正则表达式正则表达式NFA12a b12a | b12 b*123ab12ab123 b X XW W 3.4.13.4.1 正则表达式到正则表达式到DFADFA的转换的转换313.4.23.4.2 DFADFA到正则表达式的转换到正则表达式的转换123ab12ab12313a b12a | b13a b* cabc32思考思考1 1 设计设计DFADFA以识别能够被以识别能够被4 4整除的二进制数。整除的二进制数。330120011103100思考思考2 2 设计设计DFADFA以识别所有能被以识别所有能被

20、3 3整除的无符号十整除的无符号十进制数。进制数。340123,6,93,6,91,4,702,5,82,5,81,4,72,5,83,6,91,4,7思考思考3 3 设计识别设计识别C C语言实型常数的自动机。语言实型常数的自动机。354 4 词法分析器的设计与实现词法分析器的设计与实现设计：单词分类、正则表达式法、自动机法设计：单词分类、正则表达式法、自动机法实现：转换矩阵法、转换图法、几个细节问题、构造步骤实现：转换矩阵法、转换图法、几个细节问题、构造步骤364.14.1 单词分类单词分类 标识符：标识符：标识符一般是由字母开头，字母、数字标识符一般是由字母开头，字母、数字或其它符号的任

21、意组合构成的。或其它符号的任意组合构成的。 常量：常量：用来表示各种常量。主要包括整数常数实用来表示各种常量。主要包括整数常数实数常数、字符串常量等。数常数、字符串常量等。 特殊符号：特殊符号：包括保留字、运算符和界限符。包括保留字、运算符和界限符。 保留字一般是由语言系统自身定义的通常是由字母组保留字一般是由语言系统自身定义的通常是由字母组成的字符串。成的字符串。 运算符表示序中算术运算、逻辑运算、字符运算、赋运算符表示序中算术运算、逻辑运算、字符运算、赋值运算的确定的字符或字符串。值运算的确定的字符或字符串。 界限符包括各种括号，命令结束符号等。界限符包括各种括号，命令结束符号等。 格式符

22、包括格式符包括EOFEOF，回车等符号。，回车等符号。374.1.14.1.1 正则表达式描述正则表达式描述 标识符：标识符：L(L|D)L(L|D)* * 其中其中L=a-z, A-Z, L=a-z, A-Z, D=0-9D=0-9 整数：整数：D D1 1D D* *|0, |0, 其中其中D D1 1=1-9=1-9 特殊符号：特殊符号：+|+|；| |：|:= |= |:= |= | 保留字：保留字：if | else | if | else | 384.1.24.1.2 有限自动机描述有限自动机描述1.1. 按按类类构造出相应的状态转换图。构造出相应的状态转换图。2.2. 合并各类单

23、词的状态转换图，构成一个能合并各类单词的状态转换图，构成一个能识别语言所有单词的状态转换图。识别语言所有单词的状态转换图。a.a. 将各类单词的状态转换图的初始状态合并为将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；一个唯一的初始状态；b.b. 化简调整状态冲突和对冲突状态重新编号；化简调整状态冲突和对冲突状态重新编号；c.c. 如果有必要，增加出错状态。如果有必要，增加出错状态。 39自动机设计自动机设计实例实例40抽象后的抽象后的DFADFA4101672345IDIDDD_DDDD+-._space4.2.14.2.1 状态转换矩阵法状态转换矩阵法把自动机看作一种数据结构（状

24、态转换矩把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，阵），由控制程序控制字符在其上运行，从而完成词法分析。从而完成词法分析。State=InitState;Read(CurrentChar);While(T(State,CurrentChar)error & CurrentChar Eof)State=T(State, CurrentChar);Read(CurrentChar);if (State FinalStates)Accept; else Error; 特点特点 程序短小，但占用存储空间多。程序短小，但占用存储空间多。424.2.24.2.2 状态转换图法

25、状态转换图法 每个状态对应一个带标号的每个状态对应一个带标号的casecase语句转向语句转向边对应边对应gotogoto语句语句 特点：程序长，但占用存储空间少特点：程序长，但占用存储空间少43abLi: case CurrentChar ofa:goto Ljb:goto Lkother:Error( )ijk4.3 4.3 特殊处理特殊处理 保留字识别保留字识别 符合单词、数符合单词、数 控制字符、注释控制字符、注释 语义信息存储语义信息存储444.3.14.3.1 保留字识别保留字识别 统一识别统一识别 事先构造好事先构造好保留字表保留字表。在进行词。在进行词法分析时，把保留字也当作一

26、般标识符来法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，则把它作识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标识为保留字来处理；若没有，则按一般标识符来处理。符来处理。 单独识别单独识别 在自动机中加入识别各个保留字在自动机中加入识别各个保留字的的状态状态，即把保留字和一般标识符分开来，即把保留字和一般标识符分开来识别而不统一识别。识别而不统一识别。 454.3.24.3.2 符合单词、数符合单词、数 复合单词的识别复合单词的识别 在程序设计语言中，有在程序设计语言中，有一类单词是由两个或者两个以上的符号组一类单词是由两个或者两个以上的符号组成的，这类

27、单词的前缀部分也可以是一个成的，这类单词的前缀部分也可以是一个独立的单词。在处理这类单词时要特别加独立的单词。在处理这类单词时要特别加以注意。以注意。 有时候需要向前看若干个字符才有时候需要向前看若干个字符才能判断。能判断。 数的转换数的转换 词法分析程序应该把字符串转词法分析程序应该把字符串转换成数，如换成数，如“123”123”应该转换成应该转换成123123。 464.3.34.3.3 控制字符、注释控制字符、注释 控制字符的处理控制字符的处理 无用的空格符和制表符要删掉；无用的空格符和制表符要删掉； 字符串内的空格不能删；字符串内的空格不能删； 换行符不能直接删除，而需用于错误定位。换

28、行符不能直接删除，而需用于错误定位。 注释的处理注释的处理 源程序中的注释没有任何语法源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时和语义上的意义，因此在进行词法分析时可以直接将注释可以直接将注释删除删除，而不必生成其，而不必生成其TOKENTOKEN。 474.3.44.3.4 语义信息存储语义信息存储 直接在语义信息部分存储直接在语义信息部分存储 语义信息的长度语义信息的长度有限制时，可直接将标识符或常量本身存有限制时，可直接将标识符或常量本身存储于其储于其TOKENTOKEN中的语义信息部分。中的语义信息部分。 设置标识符表和常量表设置标识符表和常量表 标识符和常量没有标

29、识符和常量没有长度限制时，构造标识符或常量表，语义长度限制时，构造标识符或常量表，语义信息中为其在表中的地址（信息中为其在表中的地址（节省存储空节省存储空间）。间）。484.44.4 构造词法分析器步骤构造词法分析器步骤1.1. 确定词法分析器的确定词法分析器的接口接口，即确定词法分析，即确定词法分析器是作为语法分析的一个子程序还是作为器是作为语法分析的一个子程序还是作为独立一遍。独立一遍。2.2. 确定单词确定单词分类分类和和TokenToken结构结构。3.3. 构造每一类单词的描述正则表达式并构造每一类单词的描述正则表达式并转换转换。正则表达式正则表达式NFANFADFADFA4.4. 设计算法设计算法实现实现DFADFA。49小结小结自动机理论自动机理论正则语言与自动机的转换正则语言与自动机的转换词法分析器的设计词法分析器的设计50