编译3词法分析(zss)3

《编译3词法分析(zss)3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、一个有限自动机（FA）M，使得L(M)＝L(G)。(1)设右线性正规文法G=。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fVN。令M=，其中状态转换函数由以下规则定义：6/17/20214(a)若对某个AVN及aVT∪{}，P中有产生式A→a，则令(A,a)=f(b)对任意的AVN及aVT∪{}，设P中左端为A，右端第一符号为a的所有产生式为：A→aA1

3、…

4、aAk（不包括A→a），则令(A,a)={A1,…,Ak}。显然，上述M是一个NFA。

5、6/17/20215对于右线性正规文法G，在Sw的最左推导过程中:利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=的情形）;在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=的情形）。综上，在正规文法G中，Sw的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wL(G)当且仅当wL(M)，故L(G)＝L(M)。+Þ+Þ6/17/20216(2)设左线性正规文法G=。将VN中的每一符号视为状态符号

6、，并增加一个初始状态符号q0，q0VN。令M=，其中状态转换函数由以下规则定义：(a)若对某个AVN及aVT∪{}，若P中有产生式Aa，则令(q0,a)=A(b)对任意的AVN及aVT∪{}，若P中所有右端第一符号为A，第二个符号为a的产生式为：A1→Aa,…,Ak→Aa，则令(A,a)={A1,…,Ak}。与(1)类似，可以证明L(G)＝L(M)。6/17/20217GR(A)：A→0

7、0B

8、1DB→0D

9、1CC→0

10、0B

11、1DD→0D

12、1D从GR出发构造NFAM=<{A,B,C,D

13、,f},{0,1},,A,{f}>，M的状态转换图如右图所示。显然L(M)=L(GR)。例:ABCD100,1110f0006/17/202183.3.4正规文法与有限自动机的等价性定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)＝L(G)。2.对每一个FAM，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。6/17/20219证明2：对每一个DFAM，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。设DFAM=

14、,,,s0,F>(1)若s0F，我们令GR=<,S,s0,P>，其中P是由以下规则定义的产生式集合：对任何a及A,BS，若有(A,a)=B，则：(a)当BF时，令A→aB，(b)当BF时，令A→a

15、aB。6/17/202110对任何w*，不妨设w=a1…ak，其中ai(i=1,…k)。若s0w，则存在一个最左推导：s0a1A1a1a2A2…a1…aiAia1…ai+1Ai+1…a1…ak因而，在M中有一条从s0出发依次经过A1，…，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,…,ak。反之亦然

16、。所以，wL(GR)当且仅当wL(M)。+Þ6/17/202111现在考虑s0F的情形：因为(s0,)=s0，所以L(M)。但不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-{}。所以，我们在上述GR中添加新的非终结符号s0，(s0S)和产生式s0s0

17、，并用s0代替s0作开始符号。这样修正GR后得到的文法GR仍是右线性正规文法，并且L(GR)=L(M)。(2)类似于(1)，从DFAM出发可构造左线性正规文法GL，使得L(GL)=L(M)。最后，由DFA和NFA之间的等价性，结论2得证

18、。6/17/202112L(M)=0(10)*GR=<{0,1},{A,B,C,D},A,P>，其中P由下列产生式组成：A