第二章 词法分析2-DFA

1、l确定有限自动机（确定有限自动机（DFADFA）的定义）的定义 lDFA的两种表示方法的两种表示方法 lDFA接受的集合接受的集合 lDFA的确定性的确定性 l用用DFA描述单词描述单词 l自动机的实现自动机的实现 l有限自动机有限自动机FAFA作为一种识别装置，它能准确作为一种识别装置，它能准确 识别正规集，即识别正规表达式所表示的语识别正规集，即识别正规表达式所表示的语 言，引入言，引入FAFA这个理论，正是为词法分析程序这个理论，正是为词法分析程序 的自动构造寻找一种特殊的方法和工具。的自动构造寻找一种特殊的方法和工具。 确定有限自动机确定有限自动机 非确定有限自动机非确定有限自动机 1

2、 1 确定有限自动机的定义确定有限自动机的定义 确定有限自动机确定有限自动机M M为一个五元组为一个五元组: : M = ( M = ( S ,S , , S , S0 0 , ,f f ,Z ),Z )，其中：其中： lS S是一个有穷状态集，它的每个元素称为一个状态；是一个有穷状态集，它的每个元素称为一个状态； l 是一个有穷字母表，它的每个元素称为一个输入字符；是一个有穷字母表，它的每个元素称为一个输入字符； lS S0 0 S S，是唯一的一个初始状态，是唯一的一个初始状态( (开始状态开始状态) )； lf f是状态转换函数是状态转换函数:S:S S S，且单值函数，且单值函数.f(

3、S.f(Si i,a)=S,a)=Sk k 表示：表示： 当前状态为当前状态为S Si i，遇输入字符，遇输入字符a a 时，自动机将唯一地转换到状时，自动机将唯一地转换到状 态态 S Sk k，称，称S Sk k为为 S Si i的一个后继状态的一个后继状态; ; 1.1.Z Z S S，是终止状态集（可接受状态集、结束状态集），其中是终止状态集（可接受状态集、结束状态集），其中 的每个元素称为终止状态（可接受状态、结束状态）的每个元素称为终止状态（可接受状态、结束状态）,Z,Z可空可空. . lDFA M=(S0, S1, S2, S3 , a,b, f , S0 , S3), 其中其中f

4、 定定 义为：义为： f (S0, a )=S1 f (S2, a )=S1 f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 f (S1, b )= S2 f (S3, b )= S3 l a. 状态转换图状态转换图 ：用有向图表示自动机：用有向图表示自动机 1. 结点表示状态：结点表示状态： 1) 非终止状态由单圆圈围住的状态标识来表示非终止状态由单圆圈围住的状态标识来表示; 2） 终止状态由双圆圈围住的状态标识来表示终止状态由双圆圈围住的状态标识来表示; 3） 开始状态由一个箭头指向的状态结点来表示开始状态由一个箭头指向

5、的状态结点来表示. 2.状态转换函数用有向边来表示，若状态转换函数用有向边来表示，若 f(Si,a)=Sk，则，则 由表示由表示Si的状态节点到表示的状态节点到表示Sk的状态节点发出的状态节点发出 一条标识为一条标识为a的有向边的有向边. lDFA M=( S0, S1, S2, S3, a,b, f, S0, S3), 其中其中 f 定义为：定义为： f (S0, a )=S1 f (S2, a )=S1 f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 f (S1, b )= S2 f (S3, b )= S3 状态转换图

6、状态转换图 S1 S0 S2 S S3 3 a a b a b a b ,b lb. 状态转换矩阵：用二维数组描述状态转换矩阵：用二维数组描述DFA 转换矩阵的行表示确定有限自动机的状态转换矩阵的行表示确定有限自动机的状态; 标识初始状态和终止状态标识初始状态和终止状态：一般约定，第一般约定，第 一行表示开始状态一行表示开始状态S0 ，或在右上角标注或在右上角标注 “+”；右上角标有；右上角标有“*”或或“-”的状态为终的状态为终 止状态止状态 ； 转换矩阵的列表示确定有限自动机的输入转换矩阵的列表示确定有限自动机的输入 字符；字符； 矩阵元素表示确定有限自动机的状态转换矩阵元素表示确定有限自

