编译原理ppt课件.ppt

《编译原理ppt课件.ppt》由会员分享，可在线阅读，更多相关《编译原理ppt课件.ppt（52页珍藏版）》请在三一办公上搜索。

1、2007年9月,湖北大学数计学院计科系,第3章 有穷自动机,（自动机是一种能进行运算并能实现自我控制的装置，是描述符号串处理的强有力的工具。本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式和有穷自动机之间的相互关系）,Compiler,2007年9月,湖北大学数计学院计科系,3.1 有穷自动机的形式定义3.2 NDFA到DFA的转换3.3 正规文法与有穷自动机3.4 正规表达式与FA3.5 DFA在计算机中的表示3.6 小结,2007年9月,湖北大学数计学院计科系,3.1 有穷自动机的形式定义,一个确定的有穷自动机（DFA）M是一个五元式:M=(Q , ，t ,q0 , F),其

2、中:1. Q 有穷状态集2. 输入字母表3. t 映射函数(也称状态转换函数) QQ t(q , a)=q , q , q Q, a4. q0 初始状态 q0 Q5. F终止状态集 FQ,2007年9月,湖北大学数计学院计科系,例如: M:（0,1,2,3,a,b,t，0，3） t（0，a）=1 t（0，b）=2 t（1，a）=3 t（1，b）=2 t（2，a）=1 t（2，b）=3 t（3，a）=3 t（3，b）=3,所谓确定的状态机，其确定性都表现在状态转移函数是单值函数！,2007年9月,湖北大学数计学院计科系,一个DFA也可以用一状态转换图表示：,2007年9月,湖北大学数计学院计科系

3、,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上能有弧的标记符号连接成符号串，则称为DFA M（接受）识别。,DFA M所接受的语言为：L(M)=|t(Q0, )=Qn, Qn Z,DFA M所接受的符号串：令=a1a2an，若 t ( t ( t (Q0, a1),a2)），an-1）,an)=Qn,且Qn Z，则可以写成 t (Q0, )= Qn,我们称可为M所接受。,2007年9月,湖北大学数计学院计科系,自动机的等价性 两个有穷自动机A1和A2， 如果L(A1)=L(A2), 则称自动机A1与A2等价。,2007年9月,湖北大学数计学院计科系,非确定有穷自动机(NFA),

