第三章词法分析及有穷自动机

第三章词法分析及有穷自动机§1、词法分析程序得任务一、词法分析程序得任务及处理方式

1、词法分析程序得任务主要任务:从左至右逐个字符地对源程序进行扫描,产生一个个单词序列,用以语法分析。词法分析程序(扫描程序):执行词法分析得程序。2、词法分析程序得处理方式词法分析程序与语法分析程序接口方式有两种:第一种方式:

将词法分析作为单独一遍扫描,即在语法分析之前,实现源程序得词法分析工作。其输出(单词串)形成一个中间文件(内部形式得源程序表),然后移交给语法分析程序。第二种方式:将词法分析程序编写成一个子程序,每当语法分析程序需要读一个新单词时,便去调用它。 注:后一种方式比较好。因为不需要在内存中构造与保存中间文件。二、词法分析程序得I/O1、输入 字符串表示得源程序

2、输出 单词符号序列或单词符号。

1)程序语言得单词符号单词:指语言中具有独立意义得最小语法单位。语言中得单词符号:一般可归结为五种:保留字(基本字):如if,for,and等――个数确定标识符:表示常量、变量、类型、过程等名称――个数不确定常数:如34,-0、37等――个数不确定运算符:如+,-,*,/,<等――个数确定界线符:如逗号,分号,括号等――个数确定注:·保留字,运算符,界线符可列表,供词法分析程序查询;

·标识符与常数可用正规文法或正规式描述,供词法分析程序识别。2)输出得单词形式二元组:(单词得种别码,单词自身值)

1o

单词得种别码:表示单词得种类分类得原则:处理简单分类得方法:使每一个单词对应一个整数码分类得目得:最大限度地区别各个单词 单词地分类法有多种:一种一类一字一类或一符一类具体:保留字:一字一种。如:

if 1 then2

。。。标识符:统归一种。常数:整数,实数,布尔统为一种或按类型分整数 11实数 12布尔 13

或全体一种+ 29 :=17= 21- 14<>18>=22* 15<19>23 16<=20…运算符:+,-,*,/,>,<等统为一种;或一符一种:

2o

单词自身值(可有可无) 单词自身值就是单词得机内代码或者单词在表格中得地址码。如:标识符:自身得字符串(1,’a’)常数:自身得二进制数(11,’100’得二进制数)例:一种一类得单词输出形式 设保留字、标识符、常数、运算符、分界符得种别码分别为1,2,3,4,5;将ifa>1thenb:=10表示为一种一类得单词输出形式。ifa>1thenb:=10＝>词法分析器=>(1,’if’)(字符串表示得源程序)(2,’a’),(4,’>’)(3,’1’

得二进制数)(1,’then’)(2,’b’)(4,’:=’)(3,’10’

得二进制数)例:采用一字一类或一符一类地分类技术,则保留字单词自身值可无,但事先构造一个保留字单词对照表,其值可在词表中查到。ifa>1thenb:=10＝>词法分析器=>(1,◎)字符串表示得源程序(10,‘a’)(23,◎)(3,’1’得二进制数)(2,◎)(10,’b’)(17,◎)(11,’10’

得二进制数)上面符号◎表示要查保留词表大家学习辛苦了，还是要坚持继续保持安静表2、1保留字单词表单词类别码单词类别码、、、、、、、、、、、、、、、If1+29Then2-14else3*15、、、、、、

/16、、、、、、、、、、、、>23for19:=17、、、§2、词法分析程序得设计过程一、词法分析程序得设计过程设计过程:词法分析程序设计过程:①把有得单词(如:标识符与常数)用正规文法或正规式描述;②将正规文法或正规式转换成等价得状态转换图(最小化得DFA图);③根据状态转换图设计词法分析程序(状态转换图可视为词法分析程序得框图)。转换规则分裂法子集法

状态转换图(DFA图)二、用状态转换图设计词法分析程序

1、词法分析程序得预处理词法分析程序在识别单词前,需要对输入到缓冲区得源程序进行预处理。预处理:删去无用得空格,跳格,回车与换行等编辑性字符;删去注释部分每次对一串定长(如120个字符)得输入字符进行预处理,并装入一个指定得扫描缓冲区中。扫描缓冲区就是一个一分为二得区域,每一个区域可容纳120个字符,且相互交替使用。搜索指针从单词起点开始搜索,如果遇到半区得边界但尚未达到单词得终点时,则可将后续得120个输入字符装进缓冲区得另一半中。2、状态转换图状态转换图就是为了识别正规文法或正规式而专门设计得有向图。她就是有穷自动机得非形式化表示。状态转换图得组成:

1o

有限个状态结点状态结点代表正规文法得非终结符(用单圈表示);开始状态结点:用双箭头指示;终止状态结点:用双圈表示。

2o弧线→弧上得标记x指明在射出弧得结点状态下可能出现得输入字符或字符类,即终结符。(→表示机器得识别方向)、大多数单词结构就是用正规文法描述得x例:<标识符>∷=<字母>|<标识符><字母>|<标识符><数字><整数>∷=<数字>|<整数><数字><运算符>∷=+|-|*|/|…、<界线符>∷=;|,|(|)|…、、。。。3、由正规文法构造状态转换图1)左线性正规文法构造状态转换图 左线性正规文法得一般形式:U∷=a|wa左线性正规文法构造状态转换图得步骤如下:增加一个开始状态结点s(假定文法得词汇表中不含s);以每个非终结符为状态作结点;对于形如U∷=a得每一个规则,引一条从开始状态s到状态U得弧,弧上标记为a;

对于形如U∷=wa得每一个规则,引一条从状态w到状态U得弧,弧上标记为a;以识别符号为终止状态。例:设有正规文法G[Z]:

