編譯原理-詞法分析(手動(dòng)實(shí)現(xiàn)正則表達(dá)式j(luò)ava)

本篇文章內(nèi)的源碼: 這里

大家都知道編譯的第一步就是詞法分析吏奸，將字符串轉(zhuǎn)換成一個(gè)個(gè) Token 荧飞，然后再根據(jù)這些 Token 構(gòu)建抽樣語法樹(AST)摄凡。
而進(jìn)行詞法分析就必須用到正則表達(dá)式，本篇文章就是分析正則表達(dá)式實(shí)現(xiàn)原理，以及使用 java 語言實(shí)現(xiàn)一個(gè)簡單的正則表達(dá)式。

說起正則表達(dá)式啊斋荞，想起筆者剛學(xué)完 java 的時(shí)候去找工作，面試的時(shí)候虐秦，聽到有一個(gè)老員工在說平酿，這個(gè)匹配郵箱的正則怎么寫啊悦陋？那個(gè)時(shí)候我心里在想蜈彼，這個(gè)員工水平怎么這么低，連個(gè)正則都不會(huì)寫啊俺驶。
后來才明白是我太年輕了啊幸逆，工作幾年我也連正則不會(huì)寫了，全都忘光了啊痒钝，遇到要匹配的公式都是臨時(shí)去網(wǎng)上查啊秉颗。

一. 正則表達(dá)式

1.1 正則語言

語言的定義:
由文法 G的開始符號(hào) S推導(dǎo)出的所有句子構(gòu)成的集合稱為文法G生成的語言，記為L(G)送矩。
公式就是: L(G)={w∣S ?* w, w∈VT*}

S ?* w 表示從文法 G的開始符號(hào) S 經(jīng)過若干(可以是0)步推導(dǎo)到底一個(gè)文法符號(hào)串 w 蚕甥。
如果這個(gè)文法符號(hào)串 w ( w ∈ (VN∪VT)* )，串里面既有終結(jié)符又有非終結(jié)符栋荸；那么 w 就是文法 G 的一個(gè)句型菇怀。
如果這個(gè)文法符號(hào)串 w ( w∈(VT)* )凭舶，串里面只有終結(jié)符；那么 w 就是文法 G 的一個(gè)句子爱沟。從這里看句子就是一個(gè)特殊的句型帅霜。

{} 符號(hào)在這里是數(shù)學(xué)上集合的意思，也就是代表所有句子的集合呼伸。

正則語言就是由正則文法的開始符號(hào) S推導(dǎo)出的所有句子構(gòu)成的集合身冀。
例如:
有一個(gè)正則文法 S→aB; B→aB; B→bB; B→ε 有這四個(gè)產(chǎn)生式。
它能生成的句子就是由 a 加上0次或者多次的 ab 串括享；即為 L(G)={a}{a, b}* 搂根。
正則表達(dá)式（Regular Expression, RE）是一種用來描述正則語言的更緊湊的表示方法。

上面那個(gè)公式可以用正則表達(dá)式 r 表示, 即 r = a(a∣b)*

正則文法和正則表達(dá)式

對(duì)任何正則文法 G铃辖，存在定義同一語言的正則表達(dá)式 r剩愧；
對(duì)任何正則表達(dá)式 r，存在生成同一語言的正則文法 G娇斩。

1.2 正則表達(dá)式的定義

通過正則表達(dá)式 r 所生成的句子集合也就是正則語言仁卷，即為 L(G)

例如 r=a , 這是一個(gè)正則表達(dá)式， a 是一個(gè)終結(jié)符犬第；那么對(duì)應(yīng)的語言 L(G)={a} 锦积。L(G) 語言的終結(jié)符串集合中只有一個(gè)元素a。

1.2.1 定義

設(shè) ∑ 是一個(gè)字母表瓶殃，則 ∑ 上的正則表達(dá)式及其所表示的正則語言可遞歸地定義如下：

ε 是一個(gè)正則表達(dá)式( r = ε)充包，則L(ε) = {ε}
a 是字母表∑ 上一個(gè)字符，它也是一個(gè)正則表達(dá)式( r = a)遥椿，則L(a) = {a}
假設(shè) r 和s都是字母表∑ 上一個(gè)字符,也都是簡單的正則表達(dá)式(r=r, r=s),那么它們對(duì)應(yīng)的語言分別是 L(r) 和 L(s)，則有下面公式:
1 . r∣s 是一個(gè)正則表達(dá)式 RE, 則 L(r|s) = L(r) U L(s)淆储。（并操作）
2 . rs 是一個(gè)正則表達(dá)式RE, 則 L(rs) = L(r)L(s)冠场。（連接操作）
3 . r* 是一個(gè)正則表達(dá)式RE, 則 L(r) = (L(r))。 (克林閉包操作）
4 . (r) 是一個(gè)正則表達(dá)式RE, 則 L((r)) = (L(r)) = L(r)本砰。

運(yùn)算符的優(yōu)先級(jí)為：() >* > &(連接操作)>|(并操作)
一般大的正則表達(dá)式是可以由小的正則表達(dá)式按照特定規(guī)則遞歸地構(gòu)建而成的碴裙。遞歸規(guī)則就是上面四個(gè)操作。
也就是說点额，一個(gè)正則表達(dá)式可以分解為多個(gè)小的正則表達(dá)式舔株，這個(gè)概念要記住，正則表達(dá)式轉(zhuǎn)換成非確定有窮自動(dòng)機(jī) NFA 就是靠這個(gè)特性还棱。

例如一個(gè)簡單例子:
如果字母表 ∑ = {a,b},那么

L(a|b) = L(a) ∪ L(b) = {a} ∪ 载慈 = {a, b}
L((a∣b)(a∣b)) = L(a∣b) L(a∣b)={a, b} {a, b}={aa, ab, ba, bb}
L(a* ) = (L(a))* = {a}* = {ε, a, aa, aaa, ...}
L((a|b)* ) = (L(a|b))* = {a, b}* = {ε, a, b, aa, ab, ...}
L(a|a* b) = L(a) ∪ L(a* b) = L(a) U ( L(a* ) L(b) ) = {a} U ({a}*) = {a, b, ab, aab, ...}

1.2.2 正則表達(dá)式的代數(shù)定律

定律	描述
r∣s = s∣r	`\|`是可以交換的
r∣(s∣t) = (r∣s)∣t	`\|`是可以結(jié)合的
r(st) = (rs)t	連接是可以結(jié)合的
r(s∣t)= rs∣rt; (s∣t)r=sr∣tr	連接對(duì) `\|` 是可分配的
εr = rε = r	ε是連接的單元
r* = (r∣ε)*	閉包中一定包含ε
r** = r*	*具有冪等性

1.2.3 正則定義

正則定義式具有如下形式的定義序列：

d1→r1
d2→r2
...
dn→rn

有如下規(guī)則:

每個(gè) di 都是一個(gè)新符號(hào)珍手，它們都不在字母表Σ中办铡，而且各不相同辞做。即(d1,d2,...dn都是新符號(hào),不是字母表Σ字符)
每個(gè) ri 的字符都屬于 Σ U {d1,d2,...d(i-1)}。即產(chǎn)生右部的字符 ri寡具，可以字母表Σ 中字符秤茅，和這個(gè)產(chǎn)生式之前產(chǎn)生式左部的字符，即 {d1,d2,...d(i-1)}

例如一般標(biāo)識(shí)符的正則定義:

digit → 0∣1∣2∣...∣9
letter_ → A∣B∣...∣Z∣a∣b∣...∣z∣_
id → letter_(letter_∣digit)*

digit 表示 0-9 中的一個(gè)數(shù)字童叠；letter_ 表示一個(gè)字母或者下劃線框喳；id 表示字母打頭的字母數(shù)字串，就是標(biāo)識(shí)符厦坛。
對(duì)應(yīng)的正則表達(dá)式就是 r = A∣B∣...∣Z∣a∣b∣...∣z∣_( A∣B∣...∣Z∣a∣b∣...∣z∣ _ |0∣1∣2∣...∣9)*

二. 有窮自動(dòng)機(jī)(FA)

2.1 起源與定義

有窮自動(dòng)機(jī)(Finite Automata帖努，F(xiàn)A)由兩位神經(jīng)物理學(xué)家MeCuloch和Pitts于1948年首先提出，是對(duì)一類處理系統(tǒng)建立的數(shù)學(xué)模型粪般；
這類系統(tǒng)具有一系列離散的輸入輸出信息和有窮數(shù)目的內(nèi)部狀態(tài)（狀態(tài)：概括了對(duì)過去輸入信息處理的狀況）拼余；
系統(tǒng)只需要根據(jù)當(dāng)前所處的狀態(tài)和當(dāng)前面臨的輸入信息就可以決定系統(tǒng)的后繼行為。每當(dāng)系統(tǒng)處理了當(dāng)前的輸入后亩歹，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生改變匙监。

簡單理解就是，有窮自動(dòng)機(jī)內(nèi)部有一個(gè)狀態(tài)集合(集合數(shù)量是有限的小作，所以叫有窮的狀態(tài)),當(dāng)它遇到一系列離散的輸入時(shí)亭姥，會(huì)根據(jù)當(dāng)前的狀態(tài)和輸入值，進(jìn)入下一個(gè)狀態(tài)顾稀。也就是說下一個(gè)狀態(tài)只會(huì)由當(dāng)前的狀態(tài)和輸入值來決定达罗。

2.2 轉(zhuǎn)換圖

轉(zhuǎn)換圖.png

圖中的節(jié)點(diǎn)就代表 FA 狀態(tài)，即 0, 1, 2, 3静秆；其中
1 . 0 表示開始狀態(tài)(初始狀態(tài)),有且只有一個(gè)粮揉，由start 箭頭指向。
2 . 3 表示終止?fàn)顟B(tài)（接收狀態(tài)）：可以有多個(gè)抚笔，用雙圈表示扶认。
帶標(biāo)記的箭頭叫做有向邊。

