本次笔记内容： 3-1 正则表达式 3-2 正则定义 3-3 有穷自动机 3-4 有穷自动机的分类 3-5 从正则表达式到有穷自动机 3-6 从NFA到DFA的转换 3-7 识别单词的DFA
文章目录
词法分析：正则表达式
正则表达式的定义
正则表达式简单例子
例子：C语言无符号整数的RE
正则语言
RE的代数定律
正则文法与正则表达式等价
正则定义
正则定义（Regular Definition）
例1：C语言中标识符的正则定义
例2：（整型或浮点型）无符号数的正则定义
词法分析重大理论基础：有穷自动机（FA）
起源与定义
FA的典型例子（电梯控制装置）
FA模型
FA模型
转换图
FA定义（接收）的语言
最长子串匹配原则（Longest String Matching Principle）
FA分类
确定的有穷自动机（DFA）
例：一个DFA
非确定的有穷自动机（NFA）
例：一个NFA
DFA和NFA的等价性
带有" ϵ \epsilon ϵ - 边"的NFA
带有和不带有" ϵ \epsilon ϵ - 边"的NFA的等价性
DFA的算法实现
从正则表达式到有穷自动机
根据RE构造NFA
例： r = ( a ∣ b ) ∗ a b b r=(a|b)^* abb r=(a∣b)∗abb对应的NFA
从NFA到DFA的转换
例子1：DFA一个状态代表NFA多个状态
例子2：从带有ε-边的NFA到DFA的转换
子集构造法
识别单词的DFA
识别标识符的DFA
识别无符号数的DFA
识别各进制无符号整数的DFA
识别注释的DFA
识别Token的DFA
词法分析阶段的错误处理
词法分析：正则表达式
正则表达式可以更好地描述语言，非正则例子如下：
语 言 L = { a } { a , b } ∗ ( { ϵ } ∪ ( { . , _ } { a , b } { a , b } ∗ ) ) 语言L = \{ a \} \{ a,b \}^* (\{ \epsilon \} \cup ( \{ .,\_ \} \{a,b\} \{ a,b \}^* )) 语言L={
a}{
a,b}∗({
ϵ}∪({
.,_}{
a,b}{
a,b}∗))
正则表达式（Regular Expression, RE）是一种用来描述正则语言的更紧凑的表示方法。
例如，上式可以用正则表达式表示： r = a ( a ∣ b ) ∗ ( ϵ ∣ ( . ∣ ) ( a ∣ b ) ( a ∣ b ) ∗ ) r=a(a|b)^* (\epsilon | (.|_)(a|b)(a|b)^*) r=a(a∣b)∗(ϵ∣(.∣)(a∣b)(a∣b)∗)
句子的第一个符号是字母a；接下来连接一个任意长度的ab串；接下来连接一个空串，此时句子结束；除此之外，还可以连接一个.或者_，接下来再连接一个长度大于等于1的ab串。
正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式r定义（表示）一个语言，记为 L ( r ) L(r) L(r)。这个语言也是根据 r r r的子表达式所表示的语言递归定义的。
正则表达式的定义
ϵ \epsilon ϵ是一个RE， L ( ϵ ) = { ϵ } L(\epsilon)=\{ \epsilon \} L(ϵ)={
ϵ}
如果 a ∈ Σ a \in \Sigma a∈Σ，则 a a a是一个RE， L ( a ) = { a } L(a)=\{ a \} L(a)={
a}
假设 r r r和 s s s都是RE，表示的语言分别是 L ( r ) L(r) L(r)和 L ( s ) L(s) L(s)，则
r ∣ s r|s r∣s是一个RE， L ( r ∣ s ) = L ( r ) ∪ L ( s ) L(r|s)=L(r) \cup L(s) L(r∣s)=L(r)∪L(s)
r s rs rs是一个RE， L ( r s ) = L ( r ) L ( s ) L(rs)=L(r)L(s) L(rs)=L(r)L(s)
r ∗ r^* r∗是一个RE， L ( r ∗ ) = ( L ( r ) ) ∗ L(r^*)=(L(r))^* L(r∗)=(L(r))∗
( r ) (r) (r)是一个RE， L ( ( r ) ) = L ( r ) = L ( r ) L((r))=L(r) = L(r) L((r))=L(r)=L(r)
运算的优先级为：*、连接、|。
正则表达式简单例子
令 Σ = { a , b } \Sigma = \{ a,b \} Σ={
a,b}，则
L ( a ∣ b ) = L ( a ) ∪ L ( b ) = { a } ∪ { b } = { a , b } L(a | b)=L(a) \cup L(b)=\{a\} \cup\{b\}=\{a, b\} L(a∣b)=L(a)∪L(b)={
a}∪{
b}={
a,b}
L ( ( a ∣ b ) ( a ∣ b ) ) = L ( a ∣ b ) L ( a ∣ b ) = { a , b } { a , b } = { a a , a b , b a , b b } L((a | b)(a | b))=L(a | b) L(a | b)=\{a, b\}\{a, b\}=\{a a, a b, b a, b b\} L((a∣b)(a∣b))=L(a∣b)L(a∣b)={
a,b}{
a,b}={
aa,ab,ba,bb}
L ( a ∗ ) = (