1. 词法分析的简介

编译器的阶段：

graph LR A(源程序) --> B[front end] B --> C(IR) C --> D[back end] D --> E[target program]

前端

image-20210304173019897.png

2. 词法分析器

词法分析器将字符流转化为记号流

字符流：和被编译的语言密切相关 (ASCII, Unicode, or …)

记号流：编译器内部定义的数据结构，编码所识别出的词法单元

例子：

if (x > 5)
    y = "hello";
else
    z = 1;

词法分析后：

IF LPAREN IDENT(x) GT INT(5) RPAREN
    IDENT(y) ASSIGN STRING(“hello”) SEMICOLON
ELSE
    IDENT(z) ASSIGN INT(1) SEMICOLON EOF

记号的数据结构定义：

enum kind{IF, LPAREN, ID, INTLIT, ...};
struct token{
    enum kind k;    // 关键词
    char *lexeme;   // 值
};

词法分析器的实现方法

  • 手工编码实现法
    • 相对复杂、且容易出错
    • 但是目前非常流行的实现方法：GCC, LLVM, …
  • 词法分析器的生成器
    • 可快速原型、代码量较少
    • 但较难控制细节

3. 词法分析 ——手工构造法

比较符

状态转移图：

image-20210304201525654.png

token nextToken ()
    c = getChar ();
    switch (c)
        case ‘<’: c = getChar ();
            switch (c)
                case ‘=’: return LE;
                case ‘>’: return NE;
                default: rollback(); return LT;
        case ‘=’: return EQ;
        case ‘>’: c = nextChar ();
            switch (c): // similar
                ...

标识符

状态转移图

image-20210304202557398.png

token nextToken ()
    c = getChar();
    switch (c)
    // continued from above cases…
        case ‘a’, …, ‘z’, ‘A’, …, ‘Z’, ‘_’:
            c = getChar ();
            while (c==‘a’ || c==‘b’|| … || c==‘_’) c = getChar();

标识符和关键字

很多语言中的标识符和关键字有交集

从词法分析的角度看，关键字是标识符的一 部分
以C语言为例：
标识符：以字母或下划线开头，后跟零个或 多个字母、下划线、或数字
关键字：if, while, else, …

关键字

两种方案

第一种：在状态转移图上扩展新的边

image-20210304202817056.png

第二种：关键字表算法

  1. 对给定语言中所有的关键字，构造关键字构成的哈希表H
  2. 对所有的标识符和关键字，先统一按标识符的转移图进行识别
  3. 识别完成后，进一步查表H看是否是关键字
  4. 通过合理的构造哈希表H（完美哈希）， 可以 $O(1)$ 时间完成

4、词法分析——正则表达式

对于给定的字符集 $\sum=\left \{ c_{1}, c_{2}, …, c_{n} \right \}$，归纳定义：

  • 空串 $\varepsilon$ 是正则表达式
  • 对于任意的 $c \in \sum$，$c$ 是正则表达式
  • 如果 $M$ 和 $N$ 是正则表达式，那么以下也是正则表达式
    • 选择： $M|N=\left \{ M\cup N \right \}$
    • 连接：$MN = \left \{ mn | m\in M, n \in N \right \}$
    • 闭包：$M^*=\left \{ \varepsilon,M,MM,MMM,...\right \}$（Kleene闭包）

语法糖：可以引入更多的语法糖，来简化构造

语法糖 意义
$[c_{1}-c_{n}]$ $c_{1}
$e+$ 一个或多个 $e$
$e?$ 零个或一个 $e$
$“a_{*}”$ $a*$ 自身, 不是 $a$ 的Kleen闭包
$e \left \{i, j\right \}$ $i$ 到 $j$ 个 $e$ 的连接
. 除‘\n’外的任意字符

5、词法分析——有限状态自动机

graph LR subgraph 有限状态自动机 A("输入的字符串") ==> B["FA"] B ==> C("{Yes, No}") end

自动机：$M = (\sum, S, q_{0}, F, \delta)$

  • $\sum$：字母表，不同的语言不一样
  • $S$：状态集，指的是有限自动机的状态
  • $q_{0}$：初始状态
  • $F$：终结状态集，注意为状态集
  • $\delta$：转移函数

确定状态有限自动机（DFA）

对任意的字符，最多有一个状态可以转移

串读完的时候为最终状态即为可接受

graph LR O( ) --> A A((0)) --a--> B((1)) B --a--> C[2] A --b--> A B --b--> B C --a,b--> C
  • $\sum = \left \{a, b \right \}$
  • $S = \left \{0,1,2 \right \}$
  • $q_{0} = \left \{ 0 \right \}$
  • $F = \left \{ 2 \right \}$
  • $\delta =$ $ \left \{ (q0,a) \to q1, (q0, b) \to q0,\right \}$
    $\left \{(q1,a) \to q2,(q1,b) \to q1, \right \}$
    $\left \{ (q2,a) \to q2, (q2, b) \to q2\right \}$