即對(duì)于輸入 a殊橙，存在一個(gè)從狀態(tài)p到狀態(tài)q的轉(zhuǎn)換辐宾，就在p、q之間畫一條有向邊膨蛮，并標(biāo)記上a叠纹。

2.3 有窮自動(dòng)機(jī)對(duì)應(yīng)語言

如果給定輸入串x，有窮自動(dòng)機(jī)(FA)存在一個(gè)對(duì)應(yīng)串x的從初始狀態(tài)到某個(gè)終止?fàn)顟B(tài)的轉(zhuǎn)換序列, 那么該輸入串x 能被該有窮自動(dòng)機(jī)(FA)接收敞葛。

那么由一個(gè)有窮自動(dòng)機(jī)(FA)接收的所有串構(gòu)成的集合, 就稱為該有窮自動(dòng)機(jī)(FA)對(duì)應(yīng)的語言誉察，記為 L(M)，其中制肮，M表示的是 Machine冒窍。

注: 有窮自動(dòng)機(jī)(FA)接收輸入串x递沪，遵循最長子串匹配原則(Longest String Matching Principle）

最長子串匹配原則(Longest String Matching Principle）

當(dāng)輸入串的多個(gè)前綴與一個(gè)或多個(gè)模式匹配時(shí)，總是選擇最長的前綴進(jìn)行匹配综液。
在到達(dá)某個(gè)終態(tài)之后款慨，只要輸入帶上還有符號(hào)，DFA就繼續(xù)前進(jìn)谬莹，以便尋找盡可能長的匹配檩奠。

2.4 有窮自動(dòng)機(jī)公式

M=(S, Σ, δ, s0, F)

S : 表示有窮狀態(tài)的集合。
Σ : 表示輸入字母表附帽，即輸入符號(hào)集合埠戳。
δ : 表示一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)。對(duì)于任一狀態(tài) s蕉扮，遇到任一輸入符號(hào)a ,得到的下一個(gè)狀態(tài)整胃。

即當(dāng)s∈S, a∈Σ時(shí)，δ(s,a)表示從狀態(tài)s出發(fā)喳钟，沿著標(biāo)記為a的邊所能到達(dá)的狀態(tài)屁使。
注: 如果是 DFA ，那么這里就是下一個(gè)狀態(tài)奔则；如果是 NFA ,那么這里就是下一個(gè)狀態(tài)集合蛮寂。

s0 : 開始狀態(tài)(或初始狀態(tài)), s0∈S
F ：接收狀態(tài)（或終止?fàn)顟B(tài)）集合，F(xiàn)?S易茬。

注: 根據(jù) δ 公式酬蹋，對(duì)于當(dāng)前狀態(tài) s ，遇到輸入字符 a 時(shí)抽莱，返回是單一狀態(tài)范抓，還是狀態(tài)集合，將有窮自動(dòng)機(jī)分為確定的有窮自動(dòng)機(jī)(DFA) 和非確定的有窮自動(dòng)機(jī)(NFA)

三. 非確定的有窮自動(dòng)機(jī)(NFA)

NFA 就是當(dāng)前狀態(tài)s 遇到輸入符號(hào)a 時(shí)岸蜗，得到是下一個(gè)狀態(tài)集合尉咕。也就是說，它不確定下一個(gè)狀態(tài)是什么璃岳，所以叫做非確定的有窮自動(dòng)機(jī)。
先說 NFA 的原因是因?yàn)檎齽t表達(dá)式 RE 很容易就轉(zhuǎn)換成 NFA悔捶。這里一般就用到了 Thompson 算法铃慷。

3.1 `Thompson` 算法

Thompson 算法非常簡單，它就是利用了正則表達(dá)式是可以由小的正則表達(dá)式按照特定規(guī)則遞歸地構(gòu)建而成的原理蜕该。

3.1.1 基礎(chǔ)規(guī)則

對(duì)于空串 ε , 即正則表達(dá)式 r = ε , 對(duì)應(yīng) NFA 的轉(zhuǎn)換圖

ε構(gòu)造.png
對(duì)于輸入符號(hào)a , 即正則表達(dá)式 r = a , 對(duì)應(yīng) NFA 的轉(zhuǎn)換圖

a構(gòu)造.png

3.1.2 歸納規(guī)則

對(duì)于正則表達(dá)式 r = a | b犁柜，構(gòu)造為

a|b.png
對(duì)于正則表達(dá)式 r = ab，構(gòu)造為

ab.png
對(duì)于正則表達(dá)式 r = a* , 構(gòu)造為

a*.png

a* 表示0次或者多次堂淡，也可以表示為 a*=a+|ε 馋缅。這里的 a+ 就表示 a 出現(xiàn)一次或者多次扒腕。

通過 Thompson 算法，我們就可以將一個(gè)正則表達(dá)式轉(zhuǎn)成一個(gè)非確定的有窮自動(dòng)機(jī)(NFA) 萤悴。

3.2 代碼實(shí)現(xiàn)(`java`)

代碼的主要功能就是將一個(gè)正則表達(dá)式瘾腰，轉(zhuǎn)換成一個(gè) NFA 的轉(zhuǎn)換圖帖旨。

3.2.1 NFAState 類

package xinhao.regex;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author by xinhao  2021/8/8
 * 表示 NFA 轉(zhuǎn)換圖中的狀態(tài)
 */
public class NFAState implements Comparable<NFAState> {

    // 表示 ε 空串
    public static final String EPSILON = "epsilon";
    private static int idGenerate = 0;
    // 標(biāo)志是狀態(tài)幾
    private int id;
    // NFA 轉(zhuǎn)換圖中寂殉，當(dāng)前狀態(tài)通往下一個(gè)狀態(tài)所有有向邊
    private Map<String, Set<NFAState>> edges;
    // 表示當(dāng)前狀態(tài)是不是終止?fàn)顟B(tài)
    private boolean isEnd;

    public NFAState() {
    }

    // 創(chuàng)建狀態(tài)節(jié)點(diǎn)
    public static NFAState create() {
        NFAState state = new NFAState();
        state.id = idGenerate++;
        state.edges = new HashMap<>();
        return state;
    }

    // 添加當(dāng)前狀態(tài)遇到輸入字符 `path` ，進(jìn)入的一個(gè)狀態(tài)后德。就是其中一條有向邊
    public void addEdge(String path, NFAState nextState) {
        Set<NFAState> set = edges.get(path);
        if (set == null) {
            set = new HashSet<>();
            edges.put(path, set);
        }
        set.add(nextState);
    }

    public Map<String, Set<NFAState>> getEdges() {
        return edges;
    }

    public int getId() {
        return id;
    }

    public boolean isEnd() {
        return isEnd;
    }

    public void setEnd(boolean end) {
        isEnd = end;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("[");
        sb.append("id=").append(id);
        sb.append(']');
        return sb.toString();
    }

    @Override
    public int compareTo(NFAState o) {
        return id - o.id;
    }
}

