编译原理-词法分析

阅读更多

1 正则表达式

正则表达式(Regular Expression, RE)是一种用来描述正则语言的更紧凑的表示方法

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

1.1 正则表达式的定义

1. $\varepsilon$是一个RE，$L(\varepsilon) = \{\varepsilon\}$
2. 如果$a \in \sum$，则$a$是一个RE，$L(a) = \{a\}$
3. 假设$r$和$s$都是RE，表示的语言分别是$L(r)$和$L(s)$，则
   • $r|s$是一个RE，$L(r|s) = L(r) \cup L(s)$
   • $rs$是一个RE，$L(rs) = L(r) L(s)$
   • $r^*$是一个RE，$L(r^*) = (L(r))^*$
   • $(r)$是一个RE，$L((r)) = L(r)$
   • 运算优先级：() > * > 连接 > |

1.2 正则语言

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

RE的代数定理

1.3 正则文法与正则表达式等价

对于任何正则文法$G$，存在定义同一语言的正则表达式$r$

对于任何正则表达式$r$，存在生成同一语言的正则文法$G$

2 正则定义

正则定义是具有如下形式的定义序列：

$$\begin{split}d_1 &\to r_1 \\ d_2 &\to r_2 \\ &... \\ d_n &\to r_n \\ \end{split}$$

• 每个$d_i$都是一个新符号，它们都不在字母表$\sum$中，而且各不相同
• 每个$r_i$是字母表$\sum \cup \{ d_1, d_2, ..., d_{i-1} \}$上的正则表达式

3 有穷自动机

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

• 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的情况）
• 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统内部的状态也将发生改变

3.1 FA模型

FA模型由三部分组成

1. 输入带(input tape)：用来存放输入符号串
2. 读头(head)：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动
3. 有穷控制器(finite control)：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态

3.2 FA的表示

转换图(Transition Graph)可以用来表示FA，其结构如下

1. 结点：FA的状态
   • 初始状态（开始状态）：只有一个，由start箭头指向
   • 终止状态（接收状态）：可能有多个，用双圈表示
2. 带有标记的有向边
   • 如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a，如下
   • 

3.3 FA定义（接收）的语言

给定输入串$x$，如果存在一个对应于串$x$的从初始状态到某个终止状态的转换序列，则称串$x$被该FA接收

由一个有穷自动机$M$(Machine)接收的所有串构成的集合称为是该FA定义（接收）的语言，记为$L(M)$

3.4 最长子串匹配原则

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

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

4 有穷自动机的分类

FA的分类

1. 确定的FA(Deterministic finite automata, DFA)
2. 非确定的FA(Nondeterministic finite automata, NFA)

4.1 确定的有穷自动机(DFA)

$$M = ( S, \sum, \delta, s_0, F )$$

1. $S$：有穷状态集
2. $\sum$：输入字母表，即输入符号集合。假设$\varepsilon$不是$\sum$中的元素
3. $\delta$：将$S\;\times\;\sum$映射到$S$的转换函数。$\forall s \in S, a \in \sum, \delta(s,a)$表示从状态$s$出发，沿着标记为$a$的边所能到达的状态
4. $s_0$：开始状态（或初始状态），$s_0 \in S$
5. $F$：接收状态（或终止状态）集合，$F \subseteq S$

4.2 非确定的有穷自动机(NFA)

$$M = ( S, \sum, \delta, s_0, F )$$

1. $S$：有穷状态集
2. $\sum$：输入字母表，即输入符号集合。假设$\varepsilon$不是$\sum$中的元素
3. $\delta$：将$S\;\times\;\sum$映射到$\textbf{2}^\textbf{S}$的转换函数。$\forall s \in S, a \in \sum, \delta(s,a)$表示从状态$s$出发，沿着标记为$a$的边所能到达的状态集合
4. $s_0$：开始状态（或初始状态），$s_0 \in S$
5. $F$：接收状态（或终止状态）集合，$F \subseteq S$

非确定的有穷自动机与确定的有穷自动机的唯一区别：

• 确定有穷自动机由当前状态和当前输入符号可以唯一确定下一个状态
• 非确定有穷自动机由当前状态和当前输入符号不能唯一确定下一个状态，只能得到一个状态集合

4.3 DFA和NFA的等价性

对任何非确定的有穷自动机N，存在定义同一语言的确定的有穷自动机D

对任何确定的有穷自动机D，存在定义同一语言的非确定的有穷自动机N

4.4 带有$\varepsilon -$边的NFA

$$M = ( S, \sum, \delta, s_0, F )$$

1. $S$：有穷状态集
2. $\sum$：输入字母表，即输入符号集合。假设$\varepsilon$不是$\sum$中的元素
3. $\delta$：将$S\;\times\;(\sum \cup \{ \varepsilon \})$映射到$\textbf{2}^\textbf{S}$的转换函数。$\forall s \in S, a \in (\sum \cup \{ \varepsilon \}), \delta(s,a)$表示从状态$s$出发，沿着标记为$a$的边所能到达的状态集合
4. $s_0$：开始状态（或初始状态），$s_0 \in S$
5. $F$：接收状态（或终止状态）集合，$F \subseteq S$

