第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 节目录