编译3词法分析_zss_3

1、编译原理编译原理(第三版第三版) 陈火旺等编著22022-3-183.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n对于正规文法对于正规文法G和有限自动机和有限自动机M，如果，如果L(G)L(M)，则称，则称G和和M是是等价等价的。关于的。关于正规文法和有限自动机的等价性，有以正规文法和有限自动机的等价性，有以下结论：下结论：32022-3-18n定理：定理： 1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正或左线性正规文法规文法G，都存在一个有限自动机，都存在一个有限自动机(FA) M，使得，使得L(M)L(G)。 2.对每一个对每一个FA M，都存在一个右线

2、性正规，都存在一个右线性正规文法文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。42022-3-18n证明：证明： 1. 1. 对每一个右线性正规文法对每一个右线性正规文法G或左线性正或左线性正规文法规文法G，都构造一个有限自动机（，都构造一个有限自动机（FA） M，使得，使得L(M)L(G)。(1) 设右线性正规文法设右线性正规文法G=。将。将VN中的每一非终结符号视为状态符号，中的每一非终结符号视为状态符号，并增加一个新的终结状态符号并增加一个新的终结状态符号f，f VN。 令令M=，其中状态，其中状态转换函数转换函数 由以下规则定义：由以下规则定义：

3、52022-3-18(a) 若对某个若对某个A VN及及a VT ，P中有中有产生式产生式Aa，则令，则令 (A,a)=f(b) 对任意的对任意的A VN及及a VT ，设，设P中中左端为左端为A，右端第一符号为，右端第一符号为a的所有产的所有产生式为：生式为：AaA1|aAk （不包括（不包括Aa），）， 则令则令 (A,a)=A1,Ak。 显然显然，上述，上述M是一个是一个NFA。62022-3-18对于右线性正规文法对于右线性正规文法G，在，在S w的最左推的最左推导过程中导过程中:利用利用AaB一次就相当于在一次就相当于在M中从状态中从状态A经经过标记为过标记为a的箭弧到达状态的箭弧到

4、达状态B（包括（包括a= 的情的情形）形）;在推导的最后，利用在推导的最后，利用Aa一次则相当于在一次则相当于在M中从状态中从状态A经过标记为经过标记为a的箭弧到达终结状态的箭弧到达终结状态f（包括（包括a= 的情形）。的情形）。综上，在正规文法综上，在正规文法G中，中，S w的的充要条件充要条件是：在是：在M中，从状态中，从状态S到状态到状态f有一条通路，有一条通路，其上所有箭弧的标记符号依次连接起来恰好其上所有箭弧的标记符号依次连接起来恰好等于等于w，这就是说，这就是说，w L(G)当且仅当当且仅当w L(M)，故，故L(G)L(M)。+ + +72022-3-18(2) 设左线性正规文法

5、设左线性正规文法G=。将。将VN中的每一符号视为状态符号，并增加一个初中的每一符号视为状态符号，并增加一个初始状态符号始状态符号q0，q0 VN。 令令M=，其中状态转，其中状态转换函数换函数 由以下规则定义：由以下规则定义：(a) 若对某个若对某个A VN及及a VT ，若，若P中有产中有产生式生式Aa，则令，则令 (q0,a)=A(b) 对任意的对任意的A VN及及a VT ，若，若P中所有中所有右端第一符号为右端第一符号为A，第二个符号为，第二个符号为a的产的产生式为：生式为：A1Aa, , AkAa， 则令则令 (A,a)=A1,Ak。与与(1)类似，可以证明类似，可以证明L(G)L(

6、M)。82022-3-18nGR(A) ：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1Dn从从GR出发构造出发构造NFA M = ，M的状态转换图的状态转换图如右图所示。如右图所示。n显然显然 L(M) = L(GR)。例例: (理解理解“等价性等价性”)ABCD100,1110f00092022-3-183.3.4 正规文法与有限自动机的等价性（续）正规文法与有限自动机的等价性（续）n定理：定理： 1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正或左线性正规文法规文法G，都存在一个有限自动机，都存在一个有限自动机(FA) M，使得，使得L(M)L

7、(G)。 2.对每一个对每一个FA M，都存在一个右线性正规，都存在一个右线性正规文法文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。102022-3-18证明证明2：对每一个：对每一个DFA M，都存在一个右线，都存在一个右线性正规文法性正规文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。 设设DFA M= (1) 若若s0 F，我们令，我们令GR=，其，其中中P是由以下规则定义的产生式集合：是由以下规则定义的产生式集合：对任何对任何a及及A,B S，若有，若有 (A,a)=B，则：，则： (a) 当当B F时，令时

8、，令AaB， (b) 当当B F时，令时，令Aa | aB。112022-3-18对任何对任何w*，不妨设，不妨设w=a1ak，其中，其中ai (i=1,k)。若。若s0 w，则存在一个最左推导：，则存在一个最左推导： s0a1A1a1a2A2a1aiAia1ai+1Ai+1a1ak因而，在因而，在M中有一条从中有一条从s0出发依次经过出发依次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的到达终态的通路，该通路上所有箭弧的标记依次为标记依次为a1,ak。反之亦然。所以，。反之亦然。所以，w L(GR)当且仅当当且仅当w L(M)。+ +122022-3-18q 现在考虑现在考虑s0 F的

