编译3词法分析(zss)3.ppt

1、编译原理(第三版) 陈火旺等编著,（2012年9月-12月） 主讲：朱世松 计算机学院,2,2020/8/6,3.3.4 正规文法与有限自动机的等价性,对于正规文法G和有限自动机M，如果L(G)L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：,3,2020/8/6,定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。,4,2020/8/6,证明： 1. 对每一个右线性正规文法G或左线性正规文法G，都构

2、造一个有限自动机（FA） M，使得L(M)L(G)。 (1) 设右线性正规文法G=。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fVN。 令M=，其中状态转换函数由以下规则定义：,5,2020/8/6,(a) 若对某个AVN及aVT，P中有产生式Aa，则令(A,a)=f (b) 对任意的AVN及aVT，设P中左端为A，右端第一符号为a的所有产生式为： AaA1|aAk （不包括Aa）， 则令(A,a)=A1,Ak。 显然，上述M是一个NFA。,6,2020/8/6,对于右线性正规文法G，在S w的最左推导过程中: 利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到

3、达状态B（包括a=的情形）; 在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=的情形）。 综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wL(G)当且仅当wL(M)，故L(G)L(M)。,7,2020/8/6,(2) 设左线性正规文法G=。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0VN。 令M=，其中状态转换函数由以下规则定义： (a) 若对某个AVN及aVT，若P中有产生式Aa，则令(q0,a)=A (b) 对任意的AVN及aVT，若P中所有

4、右端第一符号为A，第二个符号为a的产生式为： A1Aa, , AkAa， 则令(A,a)=A1,Ak。 与(1)类似，可以证明L(G)L(M)。,8,2020/8/6,GR(A) ： A0 | 0B | 1D B0D | 1C C0 | 0B | 1D D0D | 1D 从GR出发构造NFA M = ，M的状态转换图如右图所示。 显然 L(M) = L(GR)。,例:,A,B,C,D,1,0,0,1,1,1,0,f,0,0,0,9,2020/8/6,3.3.4 正规文法与有限自动机的等价性,定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)L

5、(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。,10,2020/8/6,证明2：对每一个DFA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。 设DFA M= (1) 若s0F，我们令GR=，其中P是由以下规则定义的产生式集合： 对任何a及A,BS，若有(A,a)=B，则： (a) 当BF时，令AaB， (b) 当BF时，令Aa | aB。,11,2020/8/6,对任何w*，不妨设w=a1ak，其中ai (i=1,k)。若s0 w，则存在一个最左推导： s0a1A1a1a2A2a1

6、aiAi a1ai+1Ai+1a1ak 因而，在M中有一条从s0出发依次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,ak。反之亦然。所以，wL(GR)当且仅当wL(M)。,12,2020/8/6,现在考虑s0F的情形： 因为(s0, )=s0，所以L(M)。但不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-。 所以，我们在上述GR中添加新的非终结符号s0，(s0S)和产生式s0s0|，并用s0代替s0作开始符号。这样修正GR后得到的文法GR仍是右线性正规文法，并且L(GR)=L(M)。 (2) 类似于(1)，从DFA M出发可构造左线性正规文

7、法GL，使得L(GL)=L(M)。 最后，由DFA和NFA之间的等价性，结论2得证。,13,2020/8/6,L(M) = 0(10)* GR = ，其中P由下列产生式组成： A0 | 0B | 1D B0D | 1C C0 | 0B | 1D D0D | 1D L(GR) = L(M) = 0(10)*,例3.4 设DFA M = 。M的状态转换图如下图所示。,14,2020/8/6,从NFA M出发构造左线性正规文法GL = ，其中P由下列产生式组成： f0 | C0 CB1 B0 | C0 D1 | C1 | D0 | D1 | B0 易证 L(GL) = L(M)。,从GR构造NFA

8、M，参见 (p53)。M的状态转换图如图3.9(b)所示。,15,2020/8/6,FA,正规集,正规式,DFA,NFA,正规文法,3.3.1,3.3.2 3.3.3,3.3.4,3.3.5,16,2020/8/6,3.3.5 正规式与有限自动机的等价性,定理： 1. 对任何FA M，都存在一个正规式r，使得L(r)=L(M)。 2. 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。 对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号),17,2020/8/6,证明： 1 对上任一NFA M，构造一个上的正规式r，使得L(r)=L(M)。 首先，在M的转换图上加进两个

