詞法分析（英語：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 的代碼表示

轉移表

驅動代碼

繼續閱讀