Z∷=U0|V1 U∷=Z1|1 V∷=Z0|0(描述得语言为L(G)={01,10})则状态转换图如下:＋以开始符号Z作终态新增加开始状态S例:标识符得转换图:

从开始状态出发到某一终止状态结点为止,所经过得路径上得符号串,称能为该状态转换图所接收(识别)得符号串。如:标识符x26为上述转换图识别,识别路径为2)

右线性正规文法构造状态转换图右线性正规文法U∷=a|aV构造状态转换图得步骤:增加一个终止状态结点z(假定文法得词汇表中不含z);以每个非终结符为状态作结点;对于形如U∷=a得每一个规则,引一条从开始状态U到终止状态z得弧,弧上标记为a;对于形如U∷=aV得每一个规则,引一条从状态U到状态V得弧,弧上标记为a;以识别符号为开始状态。４、根据状态转换图设计词法分析程序状态转换图实际上就是编写词法分析程序得框图根据状态转换图写出相应得词法分析程序得方法:

1o对于每个状态构造一小段程序。 功能:从输入串中读一个字符;判明读入字符与由此状态出发得哪条弧上得标记匹配,便转至相匹配得那条弧所指得状态;均不匹配时便失败(不能达到正常出口)2o再根据图形决定小段程序之间得调用。 注:词法分析程序除了识别单词外,还可为语法程序提供更多得信息。因此,可在这些小段程序中加上一些语义处理(如对数值进行10=>2等)例:设有关于单词<无符号数>得文法G=(VN,VT,P,N1)其中,VN={N1,N2,N3,N4,N5,N6,N7}VT={d,、,e,f,∧}P: N1∷=dN2|、N3|eN5 N2∷=dN2|、N3|eN5|∧ N3∷=dN4

这里d表示数字(0～9);e＝10;f＝;∧表示空字符;N1表示无符号数,其一般形式为:d…d、d…defd…dN4∷=dN4|eN5|∧N5∷=dN7|fN6N6∷=dN7N7∷=dN7|∧试构造识别此单词得词法分析程序1>根据右线性正规文法,画出状态转换图N1=>3N2=>34N2=>34·N3=>34·5N4

=>34·56N4=>34·56(达到出口),自上而下得推导过程。2>根据状态转换图写词法分析程序为每一个状态结点写一个过程或函数:对N1结点:ProcedurePN1 Begin Ch:=getchar(); Ifch=”e”thenPN5 Elseifch=”d”thenPN2 Elseifch=”·”thenPN3 Elseerror End;对N2结点:ProcedurePN2 Begin Ch:=getchar(); Ifch=”e”thenPN5 Elseifch=”d”thenPN2 Elseifch=”·”thenPN3 Elsereturn; End;对N3,N4,N5,N6,N7结点分别写出程序段:……§3正规式与有穷自动机为了进一步讨论词法分析程序得自动生成,需要将状态转换图得概念加以形式化;同时将由正规文法描述得单词由正规式描述,可利用有穷自动机生成词法分析程序。一、正规式与正规集 语言得单词结构不仅由正规文法描述,还可以由正规式描述。例:<标识符>∷=<字母>|<标识符><字母>|<标识符><数字>

此正规文法描述了一个语言得集合。定义在{字母,数字}上得以字母开头得符号串得集合。这个集合还可以用正规式描述:字母(字母|数字)*。正规式描述得字符串得集合称为正规集1、正规式(也称正则式,正则表达式)与正规集得递归定义设有字母表∑={a1,a2,…,an},那么(1)ε,Φ,ai都就是∑上得正规式,它们所描述得正规集分别为{ε},Φ,{ai};(2)若e1与e2都就是∑上得正规式,它们所描述得正规集L(e1)、L(e2),则:1o正规式得“或”(|)运算:e1|e2也就是正规式,相应正规集为L(e1|e2)=L(e1)∪L(e2);2o正规式得“连接”(、)运算:e1e2也就是正规式,相应正规集为L(e1e2)=L(e1)L(e2);3o正规式得“闭包”(*)运算:(e1)*也就是正规式,相应正规集为

L((e1)*)=(L(e1))*;(3)仅由有限次使用(1),(2)定义得表达式才就是∑上得正规式,由这些正规式所表示得字符集才就是∑上得正规集。例:设∑={a,b},则∑上得正规式与正规集有正规式正规集1o

a与baL(a)={a}与L(b)={b}L(a)=L(a)∪L(a)∪L(a)∪…={a}={a,aa,、、、}基本3oa|bL(a|b)=L(a)∪L(b)={a,b}4oabL(ab)=L(a)L(b)={ab}5oa*L(a*)=(L(a))*=L(a)∪L(a)∪L(a)∪…、={a}*={ε,a,aa,aaa,、、…}复合6oba*L(ba*)=L(b)L(a*)={b,ba,baa,baaa,……}7oa|ba*L(a|ba*)=L(a)∪L(ba*)={a,b,ba,baa,……}8o(a|b)*L((a|b)*)=(L(a|b))*={a,b}*={ε,a,b,aa,ab,……所有ab组成得串}9oa(a|b)*L(a(a|b)*)=L(a)(L(a)∪L(b))*={a}{a,b}*10o(a|b)*(aa|bb)(a|b)*L((a|b)*(aa|bb)(a|b)*)={a,b}*{aa,bb}{a,b}*012+123++2o

注:、正规式仅由字母∑中得终结符号,通过或,连接与闭包三种运算组成得式子。例:有字母表∑={a,b},下面正规式,求正规集。

ba*正规集:b开头后面跟0个或若干个a。