9、状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。 然后，反复使用下面的一条规则，逐步消去所有结点，直到只剩下X和Y为止：,18,2020/8/6,代之为,代之为,代之为,19,2020/8/6,1,2,5,4,V1(U1|U2)*W1,V1(U1|U2)*W2,V2(U1|U2)*W2,V2(U1|U2)*W1,例：,20,2020/8/6,最后，X到Y的弧上标记的正规式即为所构造的正规式r 显然L(r)=L(M)=L(M),21,2020/8/6,证明2: 对于上的正规式r，构造

10、一个NFA M，使L(M)=L(r)，并且M只有一个终态，而且没有从该终态出发的箭弧。 下面使用关于r中运算符数目的归纳法证明上述结论。 (1) 若r具有零个运算符，则r=或r=或r=a，其中a。此时下图所示的三个有限自动机显然符合上述要求。,22,2020/8/6,(2) 假设结论对于少于k(k1)个运算符的正规式成立。 当r中含有k个运算符时，r有三种情形： 情形1：r=r1|r2，r1,r2中运算符个数少于k。从而，由归纳假设，对ri存在Mi=，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。不妨设S1S2=，在S1 S2中加入两个新状态q0，f0。,23,202

11、0/8/6,令M=，其中定义如下： (a) (q0, )=q1,q2 (b) (q,a)= 1(q,a), 当qS1-f1, a1 (c) (q,a)= 2(q,a), 当qS2-f2, a2 (d) (f1,)=(f2,)=f0。 M的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r),q0,f0,24,2020/8/6,情形2：r=r1r2, 设Mi同情形1(i=1,2)。 令M=，其中定义如下： (a) (q,a)= 1(q,a), 当qS1-f1, a1 (b) (q,a)= 2(q,a), 当qS2, a2 (c) (f1,)=q2 M的状态转换如

12、右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。,25,2020/8/6,情形3：r=r1*。设M1同情形1。 令M=，其中q0, f0S1，定义如下： (a) (q0,)=(f1,)=q1, f0 (b) (q,a)= 1(q, a), 当qS1-f1, a1。 M的状态转换如右图所示。 L(M) = L(M1)* = L(r1)* = L(r) 至此，结论2获证。,q0,f0,26,2020/8/6,1) 构造上的NFA M 使得 L(V)=L(M) 首先，把V表示成,上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。,27,2020/8/6,代之为

13、,代之为,代之为,然后，按下面的三条规则对V进行分裂,28,2020/8/6,逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然L(M)=L(V),29,2020/8/6,(a|b)*(aa|bb)(a|b)*,30,2020/8/6,31,2020/8/6,32,2020/8/6,FA,正规集,正规式,DFA,NFA,正规文法,3.3.1,3.3.2 3.3.3,3.3.4,3.3.5,DFA,3.3.6,33,2020/8/6,3.3.6 确定有限自动机的化简,对DFA M的化简:寻找一个状态数比M少的DFA M，使得L(M)=L(M) 假设s和t为M的两个状态，

14、称s和t等价:如果从状态s出发能读出某个字而停止于终态，那么同样，从t出发也能读出而停止于终态；反之亦然。 两个状态不等价，则称它们是可区别的。,状态等价,状态可区别,34,2020/8/6,对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，从每个子集选出一个代表，同时消去其他状态。,35,2020/8/6,具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分。 假定到某个时候，已含m个子集，记为=I(1)，I(2)，I(m)，检查中的每个子集看是否能进一步划分:

15、 对某个I(i)，令I(i)=s1,s2, ,sk，若存在一个输入字符a使得Ia(i) 不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。,36,2020/8/6,例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行中的两个不同子集，说明有一个字， t1读出后到达终态，而t2读出后不能到达终态，或者反之，那么对于字a ， s1读出a后到达终态，而s2读出a不能到达终态，或者反之，所以s1和s2不等价。,s1,t1,a,s2,t2,a,i,j,37,2020/8/6,则将I(i)分成两半，使得一半含有s1 : I(i1)=s|sI(i)且s经a弧到达t, 且t

16、与t1属于现行中的同一子集 另一半含有s2 : I(i2)=I(i)-I(i1),38,2020/8/6,一般地，对某个a和I(i)，若Ia(i) 落入现行中 N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的同一子集。这样构成新的划分。 重复上述过程，直到所含子集数不再增长。 对于上述最后划分中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的DFA M。 若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。,39,2020/8/6,I(1)=0, 1, 2 I(2)=3, 4, 5, 6,Ia(1) =1, 3 I(11) =0, 2 I(12) =1,I(2)=3, 4, 5, 6,I(11) =0, 2 Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2,I(12) =1 I(2)=3, 4