4.5 带有和不带有$\varepsilon -$边NFA等价

4.6 DFA算法的实现

输入：以文件结束符eof结尾的字符串$x$。DFA $D$的开始状态$s_0$，接收状态集$F$，转换函数$move$
输出：如果$D$接收$x$，则回答“yes”，否则回答“no”
方法：将下述算法应用于输入串$x$

• 函数nextChar()返回输入串$x$的下一个符号
• 函数move(s, c)返回从状态$s$出发，沿着标记为$c$的边所能到达的状态

s = s0;
c = nextChar();
while(c != eof) {
    s = move(s, c);
    c = nextChar();
}

if(s in F) return "yes";
else return "no";

5 从正则表达式到有穷自动机

从正则表达式转换到DFA比较困难，但是从正则表达式转换到带有$\varepsilon -$边的NFA是比较容易的

5.1 根据RE构造NFA

1. $\varepsilon$对应的NFA
   • 
2. 字母表$\sum$中符号$a$对应的NFA
   • 
3. $r = r_1r_2$对应的NFA
   • 
4. $r = r_1 | r_2$对应的NFA
   • 
5. $r = r1^*$对应的NFA
   • 

下面以一个例子进行说明，$RE = (a|b)^*abb$

• 
• 转化的过程，就是将复合表达式进行拆分的过程

6 从NFA到DFA的转换

以上图中的例子进行说明

• 起始状态$A$，在接收到字符$a$后，下一个状态集合是$\{A、B\}$
• 我们将状态集合$\{A、B\}$单独作为DFA中的一个状态。状态$\{B、C\}$、$\{C、D\}$同理
• 在NFA中，状态$A$接收字符$a$后，转换到状态集合$\{A、B\}$，因此，在DFA中，状态$\{A、B\}$接收字符$a$后，转换到状态$\{A、B\}$
• 在NFA中，状态$B$接收字符$b$后，转换到状态集合$\{B、C\}$，因此，在DFA中，状态$\{A、B\}$接收字符$b$后，转换到状态$\{B、C\}$
• 其他同理，不再赘述

6.1 子集构造法(subset construction)

输入：NFA N
输出：接收同样语言的DFA D
方法：一开始，$\varepsilon -closure( s_0 )$是Dstates中的唯一状态，且它未加标记

while(在Dstates中有一个未标记状态T)｛
    给T加上标记;
    for(每个输入符号a)｛
        //首先，move(T, a)函数返回的是一个集合
        //然后，通过ε-closure(T)计算出包含ε-边的集合
        //注意到，这里的U在NFA中是一个状态集合，但是对于DFA而言仅是一个状态，理解这一点很重要
        U = ε-closure(move(T, a));

        //如果状态U是一个新状态，那么将其加入Dstates中
        if(U不在Dstates中) {
            将U加入到Dstates中，且不加标记;
        }

        //在DFA D中，状态T在输入a时转移到状态U，即画一条边
        Dtran[T, a]=U;
    }
}

操作	描述
$\varepsilon -closure( s )$	能够从NFA的状态$s$开始只通过$\varepsilon$转换到达的NFA状态集合
$\varepsilon -closure( T )$	能够从$T$中的某个NFA状态$s$开始只通过$\varepsilon$转换到达的NFA状态集合，即$U_{s \in T}\; \varepsilon -closure( s )$
$move(T, a)$	能够从$T$中的某个状态$s$出发通过标号为$a$的转换到达的NFA状态的集合

计算$\varepsilon -closure( T )$的算法，该过程类似于BFS算法

将T的所有状态压入stack中;
将ε-closure(T)初始化为T;
while(stack非空)｛
    将栈顶元素t弹出;
    for(每个满足如下条件的u:从t出发有一个标号为ε的转换到达状态u) {
        if(u不在ε-closure(T)中) {
            将u加入到ε-closure(T)中
            将u压入栈中;
        }
    }
}

7 识别单词的DFA

7.1 识别标识符的DFA

标识符的正则定义如下

$$\begin{split} digit &\to 0|1|2|...|9 \\ letter\_ &\to A|B|...|Z|a|b|...|z|\_ \\ id &\to letter\_( letter\_|digit )^* \end{split}$$

7.2 识别无符号数的DFA

无符号数的正则定义如下

$$\begin{split} digit &\to 0|1|2|...|9 \\ digits &\to digit\;\;digit^* \\ optionalFraction &\to .digits|\varepsilon \\ optionalExponent &\to ( E( +|-|\varepsilon ) digits ) | \varepsilon \\ number &\to digits\;\;optionalFraction\;\;optionalExponent \end{split}$$

7.3 识别各进制无符号整数的DFA

7.4 识别注释的DFA

7.5 识别Token的DFA

7.6 词法分析阶段的错误处理

词法分析阶段可检测的错误类型

1. 单词拼写错误
2. 非法字符

语法错误检测：如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序

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

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

错误恢复策略：

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

8 参考

• 《MOOC-编译原理-陈鄞》
• 实现一个 DFA 正则表达式引擎
• 能不能用高级语言的正则表达式匹配来写一个词法分析器呢？
• 正则表达式图形化引擎