4、若t是一个多值函数，且输入可允许为，则有穷自动机是不确定的,即在某个状态下，对于某个输入字符存在多个后继状态.,NFA的形式定义为:,一个非确定的有穷自动机NFA M是一个五元式: NFA M=( Q , , t , Q0 , F )其中 Q有穷状态集 输入符号加上,即自动机的每个结点所射出的弧 可以是中的一个字符或是. Q0初态集 F终态集 t转换函数 Q 2Q (2Q -Q的幂集Q的子集构成的集合）,2007年9月,湖北大学数计学院计科系,NFA M所接受的语言为: L(M)=| t(Q0,)=Q QF,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,3.2

5、 NDFA到DFA的转换,2007年9月,湖北大学数计学院计科系,如果自动机的弧上允许标记，则称此自动机为自动机，记为NDFA或DFA。 自动机的状态转换图中会出现由若干条弧组成的空移环路或空移。, 消除空移环路和空移,2007年9月,湖北大学数计学院计科系,消除空移环路 找到空移环路之后，要消除它只需把空移环路上的所有节点合并成一个节点，并消除它们所有的弧。如果其中的某一个节点是开始状态或终止状态，则将此合并之后的新节点相应设置为开始状态或终止状态。,消除空移 消除某条弧的空移，需要引入若干条新弧来取代原来弧的作用。 假设状态A有一条弧发出到达状态B，则在消除空移后，如果B是终止状态，则设置

6、A为终止状态，而如果从开始状态经过一条路径到达状态A，则设置B为开始状态。,2007年9月,湖北大学数计学院计科系, NDFA确定化,子集法 设NDFA A=(,Q ,t ,Q0,F)是一个非确定的有穷自动机，那么可以通过子集法构造一个和它等价的确定有穷自动机DFA A=(,Q, t, q0, F)。构造方法如下： 输入字母表不变 把NDFA A的每一个状态子集都作为DFA A的一个状态 DFA A的映射定义 t(r1,r2,rm , a) = q = t (r1,a)t (r2,a)t (rm,a) DFA A的开始状态q0s1 , s2 , , sk，其中，siQ0( i =1,2,k)

7、DFA A的终态集为包含原终止状态的子集组成,2007年9月,湖北大学数计学院计科系,造表法 造表法中DFA A的输入字母表 、开始状态q0和终态集F的确定都与子集法的构造方法一致。 状态集Q与映射函数t则是随着造表的过程而动态生成。 首先求出开始状态q0在接受各输入字母后状态变迁的结果，将其填入表中。然后把得到的结果作为新的状态，再求其接受各输入字母后状态变迁的结果，填入表中，如此过程不断重复，直到最后无新结果（状态）出现为止，此时造表结束。,2007年9月,湖北大学数计学院计科系,定义1、集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为：1）若sI，则s-closur

8、e（I）；2）若sI，则从s出发经过任意条弧能够到达的任何 状态都属于-closure（I）。 状态集-closure（I）称为I的-闭包,我们可以通过一例子来说明状态子集的-闭包的构造方法, NDFA的确定化,2007年9月,湖北大学数计学院计科系,例：如图所示的状态图：令I=1，求-closure（I）=？,根据定义：-closure（I）=1，3,2007年9月,湖北大学数计学院计科系,我们同样可以通过一例子来说明上述定义,仍采用前面给定的状态图为例,- J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合.,-Ia是状态子集,其元素为J中的状态,加上从J中每一个状态出发通

9、过弧到达的状态,定义2: 令I是NFA M的状态集的一个子集, a 定义: Ia=-closure(J) 其中J = (s,a),SI,2007年9月,湖北大学数计学院计科系,例：令 I=1 Ia=-closure(J) =-closure(（1，a） =-closure(2，4）=2，4，6,根据定义1，2，可以将上述的M确定化（即可构造出状态的转换矩阵）,2007年9月,湖北大学数计学院计科系,例：有NFA M,a,I=-closure(1)=1,4Ia=-closure(1,a)(4,a) = -closure(2,3） = -closure (2,3) =2,3Ib= -closure

10、(1,b)(4,b) = -closure(） =Ic= -closure(1,c)(4,c) = I=2,3, Ia=2,Ib=4,Ic=3,4,2007年9月,湖北大学数计学院计科系,I Ia Ib Ic,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,2007年9月,湖北大学数计学院计科系,将求得的状态转换矩阵重新编号DFA M状态转换矩阵：,2007年9月,湖北大学数计学院计科系,DFA M的状态图：,0,1,4,2,3,start,1,4,2,3,4,2,a,c,a,b,b,c,3,4,2007年9月,湖北大学数计学院计科系, 消除不可达状态,在自动机中

11、，从开始状态出发没有任何一条路径能达到的状态称为不可达状态。,注：在使用子集法对NDFA进行确定化的过程中，常会产生一些不可达状态，需要在最后将其消除。,2007年9月,湖北大学数计学院计科系, DFA的化简,“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”一个有穷自动机是化简的 它没有多余状态并且它的状态 中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,1)一致性条件：状态s和t必须同时为可接受状态或 不接受状态.2)蔓延性条件：对于所有

12、输入符号,状态s和t必须 转换到等价的状态里.,对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同的后继，则称s，t是等价的。（任何有后继的状态和任何无后继的状态一定不等价）,有穷自动机的状态s和t不等价,称这两个状态是可区别的。,2007年9月,湖北大学数计学院计科系,“分割法”：把一个DFA(不含多余状态)的状态分割成一些 不相关的子集，使得任何不同的两个子集状态 都是可区别的，而同一个子集中的任何状态都 是等价的.,2007年9月,湖北大学数计学院计科系,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,

13、a,b,区号,区号,2007年9月,湖北大学数计学院计科系,区号,区号,2007年9月,湖北大学数计学院计科系,将区号代替状态号得:,2007年9月,湖北大学数计学院计科系,3.3 正规文法与有穷自动机,（1）正则文法G有穷自动机A,令正规文法G的终结符号集作为有穷自动机A的字母表。文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符号作为自动机A的开始状态。在自动机A中增加一个新状态Z作为自动机的终止状态。对于文法G的形如U:=aV的产生式，在自动机A中构造形如t(U,a)=V的映射。对于文法G的形如U:=a的产生式，在自动机A中构造形如t(U,a)=Z的映射。,2007年9

14、月,湖北大学数计学院计科系,例:求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA|,2007年9月,湖北大学数计学院计科系,（2）有穷自动机A 正则文法G,自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。对于自动机的映射t（U,a）=V，构造文法的一条产生式 U:= a V对于自动机的终止状态Z，在正规文法中增加一条产生式 Z:=,2007年9月,湖北大学数计学院计科系,例:给出如图NFA等价的正规文法G,2007年9月,湖北大学数计学院计科系,3.4 正规表达

15、式与FA,正规表达式和正规集合的递归定义,有字母表, 定义在 上的正规表达式和正规集合递归定义如下:1. 和都是 上的正规表达式, 它们所表示的正规集合分别为:和;2. 任何a , a是 上的正规表达式,它所表示的正规集合为:a; 3. 假定U和V都是 上的正则表达式, 它们所表示的正则集合分别记为L(U)和L(V), 那么U|V, UV和U*也都是 上的正则表达式, 它们所表示的正则集合分别为L(U) L(V)、 L(U) L(V)和L(U)*4. 任何 上的正规表达式和正规集合均由1、2和3产生。,2007年9月,湖北大学数计学院计科系,正则表达式中的运算符： | - 或（选择） - 连接

16、 * - 重复 / （） - 括号,运算符的优先级： 先*（闭包）, 后 （连接） , 最后 |（或） 在正则表达式中可以省略.,正则表达式相等 这两个正则表达式表示的语言相等,2007年9月,湖北大学数计学院计科系,例：设 = a,b ,下面是定义在上的正规表达式和正规集合,正规表达式 正规集 ba* b , ba , baa , baaa , a(a|b)* a , aa , ab , aaa , aab , aba , abb , (a|b)*(aa|bb)(a|b)* aa , bb , aaa , baa , abaaba , abbaab , ,2007年9月,湖北大学数计学院计科

17、系,正则表达式的性质： 设e1, e2和e3均是某字母表上的正则表达式, 则有: 单位正则表达式: e = e = e 交换律: e1 | e2 = e2 | e1结合律: e1|(e2|e3) = (e1|e2)|e3 e1(e2e3) = (e1e2)e3分配律: e1(e2|e3) = e1e2|e1e3 (e1|e2)e3 = e1e3|e2e3 此外: r* = (r|)* r* =r* (r|s)* = (r*s*)*,2007年9月,湖北大学数计学院计科系,（1）正则表达式 NDFA,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,2007年9月,

18、湖北大学数计学院计科系,（2） NDFA 正则表达式,在转换之前，先对NDFA进行扩充，允许状态转换图中弧上可以是正规表达式。具体操作如下： 在NDFA的状态转换图中，新设置一个唯一的开始状态S和一个唯一的终结状态Z。然后，从开始状态S到原开始状态连接弧，再从原终止状态到Z状态也连接弧。修改后的NDFA，显然和原NDFA等价。接着，对新NDFA按照如下替换规则进行替换，直到状态转换图中只剩下状态S和Z为止。当状态转换图中只有状态S和Z时，在S到Z的弧上标记的正规表达式e便是所求结果。,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学

19、院计科系,(2)消除M中的所有结点,2007年9月,湖北大学数计学院计科系,（3）正规文法正规表达式,在转换之前，先将正规文法拓广，其产生式可以是 U:=V 或 U:= 其中U、VVN , VT*转换规则为：产生式U:=V , V:= , U、VVN , 、 VT* ，转换为正规表达式U=产生式U:=U|，转换为U=*产生式U:=|，转换为U=|,2007年9月,湖北大学数计学院计科系,例:有文法Gs SaA|a, AaA|dA|a|d,于是: S=aA|a A=(aA|dA)|(a|d)A=(a|d)A|(a|d),由规则: A=(a|d)*(a|d) 代入:S=a(a|d)*(a|d)|a

20、 于是:S=a(a|d)*(a|d)|),2007年9月,湖北大学数计学院计科系,（4）正规表达式正规文法,算法:1)对任何正规式r,选择一个非终结符S作为识别符号. 并产生产生式 Sr2)若x,y是正规式,对形为Axy的产生式,重写为 AxB By,其中B为新的非终结符,BVN 同样: 对于 Ax*y AxA Ay Ax|y Ax Ay,例:将R=a(a|d)*转换成相应的正规文法,解:1) Sa(a|d)*,2) SaA A(a|d)*,SaA A(a|d)A A,SaA AaA|dA A,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,3.5 DFA在计算机中的表示,矩阵表示法表结构,2007年9月,湖北大学数计学院计科系,本章重点：正规表达式到最简DFA的转换,作业：P58-59 3.2 3.3 3.4 3.7 3.9 3.10,