词法分析（英语：lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

词法分析

词法分析的任务

字符流到记号流

字符流:
- 和被编译的语言密切相关(ASCII, Unicode, or ..)
记号流:
- 编译器内部定义的数据结构，编码所识别出的词法单元

记号的数据结构定义

enum kind {IF, LPAREN, ID, INTLIT, ...};
struct token {
    enum kind k;
    char *lexeme;
};

词法分析器--手工构造法

至少两种实现方案:

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

转移图

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 = getChar();
            switch (c): // similar

标识符的转移图

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, ...

关键字表算法

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

正则表达式

对给定的字符集∑={c1, c2, ..., cn}
归纳定义：
- 空串ε是正则表达式
- 对于任意c∈∑，c是正则表达式
- 如果M和N是正则表达式, 则以下也是正则表达式
  - 选择 M | N = {M, N}
  - 连接 MN = {mn | m∈M, n∈N}
  - 闭包 M* = {ε, M, MM, MMM, ...}

语法糖

可以引入更多的语法糖，来简化构造
- [c1-cn] == c1|c2|...|cn
- e+ == 一个或多个e
- e? == 零个或一个e
- “a” == a 自身, 不是a的Kleen闭包
- e{i, j} == i到j个e的连接
- . == 除‘\n’外的任意字符

有限状态自动机

确定状态有限自动机DFA
- 对任意的字符，最多有一个状态可以转移
  - δ: S x Σ → S
非确定的有限状态自动机NFA
- 对任意的字符，有多于一个状态可以转移
  - δ: S x (Σ∪ε) → 2^S （幂集）

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

Thompson 算法

基于对RE的结构做归纳
- 对基本的RE直接构造
- 对复合的RE递归构造
递归算法，容易实现

NFA 到 DFA

子集构造算法

/* 子集构造算法：工作表算法 */
q0 <- eps_closure(n0)
Q <- { q0 }
workList <- q0
while (workList != [])
  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

对算法的讨论

不动点算法
- 算法为什么能够运行终止
时间复杂度
- 最坏情况 O(2N)
- 但在实际中不常发生
  - 因为并不是每个子集都会出现

ε 的闭包运算

深度优先

/* 基于深度优先遍历的算法 */
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)

DFA 的最小化

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)

算法的讨论

- 最坏情况O(2N)？
- 实际中运行可能会更快
  - 因为并不是每个子集都会分裂

DFA 的代码表示

概念上讲, DFA是一个有向图
实际上，有不同的DFA的代码表示
- 转移表(类似于邻接矩阵)
- 哈希表
- 跳转表
取决于在实际实现中，对时间空间的权衡

转移表

驱动代码

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

不一定每天 code well 但要每天 live well

词法分析

词法分析

词法分析的任务

记号的数据结构定义

词法分析器--手工构造法

转移图

标识符的转移图

标识符和关键字

关键字表算法

正则表达式

语法糖

有限状态自动机

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

Thompson 算法

NFA 到 DFA

子集构造算法

对算法的讨论

ε 的闭包运算

深度优先

广度优先

DFA 的最小化

Hopcroft 算法

算法的讨论

DFA 的代码表示

转移表

驱动代码

继续阅读