第3章 词法分析 口3.1词法分析程序的设计 口手工设计3.2PL0编译程序的词法分析（理解实践） 口自动设计原理 口3.3单词的形式化描述工具（理解) 口3.4有穷自动机（掌握重点难点） 0 35正规式和有穷自动机的等价性（掌握重点) 0 3.6正规文法和有穷自动机的等价性（了解） 口自动设计工具3.7词法分析程序的自动构造工县（了解） 口本章练习 0 作业 课程目录 25.4.2 国21
25.4.2 1 第3章 词法分析 3.1 词法分析程序的设计 手工设计 3.2 PL/0编译程序的词法分析（理解实践） 自动设计原理 3.3 单词的形式化描述工具（理解） 3.4 有穷自动机（掌握 重点 难点） 3.5 正规式和有穷自动机的等价性（掌握 重点 ） 3.6 正规文法和有穷自动机的等价性（了解） 自动设计工具3.7 词法分析程序的自动构造工具(了解) 本章练习 作业 课程目录
空白 字母或数字 字 标识符if sum 字 其它 数字 其它 用来 十进制整数 语 识别 言 PL/0 语言 中的 非+ 析的 ++ 状态 转换 main() 其它 {inta=10;.} 图 出错 25.4.2 ☒22
25.4.2 2 对简 单语 言进 行词 法分 析的 状态 转换 图 0 空白 字母 1 字母或数字 其它 2 * 标识符 if sum 数字 3 数字 其它 4 * 十进制整数 ， 5 ， ； 6 ； + 非 + 8 + + 9 ++ . ) 12 ) 其它 13 出错 用来 识别 PL/0 语言 中的 单词 符号 7 main() { int a=10;.}
正规表达式和有限自动机 语言单词 描述】 等价② 正规集 正规式ro 正规文法 构造⑤ 不确定有限自动机NFA④ 等价⑧ 确定化囵 】子集法 非最小确定有限自动机DFA 最小化@ 分割法 识别 最小确定有限自动机DFA® 单词 章节目录 25.4.2 ]D3
25.4.2 3 正规表达式和有限自动机 语言单词 正规式 r① 不确定有限自动机NFA ④ 非最小确定有限自动机 DFA 最小确定有限自动机DFA ③ 正规集 正规文法 识别 单词 描述 构造 ⑤ 确定化⑥ 子集法 最小化⑦ 分割法 章节目录 等价 ② 等价 ⑧
3.3单词的形式化描述工具p44 口正规集（正规语言） 某字母表上，我们感兴趣的符号串的集合。 o正规表达式(regular expression.) 是定义正规集（正规语言）的一种表示法。 口正规文法 是对正规语言（正规集）的一种描述工具。 25.4.2 ☒24
25.4.2 4 3.3 单词的形式化描述工具 p44 正规集(正规语言) 某字母表上，我们感兴趣的符号串的集合。 正规表达式（regular expression） 是定义正规集(正规语言)的一种表示法。 正规文法 是对正规语言(正规集)的一种描述工具
3.3.1正规文法p44 口程序设计语言中几类单词的规则描述： 0→11→1d1d字母数字> 口→dd 0〈运算符〉>→+-*/=>〈等号>. 0〈等号》→= 口→，：(). 25.4.2 D5
25.4.2 5 3.3.1 正规文法 p44 程序设计语言中几类单词的规则描述： → l|l →l|d|l |d →d|d →+|-|*|/|=||> . →= →,|;|(|)|
3.3.2正规式和正规集p45-46 对于字母表∑，正规式和正规集的递归定义为： 说明 正规式r 正规集L(r) 1.∧是空符号 e, {e},Φ 2.若a∈∑ a {a} 3.若u,v是正规 uV(或) L(u)UL(v) 式对应正规集 u.V(连接) L(u)L(v) 是L(u),L(v) u*(闭包) L(u)* 4.仅由有限次使用上述三步骤而得到的表达式才是∑上 的正规式，仅由这些正规式所表示的字集才是∑上的正 规集 连 25.4.2 ☒26
25.4.2 6 3.3.2 正规式和正规集 p45-46 对于字母表∑，正规式和正规集的递归定义为： 说明 正规式 r 正规集L(r) 1.∧是空符号 ε,∧ {ε},φ 2.若a∈∑ a {a} 4.仅由有限次使用上述三步骤而得到的表达式才是∑上 的正规式，仅由这些正规式所表示的字集才是∑上的正 规集 u|v(或) L(u)∪L(v) u ● v (连接) L(u)L(v) u* (闭包) L(u)* 3.若u,v是正规 式对应正规集 是 L(u),L(v)
正规式和正规集举例D45例3.2 0 设∑={a,b} 正规式 正规集 a {a} a b {a}U[b}{a,b} ab {a}{b}{ab} a* {a}*{e,a,aa,aaa,.} (a b)*{a,b)*{s,a,b,aa,ab,ba,bb,aaa,. 所有由a,b组成的串} 25.4.2 27
25.4.2 7 正规式和正规集举例 p45 例3.2 设 ∑={a，b} 正规式 正规集 a {a} a|b {a}∪{b}{a,b} ab {a}{b} {ab} a * {a}* {ε,a,aa,aaa,.} (a|b) * {a,b} * {ε,a,b,aa,ab,ba,bb,aaa,., 所有由a,b组成的串}
正规式和正规集举例p45例3.2 o设∑={a,b} 正规式 正规集 ba* Σ上所有以b为首后跟任意多个a的字 a(a b)* Σ上所有以a为首的字 (a b)*(aa bb)(a b)* ∑上所有含有两个相继的a或两个相继的b的字 设∑={A,B,0,1 正规式 正规集 (AB)(AB01)* ∑上的“标识符”的全体 (01)(01)* ∑上的“数”的全体 25.4.2 ☒28
25.4.2 8 正规式和正规集举例 p45 例3.2 设 ∑={a，b} 正规式 正规集 ba* ∑上所有以b为首后跟任意多个a的字 a(a|b) * ∑上所有以a为首的字 (a|b) *(aa|bb)(a|b) * ∑上所有含有两个相继的a或两个相继的b的字 设∑={A,B,0,1} 正规式 正规集 (A|B)(A|B|0|1)* ∑上的“标识符”的全体 (0|1)(0|1)* ∑上的“数”的全体
正规式运算符的优先级p45 高于 口·高于，具有结合律、分配律，可省略 ▣具有交换律、结合律 ()指定优先关系 口正规式的性质，设U、V和W均为正规式，则 or|s=sr(交换律) or|(st)=(rs)|t(结合律) ▣(rs)t=r(st)(结合律) or(st)=rsrt(st)r=sr|tr(分配律) 口er=r,re=r（恒等率) orr=r(抽取率) 25.4.2 ☒D9
25.4.2 9 正规式运算符的优先级 p45 * 高于 . . 高于|，具有结合律、分配律,可省略 | 具有交换律、结合律 ( )指定优先关系 正规式的性质,设U、V和W均为正规式,则 r|s=s|r (交换律) r|(s|t)=(r|s)|t (结合律) (rs)t=r(st)(结合律) r(s|t)=rs|rt (s|t)r=sr|tr (分配律) εr=r,rε=r（恒等率） r|r=r（抽取率）
正规式的等价性p45 口一个正规式r表示的正规集也就是r 所定义的语言，记为L(r) 0 若两个正规式r和s所表示的正规集 L(r)=L(s),则称r,s等价 记作r=S 例如：1(01)*=(10)*1 (a b)=b a {1,101,10101,.} (ab)*=(a*b*)* 25.4.2 ☒210
25.4.2 10 正规式的等价性 p45 一个正规式 r 表示的正规集也就是 r 所定义的语言，记为 L(r) 若两个正规式r和s所表示的正规集 L(r)=L(s),则称r,s等价 记作 r = s 例如：1(01) *=(10) *1 {1,101,10101,.} (a|b)=b|a (a|b)*=(a*|b*) *