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

文档介绍：编译原理(第三版)陈火旺等编著(2012年9月-12月)主讲:朱世松计算机学院*,如果L(G)=L(M),则称G和M是等价的。关于正规文法和有限自动机的等价性,有以下结论:Date2定理:,都存在一个有限自动机(FA)M,使得L(M)=L(G)。,都存在一个右线性正规文法GR和左线性正规文法GL,使得L(M)=L(GR)=L(GL)。Date3证明:,都构造一个有限自动机(FA)M,使得L(M)=L(G)。(1)设右线性正规文法G=<VT,VN,S,P>。将VN中的每一非终结符号视为状态符号,并增加一个新的终结状态符号f,fVN。令M=<VN∪{f},VT,,S,{f}>,其中状态转换函数由以下规则定义:Date4(a)若对某个AVN及aVT∪{},P中有产生式A→a,则令(A,a)=f(b)对任意的AVN及aVT∪{},设P中左端为A,右端第一符号为a的所有产生式为:A→aA1|…|aAk(不包括A→a),则令(A,a)={A1,…,Ak}。显然,上述M是一个NFA。Date5对于右线性正规文法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)。+Þ+ÞDate6(2)设左线性正规文法G=<VT,VN,S,P>。将VN中的每一符号视为状态符号,并增加一个初始状态符号q0,q0VN。令M=<VN∪{q0},VT,,q0,{S}>,其中状态转换函数由以下规则定义:(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)。Date7GR(A):A→0|0B|1D B→0D|1CC→0|0B|1D D→0D|1D从GR出发构造NFAM=<{A,B,C,D,f},{0,1},,A,{f}>,M的状态转换图如右图所示。显然L(M)=L(GR)。例:ABCD100,:,都存在一个有限自动机(FA)M,使得L(M)=L(G)。,都存在一个右线性正规文法GR和左线性正规文法GL,使得L(M)=L(GR)=L(GL)。Date9证明2:对每一个DFAM,都存在一个右线性正规文法GR和左线性正规文法GL,使得L(M)=L(GR)=L(GL)。设DFAM=<S,,,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|aB。Date10