编译原理（2）：正则表达式和有穷自动机

• 正则表达式
• • 基本概念
  • 正则定义
  • 有穷自动机（FA）
  • • FA的表示
    • 最长子串匹配原则
  • 有穷自动机分类
  • • 确定的FA
    • 非确定的FA
    • DFA和NFA的等价性
  • 从正则表达式到有穷自动机
  • • 从正则表达式到NFA
    • 从NFA变成DFA
  • 识别单词的DFA功能
  • 词法分析的错误处理

正则表达式（RE），是一种描述正则语言的更紧凑的方法

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式r定义(表示)一个语言，记为L(r )。这个语言也是根据r 的子表达式所表示的语言递归定义的

epsilon是一个RE，L(ε)={ε}

• 如果a∈E，则a是一个RE，L(a)={a}
• 假设r和s都是RE，表示的语言分别是L®和L(s)，则 rs是一个RE，L(r|s )= L®UL(s)
• rs 是一个RE，L( rs ) = L®L(s)r”是一个RE，L(r*)=(L®)®是一个RE，L(®)=L®运算的优先级:*、连接、|

可以用RE定义的语言叫做正则语言或正则集合

正则定义是具有如下形式的定义序列:
d1→r1
d2→r2
…
dn→rn
其中:

• 每个di都是一个新符号，它们都不在字母表∑中，而且各不相同
• 每个ri是字母表∑U{d ,d,… ,d}上的正则表达式

给一些RE命名,并在之后的RE中像使用字母表中的符号一样使用这些名字

有穷自动机( Finite Automata，FA)由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

转换图(Transition Graph)结点:FA的状态

• 初始状态(开始状态)︰只有一个，由start箭头指向
• 终止状态(接收状态）︰可以有多个，用双圈表示

带标记的有向边:如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边并标记上a

L(M)=所有以abb结尾的字母表{a, b}上的串的集合

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收由一个有穷自动机M接收的所有串构成的集合称为是该FA定义(或接收)的语言，记为L(M）

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配

在到达某个终态之后，只要输入带上还有符号，FA就继续前进,以便寻找尽可能长的匹配

M = (S，∑，α，s0，F)

• S:有穷状态集
• ∑:输入字母表，即输入符号集合。假设ε不是二中的元素
• α:将S×E映射到S的转换函数。VsES, a∈E,(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态
• S0︰开始状态(或初始状态)，s0∈ S
• F:接收状态（或终止状态）集合，F∈S

M = (S，2，α，s0，F)

• S:有穷状态集
• ∑:输入符号集合，即输入字母表。假设ε不是工中的元素
• α：将S×E映射到2s的转换函数。Vs Es,a∈E,0(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
• s0︰开始状态(或初始状态)，s0∈s
• F:接收状态（或终止状态）集合，F∈s

• 对任何NFA N，存在识别同一语言的DFA D
• 对任何DFA D ，存在识别同一语言的NFAN

DFA的每个状态都是一个由NFA中的状态构成的集合,即NFA状态集合的一个子集

步骤：

• 写出转换表

• 识别标识符
• 识别无符号数
• 识别各进制的无符号数
• 识别注释
• 识别Token

常见错误：

• 单词拼写错误
• 非法字符

查找已扫描字符串中最后一个对应于某终态的字符

• 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词
• 如果没找到，则确定出错，采用错误恢复策

最简单的错误恢复策略:“恐慌模式(panic mode)”恢复：从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止

本章架构分析：词法分析中，先是将句子用正则表达式表示出来，然后将其转换成NFA，再转化成DFA，用来进行词法分析。

最近新建了一个交流群，欢迎加入交流群