CS143 4 Implementation of Lexical Analysis and WA1

本篇是第4节的笔记。

概要

第四节主要讲了以下几个部分：

• 将规则用正则表达式表示，主要是在flex中如何处理冲突
• 有穷自动机、NFA和DFA
• 正则表达式转换为NFA
• NFA转换为DFA
• 用表（Table）来表示DFA

正则表示式匹配冲突

当字符串与其子串都匹配

设$S_1=s_i{s}_{i+1}...s_j$与$S_2=s_i{s}_{i+1}...s_k$，其中$i<k<j$，且$S_1$与表达式1匹配，$S_2$与表达式2匹配，此时，匹配更长的那个，即$S_1$。

例子：

如字符串$S=rob$，表达式有：

ro
ro[a-z]

此时，第一个可以匹配ro，而第二个可以匹配rob，因此第二个匹配。

一个字符串可以匹配多个表达式

只需与排在上面的匹配就可以了。

WA1的第5题涉及了上面的匹配冲突：

让我们构造一个字符串，使用给出的正则表达式来匹配，使得flex作用后可以输出想要的结果。

一开始我没朝会匹配冲突这方面想，直接能简则简，写的是$(01{)}^3((01010{)}^{2}1010{)}^2$，但这就会造成它尽可能长地匹配，结果会是$(banana{)}^4$。

想到会匹配冲突后还是比较简单的，为了不让apple被当作banana，就要011来匹配apple，而为了不让banana和coconut被匹配成多个apple，需要01010匹配banana、01001匹配coconut，因此答案是$(011{)}^3((01010{)}^{2}01001{)}^2$。

从这里可以看出，增长表达式可以减少一些冲突（因为匹配标准更加严格了）。

有穷自动机

上面的正则表达式是我们用于匹配的规范（specification），而在代码实现这个规范中，我们使用的就是有穷自动机（finite automation）。

组成

由以下几个部分组成：

• 一系列的状态的集合，包括一个开始状态（start state）和若干个结束状态（accepting state）
• 一系列状态转移条件（transition）
• 输入字符串（input）中字符的集合（alphabet）

书写表示：

例子：

字母表 ∑ = { 0 , 1 } \sum = \{0,1\} ∑={0,1}，下面图片中的自动机表示正则表达式：

1*0(0[01]+)?

$ϵ$

表示可以无条件地从一个状态转移到另一个状态，如下，A可以无条件地转移到B：

DFA、NFA

DFA： deterministic finite automation，状态确定的有穷自动机

NFA： nondeterministic finite automation，不定的有穷自动机。

区别：

1. NFA中，在某个状态时，一个输入可以导致该状态向多个状态转移，而DFA则没有这种情况出现，例子如下，在第一个状态输入0，可以进入第二个状态或继续在第一个状态。：

​

2. NFA中可能有$ϵ$状态转移，而DFA中没有。

正则表达式转换为NFA

就是按照正则表达式的意思写下来就可以了，这部分主要还是看经验。

NFA转为DFA

使用子集构造法，下面是具体的操作步骤。

一些操作

1. $ϵ-closure(s)$：求出从状态s开始，仅通过$ϵ$转移可以到达的状态的集合。
2. $ϵ-closure(T)$：对状态集合T中的每个状态执行操作1后得到的所有状态的集合。
3. $move(s,a)$：状态s接收a后转移到的状态的集合。

算法步骤

1. 对开始状态s0执行操作1得到集合T
2. 对T中的所有状态（用s表示）以及字母表中的所有字母（用a表示）依次执行move(s,a)，得到多个集合。
3. 对2中得到的每个集合再次执行2，直到所有得到的集合都执行过2。