NFAState 表示 NFA 的轉(zhuǎn)換圖中的狀態(tài)節(jié)點(diǎn)硝全。
那么我們思考一下栖雾，這個(gè)狀態(tài)節(jié)點(diǎn)NFAState應(yīng)該有那些屬性呢?

需要一個(gè) id 屬性來區(qū)分不同的狀態(tài)節(jié)點(diǎn)。
需要一個(gè) isEnd 屬性來表示這個(gè)狀態(tài)節(jié)點(diǎn)是不是終止?fàn)顟B(tài)伟众。
還需要一個(gè) edges 屬性來表示這個(gè)狀態(tài)節(jié)點(diǎn)到達(dá)下一個(gè)節(jié)點(diǎn)的所有有向邊析藕。

對(duì)于 NFA 轉(zhuǎn)換圖來說，當(dāng)前節(jié)點(diǎn)可以匹配多個(gè)輸入符號(hào) (a, b)凳厢，并且對(duì)于同一個(gè)輸入符號(hào) a, 能得到一個(gè)狀態(tài)集合账胧。
所以 edges 定義為 Map<String, Set<NFAState>> 類型。

3.2.2 NFAGraph 類

package xinhao.regex;

/**
 * @author by xinhao  2021/8/8
 * 表示 NFA 對(duì)應(yīng)的轉(zhuǎn)換圖
 */
public class NFAGraph {
    // 開始狀態(tài)節(jié)點(diǎn)
    private NFAState startState;
    // 結(jié)束狀態(tài)節(jié)點(diǎn)数初，注意它不一定是終止?fàn)顟B(tài)找爱，
    // 一般過程圖的結(jié)束狀態(tài)節(jié)點(diǎn)就不是終止?fàn)顟B(tài)，一般最后大轉(zhuǎn)換圖的結(jié)束狀態(tài)才是終止?fàn)顟B(tài)泡孩。
    private NFAState endState;

    private NFAGraph() {
    }

    private NFAGraph(NFAState startState, NFAState endState) {
        this.startState = startState;
        this.endState = endState;
    }

    // 對(duì)應(yīng) Thompson 算法基礎(chǔ)規(guī)則中的车摄，遇到字符 a
    public static NFAGraph createByPath(String path) {
        // 創(chuàng)建開始和終止?fàn)顟B(tài)節(jié)點(diǎn)
        NFAState newStart = NFAState.create();
        NFAState newEnd = NFAState.create();
        // 添加一條開始到終止?fàn)顟B(tài)節(jié)點(diǎn)的有向邊
        newStart.addEdge(path, newEnd);
        return new NFAGraph(newStart, newEnd);
    }

    // 對(duì)應(yīng)操作符 &; 對(duì)應(yīng) Thompson 算法歸納規(guī)則中的連接操作
    public void addSerial(NFAGraph nextGraph) {
        // 將本轉(zhuǎn)換圖的結(jié)束狀態(tài)節(jié)點(diǎn)，添加一個(gè) ε有向邊 連接到下一個(gè)本轉(zhuǎn)換圖開始節(jié)點(diǎn)
        this.endState.addEdge(NFAState.EPSILON, nextGraph.startState);
        // 更新一個(gè)本轉(zhuǎn)換圖的結(jié)束狀態(tài)節(jié)點(diǎn)仑鸥，就得到一個(gè)新的轉(zhuǎn)換圖了吮播。
        this.endState = nextGraph.endState;
    }

    // 對(duì)應(yīng)操作符 |; 對(duì)應(yīng) Thompson 算法歸納規(guī)則中的并操作
    public void addParallel(NFAGraph nextGraph) {
        // 創(chuàng)建新的開始和終止?fàn)顟B(tài)節(jié)點(diǎn)
        NFAState newStart = NFAState.create();
        NFAState newEnd = NFAState.create();
        // 根據(jù) Thompson 算法，我們要添加四條 ε有向邊
        newStart.addEdge(NFAState.EPSILON, this.startState);
        newStart.addEdge(NFAState.EPSILON, nextGraph.startState);
        this.endState.addEdge(NFAState.EPSILON, newEnd);
        nextGraph.endState.addEdge(NFAState.EPSILON, newEnd);

        // 更新本轉(zhuǎn)換圖的開始和結(jié)束狀態(tài)節(jié)點(diǎn)眼俊，得到一個(gè)新的轉(zhuǎn)換圖了意狠。
        this.startState = newStart;
        this.endState = newEnd;
    }

    // 對(duì)應(yīng)操作符 * 即0次以上
    public void repeatStar() {
        // 將 * 分為1次以上和0次
        repeatPlus();
        zero();
    }

    // 對(duì)應(yīng)操作符 + 即一次以上
    public void repeatPlus() {
        // 創(chuàng)建新的開始和終止?fàn)顟B(tài)節(jié)點(diǎn)
        NFAState newStart = NFAState.create();
        NFAState newEnd = NFAState.create();
        // 根據(jù) Thompson 算法，我們要添加三條 ε有向邊
        newStart.addEdge(NFAState.EPSILON, this.startState);
        this.endState.addEdge(NFAState.EPSILON, newEnd);
        this.endState.addEdge(NFAState.EPSILON, this.startState);

        // 更新本轉(zhuǎn)換圖的開始和結(jié)束狀態(tài)節(jié)點(diǎn)疮胖，得到一個(gè)新的轉(zhuǎn)換圖了环戈。
        this.startState = newStart;
        this.endState = newEnd;
    }

    // 對(duì)應(yīng)0次
    public void zero() {
        // 添加 ε有向邊
        this.startState.addEdge(NFAState.EPSILON, this.endState);
    }

    public NFAState getStartState() {
        return startState;
    }

    public NFAState getEndState() {
        return endState;
    }
}

NFAGraph 就是表示 NFA 對(duì)應(yīng)的轉(zhuǎn)換圖。
根據(jù) Thompson 算法, 一個(gè)大的轉(zhuǎn)換圖可以看成由小的轉(zhuǎn)換圖按照一定的規(guī)則構(gòu)建的澎灸。
NFAGraph 就是借助 Thompson 算法來生成一個(gè)轉(zhuǎn)換圖院塞。

重要屬性 : startState 和 endState 表示開始狀態(tài)節(jié)點(diǎn)和結(jié)束狀態(tài)節(jié)點(diǎn)。

這個(gè)結(jié)束狀態(tài)節(jié)點(diǎn) endState 并不一定是轉(zhuǎn)換圖的終止?fàn)顟B(tài)性昭，因?yàn)檫@個(gè) NFAGraph 可能只是整個(gè) NFA 轉(zhuǎn)換圖中的一部分拦止。所以終止?fàn)顟B(tài)是等生成整個(gè) NFA 轉(zhuǎn)換圖后，再進(jìn)行設(shè)置。

createByPath 方法

    // 對(duì)應(yīng) Thompson 算法基礎(chǔ)規(guī)則中的汹族，遇到字符 a
    public static NFAGraph createByPath(String path) {
        // 創(chuàng)建開始和終止?fàn)顟B(tài)節(jié)點(diǎn)
        NFAState newStart = NFAState.create();
        NFAState newEnd = NFAState.create();
        // 添加一條開始到終止?fàn)顟B(tài)節(jié)點(diǎn)的有向邊
        newStart.addEdge(path, newEnd);
        return new NFAGraph(newStart, newEnd);
    }

對(duì)應(yīng) Thompson 算法中基礎(chǔ)規(guī)則

addSerial 方法

   // 對(duì)應(yīng)操作符 &; 對(duì)應(yīng) Thompson 算法歸納規(guī)則中的連接操作
    public void addSerial(NFAGraph nextGraph) {
        // 將本轉(zhuǎn)換圖的結(jié)束狀態(tài)節(jié)點(diǎn)萧求，添加一個(gè) ε有向邊 連接到下一個(gè)本轉(zhuǎn)換圖開始節(jié)點(diǎn)
        this.endState.addEdge(NFAState.EPSILON, nextGraph.startState);
        // 更新一個(gè)本轉(zhuǎn)換圖的結(jié)束狀態(tài)節(jié)點(diǎn)，就得到一個(gè)新的轉(zhuǎn)換圖了顶瞒。
        this.endState = nextGraph.endState;
    }

對(duì)應(yīng) Thompson 算法歸納規(guī)則中的連接操作

