詞法分析程式之正規式轉換成NFA

點贊再看，養成習慣！覺得不過瘾的童鞋，歡迎關注公衆号《機器學習算法工程師》，有非常多大神的幹貨文章可供學習噢…

目錄

• • 前言
  • 正文
  • • 正規式
    • 非法字元與加入連接配接符
    • 中綴表達式轉字尾表達式
    • 構造NFA
    • 測試案例
  • 結語
  • 參考文獻

前言

PS: 鑒于本文對很多童鞋有所幫助，小編于2020/6/7對其回爐重造，在CodeBlocks IDE(采用GCC套裝 編譯器)中成功編譯運作，代碼已上傳至Github上，童鞋們可在參考文獻中找到連結。

本篇是憑借Thompson方法，進而根據正規表達式(正規式)構造對應的NFA(不确定有窮自動機)，其實作語言是C++。基本邏輯如下圖所示：

正文

正規式

本篇中，有效的正規式的字母表 ∑ = { a − z , A − Z } \sum=\{a-z,A-Z\} ∑={a−z,A−Z}，輔助字母表 ∑ ′ = { ∗ , ∣ , ( , ) } \sum'=\{*,|,(,)\} ∑′={∗,∣,(,)}。對應的規則：

1. ‘*’：閉包；
2. ‘|’：或；

其實還有連接配接符号，不過我們平時寫正規式時會省略它，但小編在源碼中其實加上了就是’+’，參考文獻的那個課本用的是’.’。這些算符的優先順序為先’*’，再’+’，最後’|’。這個優先關系在中綴表達式轉字尾表達式的時候會用到。

非法字元與加入連接配接符

非法字元

評論中曾有童鞋問小編非法字元指的那些，當時文章寫得并不清晰。這次，小編将從源碼角度解釋，非法字元指的便是除字母表與輔助字母表以外的字元，并且源碼額外還對括号進行檢查。

/**檢測輸入的正規表達式是否合法
*/
int check_legal(const string check_string)
{
	if (check_character(check_string) && check_parenthesis(check_string))
	{
		return true;
	}
	return false;
}

/**
檢查輸入的字元是否合适 () * | a~z A~Z
合法傳回true,非法傳回false
*/
int check_character(const string check_string)
/**檢查括号是否比對
*合法傳回true,非法傳回false
*/
int check_parenthesis(const string check_string)

           

加入連接配接符

這一步主要是為了友善後面的工作（中綴轉字尾），将省略的連接配接符顯式加進去。要加的地方如ab 、 *b 、 a( 、 )b 等情況，一次周遊即可完成。

中綴表達式轉字尾表達式

這一節的算法，小編特地寫了一篇博文幫助了解，童鞋可在參考文獻中找到。其實在源碼中這塊有比較詳細的注釋，這裡要利用上前面說的算符優先關系。

構造NFA

一個NFA M是一個五元組， M = ( K , ∑ , f , S , Z ) M=(K,\sum,f,S,Z) M=(K,∑,f,S,Z)。我們目前知道的隻有 ∑ \sum ∑有窮字母表，即是正規式的字母表，而其他的像 K K K狀态集， f f f轉移函數， S S S非空初态集， Z Z Z終态集，就在這一節能夠得到。源碼實作的方法便是Thompson方法，在參考文獻《編譯原理》書中第4章能夠找到與下面内容一樣的解釋，不再贅述。

下面的理論光看文字描述可能難以快速了解，小編打算以一個demo并輔助源碼來細緻講解，希望能達到過一遍就能上手源碼的效果！

Demo

正規式為a(a|b)*，很明顯這個簡單的正規式包含了所有的輔助字母表的符号（即所有的規則），和字母表裡的字母a和b，不過我們不要簡單地把它們看成字母a和b，實際上它們可以抽象為兩個不同的符号，他們所代表的可以是一類符号，比如是數字或者是英文字母，這取決于我們在源碼中把這些符号識别成什麼。

首先，介紹一下源碼中用到的資料結構：

//NFA的節點，定義成結構體，便于以後擴充
struct state
{
	string StateName;
};

