第3章词法分析 n3.1词法分析程序的设计 n手工设计3.2PL/0编译程序的词法分析（理解实践） n自动设计原理 u33单词的形式化描述工具（理解) u3.4有穷自动机（掌握重点难点） u3.5正规式和有穷自动机的等价性（掌握重点） u3.6正规文法和有穷自动机的等价性（了解） n自动设计工县3.7词法分析程序的自动构造工县（了解） n本章练习 n作业 课程目录 28-二月-23 ☒21
28-二月-23 1 第3章 词法分析 n 3.1 词法分析程序的设计 n 手工设计 3.2 PL/0编译程序的词法分析（理解实践） n 自动设计原理 u 3.3 单词的形式化描述工具（理解） u 3.4 有穷自动机（掌握 重点 难点） u 3.5 正规式和有穷自动机的等价性（掌握 重点 ） u 3.6 正规文法和有穷自动机的等价性（了解） n 自动设计工具3.7 词法分析程序的自动构造工具(了解) n 本章练习 n 作业 课程目录
正规表达式和有限自动机 语言单词 描述 等价② 正规集 正规式r四 正规文法 构造旦 不确定有限自动机NFA生1 等价國 确定化@子集法 非最小确定有限自动机DFA 最小化@】分割法 识别 最小确定有限自动机DFA@ 单词 章节目录 28-二月-23 ☒22
28-二月-23 2 正规表达式和有限自动机 语言单词 正规式 r① 不确定有限自动机 NFA ④ 非最小确定有限自动机 DFA 最小确定有限自动机 DFA ③ 正规集 正规文法 识别 单词 描述 构造 ⑤ 确定化 ⑥ 子集法 最小化⑦ 分割法 章节目录 等价 ② 等价 ⑧
正规式和正规集举例p45例3.2 n设∑={a,b} 正规式 正规集 (a b)*(aa bb)(a b)* ∑上所有含有两个相继的a 或两个相继的b的字 n设∑={A,B,0,1 正规式 正规集 (AB)(AB01)* ∑上的“标识符”的全体 (011)(01)* ∑上的“数”的全体 节目录 28-二月-23 ☒D 3
28-二月-23 3 正规式和正规集举例 p45 例3.2 n 设 ∑={a，b} 正规式 正规集 (a|b)*(aa|bb)(a|b)* ∑上所有含有两个相继的a 或两个相继的b的字 n 设∑={A,B,0,1} 正规式 正规集 (A|B)(A|B|0|1)* ∑上的“标识符”的全体 (0|1)(0|1)* ∑上的“数”的全体 节目录
3.4.1确定有限自动机（①FA)的定义p47-48 n确定的有限自动机DFAM是一个五元组 M=(S,口，8，s0,F) 6是状态转换函数，是在SX口→S上的单值映射。 s0∈S,是唯一的一个初态。 a,b b SDFA M所能接受的字符串的全体为 L (M)={a so sj且si∈F} 28-二月-23 节目录 ☒24
28-二月-23 4 3.4.1 确定有限自动机(DFA)的定义 p47-48 n 确定的有限自动机DFA M是一个五元组 M =（S， ，δ ，s0 ，F ) δ是状态转换函数，是在S× →S上的单值映射。 s0 ∈S，是唯一的一个初态。 a 1 0 b 3 2 a a b b a,b §DFA M 所能接受的字符串的全体为 sj L（M）={α| s0 且sj ∈F } 节目录
3.4.2不确定有限自动机NFAp49 n定义一个NFAM是五元式M作(S,口，6，S,F) u6从S口∑*+2s映射 uSo口S是S的非空子集，称为初始状态集合 a,b nNFA-一分析不确定，不断 试探，效率将降低 a,b n将NFA转换为等价的DFA SNFA M所能接受的字符串的全体为： L(M)={a|s0日s1且s。∈50， S,∈F} 28-二月-23 节目录
28-二月-23 5 3.4.2 不确定有限自动机NFA p49 n 定义 一个NFA M是五元式 M=(S, ,δ,S0,F) u δ 从S ∑*→2S映射 u S0 S 是S的非空子集，称为初始状态集合 0 b a,b 1 2 a a,b a,b 3 4 a b §NFA M 所能接受的字符串的全体为： sj L（M）={α| s0 且s0 ∈S0， sj ∈F } n NFA-分析不确定,不断 试探,效率将降低 n 将NFA转换为等价的DFA 节目录
从正规式r构造NFAM 2.当r中含有k个运算符时，分下列三种情况 r=2r=12r=r*,对应的三个 状态转换图如下： 替换规则 2 2 2 qo q2 22 qo 02 28-二月-23 ☒6
28-二月-23 6 从正规式 r 构造NFA M 2.当 r 中含有 k 个运算符时，分下列三种情况 r = r1| r2 r = r1 r2 r = r1 * ，对应的三个 状态转换图如下： = 1 | 2 = 1 2 = 1 * 1 2 q0 q1 q2 1 q0 q1 q2 ε ε 2 1 q0 q1 替 换 规 则
从正规式r构造NFAM举例 已知正规式r=(ab)*(aabb)(ab)* 试给出能识别L(r)的确定有限自动机FA (a b)*(aa bb)(a b)* 〉 3 a a 28-二月-23 节目录 ☒7
28-二月-23 7 从正规式 r 构造NFA M 举例 已知正规式 r=(a|b)*(aa|bb)(a|b)* 试给出能识别L(r)的确定有限自动机NFA (a | b )*(aa | bb) (a | b )* X Y a X 5 b 3 a 4 2 b 1 a b 6 Y b a 节目录
3.4.3NFA的确定化p50 SDFA是NFA的特例： (1)NFA的初态集中只有唯一初态 (2)状态转换函数单值（状态集之间转换） S对每一个NFAN一定存在一个DFAM,使得 L M)=LN) 即对每个NFAN存在着与之等价的DFAM。 S注意：与某一NFA等价的DFA不唯一。 确定化 NFA- DFA 子集法 28-二月-23 ☒28
28-二月-23 8 3.4.3 NFA的确定化 p50 §DFA是NFA的特例： （1）NFA的初态集中只有唯一初态 （2）状态转换函数单值（状态集之间转换） §对每一个NFA N一定存在一个DFA M，使得 L(M)=L(N) 即对每个NFA N存在着与之等价的DFA M。 §注意：与某一NFA等价的DFA不唯一。 NFA DFA 确定化 子集法
I-状态集 Ia输入a到达的状态集 Ib输入b到达的状态集 子 {X,5,1} {5,3,1) {5,4,1} 5,3,1 5,2,3,1,6,Y} {5,4,1} 举 {5,4,1} {5,3,1 {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,2,3,6,1,Y} {5,4,6,1,Y} {5,2,4,1,6,Y {5,3,6,1,Y] {5,2,4,6,1,Y} {5,4,6,1,Y} {5,6,3,1,Y) {5,2,6,4,1,Y} {5,3,6,1,Y 5,2,6,3,1,Y) {5,6,4,1,Y 3 →区 28-二月-23 ☒9
28-二月-23 9 子 集 法 举 例 {X,5,1} I-状态集 Ia-输入a到达的状态集 Ib-输入b到达的状态集 {5,3,1} {5,4,1} {5,3,1} {5,4,1} {5,2,3,1,6,Y} {5,4,1} {5,2,3,1,6,Y} {5,3,1} {5,2,4,1,6,Y} {5,2,4,1,6,Y} {5,2,3,6,1,Y} {5,4,6,1,Y} {5,3,6,1,Y} {5,2,4,6,1,Y} {5,4,6,1,Y} {5,6,3,1,Y} {5,2,6,4,1,Y} {5,3,6,1,Y} {5,2,6,3,1,Y} {5,6,4,1,Y} a X 5 b 3 a 4 2 b 1 a b 6 Y b a
状态子集重命名后的 确定化后的 状态转换矩阵 状态转换图 a a b 0 1 2 5 1 3 2 2 1 4 3+ 3 5 4 6 4 5 6 4 6+ 3 5 28-二月-23 ☒10
28-二月-23 10 状态子集重命名后的 状态转换矩阵 确定化后的 状态转换图 a b 0 - 1 2 3 + 1 2 3 2 1 4 3 5 4 + 6 4 5 + 6 4 6 + 3 5 a 1 0 b 2 a b b 3 5 a b a a b 4 6 b a b a