第2周 星期二 第2大节

• 视频：screen_编译原理与设计_第2周_星期二_第2大节.mp4
• 字幕：transcripts/第2周_星期二_第2大节.srt

时间轴

• 01:00 复习：正规式定义词法规则，DFA识别单词
• 04:23 字符串集合乘积（A·B）、{ε}集vs∅集
• 08:54 字符串集合方幂
• 11:20 正闭包（A⁺）和自反闭包（A*）
• 14:47 变量名定义：L·(L∪D)*
• 23:21 正规式递归定义与正规集
• 28:31 正规式示例（{0,1}和{A,B,0,1}字母表）
• 40:15 有符号整数、浮点数正规式
• 51:00 简化C语言词法正规式（关键字、标识符、常量、运算符）
• 55:54 正规式代数性质
• 58:28 有限自动机模型（纸带、读头、状态）
• 01:01:49 DFA五元组定义及三种表示（形式化、图、矩阵）
• 01:12:20 DFA识别机制（1010/11001示例）
• 01:34:27 NFA引入：实际多值映射需求
• 01:43:50 NFA五元组定义（含ε转移）
• 02:00:52 定理：∀NFA ∃等价DFA
• 02:06:47 ε-闭包定义与IA三步计算
• 02:20:34 子集构造法示例

关键点

考勤/签到/小测

无。

作业

无布置。

考试/复习重点

• {ε}集≠∅集，必须区分（06:26）
• 正规式运算优先级：() > * > · > |（28:11）
• DFA五元组（S, Σ, f, S₀, Z）及三种表示法（01:01:49）
• NFA与DFA区别：确定性vs非确定性，ε转移（01:43:50）
• ε-闭包和IA计算（02:06:47）→ 子集构造法基础

其他需要回看的片段

• 40:15-45:21 有符号整数和浮点数正规式设计
• 55:54-57:36 正规式代数性质（交换、结合、分配）
• 01:23:56-01:31:14 DFA设计示例：含”001”的二进制串

省流

词法分析理论核心：正规式和有限自动机。从字符串集合运算出发，到正规式递归定义和代数性质，再到DFA/NFA五元组定义及二者关系。重点掌握ε-闭包、IA计算、子集构造法。