//NFA的邊，空轉換符用'#'表示
struct edge
{
	state StartState;  
	state EndState;
	char TransSymbol;  //轉換符号
};

//NFA單元，一個大的NFA單元可以是由很多小單元通過規則拼接起來
struct cell
{
	edge EdgeSet[MAX];  //這個NFA擁有的邊
	int EdgeCount;  //邊數
	state StartState;  //開始狀态
	state EndState;  //結束狀态
};

           

Thompson原理

方法：将r分解成最基本的子表達式，使用下面的規則1和2為r的每個基本符号（ # 或Σ中的符号）構造NFA。用規則3逐漸組合前面構造的NFA，直到獲得整個正規表達式的NFA為止。

規則1. 對#, 構造NFA 。

這裡 i 是新的開始狀态，f是新的接受狀态。很明顯這個NFA識别{#}。

規則2. 對于Σ中的每個符号a，構造NFA。

同樣，i 是新的開始狀态， f 是新的接受狀态。 這個NFA識别 {a}。

【小編講解】

規則1和2是NFA建構的基本單元，含有兩個狀态以及狀态轉換的邊。在源碼中實作是如下面代碼所示的，會新增兩個狀态與一條邊，狀态從new_StateNode函數生成，能夠保證全局唯一性；而邊則記錄轉換的符号以及起始狀态資訊。而最終傳回的便是一個包含了新狀态節點與邊的NFA單元NewCell。

//處理 a
cell do_Cell(char element)
{
	cell NewCell;
	NewCell.EdgeCount = 0;
	edge NewEdge;
	//獲得新的新狀态節點
	state StartState = new_StateNode();
	state EndState = new_StateNode();
	//建構邊
	NewEdge.StartState = StartState;
	NewEdge.EndState = EndState;
	NewEdge.TransSymbol = element;
	//建構單元
	NewCell.EdgeSet[NewCell.EdgeCount++] = NewEdge;
	NewCell.StartState = NewCell.EdgeSet[0].StartState;
	NewCell.EndState = NewCell.EdgeSet[0].EndState;//EdgeCount此時為1
	return NewCell;
}

           

規則3 . 如果N(s) 和 N(t) 是正規表達式s和t的NFA，則：

①對于正規表達式 s | t, 可構造複合的NFA N(s|t):

【小編講解】

在規則1和2建構好基本的NFA單元後，遇到規則①，我們隻需要增添2個狀态和4條邊，并按照要求連接配接起來即可，實作如下：

//處理 a|b
cell do_Unite(cell Left, cell Right)
{
	cell NewCell;
	NewCell.EdgeCount = 0;
	edge Edge1, Edge2, Edge3, Edge4;
	//獲得新的新狀态節點
	state StartState = new_StateNode();  //s
	state EndState = new_StateNode();  //e
	//建構邊
	//e1
	Edge1.StartState = StartState;
	Edge1.EndState = Left.EdgeSet[0].StartState;
	Edge1.TransSymbol = '#';  //代表空串
	//e2
	Edge2.StartState = StartState;
	Edge2.EndState = Right.EdgeSet[0].StartState;
	Edge2.TransSymbol = '#';
	//e3
	Edge3.StartState = Left.EdgeSet[Left.EdgeCount - 1].EndState;
	Edge3.EndState = EndState;
	Edge3.TransSymbol = '#';
	//e4
	Edge4.StartState = Right.EdgeSet[Right.EdgeCount - 1].EndState;
	Edge4.EndState = EndState;
	Edge4.TransSymbol = '#';

	//建構單元
	//先将Left和Right的EdgeSet複制到NewCell
	cell_EdgeSet_Copy(NewCell, Left);
	cell_EdgeSet_Copy(NewCell, Right);

	//将新建構的四條邊加入EdgeSet
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge1;
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge2;
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge3;
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge4;

	//建構NewCell的起始狀态和結束狀态
	NewCell.StartState = StartState;
	NewCell.EndState = EndState;

	return NewCell;
}
           

②對于正規表達式 st, 可構造複合的NFA N(st)：

【小編講解】

規則②并不需要新增邊和狀态，而是在已有的NFA單元上修改，把N(s)的終止狀态與N(t)的起始狀态合并，源碼實作中是保留了N(s)的終止節點而删掉N(t)的起始節點，然後把N(t)與起始節點有關的邊都要修改，代碼如下：

//處理 ab
cell do_Join(cell Left, cell Right)
{
	//将Left的結束狀态和Right的開始狀态合并，将Right的邊複制給Left，将Left傳回
	//将Right中所有以StartState開頭的邊全部修改
	for (int i = 0; i<Right.EdgeCount; i++)
	{
		if (Right.EdgeSet[i].StartState.StateName.compare(Right.StartState.StateName) == 0)
		{
			Right.EdgeSet[i].StartState = Left.EndState;  //該邊e1的開始狀态就是N(t)的起始狀态
			STATE_NUM--;
		}
		else if (Right.EdgeSet[i].EndState.StateName.compare(Right.StartState.StateName) == 0)
		{
			Right.EdgeSet[i].EndState = Left.EndState;  //該邊e2的結束狀态就是N(t)的起始狀态
			STATE_NUM--;
		}
	}
	Right.StartState = Left.EndState;

	cell_EdgeSet_Copy(Left, Right);
	//将Left的結束狀态更新為Right的結束狀态
	Left.EndState = Right.EndState;
	return Left;
}

           

③對于正規表達式 s, 構造複合的NFA N(s)😗*

【小編講解】

規則③要新增4條邊與兩個狀态，圖示與代碼可以一一對照。

//處理 a*
cell do_Star(cell Cell)
{
	cell NewCell;
	NewCell.EdgeCount = 0;
	edge Edge1, Edge2, Edge3, Edge4;
	//獲得新的新狀态節點
	state StartState = new_StateNode();  //s
	state EndState = new_StateNode();  //e
	//建構邊
	//e1
	Edge1.StartState = StartState;
	Edge1.EndState = EndState;
	Edge1.TransSymbol = '#';  //閉包取空串
	//e2
	Edge2.StartState = Cell.EndState;
	Edge2.EndState = Cell.StartState;
	Edge2.TransSymbol = '#';  //取字元，自連接配接
	//e3
	Edge3.StartState = StartState;
	Edge3.EndState = Cell.StartState;
	Edge3.TransSymbol = '#';
	//e4
	Edge4.StartState = Cell.EndState;
	Edge4.EndState = EndState;
	Edge4.TransSymbol = '#';
	//建構單元
	//先将Cell的EdgeSet複制到NewCell
	cell_EdgeSet_Copy(NewCell, Cell);
	//将新建構的四條邊加入EdgeSet
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge1;
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge2;
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge3;
	NewCell.EdgeSet[NewCell.EdgeCount++] = Edge4;
	//建構NewCell的啟示狀态和結束狀态
	NewCell.StartState = StartState;
	NewCell.EndState = EndState;

	return NewCell;
}

           

④對于括起來的正規表達式 (s), 使用N (s) 本身作為它的NFA。

在構造過程中，每次構造的新狀态都要賦予不同的名字。這樣，任何NFA的兩個狀态都具有不同的名字。即使同一符号在r中出現多次，我們也要為該符号的每個執行個體建立一個獨立的帶有自己狀态的NFA。

測試案例

兩個正規式：

1. a(a|b)*也是構造NFA一節中的demo
2. bb*更簡單的例子

Console控制台程式結果圖

對應的NFA圖示

結語

編譯原理的相關算法難在理論，這是小編再大學二年級的項目，距今過去了4年，其實沒怎麼用到過相關知識點，不過要深入一門程式設計語言的編譯器源碼看看，那這些知識還是必不可少的。另外，我們常用的正規表達式底層用到的便是這個算法，我們構造好NFA，又該如何使用它，這都是值得進一步探讨的問題。

參考文獻

1. https://github.com/Ggmatch/The-principle-of-compiling/tree/master/NFA
2. 張素琴. 《編譯原理》第二版
3. 中綴轉字尾：https://blog.csdn.net/gongsai20141004277/article/details/106607743

童鞋們，讓小編聽見你們的聲音，點贊評論，一起加油。