用C/C++手撕CPlus語言的集成開發環境（1）—— 語言規范 + 詞法分析器-有解無憂

序言

之所以叫做CPlus語言，是因為原本是想起名為CMinus的，結果發現GitHub和Gitee上一堆的CMinus的編譯器（想必都是開過編譯原理課程并且寫了個玩具級的語言編譯器的大佬們吧），但是CPlus相較于C多了一些東西，而相較于C++又少了一些東西，又有點C#的影子，而且并不嚴格遵守編譯原理課本上的CMinus標準，所以暫且取個中間值，就叫C+（CPlus，反正目前還沒人用，那我就抱走了），

在開始之前，老規矩：

如果覺得這篇文章可以幫到你，歡迎一鍵三連（點贊，收藏，打賞（這一項只適用于在CSDN上））或者star和watch我的GitHub博客，
如果想要幫忙宣傳一下，當然歡迎，不過還請轉載標明出處，
我使用的C/C++ IDE是Microsoft Visual Studio 2017 Community（以下簡稱VS2017），WinSDK是10.0.17763.0，不過由于WinSDK造成的Bug在這種軟體上并不致命，所以暫時忽略，

那么，好戲開場！（打響指）

1. 理論

在直接開始手撕CPlus的IDE之前，我們需要預先定義好CPlus的一些基礎規則，當然，不是全部，因為在后面的話可能還是會像C++標準一樣每隔一段時間就添加上那么億點點細節，首先，說明一下CPlus和普通的C/C++有什么區別，這樣或許更直觀些：

CPlus支持面向物件編程，但不會像C++那樣支持多繼承，在這點上和目前主流的Java以及C#保持一致，當然，類與結構體中的成員有兩種展現方式：public以及private，
關于比較惱人的指標問題，CPlus并不允許在基礎資料型別（整型，浮點，布林值等）上使用指標，但是，為了使CPlus更好的契合設計模式，允許在自定義結構體以及型別別里使用指標，而且在物件的生命周期結束后會自動回收（這一點有點兒難，不過這只是目前設想），
稍微有點C/C++基礎的各位都知道，在C++ 20標準之前，頭檔案一直是一個比較頭疼的存在，尤其在VS上，加載速度慢以及 “LNK2019” 是常客，雖說前向宣告可以解決不少問題，但還是有些力不從心（尤其是前向宣告標準庫的那些‘大爺們’），CPlus吸取了C++ 20以及C#的包匯入優點，使用import關鍵字作為外部匯入關鍵字，
采用了多種長度的int型別：int8、int16、int32、int64以及相應的uint（無符號整型），

接下來，就是定義CPlus里的關鍵字、運算子、界符、識別符號相關的定義了，以便在撰寫詞法分析器中起作用，

關鍵字：

        "int8",		"int16",	"int32",	"int64",
	"uint8",	"uint16",	"uint32",	"uint64",
	"float",	"double",	"bool",		"char",
	"void",		"if",		"else",		"switch",
	"case",		"break",	"continue",     "while",
	"for",		"return",	"struct",	"class",
	"public",	"private",	"import",	"true",
	"false",	"default"

和C/C++沒多大區別，少了#include以及#define等前處理器指令關鍵字，增加了import關鍵字，

運算子：

        "+", "-",  "*",  "/",  ">",
	"<", "=",  ">=", "<=", "==",
	"!", "!=", "&&", "||", "&",
	"|", ":",  "::", "+=", ".", ","

這沒什么可說的

界符：" " ", "{", "}", "(", ")", "[", "]", ";"
數字：阿拉伯數字0 ~ 9，支持浮點數以及帶正負號的數，
識別符號：同C/C++一致，支持下劃線作為識別符號，同時支持字母與數字的組合作為識別符號，但不允許以數字為開始字符，
注釋：支持多行注釋，但目前只支持" /**/ "注釋符，

在上述這些基礎定義完后，我們便可以開始定義詞法分析器了，對于詞法分析器的構建，我們可以用多種方法：使用現成輔助工具生成相關代碼（著名的有JavaCC）、采用一大堆的if-else陳述句對讀入的每個字符做一次判斷、或者親手構建一個符合CPlus詞法的DFA，從方便性上來說，第一種方法是最不錯的選擇，但咱們是手撕，所以不做考慮，而且由于一大堆的if-else陳述句邏輯結構實在太過復雜，想用if-else實作樹狀結構實屬愚蠢，所以，也就剩下最后一條路——構建符合CPlus詞法的DFA，話不多說，先上圖：