a(a|b)*正规集:a开头后面跟0个或a、b任意排列。例:有字母表∑={a,b},下面用自然语言描述得正规集,求正规式(可能不唯一)。以ab结尾得所有字符串。(a|b)*ab

包含偶数个b得所有字符串。(bb)*

只包含一个a得所有字符串。b*ab*

不包含ab子串得所有字符串。b*a*

以a开头b结尾得所有字符串。a(a|b)*b

２、正规式得性质(1)正规式得等价性定义:若正规式e1与e2描述得正规集相同,即L(e1)=L(e2),则e1与e2等价,记做e1=e2。(2)正规式得代数性质设r,s,t为正规式,正规式服从得代数规律有:1or|s=s|r“或”满足交换律2or|(s|t)=(r|s)|t“或”满足结合律3o(rs)t=r(st)“连接”满足结合律。

“连接”不满足交换律4or(s|t)=rs|rt(s|t)r=sr|tr“连接”满足分配律5oεr=rrε=r

ε

就是“连接”得恒等元素(3)正规式得恒等式 设A与B式正规式,有例:证明:A*=ε|AA*成立。 证明:利用对应得正规集来证明:

L(AA*|ε)=L(A)L(A*)UL(ε)=L(A)L(A)*UL(ε)=L(A)((L(A))UL((A))U(L(A))…、、)UL(ε)=L(ε)U((L(A))U(L((A))U(L(A))…、、)=(L(A)*)=L(A*)∴A*=AA*|ε例:设∑={d,、,e,+,-}则∑上得正规式:

d*(、dd*|ε)(e(+|-|ε)dd*|ε)表示无符号数:2、12,3、6e-2等。表示无符号数得正规式,比表示无符号数得正规文法显得直观,简洁。1o(A*)*=A*2oA|BA=(ε|B)A3oAA*=A*A;A=AA*4oA*=ε|AA*;A*=(A|ε)*012312+3、正规文法与正规式得转换关系:对任意一个正规文法存在定义同一语言得正规式反之:对于每一个正规式,存在一个生成同一语言得正规文法。两者之间具有等价得转换关系。 有得语言容易用正规文法定义,有得语言则更容易用正规式定义转换:1o

正规式-——>正规文法将∑上得一个正规式转换成正规文法G=(VN,VT,S,P):首先:令VT=∑再确定产生式P与VN,其方法: 对任何正规式r,选择非终结符S生成产生式S∷=r,并将S定义为G得识别符号。<a>若r含有正规式x,y,对形如A∷=xy(连接得变换)产生式,用A∷=xB,B∷=y两个产生式替换。其中B就是新选择得非终结符。<b>对已经转换成文法中得形如:A∷=x*y(闭包与连接得变换)得产生式,则重写为:

A∷=xA注:若y就是ε则,A→xA A∷=yA→ε<c>对形如:A∷=x|y(或得变换)得产生式,重写为A∷=x,A∷=y<d>不断利用上述规则作变换,直到每个产生式右部最多含有一个终结符为止。例:将正规式R=a(a|d)*转换成相应得正规文法。解:令S就是文法得识别符号,则首先形成:

S∷=a(a|d)*然后形成:

S∷=aA,A∷=(a|d)*(其中A∈VN)对于A∷=(a|d)*重写为:

A∷=(a|d)A A∷=ε对于A∷=(a|d)A重写成:A∷=aA,A∷=dA最后转换得等价正规文法G=(VN,VT,S,P) VT={a,d} VN={S,A} P:S∷=aA A∷=aA|dA|ε2o正规文法——>正规式 基本就是上述得逆过程。最后只剩下一个识别符号定义得产生式,且产生式得右部不含非终结符。其转换规则如下表:规则文法产生式正规式1A∷=xB,B∷=yA=xy2A∷=xA|yA=x*y3A∷=x,A∷=yA=x|y注:正规文法与正规式互相转换,关键式:A→xA|yA=x*y例:正规文法G[s]:

S∷=aA S∷=a A∷=aA A∷=dA A∷=a A∷=d求正规式解:先有:S＝aA|a规则3 A=(aA|dA)|(a|d) 规则3再将A得正则式变成:A=(a|d)A|(a|d) “或”分配律根据规则2变成:A=(a|d)*(a|d)再代入S得右部得:S=a(a|d)*(a|d)|a再利用正则式代数变换:

S=a((a|d)*(a|d)|ε) S=a(a|d)*

即:a(a|d)*为所求得正则式简便转换方法就是:(1)将正规文法中得每一个非终结符表示成关于它得一个正规方程,获得一个联立方程组、(2)依据求解规则:若x∷=αx|β,写成方程x=αx+β(“|”用“+”表示);则解为x=α*β、若x∷=xα|β,写成方程x=xα+β(“|”用“+”表示);则解为x=βα*、以及正规式得分配律,交换律与结合律求关于文法识别符号得正规式方程组得解、此解就就是关于文法识别符号S得一个正规式、例如,上例:先写出正规式方程组(方程组中用“+”代替“|”): S∷=aA|a 写成:S=aA+a……(1)

A∷=aA|dA|a|d 写成:A=aA+dA+a+d……(2)将(2)式简化为:A=(a+d)A+(a+d)使用求解规则:A=(a|d)*(a|d)……(3)将(3)得A代入(1)式:S=a(a|d)*(a|d)|a=a((a|d)*(a|d)|ε)∴a((a|d)*(a|d)|ε)=a(a|d)*即为所求得正规式。

例:设有正规文法G:Z∷=0AA∷=0A|0BB∷=1A|ε试给出该文法得正规式。解:给出相应得正规式方程组:

Z=0A……(1)

A=0A+0B……(2)

B=1A+ε……(3)(3)代入(2)中得B得:A=0A+01A+0=(0+01)A+0使用求解规则:A=(0|01)*0……(4)(4)代入(1)式中得A得:Z=0(0|01)*0所以,0(0|01)*0即为所求得正规式。例:设有正规文法G:P:{A::=aB|bB,B::=aC|a|b,C::=aB}相应得正规式方程:A=aB+bB………(1)

B=aC+a+b………(2)C=aB………、(3)(3)代入(2)中得C:B=aaB+a+b……、(4)

对(4)式使用求解规则:B=(aa)*(a|b)……、(5)

将(5)代入(1)式中得B:A=(a|b)(aa)*(a|b)∴(a|b)(aa)*(a|b)即为所求。二、有穷自动机(FA)自动机:就是一种能进行运算,并能实现自我控制得装置。装有程序得计算机也具有运算与自我控制能力,因此计算机就是一部自动机所谓有穷自动机:自动机受囿于它能存储得信息量,因此就是有限得(有穷得)自动机就是识别符号串处理得强有力得工具,因而它成为研究词法分析器得重要基础。有穷自动机分为:确定得有穷自动机(DFA)非确定得有穷自动机(NFA)１、确定得有穷自动机(DFA)(1)DFA得形式定义:一个DFAM就是一个五元组:

M=(S,∑,f,S0,F)其中:S:非空有穷得状态集:每个元素就是一个状态。∑:有穷输入字母表;每个元素就是输入得一个字符。

f:状态转换函数:就是从S×∑－>S得单值映射函数:

f(S1,a)=S2S0∈S就是唯一得开始状态

FS就是终止状态集,可空(识别不出得字符串)例:设有DFAM=({0,1,2,3},{a,b},f,0,{3})其中:f:f(0,a)=1 f(0,b)=2DFA得函数式表示

f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3(2)DFA得状态图表示:开始状态为0,终止状态为3,状态集为{0,1,2,3},字母表为:{a,b}

一般:假定DFAM含有m个状态,n个输入字符,则状态图含有m个结点,每个结点最多有n条弧射出。(3)DFA得矩阵表示:矩阵得行表示状态,列表示输入字符,矩阵中得元素表示相应状态行与输入字符列下得新状态。即K行a列为f(K,a)得值。DFA得功能:对于∑*中得任何字符串α,若存在一条从开始结点到某一终态结点得道路,其路上所有弧得标记符连成得字符串等于α,则称α能为DFA所识别(接受)。特别:若DFA得开始态结点同时又就是终态结点,则空串可为DFA所识别。状态\字符ab012132213333注:

①

DFA有3种表示法:函数表示,状态图表示,状态矩阵表示。

②

DFA得确定性表现在转换函数f:S×∑－>S就是一个单值函数。即:对于任何状态s∈S,与输入符号a∈∑,f(s,a)能唯一确定下一个状态。③可以证明:若存在一个正规文法G,G产生得语言L(G),当且仅当存在一个∑上得确定有穷自动机M,使得L(G)＝L(M)。 即:正规文法G在∑上描述得语言,一定存在DFA能够识别这个语言。反之:若存在一个被DFA识别得语言,一定由存在得正规文法所描述。④由于DFA能识别正规文法描述得单词,因此要想构造识别单词得词法分析程序,也就成为怎样构造DFA得问题了。2、非确定得有穷自动机(NFA)定义:一个NFA也就是一个五元组:

M＝(S,∑,f,S0,F)其中:S,∑,F同DFAS0S就是一个非空开始状态集f:就是一个多值得转换函数:S×∑－>S得子集映射NFA与DFA得区别:NFA有一个开始状态集,而DFA只有一个开始状态;NFA转换函数就是多值函数,DFA得转换函数就是单值函数。例:设有NFAM＝(S,∑,f,S0,F)其中,S={q0,q1,q2,q3},∑={x,y},S0={q0},F={q1}f: f(q0,x)={q1,q2} f(q0,y)={q0} f(q1,x)={q0} f(q1,y)={q1,q2} f(q2,x)={q3} f(q2,y)={q3} f(q3,x)={q1,q3} f(q3,y)={q3}NFAM得状态图表示:状态\字符xyq0{q1,q2}{q0}q1{q0}{q1,q2}q2{q3}{q3}q3{q1,q3}{q3}NFAM得矩阵表示:注:DFA就是NFA得特例;对于每个NFAM,存在一个DFAM’,使得L(M)=L(M’)对于任何两个有穷自动机M与M’,若L(M)=L(M’),则称M与M’等价。三、由正规式构造NFA或将NFA转换成正规式１、理论依据定理:正规式与有穷自动机就是等价得。１o

∑上得NFAM,可以构造∑上得正规式R,使:

L(M)=L(R)２o

在∑上得每个正规式R,可以构造∑上得NFAM使:

L(R)=L(M)注:由正规式(或正规文法)构造有穷自动机得意义在于:将单词得描述结构转换为对单词得识别结构。２、由正规式构造NFA

方法:分裂法输入:∑上得正规式R输出:识别R得NFA步骤:1o引进一个开始状态结点x与终止状态结点y:

2o若R为复合公式,分裂R直到每条边上只留下一个符号(可以为ε)为止;3o

分裂得结果:保证一个唯一得开始状态结点与终止状态结点。例:设∑={x,y}上得正规式e=xy*(xy|yx)x*,构造一个NFAM,使得L(M)=L(e)解:例:已知正则式e=0(1*)*|01 ,求:NFA ∵(A*)*=A* (A|A*=A*) ∴e=0(1*)*|01(利用恒式化简,然后构造NFA)

=01*|01=0(1*|1)=01*构造NFA:３、将NFA转换成正规式方法:合并法(与分裂法相反) 输入:NFAM

输出:一个正规式e

步骤:

1o

对于NFAM中得开始状态与终止状态分别新设置一个唯一得开始状态与终止状态,使所设得开始状态到原开始状态连接ε弧;原终止状态到所设得终止状态连接ε弧。s为新增得开始状态Z为新增得终止状态2o

利用下列规则进行合并,直到图中只剩下新设置得开始态与终止态为止。那么在开始态与终止态弧上得正规式便就是所求得结果。例:已知NFA如下,求正规式e1o新设置一个唯一得开始状态与终止状态:2o

按照合并规则进行合并

∴e=(x|y)*(xy*y|yx*x)四、NFA到DFA得转换(NFA得确定化)

1、理论依据与目得

定理:若L为一个能被NFA接受得语言,则存在一个能接受L得DFA: 即:L(NFAM)=L(DFAM)

目得:①

消除NFA中ε弧。ε弧会使自动机做无用功。

②合并NFA中不确定得状态。不确定状态不仅给自动机识别字符串带来困难,而且使得编制相应得词法分析程序变得更为复杂。

NFA到DFA得转换得基本思想:

DFA得每一个状态对应于NFA得一组状态(状态集合)。

方法:子集法

2、子集法分两种情况介绍NFA得确定化:①不含ε弧得NFA得确定化。②含ε弧得εNFA得确定化 由NFAA=(S,∑,f,S0,F)构造DFAA’=(S’,∑,f’,q0,F’)方法:1o

DFAA’得输入字母表∑与NFAA得∑完全相同2o

把NFAA得每一个状态子集作为DFAA’得一个状态,因此该构造方法称为子集法。3o

设NFAA得任一状态子集{r1,r2,…,rn},ri∈S(i=1,2,…,n),令r’=[r1,r2,…,rn],r’∈S’。取a∈∑,DFAA’得映射函数定义为:

f’(r’,a)=q’∈S’

其中,q’=[q1,q2,…,qm],而{q1,q2,…,qm}=f(r1,a)∪f(r2,a)∪…∪f(rm,a)。4oDFAA得开始状态q0={S1,S2,…,SK},其中,Si∈S0(i=1,2,…,K)5oDFAA得终止状态F’={e’|e’=[e1,e2,…,ep],{e1,e2,…,ep}∩F≠Φ}具体操作方法:1o

依据NFA,构造确定化矩阵:

步骤:设状态S0就是NFA得开始状态,以[S0]作为DFA得开始状态,[S0]∈S’、再由f’([S0],a)=[S1,S2](a∈∑)若:f’([S0],b)=[S0](b∈∑)则:[S0]状态对于输入字符a,b得映射分别就是状态[S1,S2]与[S0]。其中:[S1,S2]∈S’就是DFA得新状态。再求新状态[S1,S2]对于a,b得映射,设:

f’([S1,S2],a)=[S0,S3]∈S’ f’([S1,S2],b)=[S1,S2,S3]∈S’,即:[S0,S3]与[S1,S2,S3]均为DFA得新状态。每得到一个新状态,就继续求新状态对a,b得映射,直到再没有新状态为止。

2o

依据1o求出得确定化矩阵,代换出确定化得状态转换矩阵。

3o

依据确定化得状态转换矩阵画出状态转换图。(1)不含ε弧得NFA得确定化例:设有NFA得N=({q0,q1,q2,q3},{x,y},f,{q0},{q1})得状态转换图如下:求等价得DFA(见前例)

解:1o依据NFA,构造确定化矩阵:状态\输入xy{q0}{q1,q2}{q0}{q1,q2}{q0,q3}{q1,q2,q3}{q0,q3}{q1,q2,q3}{q0,q3}{q1,q2,q3}{q0,q1,q3}{q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}{q0,q1,q2,q3}2o

依据构造得确定化矩阵,代换成确定化得状态转换矩阵(用符号重写确定化矩阵)

将确定化矩阵中得{q0},{q1,q2},{q0,q3}……分别用符号标记:A1,A2,……,A6即可。状态\输入xyA1A2A1A2A3A4A3A4A3A4A5A4A5A6A6A6A6A63o

依据确定化得转换矩阵画出状态转换图确定开始状态为:A1(代替[q0])终止状态为:A2,A4,A5,A6(A2,A4,A5,A6分别代替{q1,q2},{q1,q2,q3},{q0,q1,q3},{q0,q1,q2,q3},其中包含NFA中得终止态q1)(2)εNFA得确定化(带有空移或空环路得NFA)设εNFAM=(Q,∑∪{ε},f,Q0,F),有:

1o状态子集I得ε闭包(记为ε-closure(I))I蕴涵于Q,状态子集I得ε-closure(I)定义如下:若状态q∈I,则q∈ε-closure(I);若状态q∈ε-closure(I),q’就是由q出发经多条ε弧到达得状态,则q’∈ε-closure(I),显然,

ε-closure(I)蕴涵于Q例:设有状态转换图如下:

显然,状态集Q={1,2,3,4,5,6,7,8}若子集I={1},则:ε-closure(I)={1,2}(∵状态1∈I,∴1∈ε-closure(I);又∵从状态1出发经ε弧可到达状态2∴2∈ε-closure(I))若子集I={4,5},则:ε-closure(I)={2,4,5,6,7,8}2o状态集合I得a弧转换表示为

f(I,a)={q’|f(q,a)=q’,q∈I}=J(其中J蕴涵Q)即:J就是由子集I中得状态出发,经过一条a弧(跳过a弧前得任意条ε弧)可到达得状态得集合。令:Ia=ε-closure(J)表示:子集Ia就是从子集I中任意状态出发,经a弧(前后可跳过ε弧)而到达得状态得集合。例:上例,若子集I={1},根据定义:子集J=f({1},a)={5,3,4}

于就是:子集Ia=εclosure(J)=εclosure({5,3,4}={5,3,4,6,2,8,7}1,2得定义就是为了消除空弧或空环。例:已知εNFAM如下图。下面以此为例介绍εNFA确定化过程。解:依据εNFA得开始状态集{S},求ε-closure({S})={S}(汇集S射出ε弧得结点集合)作为DFA得开始状态。不断地按新得非空子集求对输入符号x,y得Ix与Iy,并将新得Ix或Iy作为DFA得状态。这一过程一直重复到不再出现新得Ix或Iy为止。如:Ix=ε-closure({1})={1,2,3} Iy=ε-closure(Φ)=Φ∵Ix为非空新子集,作为DFA得状态,且继续以{1,2,3}求Ix与Iy。

Ix=ε-closure({1,2,3})={4} Iy=ε-closure({1,2,3})={2,3,5}

其中,{4}与{2,3,5}作为DFA得结点,且又就是新得Ix,Iy,,继续求Ix,ly,过程如下矩阵:IxIy{S}{1,2,3}Φ{1,2,3}{4}{2,3,5}{4}Φ{6,7,Z}{2,3,5}{4,6,7,Z}{2,3,5}{6,7,Z}{7,Z}Φ{4,6,7,Z}{7,Z}{6,7,Z}{7,Z}{7,Z}Φ分别:将七种状态集:{S},{1,2,3},{4},{2,3,5}, {6,7,Z},{4,6,7,Z},{7,Z}用符号q0~q6命名得DFA七 种状态矩阵:DFA图如下:

即为所求得DFA。IxIyq0q1Φq1q2q3q2Φq4q3q5q3q4q6Φq5q6q4q6q6Φ例:已知εNFA(如图),求与之等价得DFA。

解:求DFA得开始状态(与上例不同)

ε-closure({x})={x,0,1},作为DFA得开始态。构造确定化矩阵:IaIb{x,0,1}{0,2,1}{0,1}{0,2,1}{0,2,1}{0,1,3}{0,1}{0,2,1}{0,1}{0,1,3}{0,2,1}{0,y,1}{0,y,1}{0,2,1}{0,1}IaIbABCBBDCBCDBEEBC画DFA得图形表示五、DFA得化简(DFA得最小化)

1、化简DFA得目得寻找一个状态数比M少得DFAM’,使得L(M)=L(M’)DFA得状态少,则依据它编写得词法分析程序就简单。

2、化简化简问题:①使化简后得DFA中,没有多余得状态。②使化简后得DFA中,没有两个就是相互等价得状态。－－采用分割法。所谓多余状态:从自动机得开始状态出发,输入任何得字符串也不能到达得那个状态。从自动机得开始状态到某个结点有弧,但该结点无弧通向终止状态。不可到达得状态对于生成自动机得语言毫无意义。因此,应该从自动机中删去。两个状态s与t等价得条件就是:一致性条件:状态s与t必须同时为可接受状态(终止状态)或不可接受状态(非终止状态)。漫延条件:对于所有输入符号,状态s与t必须转换到等价得状态集里。

如果两个状态不等价,则称这两个状态就是可区别得。自动机中得非终止状态与终止状态就是可区别得(∵不满足一致性条件)非终止状态0,2,1,3与终止状态4可区别。不满足一致性条件。状态2与状态3可区别(∵状态2读入b后到达2;状态3读入b后到达4,而2与4不等价:即2,3不满足漫延条件)。注:分割法就就是使状态满足漫延条件与一致性条件。关键:满足漫延条件得分割方法。3、用分割法化简DFA

基本思想:将DFA得状态集分成若干个互不相交得子集,使每个子集中得状态都就是等价得,而不同状态子集中得状态则就是不等价得。即就是可区分得。1o

首先,将DFA得状态分成两个子集:终止状态子集与非终止状态子集。(因为终止状态与非终止状态就是可区别得)。(使状态满足一致性条件)2o

然后对每个子集进行再分解。分解后得两个状态属于同一个子集,当且仅当对于任何一个输入字符,它们得映射属于同一个子集,此过程一直执行到不能再分解为止。(使状态满足漫延条件)3o

将分解得每个子集作为化简后得DFA得每一个状态。且含有原来开始状态得子集与含有原来终止状态得子集分别作为开始状态与终止状态。

具体DFA得化简过程。例:已知有DFA图如下,化简DFA:

解:1o将所有终止状态归为一个子集S1={q1,q3,q4,q5};其余非终止状态归为另一个子集:S2={q0,q2}2o按可区别性分解子集S1与S2

分解S1:∵f(q1,x)=q2∈S2 f(q3,x)=q4∈S1 f(q4,x)=q5∈S1 f(q5,x)=q5∈S1 (也可对y字符进行)∴将S1分解成两个子集S1’={q1},S2’={q3,q4,q5}

分解S2: ∵f(q0,x)=q1∈S1’ f(q2,x)=q3∈S2’ ∴将S2分解成两个子集{q0},{q2}最后分解成4个子集:{q1},{q3,q4,q5},{q0},{q2}分别用q1,q3,q0,q2来替换成4个子集得状态名。DFA得化简:用状态矩阵形式辅助完成化简xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5分解:S1={q0,q2},S2={q1,q3,q4,q5}对x,S2分解:S21={q1},S22={q3,q4,q5}对x,s1分解:S12={q0},s12={q2},S22对x或y不能分解。最后得到分解:{q0},{q1},{q2},{q3,q4,q5}例:将DFA(如下图)最小化。解:1o

将终止态与非终止态得结点分为2个子集:

=({A,B,C,D},{E})(其中S0={A,B,C,D},S1={E})20分解子集:S0＝{A,B,C,D}对a:对b:f(A,a)=B∈S0写成{A,B,C,D}a={B}∵B包含在{A,B,C,D}中,∴{A,B,C,D}对a不被分裂f(B,a)=B∈S0f(C,a)=B∈S0f(D,a)=B∈S0f(A,b)=C∈S0写成{A,B,C,D}b={C,D,E}∵{C,D,E}既不包含在{A,B,C,D}中,又不包含在{E}中,∴{A,B,C,D}对b要被分裂。f(B,b)=D∈S0f(C,b)=C∈S0f(D,b)=E∈S1∴=({A,B,C},{D},{E})(若令S2={A,B,C},S3={D},S4={E})再分解:{A,B,C}对a:对b:f(A,a)=B∈S2写成{A,B,C}a={B}∵B包含在{A,B,C}中,∴{A,B,C}对a不被分裂f(B,a)=B∈S2f(C,a)=B∈S2f(A,b)=C∈S2写成{A,B,C}b={C,D}∵{C,D}既不包含在{A,B,C}中,又不包含在{D}中,∴{A,B,C}对b要被分裂。f(B,b)=D∈S3f(C,b)=C∈S2∴＝({A,C},{B},{D},{E})再分解:{A,C}∵{A,C}a={B}(∵{B}包含在{B}中,∴对a,{A,C}不被分裂) {A,C}b={C}(∵{C}包含在{A,C}中,∴对b,{A,C}不被分裂)

结论:A,C状态等价。整个分解终止。∴ =({A,C},{B},{D},{E})DFA最小化为:IaIbABCBBDCBCDBEEBC注:可通过DFA确定化矩阵,应用状态满足漫延条件与一致性条件,直接得出等价得状态。如:上面得确定化矩阵,{B}b={D},{D}b={E},而E,D不等价,导致B,D不等价,所以,D与B要分裂。例:已知正规式R=l(l|d)*,求最小DFA解:步骤:1o求DFA2o求DFA子集法:构造确定化得矩阵IlId{x}{1,2,y}Φ{1,2,y}{2,y}{2,y}{2,y}{2,y}{2,y}IlIdABΦBCCCCC3o最小化DFA分割法:首先将DFA分解成两个子集:=({A},{B,C}){B,C}不能分解:对l: 对d:∴B,C等价:去掉C

最小化DFA:

注:实现时,扩充为:

且规定:字符串得长度为n,f(B,l)=C写成{B,C}l={C}f(C,l)=Cf(B,d)=C写成{B,C}d={C}f(C,d)=C六、由最小化得DFA到词法分析程序得构造若指明DFA得每一个状态要完成得任务再把从状态0出发得弧上所标记得输入字符视为控制条件则:DFA实际上就就是一个程序流程图。例:上例最小化DFA:

要识别一个标识符就是否结束,必须读到该标识符后继字符就是分界符(或非l,d)因此,实现时,将标识符DFA作适当修改:如果赋予状态A,B,Z一定得操作,则DFA变为识别标识符程序得框图。§4、正规文法与有穷自动机之间得转换一、正规文法到有穷自动机得转换分别就左,右线性文法到有穷自动机得转换1、右线性文法到有穷自动机得转换 设给定右线性文法G=(VN,VT,P,S),则相应得有穷自动机M=(Q,∑,f,q0,Z)、

转换方法:(1)将VN中每一个非终结符视作M1中得一个状态,并增加一个终结状态D,DVN,令Q=VN∪{D},Z={D},∑=VT,q0=S,f函数构造如下:(2)对G中每一形如:A∷=aB得产生式(A,B∈VN,a∈VT∪{ε}),令f(A,a)=B;(3)对G中每一形如:A∷=a得产生式(A∈VN,a∈VT),令f(A,a)=D;(注意:D就是终结状态)(4)对G中每一形如:A∷=ε得产生式(A∈VN),令f(A,ε)=D;

显然,这样构造得M就是具有一个开始状态得NFA。例:构造下列右线性文法G[Z]得有穷自动机。

Z∷=0AA∷=0A|0BB∷=1A|1则构造等价自动机M=({Z,A,B,D},{0,1},f,{Z},{D}),其中:

f(Z,0)={A},f(A,0)={A,B},f(B,1)={D},f(B,1)={A}右线性文法构造状态图

A

B

Z

D

0

1

0

1

0状态矩阵表示:2、左线性正规文法到有穷自动机得转换设给定义左线性正规文法G=(VN,VT,P,S),则相应得有穷自动机M=(Q,∑,f,q0,Z)、(1)新增加一个初始状态q0,且q0VN;将VT中每个非终止状态视作M中得状态,令Q=VN∪{q0},并将G得开始符号S瞧成终结状态,即Z={S},∑=VT;(2)对G中每一形如:A∷=Ba得产生式(A,B∈VN,a∈VT∪{ε}),令f(B,a)=A;

01Z{A}ΦA{A,B}ΦBΦ{A,D}DΦ

Φ(3)对G中每一形如:A∷=a得产生式(A∈VN,a∈VT∪{ε}),令f(q0,a)=A;例,构造G[A]得自动机A∷=A1|B1B∷=B0|0根据转换方法,与G对应得自动机M=({S,A,B},{0,1},f,S,{A}),其中:

f(A,1)=A,

f(B,1)=A,

f(B,0)=B,

f(S,0)=B其状态图:它为确定得,且识别得语言为:L(M)=L(G[A])=00*11*二、有穷自动机到正则文法得转换给定有穷自动机M=(Q,∑,f,q0,Z),按下列方法构造对应右线性文法G=(VN,VT,P,S):(1)令VN=Q,VT=∑,S=q0;(2)若f(A,a)=B,且B不就是终结状态,则将A∷=aB加到p中;(3)若f(A,a)=B,且B就是终结状态,则将A∷=aB|a或A∷=aB,B∷=ε加到p中;(4)若G得开始符号S就是一个终结状态,则将S∷=ε加到p中。例:设DFAM=({A,B,C,D},{0,1},f,A,{B}),其中:

f(A,0)=B,f(B,1)=C,f(C,0)=B,

(1)根据函数式构造右线性正规文法G[A]:

A→0B|0,B→1C,C→0C|0

或A∷=0B,B∷=1C|ε,C∷=0B(2)将函数式换成状态图,然后转换成右线性正规文法。由函数式得到等价得DFAM:根据状态转换图,所求右线性文法G=({A,B,C},{0,1},P,A),P为:

A∷=0B|0,B∷=1C,C∷=0B|0

或A∷=0B,B∷=1C|ε,C∷=0B注:以开始状态作为开始符号,然后依弧得方向写出产生式右边得式子。若到达得就是终结状态弧,则,该弧上得符号要作为产生式右边得式子。该自动机所识别得语言为0(01)*、注:1、自动机3种形式:函数式、状态图与状态矩阵都可以转换成正规文法。例:已知自动机3种形式如下,转换成右线性正规文法01SBΦBBAAΦAf(S,0)=B,f(B,0)=B,f(B,1)=A,f(A,1)=A、转换成右线性正规文法G[S]=({S,A,B},{0,1},P,S)P:S→0B,B→0B|1A|1,A→1A|1、2、通过状态图将左右线性正规文法可以互换上例状态图转化成左线性正规文法G[A],P:A→A1|B1,B→B0|0(终结状态作为开始符号,原来开始状态作为终结状态,然后以弧逆方向写出产生式右边得式子。)§5、词法分析程序得编写方法及实验要求一、词法分析程序编写方法两种方法:手工编写方法:根据识别语言单词得状态图,使用某种高级语言,例如c语言直接编写词法分析程序。利用词法分析程序得自动生成工具LEX自动生成此法分析程序。下面仅介绍手工编写词法分析程序得构造过程。二、词法分析程序构造过程:1、分析列出待分析语言得所有单词符号,编写对应得种别码。例:c语言子集得单词符号及种别码:(1)有穷得单词符号:关键字:main,void,if,then,while,for,printf,scanf,int,…运算符:+,-,*,/,>,>=,<,<=,==,!=,(,),…分界符:{,},;,:,,,[,],…编写对应得种别码:单词符号种别码单词符号种别码单词符号种别码单词符号种别码main1=21,30‘

‘39int2+22;31‘\0100char3-23:32ERROR-1if4*24>33else5/25<34for6(26>=35while7)27<=36ID10{28==37NUM11}29!=38(2)无穷得单词符号应写出对应得文法。如:标识符(ID)与常数(NUM) ID:letter(letter|digit)*(ID种别码见上表) letter∷=a|b|…|z|A|B|…|Z digit∷=0|1|…|9常数:整常数:NUM:digit(digit)*(NUM种别码见上表)2、画单词得状态转换图(下页)Z1035678941011letter非letter非digitletter|digitdigit非digitdigit+-*/>其它=100n其它出错处理……3、根据状态图与单词符号得种别码表,构造词法分析程序简单得方法:让每个状态对应一小段程序。在此引进词法分析程序所用得全局变量与需要调用得函数;(1)ch字符变量,存放当前读入得源程序字符。(2)token字符数组,存放构成单词符号得字符串、(3)getch()读字符函数,每调用一次从输入缓冲区中读入源程序得下一个字符放在ch中,并把读字符指针指向下一个字符串。(4)getbc()函数,每次调用时,检查ch中得字符就是否为空白字符。就是,则反复调用getch(),直至ch读入一个非空白字符为止。(5)concat()函数,每次调用把当前ch中得字符与token中得字符串连接。例如:token字符数组中原有值为”ab”,ch存放着”c”,经调用concat后,token中得值为:”abc”、(6)lett(ch)与digi()布尔函数,分别用来判断ch中得字符就是否为字母与数字,从而给出true或false值。(7)reserve()整型函数,对token中得字符串查种别码表,若就是一个关键字,则返回她得种别码,否则返回标识符得种别码10。(8)retract()函数,读字符指针回退一个字符。(9)return()函数,收集并携带必要信息返回调用程序。即返回语法分析程序。(10)dtb()十进制转换函数,它将token中得数字出转换成二进制数值表示,并以此作为涵数值返回。根据状态转换图,用c语言编写得词法分析程序如下:scaner(){ token=NULL; getch(); getbc(); if(lett(ch)) { while(lett(ch)||digi(ch))//识别关键字与标识符

{ cancat(); getch(); } retract();c=reserve(); if(c!=10)return(c,token); elsereturn(10,token); }elseif(digi(ch))//识别常数

{while(digi(ch)) { concat(); getch(); } retract(); return(11,dtb()); } else//识别运算符与分界符

switch(ch){ case‘+’:retrun(22,-);break; case‘-’:retrun(23,-);break; case‘*’:retrun(24,-);break; case‘/’:retrun(25,-);break; case‘>’:getch(); if(ch==‘=‘)return(35,-); retract();break; …… default:error(); }}三、词法分析程序构造得实验1、实验报告得内容(1)实验目得(2)实验要求a