非确定的有限状态自动机（NFA）

对任意的字符，有多于一个状态可以转移

graph LR O( ) --> A A((0)) --a,b--> B[1] A --a--> A B --b--> B B --b--> A
  • $\sum = \left \{a, b \right \}$
  • $S = \left \{0,1 \right \}$
  • $q_{0} = \left \{ 0 \right \}$
  • $F = \left \{ 1 \right \}$
  • $\delta =$ $ \left \{ (q0,a) \to \left \{ q0, q1 \right \} \right \}$
    $\left \{(q1,a) \to q1 \right \}$
    $\left \{ (q2,a) \to \left \{ q0,q1\right \} \right \}$

转换过程

graph LR A(RE) --Thompson<br>算法--> B(NFA) B --子集构造算法--> C(DFA) C --Hopcroft<br>最小化算法--> D>词法分析器代码]

6、RE到NFA：Thompson算法

正则表达式到非确定有限状态自动机: Thompson算法

  • 基于对RE的结构做归纳（数学归纳法）
    • 对基本的RE直接构造（2种）
    • 对复合的RE递归构造（3种）
  • 递归算法，容易实现
    • 在我们的实现里，不到100行的C代码

image-20210304224238881.png

image-20210304224247931.png

【例】$a(b|c)*$

graph LR Begin( ) --> A A(0) --a--> B((1)) B --ε--> C((2)) C --ε--> D((3)) D --ε--> E((4)) E --b--> G((5)) D --ε--> F((6)) F --c--> H((7)) G --ε--> Y((8)) H --ε--> Y Y --ε--> D Y --ε--> Z(9) C --ε--> Z

7、NFA到DFA：子集构造算法

NFA->DFA：子集构造算法

算法思想

【例】$a(b|c)*$

使用Thompson算法构造的NFA：

graph LR Begin( ) --> A A(n0) --a--> B((n1)) B --ε--> C((n2)) C --ε--> D((n3)) D --ε--> E((n4)) E --b--> G((n5)) D --ε--> F((n6)) F --c--> H((n7)) G --ε--> Y((n8)) H --ε--> Y Y --ε--> D Y --ε--> Z(n9) C --ε--> Z

此时边上转移包含 $\varepsilon$（代价为0），即转移是不确定的，现在要转换成等价的DFA：

$n0\overset{a}{\rightarrow} n1$

  • $n1 \to n2$代价为0，以此推算 $n0$ 可以无代价走到 $n1,n2,n3,n4,n6,n9$；

  • 此时令集合 $q1 = \left \{n1,n2,n3,n4,n6,n9\right \}$，即 $n0\overset{a}{\rightarrow} q1$；

下面再从 $q1$ 出发：

  • $q1\overset{b}{\rightarrow} \left \{ n5,n8,n9,n3,n4,n6 \right \}:q2$
  • $q1\overset{c}{\rightarrow} \left \{ n7,n8,n9,n3,n4,n6 \right \}:q3$

从 $q2$ 出发：$q2\overset{...}{\rightarrow} \left \{ ... \right \}$

依次类推求出所有子集，构造出 $n0 \overset{a}{\rightarrow} q1 \overset{b}{\rightarrow} q2 ......$，实现从NFA转化为DFA

在新的DFA里面，$q1,q2$ 其实都是接收状态

两个重要操作，称为ε-闭包

  • 状态转换
  • 对每个集合求边界

子集构造算法（工作表算法）

q0 <- eps_closure(n0) // 计算n0能到达的地方
Q <- {q0} // 构造状态集
workList <- q0 // 队列
while (workList != []) // BFS
    remove q from workList
    foreach (character c)
        t <- eps_closure(delta(q, c)) 
        D[q, c] <- t
        if (t \not\in Q)
            add t to Q and workList

对于上述例子来说：

  • $q0= \left \{ n0 \right \}$；

  • $q1 =t= \left \{ n1,n2,n3,n4,n6,n9\right \}$；

  • $q2 = \left \{ n5.n8,n9,n3,n4,n6 \right \}$；

  • $q3 = \left \{ n7,n8,n9,n3,n4,n6 \right \}$；

  • $Q = \left \{ q0,q1,q2,q3 \right \}$