addParallel 方法

   // 對(duì)應(yīng)操作符 |; 對(duì)應(yīng) Thompson 算法歸納規(guī)則中的并操作
    public void addParallel(NFAGraph nextGraph) {
        // 創(chuàng)建新的開始和終止?fàn)顟B(tài)節(jié)點(diǎn)
        NFAState newStart = NFAState.create();
        NFAState newEnd = NFAState.create();
        // 根據(jù) Thompson 算法夸政，我們要添加四條 ε有向邊
        newStart.addEdge(NFAState.EPSILON, this.startState);
        newStart.addEdge(NFAState.EPSILON, nextGraph.startState);
        this.endState.addEdge(NFAState.EPSILON, newEnd);
        nextGraph.endState.addEdge(NFAState.EPSILON, newEnd);

        // 更新本轉(zhuǎn)換圖的開始和結(jié)束狀態(tài)節(jié)點(diǎn)，得到一個(gè)新的轉(zhuǎn)換圖了搁拙。
        this.startState = newStart;
        this.endState = newEnd;
    }

對(duì)應(yīng) Thompson 算法歸納規(guī)則中的并操作

repeatStar 方法

// 對(duì)應(yīng)操作符 * 即0次以上
    public void repeatStar() {
        // 將 * 分為1次以上和0次
        repeatPlus();
        zero();
    }

    // 對(duì)應(yīng)操作符 + 即一次以上
    public void repeatPlus() {
        // 創(chuàng)建新的開始和終止?fàn)顟B(tài)節(jié)點(diǎn)
        NFAState newStart = NFAState.create();
        NFAState newEnd = NFAState.create();
        // 根據(jù) Thompson 算法秒梳，我們要添加三條 ε有向邊
        newStart.addEdge(NFAState.EPSILON, this.startState);
        this.endState.addEdge(NFAState.EPSILON, newEnd);
        this.endState.addEdge(NFAState.EPSILON, this.startState);

        // 更新本轉(zhuǎn)換圖的開始和結(jié)束狀態(tài)節(jié)點(diǎn)，得到一個(gè)新的轉(zhuǎn)換圖了箕速。
        this.startState = newStart;
        this.endState = newEnd;
    }

    // 對(duì)應(yīng)0次
    public void zero() {
        // 添加 ε有向邊
        this.startState.addEdge(NFAState.EPSILON, this.endState);
    }

將 Thompson 算法歸納規(guī)則中 * 操作酪碘，拆分成兩個(gè)方法。

3.2.3 正則表達(dá)式生成 `NFAGraph`

NFAGraph 就表示 NFA 對(duì)應(yīng)的轉(zhuǎn)換圖盐茎，那么如何通過正則表達(dá)式生成對(duì)應(yīng)的 NFAGraph 實(shí)例呢?

例如對(duì)于一個(gè)正則表達(dá)式 r = a(b|c)* 兴垦，它表示一個(gè)以 a 開頭后面跟著0個(gè)或多個(gè) bc 串。

首先要逐個(gè)讀取這個(gè)正則表達(dá)式 a(b|c)* , 生成對(duì)應(yīng)的小的 NFAGraph 實(shí)例字柠，然后根據(jù)規(guī)則生成大的 NFAGraph 實(shí)例探越。

必須注意運(yùn)算符的優(yōu)先級(jí): () > * > &(連接操作)> |(并操作)

3.2.3.1 Reader 類

public class Reader {

    public static Reader create(String regex) {
        Reader reader = new Reader();
        reader.source = regex.toCharArray();
        return reader;
    }

    // 正則表達(dá)式對(duì)應(yīng)的字符數(shù)組
    private char[] source;
    // 記錄已經(jīng)讀取字符的下標(biāo)
    private int pos;

    // 查看對(duì)應(yīng)下標(biāo)的字符， pos 不增加
    public char peek() {
        return source[pos];
    }

    // 獲取pos下標(biāo)對(duì)應(yīng)的字符窑业， 并將 pos 增加 1
    public char next() {
        if (pos >= source.length) {
            throw new RuntimeException("下標(biāo)越界 length:" + source.length + " pos:" + pos);
        }
        return source[pos++];
    }

    // 是否還有下一個(gè)字符
    public boolean hasNext() {
        return pos < source.length;
    }

    // 一直讀取到字符 ch
    public String readUntil(char ch) {
        StringBuilder builder = new StringBuilder();
        while (peek() != ch) {
            builder.append(next());
        }
        // 不包括 ch
        next();
        return builder.toString();
    }

    // 讀取剩下的字符串
    public String readUntilEnd() {
        StringBuilder builder = new StringBuilder();
        while (hasNext()) {
            builder.append(next());
        }
        return builder.toString();
    }
}

這個(gè)類就是用來逐個(gè)讀取正則表達(dá)式的字符钦幔。
readUntil 方法用來尋找正則表達(dá)式子串的，例如 () 里面包括的子串常柄。
readUntilEnd 方法讀取剩下的字符串鲤氢，用來生成對(duì)應(yīng)的 NFAGraph 實(shí)例，再與前面的 NFAGraph 實(shí)例進(jìn)行規(guī)制合并西潘，采用不斷遞歸的方法卷玉，就可以生成完整的 NFAGraph 轉(zhuǎn)換圖了。

3.2.3.2 `createNFAGraph` 生成 `NFAGraph` 轉(zhuǎn)換圖

    /**
     * 通過 pattern 生成對(duì)應(yīng)的 NFAGraph 轉(zhuǎn)換圖
     * @param pattern
     * @return
     */
    public static NFAGraph createNFAGraph(String pattern) {
        Reader reader = Reader.create(pattern);
        NFAGraph graph = null;
        while (reader.hasNext()) {
            char ch = reader.next();
            switch (ch) {
                case '(' :
                    // 通過遞歸的方法喷市，生成子串對(duì)應(yīng)的 NFAGraph 轉(zhuǎn)換圖
                    NFAGraph subGraph = createNFAGraph(reader.readUntil(')'));
                    // 因?yàn)?* ? + 這些符號(hào)的優(yōu)先級(jí)比 連接 高相种，就先處理
                    handleStar(subGraph, reader);
                    // 進(jìn)行規(guī)制合并 NFAGraph 轉(zhuǎn)換圖
                    if (graph == null) {
                        graph = subGraph;
                    } else {
                        // 進(jìn)行 連接 操作
                        graph.addSerial(subGraph);
                    }
                    break;
                case '|' :
                    // 通過遞歸的方法，生成子串對(duì)應(yīng)的 NFAGraph 轉(zhuǎn)換圖
                    NFAGraph nextGraph = createNFAGraph(reader.readUntilEnd());
                    // 這里不需要處理  * ? + 這些符號(hào)品姓，因?yàn)?reader.readUntilEnd() 已經(jīng)讀取了剩余的全部字符寝并，不會(huì)有這些符號(hào)了。
                    if (graph == null) {
                        graph = nextGraph;
                    } else {
                        // 進(jìn)行 并 操作
                        graph.addParallel(nextGraph);
                    }
                    break;
                default:
                    // 根據(jù)字符ch 生成一個(gè)小的 NFAGraph 轉(zhuǎn)換圖
                    NFAGraph pathGraph = NFAGraph.createByPath("" + ch);
                    // 因?yàn)?* ? + 這些符號(hào)的優(yōu)先級(jí)比 連接 高腹备，就先處理
                    handleStar(pathGraph, reader);
                    if (graph == null) {
                        graph = pathGraph;
                    } else {
                        // 進(jìn)行 連接 操作
                        graph.addSerial(pathGraph);
                    }
                    break;
            }
        }

        return graph;
    }

    /**
     * 處理  * ? + 這些符號(hào)優(yōu)先級(jí)
     * @param subGraph
     * @param reader
     * @return
     */
    private static NFAGraph handleStar(NFAGraph subGraph, Reader reader) {
        if (reader.hasNext()) {
            char ch = reader.peek();
            switch (ch) {
                case '*' :
                    // 0次或多次
                    subGraph.repeatStar();
                    reader.next();
                    break;
                case '?' :
                    // 0次 或 1 次
                    subGraph.zero();
                    reader.next();
                    break;
                case '+' :
                    // 1次以上
                    subGraph.repeatPlus();
                    reader.next();
                    break;
            }
        }
        return subGraph;
    }

可以看出我們采用遞歸調(diào)用的方法食茎，由小的 NFAGraph 轉(zhuǎn)換圖合并成一個(gè)完整的 NFAGraph 轉(zhuǎn)換圖。

