chapter3lexicalanalyzer(编辑修改稿)

chapter3lexicalanalyzer(编辑修改稿)内容摘要：

b)=C 23  The deduction can also be written as M (A, abab) = M (M (A, a) , bab) = M (B, bab) = M (M (B, b), ab) = M (C, ab) = M (M (C, a) , b) = M (B, b) = C 24  Example There is FA=（｛ W, S, P｝ ,｛ t, x, ε｝ , M, W,｛ P｝） M: M (W,ε) = W M (W,t) = S M (S,x) = P The question is to judge if “tx” is recognized by the FA. The deduction is as follows, M (W,ε) = W M (W, tx) = M( M (W , t) , x) M (S, x) = P Because P∈ Z, we can say “tx” is recognized by the FA. 25  The algorithm of DFA There is an input string “x”, the start symbol is S0, S is state set, G is set of leaving state. 26  FA Program There is an FA=（ {0,1,2,3}, {a,b}, M, 0, {3}） M： M(0,a)=1 M(0,b)=2 M(1,a)=3 M(1,b)=2 M(2,a)=1 M(2,b)=3 M(3,a)=3 M(3,b)=3 The question is to judge if the string “abbb” would be identified or accepted by the FA? The FA program is as follows. 27 28 29 30  Result of the FA program is shown by . 31  Nondeterministic Finite Automata (NFA) There is a grammar G: U::=Wa and V::=Wa The transition diagram of G is 32  The FA of G: M (W, a) = U and M (W, a) = V Or M (W, a) = ｛ U, V｝ So the statesymbol pair is not unique, the FA is n a me d as N o nd e t e r min is t ic F in it e Automata(NFA). . 33  The definition of NFA is (K, VT, M, S, Z) While K is state set。 VT is a set of input symbols。 S is start state, S∈ K。 Z is leaving state which belongs to nonempty set, Z K。 M is statesymbol pairs K VT* M (W, ε) = ｛ W｝ M (W, tx) = M｛ P1, x｝ ∪ M｛ P2, x｝∪ …M ｛ Pn, x｝ While, P∈ M（ W, t）； t∈ VT； x∈ VT. 204。 34  Example Regular grammar G［ Z］ : P: Z::=U1|V0|Z0|Z1 U::=Q1|1 V::=Q0|0 Z::=Q1 Q::=0 The transition state diagram of example is shown by Figure , Z is leaving state, S is start state. . 35  From the transition state of example , we know that statesymbol pairs of M is not unique, so the G［ Z］ can be described by NFA. . NFA=(｛ S, Q, U, V, Z｝ ,｛ 0, 1｝ , M,｛ S｝ ,｛ Z｝ ) While M： M (S, 0) =｛ V, Q｝ M (S, 1) =｛ U｝ M (U, 0) =Φ M (U, 1) =｛ Z｝ M (V, 0) =｛ Z｝ M (V, 1) =Φ M (Q, 0) =｛ V｝ M (Q, 1) ={U,Z} M (Z, 0) =｛ Z｝ M (Z, 1) =｛ Z｝ 36 37  The state Φ is empty state that doesn’t include any state. The deduction of string “0111” begins from the start state S, the statesymbol pair M is M (S, 0111) = M (V, 111)∪ M (Q, 111) =Φ∪ M (U, 11) ∪ M (Z, 11) = M (Z, 1) ∪ M (Z, 1) = M (Z, 1) =｛ Z｝ So M (S, 0111) =｛ Z｝ , state Z is leaving state, namely, string “0111” can be accepted by the NFA. You can try string “101” by yourselves to judge if it will be accepted by the NFA. 38  Constructing DFA from NFA Any NFA: N=(K, VT, M, S, F) can has an correspond DFA: N’=(K’, VT, M’, S’, F’). While K’ is the set ing from the subset of K. . [Q1,Q2,… ,Qm] is the elements of K’, Qi∈ K。 M’([R1 ,R2 ,… , R i] , T ) = [Q1 ,Q2 ,… . Q j] , [R1 ,R2 , … , R i ] is t h e e l e m e n t s of K,T∈ VT。 S’=[S1, S2, … , Sn]。 F’={[Sj, Sk, … , Sl]|[Sj, Sk, … , Sl]∈ K’, [Sj, Sk, … , Sl]∩F≠φ }。 L(N)=L(N’). , 39  Example Grammar[Z]:。