接下來開始解釋：

所有的狀態機都是一致的，均具備開始以及結束節點，還記得我在講虛幻引擎AI系統的時候說過的行為樹么？那也是一種狀態機，同樣具備開始和結束節點，只不過被隱藏掉了而已，雖說叫做狀態機，但DFA全名為deterministic finite automata（確定狀態的有窮自動機），實際上應該算是狀態機的一個子集，虛幻引擎AI行為樹也屬于DFA，因為每種狀態的觸發都是有不同條件的，遵循著一對一原則，當DFA讀入一個字符時，如果處于開始狀態，那么會根據給出字符在ASCII對應的位置來鎖定下一個應該到達的狀態，以符號“斜線”為例，當DFA遇到讀入字符為“斜線”時，會徑直進入DIVIDE狀態，在這時若狀態機接受的下一個字符為星號時，那么便會進入COMMENT狀態，若接收的是除星號以外的任意字符，那么便會將此“斜線”符號作為一個token保存起來，并以DIVIDE標記這個token，在以后的語法決議程序中當語法決議器遇到它后會說“啊，原來這是一個除號（DIVIDE）”，

當然，上圖只是我為了解釋DFA在真實計算機編程語言編譯程序中詞法決議的原理而畫的一個簡易的DFA，與真實的CPlus語言的DFA有一部分不一致的地方，有了基礎的DFA思想以后，接下來就要開始手撕詞法分析器部分了，當然，如何通過字串流操作將文本代碼存入記憶體的方法我就不再贅述，直接開始詞法分析器部分，Talk is cheap and show me the code.

2. 詞法分析器

2.1 DFA定義

在講解虛幻引擎AI行為樹時，我們用到了列舉型別來實作Agent的狀態切換，列舉是個好東西，在代碼層級上實作這一類的自動機也的確是要用到“enum + switch”來進行實作，(什么？構建網狀資料結構來表示DFA？在C/C++里太麻煩了吧，你用的是JavaScript？哦那沒事了，)

接下來展示一下DFA狀態：


enum lexerDFAStatus
{
	DFA_SLEEP,
	DFA_START,
	DFA_SYMBOL,
	DFA_COMMENT,
	DFA_NUM,
	DFA_IDENTIFIER,
	DFA_END
};

一共有七種：睡眠（DFA_SLEEP），開始(DFA_START)，符號(DFA_SYMBOL)，注釋(DFA_COMMENT)，數字(DFA_NUM)，識別符號(DFA_IDENTIFIER)，結束(DFA_END)，

其中，睡眠指的是在詞法分析器物件在建構式里初始化狀態機的時候用的，沒什么特別的意義，開始和結束我不再過多說明，上面有提到，符號的話，就是在DFA遇到除52個大小寫字母，0-9以及非法符號外的所有符號后跳躍到的狀態，注釋是指在DFA遇到了形如“/**/”的符號后進入的狀態，此時在注釋范圍內的所有符號，DFA一概不讀取，數字指在DFA遇到了0-9的數后進入的狀態，當然在數字中間遇到了“.”也會將其歸為數字范疇，畢竟是小數啊，識別符號就是識別符號，不解釋，當然，在注釋之外遇到了非法符號（比如‘……，￥，%，@，#’）會自動拋出例外并停止接下來的編譯流程，

然后聰明又可愛的觀眾們就會問了，說：永樂，你為什么沒有給關鍵字和識別符號做區分呢？這其實不是什么問題，還請往后看，

2.2 token定義

本人計劃使用單向鏈表來實作token物件的存盤，相關定義如下：


