《词法分析及词法分析程序..复习课程.ppt》由会员分享，可在线阅读，更多相关《词法分析及词法分析程序..复习课程.ppt（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、词法分析及词法分析程序.程序语言的单词（1）单词词文模式关键字WHILEwhilewhileFORforfor标识符IDtemp,i,max字母开头的字母数字串常数NUM3.14100数字串.数字串单词：同类词文的总称词文：源程序中能匹配某一记号的字符串模式：描述用字符串构成单词的规则5程序语言的单词（2）单词词文模式运算符MUL*GT界符,串常量STRING“hello”there双（单）引号中间的字符串（不包括引号本身）63.2 正规文法和状态转换图正规文法和状态转换图单词的描述：正规文法定义了单词的描述：正规文法定义了3 3型语言型语言，常见，常见的单词可由正规文法定义。的单词可由正规文
2、法定义。单词的识别：状态转换图可用于识别单词的识别：状态转换图可用于识别3 3型语言型语言，它是设计和实现扫描器的一种有效工具，是有它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。限自动机的直观图示。183.2.1 3.2.1 由正规文法构造状态转换图由正规文法构造状态转换图n程序设计语言的单词都能用正规文法描述，例如，标识符可定义为：字母字母字母字母 数字数字数字数字 字母字母字母字母n若把字母、数字视为终结符，则上述产生式为左线性文法，是正规文法。n若我们用d表示0-9间的数字，则C语言的的文法是右线性文法，也是正规文法（见P48）19状态转换图状态转换图n n状态转换图：状态
3、转换图：状态转换图：状态转换图：由一组矢线连接的有限个结点所组成的有向图。每个结点代表在识别分析过程中扫描器所处的状态，其中含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点）n凡能用正规文法描述的语言，均可由某种有限状态算法状态转换图状态转换图状态转换图状态转换图进行分析。20由右线性文法构造状态转换图由右线性文法构造状态转换图设设G=(VN,VT,P,S)是一右线性文法，并设是一右线性文法，并设|VN|=k,则所要构造的状态转换图共有则所要构造的状态转换图共
4、有k+1个个状态状态(结点结点)。用。用VN中的每个符号分别标记其中的每个符号分别标记其中的中的k个结点，且令个结点，且令G的开始符的开始符S为初态结点；为初态结点；余下的一个结点作为终态结点，用余下的一个结点作为终态结点，用F(VN)标标记。记。21A状态转换图的构造原则状态转换图的构造原则GG的每一个非终结符号代表一结点的每一个非终结符号代表一结点(状态状态)开始符号开始符号S S作为初始状态作为初始状态 设一符号设一符号F F不属于不属于V V作为终止状态作为终止状态 形如形如AaBAaB的规则的规则 a a 形如形如AaAa的规则的规则 a a 特别特别:A :A 未曾在未曾在A A的
5、射出弧中的射出弧中 出现过的终结符号出现过的终结符号 某些情况下也可考虑直接将某些情况下也可考虑直接将A A作为终态作为终态BSFBAAFAFA22例例:GZ:GZ:Z0U1VZ0U1VU 1Z1U 1Z1V 0Z0V 0Z0 23例例:GZ:GZ:状态转换图状态转换图:Z0U1VZ0U1VU 1Z1U 1Z1 1 V 0Z0V 0Z0 0 1 初态初态 1 0 0 ZUVF24利用状态转换图识别符号串的方法对于已给的字符串对于已给的字符串w=a1a2an,ai VT,利用状态转换图利用状态转换图对对w 识别的步骤如下识别的步骤如下:(1)从初始状态从初始状态S出发出发,自左至右逐个扫描自左至
6、右逐个扫描w的各个字符的各个字符(当前为当前为a1),此时在结点此时在结点S所射出的诸矢线中所射出的诸矢线中,寻找标寻找标记为记为a1的矢线的矢线(若不存在若不存在,则表明则表明w有语法错误有语法错误),读读入入a1并沿矢线所指方向前进并沿矢线所指方向前进,过渡到下一状态过渡到下一状态(设为设为A1).(2)设当前处在设当前处在Ai状态状态,所扫描的字符为所扫描的字符为ai+1,在结点在结点Ai所所射出的诸矢线中射出的诸矢线中,寻找标记为寻找标记为ai+1的矢线的矢线(若不存在若不存在,则表明则表明w有语法错误有语法错误),读入读入ai+1,并进入状态并进入状态Ai+1;(3)重复重复(2),
7、直到直到w中所有字符被读完且恰好进入终态中所有字符被读完且恰好进入终态F时时,宣告整个识别结束宣告整个识别结束,w可被接受可被接受.27例例:GZ:GZ:状态转换图状态转换图:Z0U1VZ0U1VU 1Z1U 1Z1 1 V 0Z0V 0Z0 0 1 初态初态 1 0 0 1 1=011001=0110012 2=111001=111001ZUVF28状态转换图识别的语言n显然显然,若从若从初态初态出发出发,分别沿分别沿一切可能一切可能的的路径路径到达到达终态终态结点结点,并将路径中并将路径中矢线上所标记的字符矢线上所标记的字符依次连接起来依次连接起来,便得到便得到状态转换图状态转换图所能识别
8、的所能识别的全部符号串全部符号串,这些符号串这些符号串组成的集合构成了该组成的集合构成了该状态转换图状态转换图状态转换图状态转换图识别的语言。识别的语言。29状态转换图与文法推导状态转换图与文法推导n用状态转换图识别符号串w w的过程，就是为w w建立一个推导S S*w*w的过程。n在第一步（在初始状态S S下，扫描到a a1 1而过渡到下一状态A A1 1），由状态转换图的构造规则可知，GG中必有产生式S Sa a1 1A A1 1;n对于识别过程的后续步骤，由状态A Ai i 识别a ai+1i+1后过渡到A Ai+1i+1恰好对应了使用产生式A Ai i a ai+1i+1A Ai+1
9、i+1。n最后在状态A An-1n-1识别a an n后到达终态F F，对应了使用产生式A A a an n。n整个推导过程：S S a a1 1A A1 1 a a1 1a a2 2A A2 2 a a1 1a a2 2aan-1n-1A An-1n-1 a a1 1a a2 2aan n30例例:GZ:GZ:状态转换图状态转换图:Z0U1VZ0U1VU 1Z1U 1Z1 1 V 0Z0V 0Z0 0 1 初态初态 1 0 0 例例:=011001:=011001通过状态图可以确定通过状态图可以确定是文法的句子是文法的句子.此过程是一种推导过程此过程是一种推导过程.Z=0U=01Z=011V
10、=0110Z=01100U=011001Z=0U=01Z=011V=0110Z=01100U=011001ZUVF31右线性文法与状态转换图右线性文法与状态转换图 设设GG是一是一右线性文法右线性文法右线性文法右线性文法,MM是相应的是相应的状态转换图状态转换图状态转换图状态转换图,则从前面的讨则从前面的讨论可以看出如下事实：论可以看出如下事实：(1)在利用在利用MM对符号串对符号串ww进行识别时进行识别时,MM中每次状态的转换都模拟了一中每次状态的转换都模拟了一步直接推导步直接推导,即识别方法即识别方法(或称分析方法或称分析方法)是是“”的的;(2)因因右线性文法右线性文法只有形如只有形如A
11、 AaBaB、A A a a的产生式，所以推导的每的产生式，所以推导的每一步所得句型只含一个非终结符，且必出现在句型的最右端，所一步所得句型只含一个非终结符，且必出现在句型的最右端，所以推导是以推导是规范推导规范推导，每步所得的句型也必为，每步所得的句型也必为规范句型规范句型；(3)对于对于MM所识别的任一符号串所识别的任一符号串x x,必存在必存在G中的一个推导中的一个推导S S*x*x(即即有有x x L(G);L(G);反之反之,对于对于L(G)L(G)中任一句子中任一句子y y,必存在一条从初态必存在一条从初态S S到终到终态态F F的路径的路径,此路径上各矢线的标记依次拼接起来所组成
12、的符号串此路径上各矢线的标记依次拼接起来所组成的符号串恰为恰为y y。32由左线性文法构造状态转换图由左线性文法构造状态转换图n设G=(VG=(VN N,V,VT T,P,S),P,S)是一左线性文法,构造相应的状态转换图的方法是:首先用V VN N中的非终结符标记M的结点，其中，开始符S S对应的结点为终态结点。引入一个新结点R(R(V VN N)标记初态。矢线的连接规则为:(1)对于GG中形如A Aa a 的产生式，引矢线R RA A，且标记为a a；(2)对于G中形如A ABaBa 的产生式，引矢线线 B BA A，且标记为a a。33由左线性文法构造状态转换图由左线性文法构造状态转换图
13、已给文法已给文法G=(S,U,0,1,SS1|U1,UU0|0,S)R RU US S0 00 01 11 1用左线性文法构造出的状用左线性文法构造出的状用左线性文法构造出的状用左线性文法构造出的状态转换图识别文法的句子态转换图识别文法的句子态转换图识别文法的句子态转换图识别文法的句子与前面的过程一样与前面的过程一样与前面的过程一样与前面的过程一样.就识别的方法而言就识别的方法而言就识别的方法而言就识别的方法而言,属于自属于自属于自属于自底向上的分析底向上的分析底向上的分析底向上的分析.以句子以句子以句子以句子00011000110001100011为例为例为例为例,给出其给出其给出其给出其识
14、别的的步骤识别的的步骤识别的的步骤识别的的步骤.见右表见右表见右表见右表.步骤步骤步骤步骤 当前状态当前状态当前状态当前状态 余留的符号串余留的符号串余留的符号串余留的符号串1 1R R 00011 000112 2U U 0011 00113 3U U 011 0114 4U U 11 115 5S S 1 16 6S S(识别结束识别结束识别结束识别结束)34例例:GZ:GZ:ZU0V1ZU0V1U Z11U Z11V Z00V Z00状态转换图状态转换图:0初态初态 1 1 0 0 1RUVZ(2)(2)状态转换图的使用状态转换图的使用 识别句子识别句子(单词符号单词符号)例例:1001
15、10:100110通过状态图可通过状态图可以确定是文法的句子以确定是文法的句子.识别过程对应着归约识别过程对应着归约过程过程 1 10011000110 U0U001100110 Z0Z0110110 V1V11010 Z1Z10 0 U0U0 Z Z353.2.2 3.2.2 状态转换图的实现状态转换图的实现-状态矩阵法状态矩阵法n状态转换图状态转换图可方便地用于识别单词.但是,如何让计算机利用状态转换图来进行词法分析呢?n一个简单实用的方法就是将图以矩阵的形式保存在内存中.这就是所谓的状态矩阵法状态矩阵法.n状态矩阵状态矩阵 以图中各个状态S S S S1 1 1 1,S,S,S,S2 2
16、 2 2,S,S,S,Sn n n n为行,以各个输入符号a a a a1 1 1 1,a,a,a,a2 2 2 2,a,a,a,ammmm为列,组成一个n n n n mmmm矩阵B B B B,其元素B B B Bij ij ij ij=B=B=B=BSSSSi i i i,a,a,a,aj j j j 指明扫描器此时应完成的语义动作和要转换到的下一状态S S S Sk k k k.其含义是,在S S S Si i i i状态下,扫描到a a a aj j j j符时,按序偶(S(S(S(Si i i i,a,a,a,aj j j j)查矩阵B B B B,扫描器根据B B B Bij i
17、j ij ij的指示,先执行相应的语义动作,再转换到下个状态S S S Sk k k k.n若B B B Bij ij ij ij为“出错出错”,则说明输入符号串有误,拒绝接受.扫描器将调用出错处理程序进行处理37程序程序3-2 状态矩阵驱动程序状态矩阵驱动程序CurStat=0;FlagOfFS=NoneSeen;/*/*将终态标志置为将终态标志置为将终态标志置为将终态标志置为“未经历未经历未经历未经历”*/”*/if(CurChar=EOF)return 0;while(CurChar!=EOF)if(Stat=TransMatCurStatCurChar!=NULL)/*/*能进行状态转
18、换能进行状态转换能进行状态转换能进行状态转换*/*/CurStat=Stat;advance();if(CurStat 是终态是终态)FlagOfFS=HasSeen;/*标记经历过的终态标记经历过的终态标记经历过的终态标记经历过的终态*/*/记下输入串中当前位置及该状态相关联的动作记下输入串中当前位置及该状态相关联的动作;/*end if CurStat/*end if CurStat 是终态是终态是终态是终态*/*/38 else /*/*不能继续进行状态转换不能继续进行状态转换不能继续进行状态转换不能继续进行状态转换*/*/if(FlagOfFS=NoneSeen)/*/*未经历过未经历
19、过未经历过未经历过终态终态终态终态*/*/报告词法错误报告词法错误;略过当前词文及输入字符略过当前词文及输入字符;CurStat=0;else /*/*经历过经历过经历过经历过终态终态终态终态*/*/回退到最近经历的那个终态的输入字符位置回退到最近经历的那个终态的输入字符位置;执行所记录的该终态的相关动作执行所记录的该终态的相关动作;/*执行经历过的终态执行经历过的终态执行经历过的终态执行经历过的终态*/*/*end if FlagOfFS=NoneSeen*/*end if FlagOfFS=NoneSeen*/*end if Stat!=NULL*/*end if Stat!=NULL*/
20、*end while*/*end while*/39贪心策略n目的是获得最长匹配单词（1）若当前状态对输入符号有后继动作，则继续进行状态转移；（2）若当前状态为终态，记下该状态和当前输入字符的位置，并继续向前扫描；（3）若当前状态已无后继状态，并且此前经历过终态，则执行曾经历的最近的终态所对应的语义动作；（4）若当前状态已无后继状态，并且此前没有经历过终态，则表明输入字符串有词法错误，报错，并略过余下的部分词文，从状态0开始继续下一单词的识别。n状态矩阵是稀疏的，应该采用紧凑的数据结构40识别识别无符号数无符号数的语义操作的语义操作n功能：把识别出的无符号数转换成整数（ICONICON）和实数
21、和实数（FCONFCON）。）。）。）。n无符号数的输入形式：d dmmd dm-1m-1dd0 0.d.d-1-1dd-n-n E E dd dddd 可改写为可改写为 d dmmd dm-1m-1dd0 0 d d-1-1dd-n-n 10(10(dd dddd-n);-n);n用w,p,n,ew,p,n,e分别计录尾数、指数、小数位及指数的符号。因此数值为：N=w N=w 10(e 10(e (p-n)p-n)n语义加工过程：w,p,nw,p,n初值为0，e e初值为1；处理整数部分时，对于每个d di i,令令令令w=ww=w 10+d10+di i;处理小数部分时，对于每个d di
22、i,令令令令w=ww=w 10+d10+di i;及及及及n+;n+;处理指数时，E E后若有-号，令e=-1e=-1；计算指数值p=pp=p 10+d10+d;在出口处，令ICON=wICON=w或或或或FCON=wFCON=w 10(e10(e (p-np-n).).41识别无符号数无符号数的状态矩阵423.3 有限自动机状态转换图实际上是有限自动机的图形表示433.3.1 确定的有限自动机DFAn抽象地看抽象地看,状态转换图状态转换图由五个部分组成由五个部分组成:(1)(1)有限个状态之集有限个状态之集,记作记作K K;(2)(2)有限个输入符号组成的字母表有限个输入符号组成的字母表,记
23、作记作;(3)(3)从从K K到到K K的的转换函数转换函数 f:Kf:KK.f(p,a)=qK.f(p,a)=q表示若表示若当前状态为当前状态为p p,且输入符号为且输入符号为a a,则进入下一个状态为则进入下一个状态为q q;(4)(4)S S0 0 K K,初始初始(开始开始)状态状态;(5)(5)若干个终态之集若干个终态之集:Z(Z(K)K)由上述五个要素组成的五元式由上述五个要素组成的五元式 M=(K,M=(K,f,S,f,S0 0,Z),Z)称为一称为一个个确定的有限自动机确定的有限自动机 (DFADFA:D Deterministic eterministic F Finite
24、inite A Automatautomata)由此可见由此可见,DFADFA实际上是状态转换图的形式描述实际上是状态转换图的形式描述(数学定义数学定义),),状态转换图是状态转换图是DFADFA的几何的几何(图形图形)表示表示.44ZUVF2=1001已知已知DFA M=(K,f,S0,Z)，其中：，其中：K=Z，U，V，F，=0，1，S0=Z，Z=Ff(Z,0)=U,f(Z,1)=V,f(U,0)=Z,f(U,1)=F,f(V,0)=Zf(V,1)=F状态转换图状态转换图:1=0010010初态初态011103=11100145DFA的接受集nDFA M的接受集 我们把一DFA M所接受的
25、符号串的全体称为M的接受集或M接受的语言，记为L(M),即 L(M)=x|f(S0,x)Z,x*nM接受(或识别)某符号串x*：从初态S0出发,经一恰好标有x 的路径后可达到某终态S Z。用f描述就是:S Z,f(S0,x)=S n将转换函数f 的定义域拓广到K*，可以得到 f:(1)f(s,)=s,s K;(2)f(s,aw)=f(f(s,a),w),s K,a,w*;n对于x*,f(s,x)=t 的含义是,当M从状态s出发,依次扫描完x的各个符号后将进入状态t.n只要f有定义,f与f的效果是一致的，以后不再区分。46转换函数转换函数 f:K f:KK.K.f(p,a)=qf(p,a)=q表
26、示若当前状态为表示若当前状态为p,p,且输入符号为且输入符号为a,a,则进入下一个状态为则进入下一个状态为q;q;把把f f拓广到拓广到f:f:f(p,f(p,x)=q)=q若若x=abcd=abcdf(p,a)=p1,f(p1,b)=p2,f(p,a)=p1,f(p1,b)=p2,f(p,f(p,x)=f(f(p,a),bcd.)=f(f(p,a),bcd.)47确定的有限自动机n确定的FA：在状态转换的每一步，根据FA当前的状态及扫描的输入字符，便能唯一地唯一地确定FA的下一状态。在转换图上看，若|=n，则任何结点所引出的矢线至多有n条，且矢线上的标记均不同。n例如，P51图3-4所对应的
27、DFA为 M=(R,U,S,0,1,f,R,S)其中，f的定义如下：f(R,0)=Uf(U,0)=Uf(U,1)=Sf(S,1)=Sn由DFA与状态转换图的关系可知，构造状态转换图的算法，同样适用于构造DFA。n可以证明，正规文法G，DFA M，使L(M)=L(G)，反之亦然。483.3.2非确定的有限自动机 在相应的状态转换图中，在相应的状态转换图中，就会出现这样的结点就会出现这样的结点U，它具有多条标记为同，它具有多条标记为同一输入符号一输入符号a的矢线的矢线图图图图3-8 NFA3-8 NFA的状态转换图的状态转换图的状态转换图的状态转换图在在U状态下，输入符号为状态下，输入符号为a时，
28、时，FA的下一状态不唯一，而的下一状态不唯一，而是在状态集是在状态集A,B,C,X中任选其一。具有这种性质的中任选其一。具有这种性质的FA称为非确定的称为非确定的FA（NFA:Nondeterministic FA）U UA AB BC CX Xa aa aa aa a.49非确定有限自动机的定义非确定有限自动机的定义nNFA M 也可用五元式定义：M=(K,f,S0,Z)，其中，K,S0,Z的含义同DFA,转换函数f的定义为 f:K(K),即将(Si,aj)映射到K的一个子集Sk1,Skm n类似地，我们可把f的定义域拓广到K*：(1)f(S,)=S;(2)f(S,aw)=f(f(S,a),
29、w)a,w*.50NFA的接受集n所有为所有为NFANFA M M所接受的符号串之集称为所接受的符号串之集称为NFA MNFA M的接受集的接受集（或识别集），记作（或识别集），记作 L(M).L(M).即即 L(M)L(M)=x x|f f（S S0 0,x,x）Z Z ,x,x*nx x*为为M M所接受：集合所接受：集合f(Sf(S0 0,x),x)中含有中含有Z Z中的元素中的元素（终态），即至少存在一条从初态（终态），即至少存在一条从初态S S0 0到某一终态的路到某一终态的路径，此路径上的符号之连接恰为径，此路径上的符号之连接恰为x x。例例3.13.1 给定给定M=(S,A,B,
30、C,M=(S,A,B,C,a,b,f,S,C),a,b,f,S,C),其状态转其状态转换图见右。由图可知换图见右。由图可知M M是一是一NFANFA。S SA AB BC Ca aa,ba,ba ab bb ba aa a51识别符号串识别符号串ababbababb的路径的路径注意注意，NFANFA识别输入符号串时有一个试探过程，为了能识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（走到终态，往往要走许多弯路（带回溯带回溯），这影响了），这影响了FAFA的效率。的效率。能否提高其工作效率就是下一小节讨论的课题。事实能否提高其工作效率就是下一小节讨论的课题。事实能否提高其工作效
31、率就是下一小节讨论的课题。事实能否提高其工作效率就是下一小节讨论的课题。事实上，对任一上，对任一上，对任一上，对任一NFA MNFA MNFA MNFA M，总可构造一个总可构造一个总可构造一个总可构造一个DFA MDFA MDFA MDFA M，使，使，使，使 L(M)=L(M)L(M)=L(M)L(M)=L(M)L(M)=L(M)成立。这就是成立。这就是成立。这就是成立。这就是NFANFANFANFA与与与与DFADFADFADFA的等价性的等价性的等价性的等价性。S SA AB BC Ca aa|ba|ba ab bb ba aa an符号串符号串ababbababb的识别路径的识别路径
32、S(S(a a)A(A(b b)B(B(a a)A(A(b b)B(B(b b)C C(接受接受)。(参见书中参见书中P60P60)523.3.3 NFA与与DFA的等价性的等价性n可将可将DFA看作看作NFA的特殊情况的特殊情况,即即DFA所接受所接受的语言类包含在的语言类包含在NFA所接受的语言类中。因所接受的语言类中。因此，要证明此，要证明NFA与与DFA的等价性，只需证明的等价性，只需证明每一个每一个NFA都可以确定化。都可以确定化。n确定化：对任意确定化：对任意NFA M，构造一个，构造一个DFA M，使得使得L(M)=L(M)。n思路：令思路：令M的某个状态与的某个状态与M的某个状
33、态子集的某个状态子集相对应，并使得在相对应，并使得在M扫描与扫描与M相同的输入符相同的输入符号时，保持对号时，保持对M的状态进行跟踪（能根据的状态进行跟踪（能根据M的状态确定的状态确定M的状态）。的状态）。53NFA确定化的例子确定化的例子例例3.23.2 M=(S0,S1,a,b,f,S0,S1)S S0 0S S1 1a ab bb ba|ba|b构造构造M的的DFA M=(K,a,b,f,S0,Z),其中其中 K=S0,S1,S0,S1,f(S0,a)=S0,S1 f(S0,b)=S1f(S1,a)=f(S1,b)=S0,S1因为因为 f(S0,S1,a)=f(S0,a)f(S1,a)=
34、S0,S1 f(S0,S1,b)=f(S0,b)f(S1,b)=S0,S1所以所以 f(S0,S1,a)=f(S0,S1,b)=S0,S1_f_|_a_ b_S0|S0,S1 S1S1|S0,S157NFA确定化的例子（续）确定化的例子（续）f(,a)=f(,b)=f|a b|new state|S0|S0,S1 S1|1S1|S0,S1|2S0,S1|S0,S1 S0,S1|3Z=S1,S0,S1M=(K,a,b,f,S0,S1,S0,S1)1 12 23 3a ab bb|ab|ab b583.3.4 具有具有 动作的动作的FAn若在一若在一FAFA中中,允许对允许对 也作状也作状态转移态
35、转移,则这样的则这样的FAFA称为具有称为具有 动作的动作的FA.n右图就是一个具有具有 动作的动作的FA。其中其中,有的矢线上标记为有的矢线上标记为（在此看作一个符号在此看作一个符号）。标记为 的矢线对识别符号串无影响,但却改变了当前的状状态态.0 01 12 23 3 a ab bb bc c例如,上图的FA中,从状态0到状态3存在路径:0(a)0(a)0()2(c)2(c)2()3,即M识别了aacc=aacc.59具有具有 动作的动作的FA的定义的定义n n具有具有具有具有 动作的动作的动作的动作的FAFA 定义为定义为 M=(K,f,S0,Z),其中,f定义为 f:K()(K).n在
36、在具有具有具有具有 动作的动作的动作的动作的FAFA中中,视为一个视为一个输入符号输入符号,在矩阵在矩阵表示中表示中,也有相应的列也有相应的列。例如，对于前面例如，对于前面具有具有具有具有 动作动作动作动作的的FAFA，相应的状态转换矩阵如，相应的状态转换矩阵如P63P63表表3-23-2所示。所示。n同理可以定义同理可以定义f:K*(K).f(S,x)是由这样是由这样的状态的状态q组成组成,存在从存在从S到到q的路径的路径,该路径上矢线的该路径上矢线的标记组成的符号串恰好为标记组成的符号串恰好为x,标记中可以包含若干标记中可以包含若干个个。60状态S的-闭包：-CLOSURE(S)n状态S的
37、-闭包闭包：记为-CLOSURE(S),它是从S出发经过若干标记为的矢线所能达到的全部状态之集，其归纳定义如下：(1)S-CLOSURE(S);(2)设Sj-CLOSURE(S),且Sj Sk,则Sk-CLOSURE(S);(3)重复使用规则（2）所得的集合为-CLOSURE(S).n-CLOSURE还可定义在状态集上，设QK，则61-CLOSURE示例n例如例如，对于右图的NFA，-CLOSURE(0)=0,1,2,3；-CLOSURE(1)=1；-CLOSURE(2)=2,3；-CLOSURE(3)=3.0 01 12 23 3 a ab bb bc c623.3.5具有具有 动作的动作的
38、NFA的确定化的确定化n为具有为具有 动作的动作的NFA M=(K,f,S0,Z)构造相应的构造相应的DFA M=(K,f,q0,Z)n基本思路：从基本思路：从M的初始状态的初始状态S0出发，仅经过任意条出发，仅经过任意条矢线所能到达的状态集合作为矢线所能到达的状态集合作为M的初态的初态q0；然后从；然后从q0出发，将对输入符号出发，将对输入符号a进行状态转移所能到达进行状态转移所能到达的状态（包括转移后再经过的状态（包括转移后再经过 矢线所能到达的状态）矢线所能到达的状态）所组成的集合作为所组成的集合作为M的状态，如此反复，直到无新的状态，如此反复，直到无新状态产生为止。状态产生为止。67构
39、造构造K,f和和Z的递归过程的递归过程1.令令 K=-CLOSURE(S0);f=;2.对对K中尚未被标记的状态中尚未被标记的状态qi=Si1,Si2,Sim:(1)标记标记qi;(2)对于每个对于每个a,令令Ta=f(Si1,Si2,Sim,a);对对a转转移移 令令 qj=-CLOSURE(Ta);进行进行 矢线转矢线转移移(3)若若qj K,则令则令K=K qj;(4)令令f=f f(qi,a)=qj;3.重复重复2.,直到直到K中无未标记的状态中无未标记的状态;4.令令Z=qj|qj Z (这里把这里把qj 视为集合视为集合)68确定化具有确定化具有 动作的动作的NFANFA的例子的例
40、子例例3.4 考虑右图具有考虑右图具有 动作的动作的NFA1.q0=-CLOSURE(0)=0,1,2,3=K;2.q0未标记未标记,故故 (1)标记标记q0;0 01 12 23 3 a ab bb bc c(2)f(q0,a)=-CLOSURE(f(0,1,2,3,a)=-CLOSURE(0)=q0;f(q0,b)=-CLOSURE(f(0,1,2,3,b)=-CLOSURE(1,3)=1,3=q1=K;f(q0,c)=-CLOSURE(f(0,1,2,3,c)=-CLOSURE(2)=2,3=q2=K;69确定化具有确定化具有 动作的动作的NFANFA的例子的例子(续续)3.K=q0,q
41、1,q2,q1,q2 没有标记，没有标记，(1)标记标记q1;(2)f(q1,a)=-CLOSURE(f(1,3,a)=f(q1,b)=q1;f(q1,c)=;4.q2 没标记没标记,(1)标记标记q2;(2)f(q2,a)=-CLOSURE(f(2,3,a)=；f(q2,b)=;f(q2,c)=q2;K不再增大，且所有的状态都已被标记，不再增大，且所有的状态都已被标记，Z=q0,q1,q2，最后的最后的DFA M 如下所示：如下所示：q1q0q2abbcc0 01 12 23 3 a ab bb bc c703.3.6 DFA状态数的最小化n对于一对于一DFA来说来说,其状态数可能并不是最小
42、的其状态数可能并不是最小的.原因是原因是DFA中有些状态是中有些状态是“等价等价”的的.为得到高效率的为得到高效率的DFA,需需将这些将这些“等价等价”状态合并状态合并,这就是这就是DFA的最小化的最小化.nDFA M的最小化的最小化:构造等价的构造等价的DFA MDFA M其状态数达到最其状态数达到最小小.n可区分状态可区分状态:设设s,t K,s,t由某由某w*所区分所区分 iff (f(s,w)Z f(t,w)Z )(f(s,w)Z f(t,w)Z)若若 w*,f(s,w)Z f(t,w)Z,则则 s与与 t不可区分，不可区分，称二者等价。称二者等价。n确定了等价状态，就可以对其进行合并
43、。确定了等价状态，就可以对其进行合并。72DFA最小化算法n基本思想:将M的状态集K逐步地进行划分,以期将K划分为满足等价关系的等价类：使得在同一类中的状态不可区分;在不同类中的状态可区分.算法如下:1.先将状态集K按终态和非终态划分为两个子集Z Z和K-K-Z Z,显然分属于这两个集合的状态是可(被)区分的.记=Z,K-Z.=Z,K-Z.2.设当前的划分 中已含有mm个子集:=I=I1 1,I,I2 2,I,Imm,其中,属于不同子集I Ii i和I Ij j(ij)的状态是可区分的,而属于同一子集I Ii i中的状态是待区分的.现对每个子集I Ii i=SSi i1 1,S,Si i2 2
44、,S,Si in n 中的各状态S Si ir r(S(Si ir r K,1K,1 r r n)n)进行考查,看其是否可区分.73DFA最小化算法(续)对于S Si ip p,S,Si iq q I Ii i,若存在a a,使得f(Sf(Si ip p,a)=S,a)=Su u I Ij j,f(Sf(Si iq q,a)=S,a)=Sv v I Ik k（即经过a a转换后落在不同的等价类中），则根据 S Su u和S Sv v被某个w w所区分可知,S Si ip p 和S Si iq q 可被awaw 区分:f(Sf(Si ip p,aw)=f(S,aw)=f(Su u,w),w)，而
45、f(Sf(Si iq q,aw)=f(S,aw)=f(Sv v,w),w)，且且S Su u与S Sv v可区分.将I Ii i细分,使其落入不同的更小的子集中.得到新划分 new.new.（细分I Ii i的方法见下页）。3.若 newnew.不等于,则令 =new.new.转2.4.对于最终的，从每个划分块I Ii i中任选一状态为代表，构成KK。若I Ii i中含有初态，则其代表也为初态；若I Ii i Z Z，则I Ii i 的代表 ZZ。删除非代表状态，将引入非代表状态的矢线引向代表状态.74DFA最小化的例子1.=0,1,2,3,4 0,1,2,3a=1 未区分未区分;0,1,2b
46、=2,3,3b=4,所以所以3与与 0,1,2 可区分可区分;=0,1,2,3,42.0,1,2a=1,未区分未区分;0,2b=2,1b=3,1与与0,2可区分可区分;=0,2,1,3,4;3.0,2a=1,0,2b=2 不可区分不可区分,new=.结束结束.0134aaababbb定理定理3.23.2 具有具有最小状态数的最小状态数的DFADFA在同构意义下是唯一的在同构意义下是唯一的.01324aaaaabbbbb接受句子：以abb为后缀的a,b符号串76词法分析程序设计的流程1、各类单词表示成不同的正规文法Gi2、求正规文法Gi对应的正规表达式3、由各个正规表达式构造对应的-NFA4、由
47、各个-NFA组合成一个大的-NFA5、大的-NFA确定化、最小化得到DFA M6、DFA M就是构造词法分析程序的流程图7、按照DFA M编写词法分析程序773.4正规表达式与正规集正规表达式与正规集到目前为止,我们已了解了对于任意三型语言L(G),存在FA M使L(M)=L(G),反之,对于任意的M,存在正规文法G,使L(G)=L(M).这称为描述语言的等价性.本节将引入正规表达式正规表达式的概念,它们可用于描述三型语言的特征,特别是对自动生成词法分析程序而言，它是非常有用的工具。所谓正规表达式正规表达式就是用特定的运算符运算符（*,|等）及运算对象运算对象按某种规则构造的表达式，它可以用于
48、描述给定三型语言的所有句子。正规表达式正规表达式所描述的句子集合(语言)称为正规集正规集。783.4.1正规表达式及正规集的定义n定义 设是一字母表,则上的正规表达式正规表达式(正则表达式,正规式)及其表示的正规集正规集可递归定义如下:(1)是一正规式,相应的正规集为;(2)是一正规式,相应的正规集为;(3)a,a 是一正规式,相应的正规集为a;(4)设r,s是正规式,且它们所表示的正规集为Lr,Ls,则 1.(r)(s)是正规式,相应的正规集为LrLs;2.(r)|(s)是正规式,相应的正规集为Lr Ls;3.(r)*是正规式,相应的正规集为Lr*有限地使用上面的规则(4),所得的表达式均是
49、正规式.79有关正规式及正规集的说明 定义中的括号主要用于规定运算顺序。一般规定优先级从高到低依次为 *,|，则可以省略某些括号,例如(r)(s)*)|(r)可简写为r s*|r。另外，常常可省略不写，进一步写成 rs*|r。80正规式与正规集的例子aa*a,aa,aaa,a|b a,ba|ba*a,b,ba,baa,baaa,(a|b)*abb 任何以abb结尾的a,b符号串(aa|ab|ba|bb)*空串或者任意长度为偶数的a,b符号串(a|b)(a|b)(a|b)*长度大于等于2的a,b符号串81给定正规式给定正规式,它唯一确定一正规集它唯一确定一正规集;反之不真反之不真.即一个正即一个
50、正规集可由多个不同的正规式表示规集可由多个不同的正规式表示.如，如，(a|b)*和(a*b*)*，b(ab)*和(ba)*b表示相同的正规集。表示相同的正规集。若二正规式描述同一正规集若二正规式描述同一正规集,则称二式则称二式等价等价等价等价(相等相等)正规式间的基本等价关系：正规式间的基本等价关系：A1.r|s=s|rA2.r|r=r A3.r|=rA4.(r|s)|t=r|(s|t)A5.(rs)t=r(st)A6.r(s|t)=rs|rt A7.(s|t)r=sr|tr A8.r=r=A9.r=r=rA10.r*=(|r)*=|rr*823.4.2 由正规文法构造相应的正规式由正规文法构