9、情形：的情形： 因为因为 (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出发可构造左线性正规出发可构造左线性正规文法文法GL，使得，

10、使得L(GL)=L(M)。 最后，由最后，由DFA和和NFA之间的等价性，结论之间的等价性，结论2得证。得证。132022-3-18nL(M) = 0(10)*nGR = ，其中，其中P由下列产生由下列产生式组成：式组成：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1DL(GR) = L(M) = 0(10)*例例3.4 设设DFA M = 。M的状态转换图如下图所示。的状态转换图如下图所示。ABCD100,11100142022-3-18n从从NFA M出发构造左线性出发构造左线性正规文法正规文法GL = ，其中，其中P 由由下列产生式组成：下列产生式组成：f

11、0 | C0CB1B0 | C0D1 | C1 | D0 | D1 | B0易证易证 L(GL) = L(M)。从从GR构造构造NFA M，参见，参见 (p53)。M的状态转换图如图的状态转换图如图3.9(b)所示。所示。ABCD100,1110f000152022-3-18FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.43.3.5162022-3-183.3.5 3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性n定理：定理： 1. 对任何对任何FA M，都存在一个正规式，都存在一个正规式r，使，使得得L(r)=L(M)。 2.

12、对任何正规式对任何正规式r，都存在一个，都存在一个FA M，使，使得得L(M)=L(r)。2对转换图概念拓广对转换图概念拓广，令每条弧可用一个，令每条弧可用一个正规式作标记。正规式作标记。(对一类输入符号对一类输入符号)172022-3-18n证明：证明： 1 1 对对 上任一上任一NFA M，构造一个，构造一个 上的正规上的正规式式r，使得，使得L(r)=L(M)。首先，在首先，在M的转换图上加进两个状态的转换图上加进两个状态X和和Y，从从X用用 弧连接到弧连接到M的所有初态结点，从的所有初态结点，从M的所的所有终态结点用有终态结点用 弧连接到弧连接到Y，从而形成一个新，从而形成一个新的的N

13、FA，记为，记为M，它只有一个初态，它只有一个初态X和一个终和一个终态态Y，显然，显然L(M)=L(M)。然后，反复使用下面的一条规则，逐步消去所然后，反复使用下面的一条规则，逐步消去所有结点，直到只剩下有结点，直到只剩下X和和Y为止：为止：182022-3-18代之为代之为ijr1r2kikr1r2代之为代之为ijr1|r2ijr2r1代之为代之为ikr1r2*r2ijr1r3kr2192022-3-1812354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1例：例：202022-3-18q最后，最后，X到到Y

14、的弧上标记的正规式即为的弧上标记的正规式即为所构造的正规式所构造的正规式rq显然显然L(r)=L(M)=L(M)212022-3-18n证明证明2: 对于对于 上的正规式上的正规式r，构造一个，构造一个NFA M，使，使L(M)=L(r)，并且，并且M只有一个终态，只有一个终态，而且没有从该终态出发的箭弧而且没有从该终态出发的箭弧。 下面使用关于下面使用关于r中运算符数目的归纳法证中运算符数目的归纳法证明上述结论。明上述结论。(1) 若若r具有零个运算符，则具有零个运算符，则r= 或或r= 或或r=a，其，其中中a。此时下图所示的三个有限自动机显然。此时下图所示的三个有限自动机显然符合上述要求

15、。符合上述要求。q0q0qfaq0qf222022-3-18(2) 假设结论对于少于假设结论对于少于k(k 1)个运算符的正个运算符的正规式成立。规式成立。 当当r中含有中含有k个运算符时，个运算符时，r有三种情形：有三种情形：l情形情形1：r=r1|r2，r1,r2中运算符个数少于中运算符个数少于k。从而，由归纳假设，对从而，由归纳假设，对ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi没有从终没有从终态出发的箭弧（态出发的箭弧（i=1,2）。不妨设）。不妨设S1S2= ，在在S1 S2中加入两个新状态中加入两个新状态q0，f0。232022-3-18 令令M=，其中其中

16、 定义如下：定义如下：(a) (q0, )=q1,q2(b) (q,a)= 1(q,a), 当当q S1-f1, a1 (c) (q,a)= 2(q,a), 当当q S2-f2, a2 (d) (f1, )= (f2, )=f0。 M的状态转换如右图所示。的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r) q0f0M1q1f1M2q2f2 242022-3-18l情形情形2：r=r1r2, 设设Mi同情形同情形1(i=1,2)。 令令M=，其中，其中 定义如下：定义如下：(a) (q,a)= 1(q,a), 当当q S1-f1, a1 (b) (q,a)=