/* 
    CPlus_CORE_API 可以無視掉，這是為了將tokenType開放出去，由于本編譯器是以
    dll元件表現的，在使用時直接掛載即可，這也是為了考慮到IDE開發中
    需要重復呼叫編譯器的某項功能的情況（我總不可能把編譯器和IDE寫進一個專案里吧，耦合度可是很高的），
    而封裝成可運行二進制.exe檔案時就沒有這么自由了，關于dll的生成與呼叫，
    敬請參閱我的《從新建檔案夾開始構建UtopiaEngine（1）》文章，里面有詳細介紹，
*/
enum CPlus_CORE_API tokenType
{
	NOTHING,
	KEYWORD,
	SYMBOL,
	DELIMITER,
	NUMBER,
	IDENTIFIER
};

struct lexerTokenData
{
	tokenType tkt;
	std::string value;
	int rowLoc;
	lexerTokenData() : tkt(NOTHING), value("Start node"), rowLoc(-1)
	{
		// Nothing.
	}
	void setToken(tokenType _tkt, std::string _value, int _rowLoc)
	{
		this->tkt = _tkt;
			this->value = https://www.cnblogs.com/Pixel-Xi-an/p/_value;
			this->rowLoc = _rowLoc;
	}
};

// This is struct for token Node.
struct lexerToken
{
	lexerTokenData tokenSave;
	lexerToken* nextNode;

	lexerToken()
	{
		this->nextNode = nullptr;
	}
};

tokenType指的是這則token所用的型別，有這么幾種：NOTHING（啥也不是），KEYWORD（關鍵字），SYMBOL（合法符號），DELIMITER（界符），NUMBER（數字），IDENTIFIER（識別符號），和DFA狀態定義一樣，NOTHING只是為了方便建構式初始化用的，

lexerTokenData是對要存盤進token的資料做一個整合，其中存盤了token的型別，token的值以及token所在的行數（話說行數這個東西在現在看來貌似沒什么用，在以后的語法分析器中我會提及），lexerToken也就是存盤token所用的鏈表結點的結構定義了，（什么？你還不知道結構體里可以寫成員函式？敬請參閱C++ 11標準哦親）

2.3 開始構建

必要的前置說明已經在上文中提過，直接上代碼吧：