7、动机的状态转换 函数函数. lDFA M=( S0, S1, S2, S3, a,b, f, S0, S3), 其中其中 f 定义为：定义为： f (S0, a )=S1 f (S2, a )=S1 f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 f (S1, b )= S2 f (S3, b )= S3 输入字符输入字符 状态状态 a ab b S0+ +S1,S2 S1S3S2 S2 S1,S3 S3* *S3S3 l对于对于 中的任何字符串中的任何字符串t,t,若存在一条从初始结点到若存在一条从初始结点到 某一终止结点

8、的路径某一终止结点的路径，且这条路上所有弧上的标记且这条路上所有弧上的标记 符连接成的字符串等于符连接成的字符串等于t,t,则称则称t t可为可为DFA MDFA M所所接受接受 （识别）（识别）. .注意路径中可以多次经过终止状态注意路径中可以多次经过终止状态. . l若若DFA MDFA M的初始状态同时又是终止状态，则空字符的初始状态同时又是终止状态，则空字符 串可为串可为DFA MDFA M所所接受（识别）接受（识别）. . lDFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M).L(M). 例例1： L( M1 )= aba, abaa, abab,

9、abaab, 0123 a ba a, b 例例2：L( M2 )=a, ab, abb, abbb, DFA M2 01 a b 例例3：L( M3 )= , b, bb, bbb, DFA M3 1 b 4 4 陷阱状态陷阱状态 例例4: 设有设有DFA M=（0,1,2,3,a,b,c,f,0,3） 其中其中 f 定义为：定义为： f(0,a) = 1 f(0,b) = 4 f(1,a) = 4 f(1,b) = 2 f(2,a) = 3 f(2,b) = 4 f(3,a) = 3 f(3,b) = 3 f(4,a) = 4 f(4,b) = 4 01 23 a ba a, b 4 a,

10、 b a b b 01 23 a ba a, b S a b 0+1 12 23 3*33 l初始状态唯一初始状态唯一. . l状态状态转换函数转换函数f: Sf: SS S是一个单值函数，也是一个单值函数，也 就是说，对任何状态就是说，对任何状态s s S,S,和输入符号和输入符号a a , , f(S,a)f(S,a)唯一地确定了下一个状态，即至多确定唯一地确定了下一个状态，即至多确定 一个状态一个状态. . l没有空边，即不接受没有任何输入就进行状态没有空边，即不接受没有任何输入就进行状态 转换（没有输入为转换（没有输入为 的情况）。的情况）。 l标识符的描述标识符的描述 L L表示所有

11、字母表示所有字母, , L=a-zA-ZL=a-zA-Z D D表示数字，表示数字， D D=0-9=0-9 则有：则有： 01 L L|D l常数的描述常数的描述 D1=D1=1-9 , D1-9 , D=0-9=0-9 无符号整数无符号整数 带符号整数带符号整数 实数实数 01 D1 D 3 2 0 4 0 5 . . 6 D D . +|-D1 l特殊符号 01 2 + 3 EOF l直接转向法：状态转换图的形式直接转向法：状态转换图的形式 每个状态对应一个带标号的每个状态对应一个带标号的switchswitch语句语句 例：例： i j k a b Li: switch ( CurCh

12、ar ) case a ： goto Lj; case b : goto Lk; case Eof : Accept; default : Error( ); l直接转向法：状态转换图的形式直接转向法：状态转换图的形式 每个状态对应一个带标号的每个状态对应一个带标号的switchswitch语句语句 例：例： i j k a b l 特点：特点： 程序长程序长 但占用存储空间少但占用存储空间少 while(curChar=getchar()!=Eof) switch(state) case 1: break; case i: switch ( curChar ) case a：state=j;

13、 break; case b: state=k; break; default : Error( ); break; case j: l状态转换矩阵的形式：状态转换矩阵的形式： s state=S0;tate=S0; curChar=readNextChar();curChar=readNextChar(); while(curChar!=eof = Tstate,curChar; curChar=readNextChar()curChar=readNextChar() ； if(curChar=eof else return(0); else return(0); l特点：程序短小，但占用存储空间多特点：程序短小，但占