[数学]编译3词法分析zss3.pptVIP

编译原理(第三版) 陈火旺等编著 （2012年9月-12月） 主讲：朱世松 计算机学院 3.3.4 正规文法与有限自动机的等价性 对于正规文法G和有限自动机M，如果L(G)＝L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论： 定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)＝L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。 证明： 1. 对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA） M，使得L(M)＝L(G)。 (1) 设右线性正规文法G=VT, VN, S, P 。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，f?VN。 令M=VN∪{f}, VT, ?, S, {f}，其中状态转换函数?由以下规则定义： (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。 对于右线性正规文法G，在S w的最左推导过程中: 利用A?aB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=?的情形）; 在推导的最后，利用A?a一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=?的情形）。 综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，w?L(G)当且仅当w?L(M)，故L(G)＝L(M)。 (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)。 例: GR(A) ： A→0 | 0B | 1D B→0D | 1C C→0 | 0B | 1D D→0D | 1D 从GR出发构造NFA M = {A, B, C, D, f}, {0, 1}, ??, A, {f}，M的状态转换图如右图所示。 显然 L(M) = L(GR)。 3.3.4 正规文法与有限自动机的等价性 定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)＝L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。 证明2：对每一个DFA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。 设DFA M=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。 对任何w??*，不妨设w=a1…ak，其中ai?? (i=1,…k)。若s0 w，则存在一个最左推导： s0?a1A1?a1a2A2?…?a1…aiAi ?a1…ai+1Ai+1?…?a1…ak 因而，在M中有一条从s0出发依次经过A1，…，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1,…,ak。反之亦然。所以，w?L(GR)当且仅当w?L(M)。 现在考虑s0?F的情形： 因为?(s0, ?)=s0，所以??L(M)。但?不属于上面构造的GR所产生的语言L(GR)。不难发现，L(GR)=L(M)-{?}。 所以，我们在上述GR中添加新的非终结符号s0?，(s0??S)和产生式s0??s0|?，并用s0?代替s0作开始符号。这样修正GR后得到的文法GR?仍是右线性正规文法，并且L(GR?)=L(M)。 (2) 类似于(1)，从DFA M出发可构造左线性正规文法GL，使得L(GL)=