for (int i = 0; i < this->codeStr.size(); i++)
{
	codeChar = this->codeStr[i];
	if (this->DFA != DFA_COMMENT)
	{
		if ((codeChar >= '0') && (codeChar <= '9') && (this->DFA != DFA_NUM) && (this->DFA != DFA_IDENTIFIER)) { this->DFA = DFA_NUM; }
		else if ((codeChar >= '0') && (codeChar <= '9') && (this->DFA == DFA_NUM));
		else if ((codeChar >= '0') && (codeChar <= '9') && (this->DFA == DFA_IDENTIFIER));
		else if ((codeChar >= 'a') && (codeChar <= 'z') && (this->DFA != DFA_IDENTIFIER) && (this->DFA == DFA_NUM)) 
		{
			ConsoleLog::PrintLog(COMPILER_LOG, CPCE_0003, CPCW_0000, "The identifier cannot start by number");
			throw std::exception();
		}
		else if ((codeChar >= 'a') && (codeChar <= 'z') && ((this->DFA != DFA_IDENTIFIER))) { this->DFA = DFA_IDENTIFIER; }
		else if ((codeChar >= 'A') && (codeChar <= 'Z') && (this->DFA != DFA_IDENTIFIER) && (this->DFA == DFA_NUM))
		{
			ConsoleLog::PrintLog(COMPILER_LOG, CPCE_0003, CPCW_0000, "The identifier cannot start by number");
			throw std::exception();
		}
		else if ((codeChar >= 'A') && (codeChar <= 'Z') && ((this->DFA != DFA_IDENTIFIER))) { this->DFA = DFA_IDENTIFIER; }
		else if ((codeChar >= 'a') && (codeChar <= 'z') && ((this->DFA == DFA_IDENTIFIER)));
		else if ((codeChar >= 'A') && (codeChar <= 'Z') && ((this->DFA == DFA_IDENTIFIER)));
		else if (codeChar == '_') { this->DFA = DFA_IDENTIFIER; }
		else if ((codeChar == '/') && (this->codeStr[i + 1] == '*')) { this->DFA = DFA_COMMENT; }
		else if ((codeChar == ' ') || (codeChar == '\n')) 
		{
			
			switch (this->DFA)
			{
			case DFA_NUM:
				this->tokenLLNodeAdd(NUMBER, subCodeStr, rowNum);
				subCodeStr.clear();
				this->DFA = DFA_END;
				break;
			case DFA_IDENTIFIER:
			{
				if (this->isKeyword(subCodeStr))
				{
					this->tokenLLNodeAdd(KEYWORD, subCodeStr, rowNum);
					subCodeStr.clear();
				}
				else
				{
					this->tokenLLNodeAdd(IDENTIFIER, subCodeStr, rowNum);
					subCodeStr.clear();
				}
			}
				this->DFA = DFA_END;
				break;
			case DFA_COMMENT:
				this->DFA = DFA_COMMENT;
				break;
			default:
				break;
			}
    		if (codeChar == '\n') { rowNum += 1; }
		}
		else if ((codeChar == '.') && (this->DFA == DFA_NUM));
		else if (codeChar == '\t');
		else
		{
			if (this->DFA == DFA_IDENTIFIER)
			{
				if (this->isKeyword(subCodeStr))
				{
					this->tokenLLNodeAdd(KEYWORD, subCodeStr, rowNum);
							subCodeStr.clear();
				}
				else
				{
					this->tokenLLNodeAdd(IDENTIFIER, subCodeStr, rowNum);
					subCodeStr.clear();
				}
				this->DFA = DFA_SYMBOL;
			}
			else if(this->DFA == DFA_NUM)
			{
				this->tokenLLNodeAdd(NUMBER, subCodeStr, rowNum);
				subCodeStr.clear();
				this->DFA = DFA_SYMBOL;
			}
			else if (this->DFA == DFA_COMMENT) 
			{
				// Nothing.
			}
			else 
			{
				this->DFA = DFA_SYMBOL;
			}
			
		}
	}
	else if (codeChar == '\n')
	{
		rowNum += 1;
	}
	switch (this->DFA)
	{
	case DFA_SYMBOL:
	{
		subCodeStr += codeChar;
		if (this->isSymbol(subCodeStr))
		{
			subCodeStr += codeStr[i + 1];
			if (this->isSymbol(subCodeStr))
			{
				i += 1;
				this->tokenLLNodeAdd(SYMBOL, subCodeStr, rowNum);
				subCodeStr.clear();
				this->DFA = DFA_START;
			}
			else
			{
				subCodeStr.clear();
				subCodeStr += codeChar;
				this->tokenLLNodeAdd(SYMBOL, subCodeStr, rowNum);
				subCodeStr.clear();
				this->DFA = DFA_START;
			}
		}
		else if (this->isDelimiter(subCodeStr))
		{
			this->tokenLLNodeAdd(DELIMITER, subCodeStr, rowNum);
			subCodeStr.clear();
			this->DFA = DFA_START;
		}
		else if (this->DFA != DFA_IDENTIFIER)
		{
			ConsoleLog::PrintLog(COMPILER_LOG, CPCE_0003, CPCW_0000, "You are use the unknown invalid symbol. This symbol is not supported at present.");
			this->tokenLLDelete();
			throw std::exception();
		}
	}
		break;
	case DFA_NUM:
		subCodeStr += codeChar;
		break;
	case DFA_IDENTIFIER:
		subCodeStr += codeChar;
		break;
	case DFA_COMMENT:
	{
		if ((codeChar == '*') && (this->codeStr[i + 1] == '/')) { 
			i += 1;
			this->DFA = DFA_START; 
		}
	}
		break;
	case DFA_END:
		this->DFA = DFA_START;
		break;
	default:
		break;
	}
}

額，這的確有點多，一行行解釋怕是各位也是聽到了后面就忘了前面的，這樣吧，我用幾個實體帶入進行說明，希望可以讓各位理解，接下來會用到行號，還煩請各位將這段代碼粘貼到NotePad++或者VSCode上方便閱讀，在開始舉例前，先對代碼結構進行說明：

整個代碼有一個外圍大回圈，主要是對每個讀入的字符對號入座進行處理的，大回圈里的步驟大致分為：分配狀態（第4行至第24行） -> 保持狀態加入子串（第98行至第155行） -> 打包token并分配token型別（凡是你能看到的this->tokenLLNodeAdd() 都是），

