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

编译原理(第三版) 陈火旺等编著
(2012年9月-12月)
主讲:朱世松
计算机学院
11/13/2018
1
正规文法与有限自动机的等价性
对于正规文法G和有限自动机M,如果L(G)=L(M),则称G和M是等价的。关于正规文法和有限自动机的等价性,有以下结论:
11/13/2018
2
定理:
,都存在一个有限自动机(FA) M,使得L(M)=L(G)。
M,都存在一个右线性正规文法GR和左线性正规文法GL,使得L(M)=L(GR)=L(GL)。
11/13/2018
3
证明:
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}>,其中状态转换函数由以下规则定义:
11/13/2018
4
(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。
11/13/2018
5
对于右线性正规文法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)。
+
Þ
+
Þ
11/13/2018
6
(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)。
11/13/2018
7
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)。
例:
A
B
C
D
1
0
0,1
1
1
0
f
0
0
0
11/13/2018
8
正规文法与有限自动机的等价性
定理:
,都存在一个有限自动机(FA) M,使得L(M)=L(G)。
M,都存在一个右线性正规文法GR和左线性正规文法GL,使得L(M)=L(GR)=L(GL)。
11/13/2018
9
证明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。
11/13/2018
10