·在状态转换图中，从某一初态结点到某一终态结点序列称为“路”。 6 字母或数字 (可识别所有标识符) 2.有穷自动机 单值函数唯一 ·定义：(DFA)M:M=(k,∑，Es,z)P52 例1：M={0,12,3,a,b,￡0，{3}) f.f(0.a)=1,f(0,b)=2,f(l,a)=3,f(1,b)=2 f(2,a)=1,f(2,b)=3 f(3.a)=3 f(3.b)=3 其矩阵表示： 、符号 状态 a 6 0 1 其转换图： 或b a. 例如：串abb,首先f0,a1一f〔1，b)=2一f2,b)=3∴该串是可识别的单词 串ab首先f0,a)=1→f(1,b)=2,终态是3∴.不是单词
在状态转换图中，从某一初态结点到某一终态结点序列称为“路”。 例： 例： = （可识别所有标识符） 2.有穷自动机 单值函数唯一 定义：（DFA）M: M=(k,, f, s, z) P52. ▲ ▲ 例 1：MD =( {0,1,2,3}, {a,b}, f, 0, {3} ) f: f(0,a)=1, f(0,b)=2, f(1,a)=3, f(1,b)=2 f(2,a)=1, f(2,b)=3 f(3,a)=3 f(3,b)=3 其矩阵表示： a b 0 1 2 1 3 2 2 1 3 3 3 3 终态 其转换图： a a a 或 b a,b a b 例如：串 abb, 首先 f(0,a)=1 → f(1,b)=2 → f(2,b)=3 该串是可识别的单词 串 ab 首先 f(0,a)=1→ f(1,b)=2 终态是 3不是单词 0 1 3 a a a b 2 b 0 字 母 1 字母或数字 符号 状态 0 1 3 2 b b
上例可识别：(ab)*(aaibb)(ab) 例2：0→回a⑥ L(Mo)=(c.a.aa,aaa.) 0 ② L(Mo-{a开头的a,b符号串； o L(MoF{e,任意长度的a,b符号串) 3.不确定有穷自动机 非单值函数一个初态集 (M-5 例：S=0,1,23}=4a,b}S0=01Z=3y ff0,a=1,3}f0,b={2,3}f1,aFof1,bF{1,3} f2,a=2,3}f2,b}=p f(3a)=o f3.b)=o 其矩阵表示： 符号 状态 a 6 0 1,3}2,3} 1,3} 2,3}9 3 转换图： 4.非确定有限自动机的确定化(NFA→DFA)P55.1.∑闭包2.a低转换 DFA是NFA的特例，对每个(NFA)M一定存在一个(DFA)M,使得L(M=L(M)与 某一NFA等价的DFA不唯一
上例可识别：（ab）* (aabb) (ab)*a 例 2： a L(MD)={ε,a,aa,aaa,.} ② a a b L(MD)={a 开头的 a,b 符号串} a b L(MD)={ε,任意长度 的 a,b 符号串｝ 3.不确定有穷自动机 非单值函数 一个初态集 ●定义：（NFA)M: M=(k,∑ , .f, s, z), . ▲ ▲ 例：S={0,1,2,3} ∑={a,b} S0={0} Z={3} f: f(0,a)={1,3} f(0,b)={2,3} f(1,a)= φ f(1,b)={1,3} f(2,a)={2,3} f{2,b}= φ f(3,a)= φ f(3,b)= φ 其矩阵表示： 符号 a b 0 {1,3} {2,3} 1 φ {1,3} 2 {2,3} φ 3 φ φ 转换图： b a b a,b a a 4. 非确定有限自动机的确定化（NFA→DFA）P55. 1.∑ 闭包 2.a 低转换 DFA 是 NFA 的特例，对每个（NFA）M 一定存在一个（DFA）M', 使得 L(M)=L(M')与 某一 NFA 等价的 DFA 不唯一 0 1 0 1 0 状态 0 1 3 2 b
例P564.8 例L. 0 先判断此为NFA,再NFA一→DFA确定化（注意：各列所有状态集都在第一列中出 现：则状态全部求完，即不再增大) 符号 0 状态 ①S ②[B ②B] ③[B.Z @[S] DFA ©[B,Z B,Z] o[s] 0,1 例2： 0.1 B 1 NFA 符号 状态 0 1 [A] [A] ②[A,B] ②[A,B O[A] [A.B.C] [A,B,C] ④[A,CJ ③[，B,C] )同为终态：所有会有原来NFA终态 ④[A,C ④[A,C] [A,B.C] 的集合在DFA中均为终态 ·FA(自动机)FNFA+DFA 5.确定有穷自动机的简化（最小化） ·没有多余状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。 一致性条件 ·状态中没有两个是互相等价的< 蔓延性条件 例P584.9
例 P56 4.8 0 例 1. 0 0 1 先判断此为 NFA,再 NFA→DFA 确定化（注意：各列所有状态集都在第一列中出 现；则状态全部求完，即不再增大） 符号 0 状态 0 1 0 [S] ②[B] φ 1 0 ②[B] [S] 1 DFA [B,Z] [B,Z] [S] 0,1 例 2： 0,1 1 1 NFA 符号 状态 0 1 [A] [A] ②[A,B] ②[A,B] [A] [A,B,C] [A,B,C] ④[A,C] [A,B,C] 同为终态 所有会有原来 NFA 终态 ④[A,C] ④[A,C] [A,B,C] 的集合在 DFA 中均为终态 ● FA(自动机)= NFA+DFA 5.确定有穷自动机的简化（最小化） ● 没有多余状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。 一致性条件 ● 状态中没有两个是互相等价的 蔓延性条件 a 例 P58 4.9 例 1. a a b b a a b a b b S B Z [B,Z] 1 2 3 A B C 0 1 3 5 6 4 2 b a b
①DFA ②S=3,4,5,6}5={0,1,2} S,中的四个状态经过a,b到达状态仍在S中，不再划分 ④S,中三个状态经过a,不在一个集合，S,划分为S={1,Sm(0,2} ⑤Sz再经过a,b,不在个集合∴.Sa划分为5a={0l,5m={2} ⑥把S,中四个等价状态合并 a.b 3】 b (简化后) 例2 S=1.2:S2=13} 经过ab都到同一集合∴合并 (简化后) B A b@】 © s=cdegy seAbe S1经过aC,D.G到中， ∴Sm=C,D,GS={E S中经过b,S={D,G,S={C}合并D,G S,经过a,S={A,B,S={F Sa经过b,Sm=(Ah,Sae(Bl @ (简化后)
DFA ② S1 ={3,4,5,6} S2={0,1,2} S1中的四个状态经过 a,b 到达状态仍在 S1中，∴不再划分 ④S2中三个状态经过 a,不在一个集合，∴S2划分为 S21=｛1｝，S22=｛0，2｝ ⑤S22再经过 a,b,不在一个集合∴S22划分为 S221={0},S222={2} ⑥把 S1中四个等价状态合并 a a a,b b b a b (简化后) 例 2. a a a S1={1,2} S2={3} b b 经过 a,b 都到同一集合∴合并 a b a (简化后) 例 3. a a b b a b b b a b S1={C,D,E,G} S2={A,B,F} S1经过 a,C,D,G 到Ф，E a G ∴S11={C,D,G} S12={E} S11中经过 b,S111={D,G},S112={C} ∴合并 D,G S2经过 a,S21={A,B},S22={F} b a S21经过 b,S211={A},S212={B} a b a b a b b (简化后) 0 1 3 2 1 2 3 1 3 A B C D F E G A B D F C E
列4 ①NFA(两个初态，Q经过1到达Q,Z) ② 人、符号 0 1 状 A[Q.P] B[P] cQ,2] B[P] D[Z] cQ.Z B(P] E[Q.Z.P] D(Z] B[P] B[P] E[Q.Z,P] B[P] E[Q.Z.P] DFA @ ④S={,B}S,={C,D,E S,=(C,E}S=(D) Su=(A)Si=(B) 0 B (简化后)
例 4. 1 1 0,1 0 1 NFA(两个初态，Q 经过 1 到达 Q，Z) ② 符号 0 1 状态 A[Q,P] B[P] C[Q,Z] B[P] Ф D[Z] C[Q,Z] B[P] E[Q,Z,P] D[Z] B[P] B[P] E[Q,Z,P] B[P] E[Q,Z,P] 0 1 0 1 0,1 0 1 DFA 1 ④ S1={A,B} S2={C,D,E} S21={C,E} S22={D} S11={A} S12={B} ⑤ 0 1 0 1 0,1 1 (简化后) Q P Z A B C D E A B C D
$3.4正则表达式正则文法与有限自动机的相互转换 1.FA一正则表达式P59例4.10 例： 0 b abG (ob"(olbXab一@ 2.正则式→FA ①e+②代之以①→④2，② 0l→9代之以①② 、①速，②代之以①市，② 例1.(ab)*a(ab) a.b +@U00@ 例2.(a*b*)bba) 列3.(ab)*baab
§3.4 正则表达式 正则文法与有限自动机的相互转换 1.FA→正则表达式 P59 例 4.10 a,b 例： a a b a,b b a,b (a|b)*(aa|bb)(a|b)* 2.正则式→FA e1e2 ② 代之以 e1 e2 ② e1 e1|e2 ② 代之以 e2 ② e e* ② 代之以 ε ε ② 例 1.（a|b）*a(a|b) a,b ε εε a a b 例 2. （a*|b*）b(ba)* a ε ε b a b ε ε ε ε b 例 3.（a*b）*ba(a|b)* a ε ε b a ε ε ε b b a ε 0 3 4 1 2 X Y 0 1 3 4 0 2 3 1 4 5 6 7 0 1 2 5 6 7 8 3 4 2
例4.1(1010*1(010)*1)*0 1,6 00 3 13 例5 b*abb*(abb*)* (10 t a §3.5正则文法和有穷自动机间的转换 ”GS1EA-个件老2 P62例4J2.4.13 例1.GSS→+0B Z-E 2.FAM-G 初态，终态表的可识别e串 例1. b G[Z]:Z-aZlbBl B->aZ B a
例 4. 1（1010*|1（010）*1）*0 1 0 ε 0 1 1 ε ε ε 0 1 1 ε ε ε 0 ε 1 0 例 5.b*abb*(abb*)* b ε b b b ε ε a b ε ε ε a ε ε § 3.5 正则文法和有穷自动机间的转换 P62 例 4.12. 4.13 G={VN,VT,P,S} 1. G FAM G={VN,VT,P,S} FAM={S,Σ,f,S0, Z} 引入一个终态 Z 例 1.G[S]: S 0B B 0B 0 S 0B B 1S 0 0 B 0B|1S|0Z B 0Z 1 Z ε Z ε 2.FAM G 初态，终态表的可识别ε串 a 例 1. b G[Z]: Z aZ|bB|ε B aZ 0 1 2 3 4 4 5 7 6 8 10 9 12 11 13 0 1 2 3 4 5 6 7 8 9 10 11 Z B S B Z a
例2： -0- o. G[A]:A-0AJIAJIB ,B-IC C-0CIICIE $3.6词法分析程序的自动机的构造工具 1.LEX系统功能P64图4.13 2.LEX源程序 3.LEX的处理过程： ①扫描每条识别规则P构造一相应的非确定有穷自动机M ②将各条规则的自动机Mi合并成一个新NFAM ③确定化，NFA→DFA,即生成该DFA的状态转换矩阵和控制 执行程序 正则文法 NFA 正则表达式 DFA 最小化 第四章 自顶向下语法分析方法 递归子程序法（递归下降分 孔)文法（预测分析法） 析法) 是判断由单词组成的符号串是否为句子 确定 两种方法厂自顶向下：推导从开始符出发一句子 不确定： 回溯，试探 算符优先 自底向上：归约从句子一开始符、 LR
例 2： 1 1 0,1 0,1 G[A]:A 0A|1A|1B ,B 1C C 0C|1C|ε §3.6 词法分析程序的自动机的构造工具 1.LEX 系统功能 P64 图 4.13 2.LEX 源程序 3.LEX 的处理过程： 扫描每条识别规则 Pi 构造一相应的非确定有穷自动机 Mi ②将各条规则的自动机 Mi 合并成一个新 NFAM 确定化，NFA→DFA,即生成该 DFA 的状态转换矩阵和控制 执行程序 ⑤ ② ⑥ ④ 最小化 第四章 自顶向下语法分析方法 递归子程序法（递归下降分 析法） 是判断由单词组成的符号串是否为句子 LL(1）文法（预测分析法） 确定 两种方法 自顶向下：推导 从开始符出发→句子 不确定 ： 回溯，试探 算符优先 自底向上：归约 从句子→开始符 LR A B C 正则文法 NFA 正则表达式 DFA
●自顶向下可能出现的问题（需要确定的推导） 1,有多个候选师，选哪一个的问题，需试探，回溯。 如：-XXSaUB ab ac 2.直接左递归： 即U-→JxlUylxly 需要消除左递归 ●自底向上可能出现的问题（句柄，可归约串） 1.右部相同(ab):左部归约为A或U例：A→ab,U→ablaclxab 2.归约ab还是Xab等的问题 84.1确定的自定向下分析思想 1.分析过程是唯一确定的文法P70 2不确定但无穷产生式集确定 3有穷产生式Follow集Select集 First集 (首符号集) G[S]-(VN,VT,P.S)FIRST(X)=(alx ay,aE VT,x.yEV+ 若Xe,则e∈FIRST() ●FIST是指由符号串x出发能够推导出的所有符号串中，处于串头的终结符的集合 ●算法P74X=XX n 如果X是终结符 则X∈FIRST() (推不出e,则不看后面FIRST()=FIRST() 如果名是非终结符，则看它能否推出空串 推出e,则FIRST(X)→e,再看后是终或非终 终，则并入FIRST 厂推e 推不出e 例P75例5.5 例1.G[S]:S→abB,B-→AbA,A-→SCe,C→BC FIRST(S)-(a) FIRST(B)=(FIRST(A)-:)U(b}=(a,b} FIRST(A)=FIRST(S)UFIRST()=a, FIRST(C)=FIRST(B)U{c}=(a,b,c} 伍2. S→eTRT]:,T-→DRe,R→dRE,D-→abd FIRST(S)=fe)U(FIRST(R)-e) J(FIRST(T)-e)U(e)=(e,e,d,a,b} FIRST(T)=FIRST(D)U{e}=(a,b,e) FIRST(R)=(d.E} FIRST(D)={a,b时 例3. D-→Sele FIRST(S)=(a,d} FIRST(A)=(FIRST(B)-e)UFIRST(S)Ue}=a,d,c,e} FIRST(B)=FIRST(S)Uc}U[E=a,d,c
●自顶向下可能出现的问题 （需要确定的推导） 1.有多个候选师，选哪一个的问题，需试探，回溯。 如：U→X1|X2 |.|Xn S + α∪β ab ac 2.直接左递归： 即 U→Ux|Uy|x|y 需要消除左递归 ●自底向上可能出现的问题（句柄，可归约串） 1.右部相同（ab）:左部归约为 A 或 U 例：A→ab,U→ab|ac|xab 2.归约 ab 还是 xab 等的问题 §4.1 确定的自定向下分析思想 1.分析过程是唯一确定的文法 P70 2.不确定但无穷产生式 First 集确定 3.有穷产生式 Follow 集 Select 集 一. First 集 （首符号集） G[S]=(VN,VT,P,S) 则 FIRST(X)=｛a|x * ay, aVT,x,yV* ｝ 若 X * ε,则εFIRST(X) ●FIRST 是指由符号串 x 出发能够推导出的所有符号串中，处于串头的终结符的集合 ●算法 P74 X=X1X2.Xn 如果 X1是终结符，则 X1FIRST(X) 推不出ε，则不看后面 FIRST(X)=FIRST(X1) 如果 X1是非终结符，则看它能否推出空串 推出ε，则 FIRST(X1)→ε，再看后是终或非终 终，则并入 FIRST 推ε 非 推不出ε 例 P75 例 5.5 例 1. G[S]: S→abB, B→AbA, A→SC|ε, C→B|C FIRST(S)={a} FIRST(B)=(FIRST(A)-ε)∪{b}={a,b} FIRST(A)=FIRST(S)∪FIRST(ε)={a,ε} FIRST(C)=FIRST(B)∪{c}={a,b,c} 例 2. S→eT|RT|ε, T→DR|ε, R→dR|ε, D→a|bd FIRST(S)={e}∪(FIRST(R)-ε)∪(FIRST(T)-ε)∪{ε}={e,ε,d,a,b} FIRST(T)=FIRST(D)∪{ε}={a,b,ε} FIRST(R)={d,ε} FIRST(D)={a,b} 例 3. S→aAbDe|d, A→BSD|e, B→SAc|cD|ε D→Se|ε FIRST(S)={a,d} FIRST(A)=(FIRST(B)-ε)∪FIRST(S)∪{e}={a,d,c,e} FIRST(B)=FIRST(S)∪{c}∪{ε}={a,d,c,ε}
FIRST(D)=FIRST(S)UIe=fa.d.e} 二.FOL0m集 FOLLOW (A)=(als Aa aeV灯}，若 .A,则#∈FOLL0W(A) (#abc#,“#“像是括号，括一个句子，标志句子的开始，结束) ●FOLLOW()是指所有句型中紧跟在A后的终结符号集 ●算法P76①先看是否求首字符，如果是开始符，则#加入℉OLL0m集 ②看产生式的右部，先看A后面有无符号，如不是最后一个符号 若符号E则为后面符号的FIRST集-:UFOLLOW(左部)》 若符号不能推出e则F0LL0丽集并入 如后面再无符号，则左部FOLLOW集并入 例P77 例l.S-→abB A-→SC1E,B-→AbAC-→Bke FOLLOW(S)=#)UFIRST(C)=(#,a,b,c} FOLLOW (A)=FOLLOW(B)U (b)=(#,a,b,c} FOLLOW (B)=FOLLOW(S)UFOLLOW (C)=#a.b.cl FOLLOW(C)=FOLLOW(A)=(a.b.c} (遇到互相代F(A=F(B)=F(C)F(C)=F(A)则其FOLLOW集都相等) 例2.S-→eTRT,R-→dRe,D-→abd FOLLOW(S)=# FOLLOW(R)=(FIRST(T)-e)UFOLLOW(S)UFOLLOW (T)=[#a,b} FOLLOW (T)=FOLLOW(S)=(#) FOLLOW(D)=(FIRST(R)-e)UFOLLOW(T)=(d}U(#)=d,#) 例3. S-aAbDeld. A→BSDIc.B+SAcIcDIe,D→See FOLLOW (S)=(#)UFIRST(D)UFOLLOW(A)UFIRST(A)UcUe ={￥.a.d.b.c.e} FOLLOW (A)=(b,c} FOLLOW(B) =FIRST(S)=(a,d) FOLLOW (D)=(e}UFOLLOW (A)UFOLLOW(B)=(e,b,c,a,d} 三.SELECT集 SELECT (A-X)=FIRST(W)当X之C FOLLOW(A)UFIRST(X)IE,当X>E(AE V XEV) (FIST对符号串求，FOLLOW对非终结符，SELECT对产生式求) 例1. G[Z]:Z→aAcBIBd. A-AaBlc.B-bBcAlb SELECT(Z-aAcB)-FIRST(aAcB)-fa) SELECT(A- SELECT(Z -FIRST(Bd)=(b) SELECT(B →bBcA={b SELECT(A-AaB=FIRST(AaB)=c SELECT(B→b=b
FIRST(D)=FIRST(S)∪{ε}={a,d,ε} 二．FOLLOW 集 FOLLOW(A)={a|s * Aa ,aVT },若 S * .A,则#FOLLOW(A) (#abc#,"#"像是括号，括一个句子，标志句子的开始，结束) ●FOLLOW(A)是指所有句型中紧跟在 A 后的终结符号集 ●算法 P76 先看是否求首字符，如果是开始符，则#加入 FOLLOW 集 ②看产生式的右部，先看 A 后面有无符号，如不是最后一个符号 若符号 * ε则为后面符号的 FIRST 集-ε∪FOLLOW(左部) 若符号不能推出ε则 FOLLOW 集并入 如后面再无符号，则左部 FOLLOW 集并入 例 P77 例 1. S→abB A→SC* |ε, B→AbA, C→B|c FOLLOW(S)={#}∪FIRST(C)={#,a,b,c} FOLLOW(A)=FOLLOW(B)∪{b}={#,a,b,c} FOLLOW(B)=FOLLOW(S)∪FOLLOW(C)={#,a,b,c} FOLLOW(C)=FOLLOW(A)={#a,b,c} (遇到互相迭代 F(A)=F(B)=F(C) F(C)=F(A)则其 FOLLOW 集都相等) 例 2. S→eT|RT, R→dR|ε, D→a|bd FOLLOW(S)={#} FOLLOW(R)=(FIRST(T)-ε)∪FOLLOW(S)∪FOLLOW(T)={#,a,b} FOLLOW(T)=FOLLOW(S)={#} FOLLOW(D)=(FIRST(R)-ε)∪FOLLOW(T)={d}∪{#}={d,#} 例 3. S→aAbDe|d, A→BSD|c, B→SAc|cD|ε, D→Se|ε FOLLOW(S)={#}∪FIRST(D)|ε∪FOLLOW(A)∪FIRST(A)∪c∪e ={#,a,d,b,c,e} FOLLOW(A)={b,c} FOLLOW(B)=FIRST(S)={a,d} FOLLOW(D)={e}∪FOLLOW(A)∪FOLLOW(B)={e,b,c,a,d} 三．SELECT 集 SELECT(A→X)= FIRST(X) 当 X ε FOLLOW(A)∪FIRST(X)|ε,当 X * ε (AVN,XV *) (FIRST 对符号串求，FOLLOW 对非终结符，SELECT 对产生式求) 例 1. G[Z]: Z→aAcB|Bd , A→AaB|c, B→bBcA|b SELECT(Z→aAcB)=FIRST(aAcB)={a} SELECT(A→c)={c} SELECT(Z→Bd)=FIRST(Bd)={b} SELECT(B→bBcA)={b} SELECT(A→AaB)=FIRST(AaB)={c} SELECT(B→b)={b}