3.2.3.3 `printNFAGraphByBFS` 查看生成的圖 `NFAGraph`

    /**
     * 采用廣度優(yōu)先遍歷的方式馏谨，來打印這個(gè) NFAGraph 轉(zhuǎn)換圖中的有向邊
     * @param nfaGraph
     */
    public static void printNFAGraphByBFS(NFAGraph nfaGraph) {
        // 采用廣度優(yōu)先遍歷的算法，需要一個(gè)先入先出的隊(duì)列數(shù)據(jù)結(jié)構(gòu)來輔助
        Queue<NFAState> queue = new LinkedList<>();
        // 因?yàn)?NFAGraph 是一個(gè)圖結(jié)構(gòu)附迷，而不是一個(gè)樹結(jié)構(gòu)惧互，所以它的邊不是單向的哎媚，存在循環(huán)指向的問題；
        // 因此我們需要一個(gè) addedSet 集合來記錄喊儡，已經(jīng)添加到queue 隊(duì)列中的節(jié)點(diǎn)拨与，否則可能會(huì)進(jìn)入死循環(huán)。
        // 注: 這里只要是添加到 queue 的節(jié)點(diǎn)艾猜，就馬上添加到 addedSet 集合中买喧。
        Set<NFAState> addedSet = new HashSet<>();
        queue.add(nfaGraph.getStartState());
        addedSet.add(nfaGraph.getStartState());

        StringBuilder builder = new StringBuilder();
        while (!queue.isEmpty()) {
            NFAState state = queue.poll();
            builder.append("狀態(tài)"+state+":");
            for (Map.Entry<String, Set<NFAState>> entry : state.getEdges().entrySet()) {
                String path = entry.getKey();
                Set<NFAState> stateSet = entry.getValue();
                builder.append("\t路徑["+path+"]有"+stateSet.size()+"條: ");
                for (NFAState childState : stateSet) {
                    // 如果沒有添加過，那么就添加到 queue 隊(duì)列中
                    if (!addedSet.contains(childState)) {
                        queue.add(childState);
                        addedSet.add(childState);
                    }
                    builder.append(state);
                    builder.append("--"+path+"-->");
                    builder.append(childState);
                    builder.append(";\t");
                }
                builder.append("\n\t\t\t");
            }
            builder.append("\n");
        }

        System.out.print(builder.toString());
    }

采用廣度優(yōu)先遍歷的方式匆赃，來查看生成 NFAGraph 轉(zhuǎn)換圖的情況淤毛。

3.2.3.4 簡單例子

    public static void main(String[] args) {
        String pattern = "a(b|c)*";

        NFAGraph graph = createNFAGraph(pattern);
        // 設(shè)置轉(zhuǎn)換圖的結(jié)束狀態(tài)節(jié)點(diǎn) 就是終止?fàn)顟B(tài)節(jié)點(diǎn)
        graph.getEndState().setEnd(true);

        printNFAGraphByBFS(graph);
}

輸出結(jié)果:

狀態(tài)[id=0]:   路徑[a]有1條: [id=0]--a-->[id=1];   
            
狀態(tài)[id=1]:   路徑[epsilon]有1條: [id=1]--epsilon-->[id=8];   
            
狀態(tài)[id=8]:   路徑[epsilon]有2條: [id=8]--epsilon-->[id=6];   [id=8]--epsilon-->[id=9];   
            
狀態(tài)[id=6]:   路徑[epsilon]有2條: [id=6]--epsilon-->[id=4];   [id=6]--epsilon-->[id=2];   
            
狀態(tài)[id=9]:
狀態(tài)[id=4]:   路徑[c]有1條: [id=4]--c-->[id=5];   
            
狀態(tài)[id=2]:   路徑[b]有1條: [id=2]--b-->[id=3];   
            
狀態(tài)[id=5]:   路徑[epsilon]有1條: [id=5]--epsilon-->[id=7];   
            
狀態(tài)[id=3]:   路徑[epsilon]有1條: [id=3]--epsilon-->[id=7];   
            
狀態(tài)[id=7]:   路徑[epsilon]有2條: [id=7]--epsilon-->[id=6];   [id=7]--epsilon-->[id=9];

與我們手動(dòng)寫出來 a(b|c)* 對(duì)應(yīng)的轉(zhuǎn)換圖是一樣的。

3.2.3.5 進(jìn)行字符串的匹配

我們已經(jīng)將正則表達(dá)式生成對(duì)應(yīng) NFA 的轉(zhuǎn)換圖了算柳，那么我們?nèi)绾芜M(jìn)行匹配呢?

根據(jù)定義我們知道低淡，所謂的匹配就是對(duì)于一個(gè)待匹配的輸入字符串 s，在 NFA 的對(duì)應(yīng)轉(zhuǎn)換圖中瞬项，找到一個(gè)從開始狀態(tài)節(jié)點(diǎn)到終止?fàn)顟B(tài)節(jié)點(diǎn)的轉(zhuǎn)換序列蔗蹋；
如果能找到就是匹配，否則就是不匹配囱淋。

因?yàn)? NFA 的轉(zhuǎn)換圖中猪杭，當(dāng)前狀態(tài)節(jié)點(diǎn)遇到輸入字符對(duì)應(yīng)的下一個(gè)狀態(tài)節(jié)點(diǎn)可能有多個(gè)，因此我們可能要對(duì)所有可能的情況進(jìn)行嘗試妥衣，直到找到對(duì)應(yīng)的轉(zhuǎn)換序列皂吮。
其實(shí)對(duì)于整個(gè)匹配過程，需要注意三點(diǎn):

對(duì)于輸入字符串 s 称鳞， NFA 的轉(zhuǎn)換圖能夠匹配完它的所有字符涮较，那就要看最后的狀態(tài)節(jié)點(diǎn)是不是終止?fàn)顟B(tài)的節(jié)點(diǎn)。
對(duì)于輸入字符串 s , NFA 的轉(zhuǎn)換圖不能夠匹配完它的所有字符冈止，即NFA 的轉(zhuǎn)換圖已經(jīng)遍歷完了狂票，卻不能匹配輸入字符串 s 所有字符。
轉(zhuǎn)換圖遵循最長子串匹配原則熙暴，所以優(yōu)先匹配空邊(ε 有向邊)``

 /**
     * 對(duì)于一個(gè)輸入字符串 regex , 在轉(zhuǎn)換圖 NFAGraph 中能否找到一個(gè)從初始狀態(tài)到某個(gè)終止?fàn)顟B(tài)的轉(zhuǎn)換序列闺属。
     * 能找到，返回ture周霉，表示能匹配
     * @param graph  轉(zhuǎn)換圖
     * @param regex  待匹配的字符串
     * @param recordState  記錄一下匹配的路徑
     * @return
     */
    public static boolean isMatch(NFAGraph graph, String regex, RecordNFAState recordState) {
        return isMatch(graph.getStartState(), regex.toCharArray(), 0, recordState);
    }

    /**
     * 通過遞歸調(diào)用來決定是否匹配
     * @param currentState
     * @param chars
     * @param pos
     * @param recordState
     * @return
     */
    public static boolean isMatch(NFAState currentState, char[] chars, int pos, RecordNFAState recordState) {

        // 當(dāng) pos == chars.length 時(shí)掂器，表示已經(jīng)匹配完最后一個(gè)字符。
        // 接下來就是看能否得到終止?fàn)顟B(tài)的節(jié)點(diǎn)
        if (pos == chars.length) {
            // 得到當(dāng)前節(jié)點(diǎn)currentState 的 所有 ε 有向邊俱箱。
            // 因?yàn)?FA 有最長子串匹配原則国瓮，所以優(yōu)先先找空邊(ε 有向邊) 對(duì)應(yīng)狀態(tài)節(jié)點(diǎn)是不是終止?fàn)顟B(tài)的節(jié)點(diǎn)
            Set<NFAState> epsilonSet = currentState.getEdges().getOrDefault(NFAState.EPSILON, EMPTY);
            for (NFAState state : epsilonSet) {
                // 記錄一下當(dāng)前匹配路徑
                recordState.setNextByPath(NFAState.EPSILON, state);
                // 遞歸調(diào)用 isMatch 方法，來判斷是否匹配
                if (isMatch(state, chars, pos, recordState.getNext())) {
                    // 如果匹配，則直接返回 true
                    return true;
                }
            }

            // 當(dāng)前節(jié)點(diǎn)是終止?fàn)顟B(tài)的節(jié)點(diǎn)乃摹，那么匹配成功禁漓，返回 true
            if (currentState.isEnd()) {
                return true;
            }

            // 如果以上都不匹配，而且已經(jīng)匹配完最后一個(gè)字符孵睬，那么就說明這個(gè) currentState 對(duì)應(yīng)的匹配轉(zhuǎn)換序列是不成功的播歼。
            // 返回 false
            return false;
        }


        // 如果還沒有匹配完所有的輸入字符，那么就先匹配輸入字符掰读。

        // 優(yōu)先匹配空邊 (ε 有向邊) 對(duì)應(yīng)狀態(tài)節(jié)點(diǎn)
        Set<NFAState> epsilonSet = currentState.getEdges().getOrDefault(NFAState.EPSILON, EMPTY);
        for (NFAState state : epsilonSet) {
            // 記錄一下當(dāng)前匹配路徑
            recordState.setNextByPath(NFAState.EPSILON, state);
            // 遞歸調(diào)用 isMatch 方法秘狞，來判斷是否匹配
            // 這里 pos 沒有任何變化，因?yàn)槭强者?(ε 有向邊)蹈集，沒有匹配任何字符
            if (isMatch(state, chars, pos, recordState.getNext())) {
                return true;
            }
        }

        String path = "" + chars[pos];
        // 當(dāng)前節(jié)點(diǎn)的有向邊集合中是否包含當(dāng)前輸入字符烁试，
        if (currentState.getEdges().containsKey(path)) {
            // 得到當(dāng)前輸入字符對(duì)應(yīng)的有向邊集合
            Set<NFAState> pathSet = currentState.getEdges().getOrDefault(path, EMPTY);
            for (NFAState state : pathSet) {
                // 記錄一下當(dāng)前匹配路徑
                recordState.setNextByPath(path, state);
                // 當(dāng)前節(jié)點(diǎn)能不能找到一條匹配轉(zhuǎn)換序列匹配剩下輸入字符；
                // 這里將 pos + 1, 因?yàn)楫?dāng)前 pos 對(duì)應(yīng)的輸入字符已經(jīng)匹配
                if (isMatch(state, chars, pos + 1, recordState.getNext())) {
                    return true;
                }
            }
        }
        return false;
    }