17、 2(q,a), 当当q S2, a2 (c) (f1, )=q2 M的状态转换如右图所示。的状态转换如右图所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。 M1q1f1M2q2f2252022-3-18l情形情形3：r=r1*。设。设M1同情形同情形1。令令M=，其中，其中q0, f0 S1， 定义如下：定义如下：(a) (q0, )= (f1, )=q1, f0(b) (q,a)= 1(q, a), 当当q S1-f1, a1 。M的状态转换如右图所示。的状态转换如右图所示。L(M) = L(M1)* = L(r1)* = L(r)至此，结论至此，结论2获证。获证

18、。 M1q1f1q0f0 262022-3-181) 1) 构造构造 上的上的NFA M 使得使得 L(V)=L(M)首先，把首先，把V表示成表示成XYV上述证明过程实质上是一个将正规表达式上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。转换为有限自动机的算法。272022-3-18代之为代之为ijV1V2kikV1V2代之为代之为ijV1|V2ijV2V1代之为代之为ikV1*ij kV1然后，按下面的三条规则对然后，按下面的三条规则对V进行分裂进行分裂282022-3-18n逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的上的一个字符或一个字符或 ，最后得

19、到一个，最后得到一个NFA M，显然，显然L(M)=L(V)292022-3-18n(a|b)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY 514236ab ababab302022-3-18IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 5142

20、36ab ababab312022-3-18Iab0121322153344655656340123546aabbbabaababab322022-3-18FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.6332022-3-183.3.6 3.3.6 确定有限自动机的化简确定有限自动机的化简n对对DFA M的化简的化简:寻找一个状态数比寻找一个状态数比M少少的的DFA M，使得，使得L(M)=L(M)n假设假设s和和t为为M的两个状态，称的两个状态，称s和和t等价等价:如果从状态如果从状态s出发能读出某个字出发能读出某个字

21、 而停止而停止于终态，那么同样，从于终态，那么同样，从t出发也能读出出发也能读出 而停止于终态；反之亦然。而停止于终态；反之亦然。n两个状态不等价，则称它们是两个状态不等价，则称它们是可区别可区别的。的。状态等价状态等价状态可区别状态可区别342022-3-18n对一个对一个DFA M最少化的基本思想最少化的基本思想: 把把M M的状态集划分为一些的状态集划分为一些不相交不相交的子的子集，使得任何两个不同子集的状态是集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是的，而同一子集的任何两个状态是等价的。最后，从每个子集选出一个代的。最后，从每个子集选出一个代表，同时消去其他状

22、态。表，同时消去其他状态。352022-3-18n具体做法具体做法: 对对M的状态集进行划分的状态集进行划分首先，把首先，把S划分为终态和非终态两个子集，划分为终态和非终态两个子集，形成基本划分形成基本划分 。 假定到某个时候，假定到某个时候， 已含已含m个子集，记为个子集，记为 =I(1)，I(2)，I(m)，检查，检查 中的每个子中的每个子集看是否能进一步划分集看是否能进一步划分:n对某个对某个I(i)，令，令I(i)=s1,s2, ,sk，若存在，若存在一个输入字符一个输入字符a使得使得Ia(i) 不会包含在现行不会包含在现行 的某个子集的某个子集I(j)中，则至少应把中，则至少应把I(

23、i)分为两分为两个部分。个部分。362022-3-18n例如，假定状态例如，假定状态s1和和s2经经a弧分别到达弧分别到达t1和和t2，而，而t1和和t2属于现行属于现行 中的两个不同子集，中的两个不同子集，说明有一个字说明有一个字 ， t1读出读出 后到达终态，而后到达终态，而t2读出读出 后不能到达终态，或者反之，那后不能到达终态，或者反之，那么对于字么对于字a ， s1读出读出a 后到达终态，而后到达终态，而s2读出读出a 不能到达终态，或者反之，所以不能到达终态，或者反之，所以s1和和s2不等价。不等价。s1t1as2t2a i j372022-3-18n则将则将I(i)分成两半，使得

24、一半含有分成两半，使得一半含有s1 : I(i1)=s|s I(i)且且s经经a弧到达弧到达t, 且且t与与t1属于现行属于现行 中的同一子集中的同一子集 另一半含有另一半含有s2 : I(i2)=I(i)-I(i1)s1t1as2t2a i j382022-3-18n一般地，对某个一般地，对某个a和和I(i)，若，若Ia(i) 落入现行落入现行 中中 N个不同子集，则应把个不同子集，则应把I(i)划分成划分成N个不相交个不相交的组，使得每个组的组，使得每个组J的的Ja都落入的都落入的 同一子同一子集。这样构成新的划分。集。这样构成新的划分。n重复上述过程，直到重复上述过程，直到 所含子集数不再增长。所含子集数不再增长。n对于上述最后划分对于上述最后划分 中的每个子集，我们选中的每个子集，我们选取每个子集取每个子集I中的一个状态代表其他状态，中的一个状态代表其他状态，则可得到化简后的则可得到化简后的D