好的，上實體：

我們先以關鍵字 “int8” 為例，此時DFA狀態為DFA_START，當我們的讀入指標codeChar到達了字符 “i” 時，DFA會先進入一個if判斷，即判斷當前DFA是否處在DFA_COMMENT狀態，若是，那么跳至第93行進行接下來的處理，關于注釋的處理我們稍后在講，但此時狀態并不是DFA_COMMENT，所以進行接下來的處理，根據要求會執行第14行的條件判斷內的處理陳述句，將DFA狀態設定為DFA_IDENTIFIER，完成后會跳至第98行進行狀態判斷，由于此時狀態為DFA_IDENTIFIER，所以執行第140行陳述句，即向子串加入字符 “i” ，此時DFA會將DFA_IDENTIFIER狀態保留并再次跳至大回圈即從第3行再次讀入下一個字符 “n” ，按照上面的邏輯回圈若干次后來到了 “8” ，此時DFA的狀態是DFA_IDENTIFIER，這時滿足第8行要求，無狀態轉換陳述句，即保持原有狀態，接下來進入第139行將“8”錄入子串中，按照普通編程習慣以及語法規定，此時若要結束，必須要有一個空格或者換行符來隔開本識別符號和下一個符號，假設是空格，此時DFA會轉至第25行進行token錄入操作，由于此時狀態在DFA_IDENTIFIER中，則跳至第35行開始錄入，在本文剛開始有一個問題即關于識別符號和關鍵字的問題，這里便給出解決方法：由于子串中的 “int8” 屬于關鍵字，則第37行判斷回傳結果為真，那么這個token便會被創建并被標識為 “KEYWORD（關鍵字）” ，DFA的狀態也轉換為DFA_END，在回圈結束后回到DFA_START狀態以便讀取別的識別符號以及別的檔案內容，
接下來舉一個關于注釋的例子：“/* abcdefgh（這里有個換行符）+=*@#$%^ */”，在開始時，DFA狀態為DFA_START，這時會進入第四行所在的條件判斷內，接下來跳至第24行并將狀態轉換為DFA_COMMENT，此時會再次跳回回圈開始處，若讀取到換行符則會跳至第93行為行數加一，所以至少在CPlus語言中，向注釋中加入 “\n” 形式的換行符且真實語意上并未換行的做法是非法的，只支持回車的隱式換行符，接下來若遇到了 “*” 以及 “/” 符號，則跳至第142行為序號i加1以跳過“/”符號，并將DFA狀態切換為DFA_START，以準備下一階段的讀取，

3. 運行

將專案生成的詞法分析器用于決議下面的 .cpc（CPlus Code） 檔案：


/* Copyright 2021-2022 Zhao Yongle. All rights reserved. */
/* This is CPlus compiler test file. */
import stdio

class Alpha
{
public:
	void func()
	{
		switch(var)
		{
		case 1:
			break;
		default:
			break;
		}
	}
private:
	double var;
};

struct Beta
{
	int64 ab;
};

/*
	Multiline comment 1,
	Multiline comment 2,
	Multiline comment 3.
*/

int8 main()
{
	if(true)
	{
		print("Hello, world!");
	}
	else if(false)
	{
		/* Nothing */
	}
	else {}
	while(true)
	{
		/* Code+-*= */
	}
	for(int8 i = 0; i < 8; i++)
	{
		/* Loop body */
	}
	int32 _a = 32;
	float b = -1.0+1.23456789;
	bool c0 = false;
	Alpha d;
	d.func();
	d.var;
	return 0;
}

運行結果如下：（由于我將專案生成的編譯器目錄加入了系統path，所以可以直接由命令CPC啟動）

4. 結語

又是個天坑（笑），當然，我并沒有忘和大家許諾的虛幻引擎系列、圖形學系列以及游戲引擎系列，只是咕一會而已，并無大礙，至少不會是麻蛇和富堅老賊那樣無限期拖更，額，也沒什么要說的，如果有什么好的建議或者意見歡迎提出，就這樣，期待下次再會！誒嘿，馕打油！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282819.html

標籤：其他

上一篇：演算法復雜度分析

下一篇：演算法復雜度分析