第二章 词法分析2-DFA

第二章词法分析2

确定有限自动机DFA确定有限自动机（DFA）的定义DFA的两种表示方法DFA接受的集合DFA的确定性用DFA描述单词自动机的实现有限自动机FA（FiniteAutomata)

有限自动机FA作为一种识别装置，它能准确识别正规集，即识别正规表达式所表示的语言，引入FA这个理论，正是为词法分析程序的自动构造寻找一种特殊的方法和工具。确定有限自动机（DFA：DeterministicFiniteAutomata)

非确定有限自动机（NFA：NondeterministicFiniteAutomata)

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

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

f(S0,a)=S1f(S2,a)=S1f(S0,b)=S2f(S2,b)=S3f(S1,a)=S3f(S3,a)=S3f(S1,b)=S2f(S3,b)=S32DFA的两种表示方式

a.状态转换图：用有向图表示自动机1.结点表示状态：1)

非终止状态由单圆圈围住的状态标识来表示;2）

终止状态由双圆圈围住的状态标识来表示;3）开始状态由一个箭头指向的状态结点来表示.2.状态转换函数用有向边来表示，若f(Si,a)=Sk，则由表示Si的状态节点到表示Sk的状态节点发出一条标识为a的有向边.DFAM=({S0,S1,S2,S3},{a,b},f,S0,{S3}),其中f定义为：

f(S0,a)=S1f(S2,a)=S1f(S0,b)=S2f(S2,b)=S3f(S1,a)=S3f(S3,a)=S3f(S1,b)=S2f(S3,b)=S3状态转换图S1S0S2S3aababab,bb.状态转换矩阵：用二维数组描述DFA转换矩阵的行表示确定有限自动机的状态;标识初始状态和终止状态：一般约定，第一行表示开始状态S0

，或在右上角标注“+”；右上角标有“*”或“-”的状态为终止状态；转换矩阵的列表示确定有限自动机的输入字符；矩阵元素表示确定有限自动机的状态转换函数.DFAM=({S0,S1,S2,S3},{a,b},f,S0,{S3}),其中f定义为：

f(S0,a)=S1f(S2,a)=S1f(S0,b)=S2f(S2,b)=S3f(S1,a)=S3f(S3,a)=S3f(S1,b)=S2f(S3,b)=S3

输入字符状态abS0+S1,S2S1S3S2S2S1,S3S3*S3S33DFA接受的字符串对于中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧上的标记符连接成的字符串等于t,则称t可为DFAM所接受（识别）.注意路径中可以多次经过终止状态.若DFAM的初始状态同时又是终止状态，则空字符串可为DFAM所接受（识别）.DFAM所能接受的字符串的全体记为L(M).

例1：L(M1)={aba,abaa,abab,abaab,…}0123abaa,b

例2：L(M2)={a,ab,abb,abbb,…}DFAM201ab

例3：L(M3)={,b,bb,bbb,…}DFAM31b4陷阱状态例4:设有DFAM=（{0,1,2,3},{a,b,c},f,{0},{3}）其中f定义为：

f(0,a)=1f(0,b)=4f(1,a)=4f(1,b)=2 f(2,a)=3f(2,b)=4 f(3,a)=3f(3,b)=3 f(4,a)=4f(4,b)=401

23abaa,b4a,babb01

23abaa,bΣS

ab0+11223

3*334444445DFA的确定性初始状态唯一.状态转换函数f:SS是一个单值函数，也就是说，对任何状态sS,和输入符号a,f(S,a)唯一地确定了下一个状态，即至多确定一个状态.没有空边，即不接受没有任何输入就进行状态转换（没有输入为的情况）。标识符的描述L表示所有字母,L=[a-zA-Z]D表示数字，D=[0-9]则有：01LL|D6DFA描述单词常数的描述D1=[1-9],D=[0-9]无符号整数带符号整数实数01D1D320405..6DD.+|-D1特殊符号01{2+3EOF7DFA的两种程序实现方法_1直接转向法：状态转换图的形式每个状态对应一个带标号的switch语句例：ijkabLi:switch(CurChar){case‘a’： goto

Lj;case‘b’: goto

Lk;case‘Eof’: Accept;default:Error();}7DFA的两种程序实现方法_1直接转向法：状态转换图的形式每个状态对应一个带标号的switch语句例：ijkab特点：程序长但占用存储空间少while((curChar=getchar())!=Eof)

switch(state)case1:……break;……casei:

switch(curChar){case‘a’：state=j;break;case‘b’:state=k;break;default:Error();}break;casej:……状态转换矩阵的形式：

state=S0;

curChar=readNextChar();

while(curChar!=eof&&T[state,curchar]error)

{//则当前状态转为新的状态state

=T[state,curChar];

curChar=readNextChar()；

}

if(curChar==eof&&stateFinalState)return(1);elsereturn(0);特点：程序短小，但占用存储空间多.7DFA的两种程序实现方法_2练习1设计DFA以识别所有能被3整除的无符号