方法流程已經(jīng)在代碼中標(biāo)注清晰了雾狈。
RecordNFAState 類只是用來記錄匹配轉(zhuǎn)換序列廓潜。

package xinhao.regex;


/**
 * @author by xinhao  2021/8/8
 * 記錄一下匹配轉(zhuǎn)換序列
 */
public class RecordNFAState {
    // 當(dāng)前狀態(tài)節(jié)點(diǎn)
    private NFAState state;
    // 匹配的下一個(gè)狀態(tài)節(jié)點(diǎn)
    private RecordNFAState next;
    // 使用的匹配路徑
    private String path;

    public RecordNFAState(NFAState state) {
        this.state = state;
    }

    public static RecordNFAState create(NFAState state) {
        return new RecordNFAState(state);
    }

    public void setNextByPath(String path, NFAState next) {
        this.path = path;
        this.next = create(next);
    }

    public NFAState getState() {
        return state;
    }

    public RecordNFAState getNext() {
        return next;
    }

    public String getPath() {
        return path;
    }
}

最后進(jìn)行匹配

  public static void main(String[] args) {
        String pattern = "a(b|c)*";

        NFAGraph graph = createNFAGraph(pattern);
        // 設(shè)置轉(zhuǎn)換圖的結(jié)束狀態(tài)節(jié)點(diǎn) 就是終止?fàn)顟B(tài)節(jié)點(diǎn)
        graph.getEndState().setEnd(true);

        String regex = "abbcbcb";
        RecordNFAState recordState = RecordNFAState.create(graph.getStartState());
        boolean isMatch = isMatch(graph, regex, recordState);
        System.out.println("isMatch(" + regex + "):" + isMatch);

        RecordNFAState rs = recordState;
        while (rs != null) {
            StringBuilder builder = new StringBuilder();
            builder.append("[(狀態(tài)" + rs.getState().getId() + ")");
            builder.append("--"+rs.getPath()+"-->");
            builder.append(rs.getNext() == null ? "null" : "(狀態(tài)"+rs.getNext().getState().getId()+"）");
            builder.append("]");
            System.out.println(builder.toString());
            rs = rs.getNext();
        }
    }

輸入結(jié)果:

[(狀態(tài)0)--a-->(狀態(tài)1）]
[(狀態(tài)1)--epsilon-->(狀態(tài)8）]
[(狀態(tài)8)--epsilon-->(狀態(tài)6）]
[(狀態(tài)6)--epsilon-->(狀態(tài)2）]
[(狀態(tài)2)--b-->(狀態(tài)3）]
[(狀態(tài)3)--epsilon-->(狀態(tài)7）]
[(狀態(tài)7)--epsilon-->(狀態(tài)6）]
[(狀態(tài)6)--epsilon-->(狀態(tài)2）]
[(狀態(tài)2)--b-->(狀態(tài)3）]
[(狀態(tài)3)--epsilon-->(狀態(tài)7）]
[(狀態(tài)7)--epsilon-->(狀態(tài)6）]
[(狀態(tài)6)--epsilon-->(狀態(tài)4）]
[(狀態(tài)4)--c-->(狀態(tài)5）]
[(狀態(tài)5)--epsilon-->(狀態(tài)7）]
[(狀態(tài)7)--epsilon-->(狀態(tài)6）]
[(狀態(tài)6)--epsilon-->(狀態(tài)2）]
[(狀態(tài)2)--b-->(狀態(tài)3）]
[(狀態(tài)3)--epsilon-->(狀態(tài)7）]
[(狀態(tài)7)--epsilon-->(狀態(tài)6）]
[(狀態(tài)6)--epsilon-->(狀態(tài)4）]
[(狀態(tài)4)--c-->(狀態(tài)5）]
[(狀態(tài)5)--epsilon-->(狀態(tài)7）]
[(狀態(tài)7)--epsilon-->(狀態(tài)6）]
[(狀態(tài)6)--epsilon-->(狀態(tài)2）]
[(狀態(tài)2)--b-->(狀態(tài)3）]
[(狀態(tài)3)--epsilon-->(狀態(tài)7）]
[(狀態(tài)7)--epsilon-->(狀態(tài)9）]
[(狀態(tài)9)--null-->null]

四. 確定的有窮自動(dòng)機(jī)(`DFA`)

4.1 `NFA` 和 `DFA` 的轉(zhuǎn)換

我們知道 NFA 和 DFA 區(qū)別就是，轉(zhuǎn)換圖中當(dāng)前狀態(tài)遇到輸入字符 a 時(shí)善榛，得到是下一個(gè)狀態(tài)辩蛋，還是下一個(gè)狀態(tài)集合。

對(duì)于 DFA 來說移盆，它的下一個(gè)狀態(tài)是確定悼院；而對(duì)于 NFA 來說，它的下一個(gè)狀態(tài)是不確定咒循。

因此据途，匹配一個(gè)輸入字符串 s 時(shí)

對(duì)于 DFA 來說，只需要遍歷輸入字符串 s 叙甸，看當(dāng)前狀態(tài)能否找到對(duì)應(yīng)輸入字符的下一個(gè)狀態(tài)颖医，如果沒有就匹配失敗，如果有就繼續(xù)匹配裆蒸，直到匹配完整個(gè)輸入字符串 s 熔萧，再查看最后狀態(tài)是不是終止?fàn)顟B(tài)。
但是對(duì)于 NFA 來說僚祷，因?yàn)楫?dāng)前狀態(tài)對(duì)應(yīng)輸入字符的下一個(gè)狀態(tài)是不確定的佛致，當(dāng)匹配不成功時(shí)，它可能需要回溯到上一個(gè)節(jié)點(diǎn)辙谜，繼續(xù)匹配俺榆，直到匹配成功，或者遍歷了整個(gè) NFA 轉(zhuǎn)換圖装哆。

有沒有一種方式罐脊，將 NFA 轉(zhuǎn)換成 DFA定嗓。

還是回到原點(diǎn)， NFA 和 DFA 區(qū)別就是 DFA 得到下一個(gè)狀態(tài)爹殊，NFA 得到的是下一個(gè)狀態(tài)集合蜕乡。
那么我們能不能將這個(gè) NFA 狀態(tài)集合就看做一個(gè)新的 DFA 狀態(tài)。然后這個(gè)新的 DFA 狀態(tài)中的 NFA 狀態(tài)集合對(duì)應(yīng)輸入字符 a 能得到所有 NFA 狀態(tài)集合又是一個(gè)新的 DFA 狀態(tài)梗夸。
這樣就能得到 DFA 中，確定的狀態(tài)了号醉。簡單來說一個(gè) DFA 狀態(tài)對(duì)應(yīng) NFA 的狀態(tài)集合反症。

這個(gè)方式就稱為子集構(gòu)造法。

4.2 子集構(gòu)造法

4.2.1 重要概念

方法	描述
edge(s, a)	從`NFA`狀態(tài) `s`沿著字符 `a` 可以到達(dá)的 `NFA`狀態(tài)的集合
edge(T, a)	`NFA`狀態(tài)集合 `T` 中每個(gè)狀態(tài) `s` 沿著字符 `a` 可以到達(dá)的`NFA`狀態(tài)的集合的合集
ε-closure(s)	從 `NFA` 的狀態(tài) `s` 開始只通過空邊(ε 有向邊)到達(dá)的`NFA`狀態(tài)集合
ε-closure(T)	`NFA`狀態(tài)集合 `T` 中每個(gè)狀態(tài) `s` 通過空邊(ε 有向邊)到達(dá)的`NFA`狀態(tài)集合的合集

這四個(gè)方法都是用來生成 DFA 狀態(tài)的重要方法畔派。

edge(s, a) 和 edge(T, a) 可以得到當(dāng)前 NFA狀態(tài)或者狀態(tài)集合铅碍，沿著輸入字符 a 能夠到達(dá)的所有NFA狀態(tài)的集合，這個(gè)是生成新的 DFA 狀態(tài)關(guān)鍵线椰。
但是僅靠 edge 方法還不夠胞谈，因?yàn)?NFA 轉(zhuǎn)換圖中存在空邊(ε 有向邊)，即不需要輸入字符憨愉，就可以到達(dá)另一個(gè)NFA狀態(tài)烦绳，那么它們也需要添加到新生成的 DFA 狀態(tài)對(duì)應(yīng)的NFA狀態(tài)集合中。這里就用到了 ε-closure(s) 和 ε-closure(T) 方法配紫。

4.2.2 算法實(shí)現(xiàn)

edge(T, a) 算法

一般都是根據(jù)你定義的儲(chǔ)存結(jié)構(gòu)径密，獲取輸入字符 a 對(duì)應(yīng)的 NFA狀態(tài)集合，再將它們合并起來躺孝。

ε-closure(T) 算法

將T的所有狀態(tài)壓入stack中;
將ε-closure (T)初始化為T;
while(stack非空) {
    將棧頂元素t 給彈出棧中;
    for(每個(gè)滿足如下條件的u: 從t出發(fā)有一個(gè)標(biāo)號(hào)為ε的轉(zhuǎn)換到達(dá)狀態(tài)u)
          //  不在 u 不在ε-closure (T)中享扔，說明 u 還沒有被尋找過空邊，所以添加到ε-closure (T)和棧中植袍。
        if( u不在ε-closure (T)中) {
            將u加入到ε-closure (T)中惧眠；
            將u壓入棧中;
        }
}

借助棧 stack 數(shù)據(jù)結(jié)構(gòu)，來尋找NFA狀態(tài)集合 T, 對(duì)應(yīng)的所有空邊得到的NFA狀態(tài)于个。

因?yàn)闂?stack 能夠?qū)崿F(xiàn)深度遍歷氛魁，所以能夠找到NFA狀態(tài) s 直接空邊或者間接空邊得到的所有狀態(tài)。

構(gòu)造轉(zhuǎn)換表的算法

一開始览濒，ε-closure (s_0) 是Dstates中的唯一狀態(tài)呆盖，且它未加標(biāo)記；
while在(Dstates中有一個(gè)未標(biāo)記狀態(tài)T){
    給T加上標(biāo)記;
    for (每個(gè)輸入符號(hào)a){
        U = ε-closure(move(T,a));
        if(U不在Dstates中)
            將U加入到Dstates中贷笛，且不加標(biāo)記;
        Dtran[T,a] = U;
    }
}

Dstates 存儲(chǔ)著由 NFA 轉(zhuǎn)換成的所有 DFA 的狀態(tài)应又。
Dtran 是一個(gè)轉(zhuǎn)換表，狀態(tài)表的行都是 DFA 的狀態(tài)乏苦，狀態(tài)表的列都是輸入字符株扛，儲(chǔ)存的值也是DFA 的狀態(tài)尤筐。

Dtran 的意義就是對(duì)于任一 DFA 的狀態(tài)，遇到任一輸入字符都可以從這個(gè) Dtran 轉(zhuǎn)換表找到對(duì)應(yīng)的唯一狀態(tài)洞就。

算法分析:

首先將 NFA 的開始狀態(tài)節(jié)點(diǎn)轉(zhuǎn)換成 DFA 的節(jié)點(diǎn)盆繁，并存儲(chǔ)到 Dstates 中。
遍歷 Dstates 旬蟋，找到一個(gè)未標(biāo)記的 DFA 的節(jié)點(diǎn)油昂，如果找不到，那么表示已經(jīng)轉(zhuǎn)換成功倾贰，直接返回冕碟。
將未標(biāo)記的 DFA 的節(jié)點(diǎn)進(jìn)行標(biāo)記，然后針對(duì)每一個(gè)輸入字符匆浙，創(chuàng)建對(duì)應(yīng)的 DFA 的節(jié)點(diǎn)安寺。
這個(gè)新的 DFA 的節(jié)點(diǎn)對(duì)應(yīng)的 NFA 狀態(tài)集合可能和之前之前創(chuàng)建的 DFA 的節(jié)點(diǎn)一樣。那我們就說這兩個(gè)DFA 的節(jié)點(diǎn)是相同的首尼。就不需要重復(fù)添加到 Dstates 中了挑庶。
Dtran[T,a] = U ，表示當(dāng)前 DFA 的節(jié)點(diǎn)遇到輸入字符 a 對(duì)應(yīng)的狀態(tài)就是創(chuàng)建的狀態(tài) U软能。

這個(gè)方法就能得到我們需要的轉(zhuǎn)換表 Dtran

DFA 匹配算法

s = s_0;
c = nextChar();
while(c! = eof) {
    s = move(s,c);
    c = nextChar();
}
if (s在F中) return "yes";
else return "no";

s_0 就是 DFA 開始狀態(tài)迎捺。
遍歷輸入字符串。
move(s, c) 方法就是通過轉(zhuǎn)換表獲取下一個(gè) DFA狀態(tài)埋嵌。
最后判斷得到狀態(tài) s 是不是終止?fàn)顟B(tài)破加。

4.3 代碼實(shí)現(xiàn) (`java`)

4.3.1 DFAState

package xinhao.regex;

import java.util.Objects;
import java.util.Set;

/**
 * @author by xinhao  2021/8/8
 * 表示 DFA 轉(zhuǎn)換圖中的狀態(tài)
 */
public class DFAState {

    // 對(duì)應(yīng)的 NFA 轉(zhuǎn)換圖中的狀態(tài)集合
    private final Set<NFAState> stateSet;
    // NFA 轉(zhuǎn)換圖中的狀態(tài)集合對(duì)應(yīng)的唯一標(biāo)志，用來兩個(gè) DFA 是否相等
    private final String statesId;
    // 表示當(dāng)前狀態(tài)是不是終止?fàn)顟B(tài)
    private final boolean isEnd;
    // 這個(gè) tag 只是輔助作用雹嗦，
    private boolean isTag;

    private DFAState(Set<NFAState> stateSet, String statesId, boolean isEnd) {
        this.stateSet = stateSet;
        this.statesId = statesId;
        this.isEnd = isEnd;
    }

    /**
     * 通過 NFA 轉(zhuǎn)換圖中的狀態(tài)集合生成對(duì)應(yīng)的 DFA 狀態(tài)
     * @param stateSet
     * @return
     */
    public static DFAState create(Set<NFAState> stateSet) {
        StringBuilder idBuilder = new StringBuilder();
        // 生成對(duì)應(yīng) DFA 狀態(tài)的 id 標(biāo)志
        stateSet.stream().sorted().forEach(state -> idBuilder.append(state.getId()+","));
        boolean isEnd = false;
        for (NFAState state : stateSet) {
            // 如果 stateSet 集合中有一個(gè)狀態(tài)節(jié)點(diǎn)是終止?fàn)顟B(tài)節(jié)點(diǎn)范舀，
            // 那么這個(gè)新生成的 DFA 狀態(tài)節(jié)點(diǎn)也是終止?fàn)顟B(tài)節(jié)點(diǎn)
            if (state.isEnd()) {
                isEnd = true;
                break;
            }
        }
        return new DFAState(stateSet, idBuilder.toString(), isEnd);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        DFAState dfaNFAState = (DFAState) o;
        return statesId.equals(dfaNFAState.statesId);
    }

    @Override
    public int hashCode() {
        return Objects.hash(statesId);
    }

    public void setTag(boolean tag) {
        isTag = tag;
    }

    public Set<NFAState> getNFAStateSet() {
        return stateSet;
    }

    public String getNFAStatesId() {
        return statesId;
    }

    public boolean isTag() {
        return isTag;
    }

    public boolean isEnd() {
        return isEnd;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("DFANFAState{");
        sb.append("statesId='").append(statesId).append('\'');
        sb.append(", isEnd=").append(isEnd);
        sb.append('}');
        return sb.toString();
    }
}

表示 DFA 的狀態(tài)節(jié)點(diǎn)，它包含了一個(gè) NFA 狀態(tài)節(jié)點(diǎn)集合 stateSet了罪。

4.3.2 DFAGraph

package xinhao.regex;

import java.util.HashMap;
import java.util.Map;

/**
 * @author by xinhao  2021/8/8
 */
public class DFAGraph {
    public static final String[] PATHS = {"0","1","2","3","4","5","6","7","8","9",".","a", "b", "c"};

    public static final Map<String, DFAState> EMPTY = new HashMap<>();
    // DFA 開始狀態(tài)節(jié)點(diǎn)
    private DFAState start;
    // DFA 對(duì)應(yīng)的轉(zhuǎn)換表锭环。采用 Map<DFAState, Map<String, DFAState>> 表明它是一個(gè)二維數(shù)組，可以轉(zhuǎn)換成 DFAState[][] 的格式
    private Map<DFAState, Map<String, DFAState>> stateTable;

    public DFAGraph(DFAState start) {
        this.start = start;
    }

    public static DFAGraph create(DFAState start) {
        DFAGraph dfaGraph = new DFAGraph(start);
        dfaGraph.stateTable = new HashMap<>();
        return dfaGraph;
    }

    /**
     * 向轉(zhuǎn)換表中添加數(shù)據(jù)
     * @param currentState
     * @param path
     * @param state
     */
    public void addStateTable(DFAState currentState, String path, DFAState state) {
        Map<String, DFAState> pathMap = stateTable.get(currentState);
        if (pathMap == null) {
            pathMap = new HashMap<>();
            stateTable.put(currentState, pathMap);
        }
        pathMap.put(path, state);
    }

    /**
     * 獲取對(duì)應(yīng)的下一個(gè)狀態(tài)節(jié)點(diǎn)
     * @param currentState
     * @param path
     * @return
     */
    public DFAState getStateByMove(DFAState currentState, String path) {
        return stateTable.getOrDefault(currentState, EMPTY).get(path);
    }

    public DFAState getStart() {
        return start;
    }

    public Map<DFAState, Map<String, DFAState>> getStateTable() {
        return stateTable;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("DFAGraph{");
        sb.append("start=").append(start);
        sb.append(", stateTable=").append(stateTable);
        sb.append('}');
        return sb.toString();
    }
}

DFAGraph 中最重要的屬性就是 stateTable泊藕，記錄 DFA 的轉(zhuǎn)換表辅辩。

4.3.3 `edge` 方法

   /**
     * 得到 DFA 狀態(tài)節(jié)點(diǎn) 經(jīng)過 path 后得到的所有 NFA 狀態(tài)節(jié)點(diǎn)集合。
     * @param tState
     * @param path
     * @return
     */
    public static Set<NFAState> edge(DFAState tState, String path) {
        Set<NFAState> resultSet = new HashSet<>();
        // 當(dāng)前 DFA 狀態(tài)對(duì)應(yīng)的 NFA 狀態(tài)集合
        for (NFAState state : tState.getNFAStateSet()) {
            if (state.getEdges().containsKey(path)) {
                resultSet.addAll(state.getEdges().get(path));
            }
        }
        return resultSet;
    }

4.3.4 `closure` 方法

   /**
     * 得到 ε-closure 的 NFA 狀態(tài)集合
     * @param state
     * @return
     */
    public static Set<NFAState> closure(NFAState state) {
        Set<NFAState> states = new HashSet<>();
        states.add(state);
        return closure(states);
    }

    /**
     * 得到 ε-closure 的 NFA 狀態(tài)集合
     * @param states
     * @return
     */
    public static Set<NFAState> closure(Set<NFAState> states) {
        Stack<NFAState> stack = new Stack<>();
        stack.addAll(states);
        Set<NFAState> closureSet = new HashSet<>(states);
        while (!stack.isEmpty()) {
            NFAState state = stack.pop();
            // 得到狀態(tài) state 對(duì)應(yīng)的空邊 狀態(tài)集合
            Set<NFAState> epsilonSet = state.getEdges().getOrDefault(NFAState.EPSILON, EMPTY);
            for (NFAState epsilonState : epsilonSet) {
                // 如果不存在娃圆，就是新發(fā)現(xiàn)的狀態(tài)玫锋，添加到 closureSet 和 stack 中
                if (!closureSet.contains(epsilonState)) {
                    closureSet.add(epsilonState);
                    stack.push(epsilonState);
                }
            }
        }
        return closureSet;
    }

4.3.5 `NFAToDFA` 方法

  /**
     * 從 dfaStates 集合中尋找一個(gè)未標(biāo)記的 DFA 狀態(tài)節(jié)點(diǎn)
     * @param dfaStates
     * @return
     */
    public static DFAState getNoTagState(Set<DFAState> dfaStates) {
        for (DFAState state : dfaStates) {
            if (!state.isTag()) {
                return state;
            }
        }
        return null;
    }

    /**
     * NFA 轉(zhuǎn)換成 DFA
     * @param nfaGraph
     * @return
     */
    public static DFAGraph NFAToDFA(NFAGraph nfaGraph) {

        // 創(chuàng)建開始的 DFA 狀態(tài)
        DFAState startDFAState = DFAState.create(closure(nfaGraph.getStartState()));
        // 創(chuàng)建 DFAGraph 圖
        DFAGraph dfaGraph = DFAGraph.create(startDFAState);
        // 這個(gè)集合記錄所有生成的 DFA 狀態(tài)節(jié)點(diǎn)
        Set<DFAState> dfaStates = new HashSet<>();
        // 將開始狀態(tài)節(jié)點(diǎn)添加到 dfaStates 中
        dfaStates.add(startDFAState);

        DFAState TState;
        // 從 dfaStates 集合中尋找一個(gè)未標(biāo)記的 DFA 狀態(tài)節(jié)點(diǎn)
        while ((TState = getNoTagState(dfaStates)) != null) {
            // 進(jìn)行標(biāo)記，防止重復(fù)遍歷
            TState.setTag(true);

            // 遍歷輸入字符
            for (String path : DFAGraph.PATHS) {
                // 創(chuàng)建新的 DFA 狀態(tài)節(jié)點(diǎn)
                DFAState UState = DFAState.create(closure(edge(TState, path)));
                // 不包含就添加
                if (!dfaStates.contains(UState)) {
                    dfaStates.add(UState);
                }
                // 添加轉(zhuǎn)換表
                dfaGraph.addStateTable(TState, path, UState);
            }

        }
        return dfaGraph;
    }

4.3.6 `isDFAMatch` 方法

 public static boolean isMatch(DFAGraph dfaGraph, String regex) {
        char[] chars = regex.toCharArray();
        int pos = 0;
        DFAState dfaState = dfaGraph.getStart();
        while (pos < chars.length) {
            String path = "" + chars[pos++];
            // 從轉(zhuǎn)換表中獲取當(dāng)前狀態(tài) dfaState 遇到字符 path讼呢，得到下一個(gè)狀態(tài) dfaState
            dfaState = dfaGraph.getStateByMove(dfaState, path);
        }
        return dfaState.isEnd();
    }

4.3.6 簡單示例

 public static void main(String[] args) {
        String pattern = "a(b|c)*";

        NFAGraph nfaGraph = NFARegexUtil.createNFAGraph(pattern);
        nfaGraph.getEndState().setEnd(true);

        DFAGraph dfaGraph = NFAToDFA(nfaGraph);

        String regex = "abbccb";
        boolean isMatch = isMatch(dfaGraph, regex);
        System.out.println("isMatch(" + regex + "):" + isMatch);
    }