graph LR A((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C

接受状态为：$q1,q2,q3$。

不动点算法

  • 算法为什么能够运行终止

时间复杂度

  • 最坏情况$O(2^n)$
  • 但在实际中不常发生
    • 因为并不是每个子集都会出现

ε-闭包的计算

深度优先方法

set closure = {};
void eps_closure (x)
    closure += {x}
    foreach (y: x--ε--> y)
        if (!visited(y))
            eps_closure (y)

广度优先方法

set closure = {};
Q = []; // queue
void eps_closure (x) =
    Q = [x];
    while (Q not empty)
        q <- deQueue (Q)
        closure += q
        foreach (y: q----> y)
        if (!visited(y))
            enQueue (Q, y)

8、DFA的最小化：Hopcroft算法

【例】DFA的$a(b|c)*$

graph LR A((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C

现在考虑合并：同样为接受状态/非接受状态

  • 合并$q2,q3$：
graph LR A((q0)) --a--> B(q1) B --b--> C(q4) B --c--> C C --b,c--> C
  • 合并$q1,q4$，此时结构图正好诠释了$a(b|c)*$：
graph LR A((q0)) --a--> B(q5) B --b,c--> B

这样的话可以占用更少的计算机资源

Hopcroft算法：基于等价类的思想

split(S)
    foreach (character c)
        if (c can split S)
            split S into T1, …, Tk

hopcroft ()
    split all nodes into N, A // 两个等价类：接受状态和非接受状态
    while (set is still changes)
        split(S)

如图，split 相当于将 $s1$ 切分成 $s2$ 和 $s3$

graph LR subgraph s1 A B C end subgraph s2 D E end subgraph s3 F end A --a--> D B --a--> E C --a--> F

【例1】对于DFA的$a(b|c)*$，根据Hopcroft的思想：

首先我们分出两个集合：$N $ 和 $A$

graph LR subgraph N Aa end subgraph A B C D end Aa((q0)) --a--> B(q1) B --b--> C(q2) B --c--> D(q3) C --b--> C D --c--> D C --c--> D D --b--> C

对于集合 $N$，不可再分；对于集合 $A$：可以接受 $b, c$ 两种不同字符，但总的来看不管怎么转换都是 $A$，即无法再分

graph LR A((q0)) --a--> B(q4) B --b,c--> B

【例2】如图

graph LR q0((q0)) --f--> q1((q1)) q1 --e--> q2((q2)) q1 --i--> q4((q4)) q2 --e--> q3(q3) q4 --e--> q5(q5)

则其对应的正则表达式为：$fee|fie = f(ee|ie)$

首先切分成两个集合：

graph LR subgraph N q0 q1 q2 q4 end subgraph A q3 q5 end q0((q0)) --f--> q1((q1)) q1 --e--> q2((q2)) q1 --i--> q4((q4)) q2 --e--> q3(q3) q4 --e--> q5(q5)

对于集合$A$，$q3,q5$ 无法区分，此集合不可分裂

对于集合$N$，到第三个字符 $e$ 时，$q2,q4$到$A$，但$q0, q1$还在内部，划分集合：

$S1=\left \{ q0,q1 \right \},S2=\left \{ q2,q4 \right \},A=\left \{ q3,q5 \right \}$

对于$S1$：都能接受$e$，且都可转换到$A$，不可再分

再看$S2$：$q0$不接受$e$，$q1$接受$e$后会转换到$S2$，拆分

最后得：

graph LR q0((q0)) --f--> q1((q1)) q1 --e--> S((q2,q4)) q1 --i--> S S --e--> A(q3,q5)

9、DFA的代码表示

  • 概念上讲，DFA是一个有向图

  • 实际上，有不同的DFA的代码表示

    • 转移表 (类似于邻接矩阵)
    • 哈希表
    • 跳转表
    • ......

  • 取决于在实际实现中，对时间空间的权衡

转移表

对于$a(b|c)*$

graph LR A((q0)) --a--> B(q1) B --b,c--> B
状态/字符 a b c
0 1
1 1 1 
int table[M][N];
table[0]['a'] = 1;
table[1]['b'] = 1;
table[1]['c'] = 1;
// other table entries are ERROR
graph LR A[转移表] <--> B[词法分析驱动代码]

驱动代码：

nextToken()
    state = 0 // 自动机目前走到的状态
    stack = [] // 用于实现最长匹配
    while (state != ERROR)
        c = getChar()
        if (state is ACCEPT)
            clear(stack)
        push(state)
        state = table[state][c]

    while(state is not ACCEPT)
        state = pop();
        rollback();

跳转表

nextToken()
    state = 0
    stack = []
    goto q0

q0:
    c = getChar()
    if (state is ACCEPT)
        clear (stack)
    push (state)
    if (c==‘a’)
        goto q1:

q1:
    c = getChar()
    if (state is ACCEPT)
        clear (stack)
    push (state)
    if (c==‘b’||c==‘c’)
        goto q1