2021級(jí)浴簾實(shí)驗(yàn)
本文只涉及功能實(shí)現(xiàn)的思路，針對(duì)期末復(fù)習(xí)，不涉及制作操作界面。
C++單詞拼裝器
實(shí)驗(yàn)內(nèi)容
1. 把C++源代碼中的各類(lèi)單詞（記號(hào)）進(jìn)行拼裝分類(lèi)。
C++語(yǔ)言包含了幾種類(lèi)型的單詞（記號(hào)）：標(biāo)識(shí)符，關(guān)鍵字，數(shù)（包括整數(shù)、浮點(diǎn)數(shù)），字符串、注釋、特殊符號(hào)（分界符）和運(yùn)算符號(hào)等【詳細(xì)的單詞類(lèi)別及拼裝規(guī)則見(jiàn)另外的文件說(shuō)明】。
2. 打開(kāi)一個(gè)C++源文件，列出所有可以拼裝的單詞（記號(hào)）。
最后呈現(xiàn)的內(nèi)容：
# 特殊符號(hào)
20.26 數(shù)字
-21.567 數(shù)字
abc123 標(biāo)識(shí)符
_ad 標(biāo)識(shí)符
if 關(guān)鍵字
實(shí)驗(yàn)思路
實(shí)現(xiàn)這個(gè)拼裝器，就會(huì)想到正則表達(dá)式。
為什么會(huì)涉及到正則表達(dá)式？
我們知道，要實(shí)現(xiàn)拼裝器的功能，需要識(shí)別關(guān)鍵字，特殊符號(hào)，運(yùn)算符號(hào)，這三類(lèi)是C++完全規(guī)定好的，比較好識(shí)別，我稱(chēng)其為簡(jiǎn)三類(lèi)。
另外三類(lèi)我稱(chēng)其為難三類(lèi)，它們是標(biāo)識(shí)符，數(shù)，注釋?zhuān)@三類(lèi)C++只是給了一個(gè)書(shū)寫(xiě)規(guī)則，并沒(méi)有具體規(guī)定它是什么，這個(gè)時(shí)候，我們就要用到正則表達(dá)式去匹配這三類(lèi)，看它們是否符合書(shū)寫(xiě)規(guī)則。
C++單詞拼裝器可以看作是詞法分析器的一個(gè)前導(dǎo)實(shí)驗(yàn)，因?yàn)榇藭r(shí)DFA和NFA還沒(méi)學(xué)利索，所以還不能用正則表達(dá)式來(lái)匹配難三類(lèi)（真正的詞法分析需要：正則表達(dá)式-->NFA--->DFA-->DFA最小化-->詞法分析），故本實(shí)驗(yàn)暫時(shí)用if-else if-else來(lái)枚舉各種情況。
代碼
1、首先要考慮的是文件操作。
#include <fstream>
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <cctype>
#include <sstream>
using namespace std;
int main() {
ifstream file("filename.txt"); //把filename處改為你要讀的file
if (!file) {//若文件打開(kāi)失敗，返回錯(cuò)誤
cout << "Unable to open file";
exit(1);
}
//將文件內(nèi)容讀到字符串fileContent里
string fileContent((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());
........
return 0;
}2、需要逐行逐個(gè)讀輸入，如果當(dāng)前讀到的不符合當(dāng)前類(lèi)型，保存并回退一個(gè)字符。
比如說(shuō)：我現(xiàn)在正在處理的串為：22.04 + 23.88，現(xiàn)在我的currentToken里有22.04，當(dāng)前類(lèi)型為digit，繼續(xù)往后讀，讀到了‘+’，‘+’類(lèi)型為symbol，所以digit結(jié)束并保存currentToken到resultToken中，別忘記把‘+’放回去，等待下一輪的讀取。
第一步：實(shí)現(xiàn)逐行處理，寫(xiě)一個(gè)split函數(shù)，它的功能是輸入一串字符，把這串字符逐行切割，并將切割結(jié)果逐行存儲(chǔ)在tokens里，返回tokens。
vector<string> split(const string &s, char delimiter) {//delimiter為切割這個(gè)串的字符
vector<string> tokens;
string token;
istringstream tokenStream(s);
while (getline(tokenStream, token, delimiter)) {
tokens.push_back(token);
}
return tokens;
}第二步：實(shí)現(xiàn)逐個(gè)處理
void Wordassembly(string fileContent) {
.............
vector<string> lines = split(fileContent, '\n');//返回切好的tokens
string resultText;//用來(lái)存儲(chǔ)處理結(jié)果
for (string &line: lines){//逐行處理
string currentToken;
.........
for (int i = 0; i < line.length(); ++i) {//逐個(gè)處理
char currentChar = line[i];
...........
}
}
}第三步：如果當(dāng)前讀到的不符合當(dāng)前類(lèi)型，保存并回退一個(gè)字符。
目前程序的實(shí)現(xiàn)方式是：讀我要分析的文件，將它保存在fileContent里 -> 用自己寫(xiě)的split函數(shù)逐行切割fileContent，以便實(shí)現(xiàn)逐行處理 -> 逐行逐個(gè)處理
??為防止對(duì)部分代碼產(chǎn)生疑惑，此處為代碼逐個(gè)字符處理邏輯的簡(jiǎn)述：
本代碼中實(shí)現(xiàn)的邏輯是，currentToken先讀一個(gè)line[i]進(jìn)去，然后再判斷currentToken究竟與什么匹配，在每個(gè)嘗試匹配的函數(shù)中，都會(huì)從line[i]開(kāi)始向后枚舉(i++)，逐個(gè)被currentToken接收，直到line[i]不是當(dāng)前類(lèi)型的字符，所以在進(jìn)入時(shí)我們需要清空currentToken，防止line[i]被接收兩次。
比如說(shuō)：currentToken讀了一個(gè)line[0] = '1'進(jìn)去，進(jìn)入匹配流程，匹配到它是一個(gè)數(shù)字，所以進(jìn)入處理數(shù)字的函數(shù)，此時(shí)i = 0，此時(shí)currenToken = "1"。
因?yàn)檫@個(gè)數(shù)字可能是1，也可能是123313，所以我們需要不停往后看（i++），邊看currentToken邊接收當(dāng)前字符，直到當(dāng)前字符不是一個(gè)數(shù)字為止。
我的邏輯是從i開(kāi)始看，在本例中，就是從i = 0開(kāi)始看。所以我需要在開(kāi)始看之前，先清空已經(jīng)記錄下line[0]的currenToken，防止它讀入兩次line[0]。
我們注意到，邏輯需要i++到直到當(dāng)前字符不是一個(gè)數(shù)字為止，當(dāng)前字符雖然不是一個(gè)數(shù)字，我們也不能把它丟掉，所以在每次匹配后我們還要把不是當(dāng)前類(lèi)型的當(dāng)前字符塞回去（i--），再進(jìn)行下一輪的匹配。
例：
void process_digit(string& currentToken, int& i ,string& line);
void Wordassembly(string fileContent) {
.............
vector<string> lines = split(fileContent, '\n');//返回切好的tokens
string resultText;//用來(lái)存儲(chǔ)處理結(jié)果
for (string &line: lines){//逐行處理
string currentToken;//記錄識(shí)別完成的字符
.........
for (int i = 0; i < line.length(); ++i) {//逐個(gè)處理
currentToken += line[i];//我們目前在看的字符
if(currentToken 是dight類(lèi)型){
process_digit(currentToken, i , line);
continue;
}
...........
}
}
}
void process_digit(string& currentToken, int& i ,string& line){
currentToken.clear();//倒掉
for(; i < line.size(); i++){
.........
if(line[i]不是digit){
break;
}
}
resultText += currentToken + "數(shù)字\n";
currentToken.clear();//清空currentToken
i--;//回退一個(gè)字符
}3、簡(jiǎn)三類(lèi)的處理
第一步：將可以識(shí)別的簡(jiǎn)三類(lèi)分別放在set里，set作為全局變量
set<string> keywords = { "asm", "auto", "bool", "break", "case", "catch", "char",
"class", "const", "continue", "default", "delete", "do", "double",
"else", "enum", "except", "explicit", "extern", "false", "finally",
"float", "for", "friend", "goto", "if", "inline", "int",
"long", "mutable", "namespace", "new", "operator", "private", "protected",
"public", "register", "return", "short", "signed", "sizeof", "static",
"struct", "string", "switch", "template", "this", "throw", "true",
"try", "typedef", "typename", "union", "unsigned", "using", "virtual",
"void", "while", "main", "std", "cin", "cout", "endl",
"scanf", "printf", "include", "define", "iostream.h", "iostream", "stdio.h"
};
set<string> symbols = { "$", "&", "_", "#", "<",
"<=", "=", ">", ">=", "<>",
"<<", "==", "!=", "&&", "||",
"!", ";", ".", "(", ")", "{", "}", ">>", "()"};
set<string> operate = { "+", "-", "*", "/", "++", "--", "^", "|", "%" };
第二步：開(kāi)始處理，找set里有沒(méi)有對(duì)應(yīng)的簡(jiǎn)三類(lèi)（第一個(gè)讀到的是字母，找keywords里有沒(méi)有，第一個(gè)讀到的是符號(hào)，找symbols/operate里有沒(méi)有），如果有，保存結(jié)果。
void Wordassembly(string fileContent) {
vector<string> lines = split(fileContent, '\n');
string resultText;//保存結(jié)果
for (string &line: lines) {
string currentToken;
for (int i = 0; i < line.length(); ++i) {
char currentChar = line[i];
process_Token_keywords(currentToken, keywords, resultText);//處理keywords
process_Token_op_or_sym(currentToken, symbols, operate, resultText);//處理符號(hào)和運(yùn)算符
}
}//處理keyword
bool isKeyword(const string& token, const set<string>& keywords) {
return keywords.find(token) != keywords.end();
}
void process_Token_keywords(string& currentToken, const set<string>& keywords, string& resultText) {
if (!currentToken.empty()) {
if (isKeyword(currentToken, keywords)) {//如果找到了keyword
resultText += currentToken + " 關(guān)鍵字\n";
currentToken.clear();
}
}
}//處理運(yùn)算符和其他符號(hào)
bool isSymbol(const string& token, const set<string>& symbols) {
return symbols.find(token) != symbols.end();
}
bool isOperator(const string& token, const set<string>& operators) {
return operators.find(token) != operators.end();
}
void process_Token_op_or_sym(string& currentToken, int& i, string& line, const set<string>& op, const set<string> &sym, string &resultText){
if(isSymbol(currentToken, sym)){//在symbols里找到了
//對(duì)兩個(gè)符號(hào)的特殊處理
if(currentToken == "<"){//列舉<開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '<'||line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + "特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken == ">"){//列舉>開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + "特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken == "="){//列舉=開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + "特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "運(yùn)算符號(hào)\n";//這里比較特殊，請(qǐng)注意
currentToken.clear();
}
}
else if(currentToken == "!"){//列舉!開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + "特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken == "&"){//列舉!開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '&')){
currentToken += line[i + 1];
resultText += currentToken + "特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken == "|"){//列舉!開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '|')){
currentToken += line[i + 1];
resultText += currentToken + "特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "特殊符號(hào)\n";
currentToken.clear();
}
}
else{
resultText += currentToken + "特殊符號(hào)\n";
currentToken.clear();}
}//end if
else if(isOperator(currentToken, op)){//在operator里找到了
//對(duì)包含兩個(gè)符號(hào)的特殊處理
if(currentToken == "+"){
if(i + 1 < line.size() && (line[i + 1] == '+')){
currentToken += line[i + 1];
resultText += currentToken + "運(yùn)算符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "運(yùn)算符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken == "-"){
if(i + 1 < line.size() && (line[i + 1] == '-')){
currentToken += line[i + 1];
resultText += currentToken + "運(yùn)算符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + "運(yùn)算符號(hào)\n";
currentToken.clear();
}
}
else{
resultText += currentToken + "運(yùn)算符號(hào)\n";
currentToken.clear();}
}//end else-if
}上述代碼只是看起來(lái)多，核心思想就是：當(dāng)我讀到一個(gè)字符時(shí)，比如我讀到了‘+’，它此時(shí)已經(jīng)可以與operator匹配了，但我們要想到，它也可能是‘++’，所以我們需要枚舉由兩個(gè)符號(hào)組成的符號(hào)的情況，以完成正確的匹配。
4、簡(jiǎn)三類(lèi)處理完畢，隨后處理難三類(lèi)
在正式開(kāi)始處理前，需要考慮空格的問(wèn)題，也就是說(shuō)，我們分析的這串程序，也可以以空格作為不同類(lèi)型的切分，比如說(shuō)int a，它用空格把keyword和標(biāo)識(shí)符分開(kāi)了。
所以我們可以加入isblank()的處理，它的作用是：分離兩個(gè)不同的類(lèi)型，并忽略無(wú)意義的空格。
空格包括：?'\f', '\r', '\t', '\v'。
在isblank里，需要先把currentToken清空一次，因?yàn)樵诒境绦虻倪壿嬂?，currentToken在輸入到isblank函數(shù)里之前，就已經(jīng)獲得了line[i]，若這個(gè)line[i]是一個(gè)空格，我們就需要把currentToken里的空格給倒掉，防止影響后續(xù)程序的判斷。
bool isblank(string& currentToken, int& i, string& line){
//是空格
if(i < line.size() && (line[i] == ' ' || line[i] == '\t' || line[i] == '\n' || line[i] == '\r' || line[i] == '\f' || line[i] == '\v')){
currentToken.clear();//倒掉空格
while(i < line.size() && (line[i] == ' ' || line[i] == '\t' || line[i] == '\n' || line[i] == '\r' || line[i] == '\f' || line[i] == '\v')){//跳過(guò)多個(gè)空格
i++;
}
i--;
return true;//表示有空格，且分離完成
}
//不是空格
return false;
}處理注釋?zhuān)捍颂幏譃閱涡泻投嘈?/p>
我們發(fā)現(xiàn)，注釋的識(shí)別與運(yùn)算符識(shí)別有重合，所以我們需要在運(yùn)算符識(shí)別里添加處理注釋的情況，字符串的識(shí)別與特殊符號(hào)識(shí)別有重合，所以我們需要在特殊符號(hào)識(shí)別里添加處理注釋的情況。
void process_Token_op_or_sym(string& currentToken, int& i, string& line, const set<string>& op, const set<string> &sym, string &resultText){
bool isComment = false;//可能匹配到注釋符號(hào)
........
if(isSymbol(currentToken, sym)){//在symbols里找到了
......
else if(currentToken == "\""){//處理string
currentToken.clear();
if(i + 1 < line.size()){//跳過(guò)前面的”
i++;
}
while(i < line.size() && line[i] != '"'){
currentToken += line[i];
i++;
}
if(i + 1 < line.size()){//跳過(guò)后面的“
i++;
}
resultText += currentToken + "字符串\n";
}
......
}
else if(isOperator(currentToken, op)){//在operator里找到了
......
else if(currentToken == "/"){
if(i + 1 < line.size() && (line[i + 1] == '/' || line[i + 1] == '*')){//處理注釋的情況
isComment = true;
}
else{
resultText += currentToken + "運(yùn)算符號(hào)\n";
currentToken.clear();
}
}
.......
}//end else-if
}string處理完畢，接下來(lái)要處理注釋
bool isComment(string& currentToken){
if(currentToken == "http://" || currentToken == "/*"){
return true;
}
return false;
}
void process_Comment(string& currentToken, int& i, string& line, string& resultText){
currentToken.clear();//因?yàn)槲也恍枰@示注釋符
bool is_break = false;
if(i + 1 < line.size()){//跳過(guò)當(dāng)前字符
i++;
}
for(;i < line.size(); i++){
if(line[i] == '*'){
if(i + 1 < line.size() && line[i] == '/'){
resultText += currentToken + "注釋\n";
currentToken.clear();
is_break = true;
break;
}
}
currentToken += line[i];
}
if(!is_break){
resultText += currentToken + "注釋\n";
currentToken.clear();
}
}處理數(shù)字：數(shù)字有浮點(diǎn)數(shù)，正負(fù)號(hào)，0x，指數(shù)（e, E）
我們注意到，需要處理標(biāo)識(shí)符中有數(shù)字的情況。
// 檢查是否為數(shù)字或正負(fù)號(hào)
bool isdigit(const string& currentToken){
if(currentToken.empty())
return false;
char firstChar = currentToken[0];
return std::isdigit(firstChar);
}
// 處理數(shù)字
void process_digit(string& currentToken, int& i, const string& line, string& resultText){
bool is_alpha = false;
i++;//因?yàn)閏urrentToken已經(jīng)獲得了line[i]
while(i < line.length() && (std::isdigit(line[i]) || line[i] == '.' || line[i] == 'e' || line[i] == 'E' || line[i] == '-' || line[i] == '+' ||(line[i - 1] == '0' && (line[i] == 'x' || line[i] == 'X')))) {
//先處理0x的情況
if(line[i - 1] == '0' && (line[i] == 'x' || line[i] == 'X')){//吃掉0x
currentToken += line[i];
i++;
}
// 如果遇到可能是標(biāo)識(shí)符的字符，停止處理數(shù)字
if (isalpha(line[i]) && line[i] != 'e' && line[i] != 'E') {
is_alpha = true;
break;
}
if(i + 1 < line.size() && line[i + 1] == '_'){
is_alpha = true;
break;
}
currentToken += line[i];
i++;
}//end while
i--;
if(is_alpha == false){
resultText += currentToken + " 數(shù)字\n";
currentToken.clear();
}
}處理標(biāo)識(shí)符
如果currentToken第一個(gè)是字母或者下劃線，它就有可能是標(biāo)識(shí)符，我們注意到，關(guān)鍵字屬于標(biāo)識(shí)符，所以把關(guān)鍵字處理也放到標(biāo)識(shí)符處理中。
注意，我們需要讓keyword遵守最長(zhǎng)匹配原則，實(shí)現(xiàn)最長(zhǎng)匹配原則，程序需要在遇到一個(gè)可能的關(guān)鍵字時(shí)繼續(xù)向前查看，直到確定沒(méi)有更長(zhǎng)的匹配可能。
比如說(shuō)double，不要匹配成do 關(guān)鍵字 uble 標(biāo)識(shí)符
//識(shí)別標(biāo)識(shí)符，把處理keyword放在處理標(biāo)識(shí)符的里面
bool issigned(const string& currentToken){
if(currentToken.empty())
return false;
char firstChar = currentToken[0];
return std::isalpha(firstChar) || firstChar == '_';
}
//處理標(biāo)識(shí)符
void process_signed(string& currentToken, int& i, const string& line, string& resultText){
string longestMatch;
currentToken.clear();//同樣是因?yàn)閏urrentToken已經(jīng)提前讀入了一個(gè)用于判斷，所以我們要把它倒回去
string tempToken = currentToken;
int tempIndex = i;
while(tempIndex < line.length() && (std::isdigit(line[tempIndex]) || std::isalpha(line[tempIndex]) || line[tempIndex] == '_')) {
tempToken += line[tempIndex];
if(isKeyword(tempToken, keywords)){
longestMatch = tempToken;
}
tempIndex++;
}
if(!longestMatch.empty()){
resultText += longestMatch + " 關(guān)鍵字\n";
currentToken.clear();
i = --tempIndex;//回退一個(gè)字符
} else {
while(i < line.length() && (std::isdigit(line[i]) || std::isalpha(line[i]) || line[i] == '_')) {
currentToken += line[i];
i++;
}
i--;//回退一個(gè)字符
resultText += currentToken + " 標(biāo)識(shí)符\n";
currentToken.clear();
}
}調(diào)用寫(xiě)好的所有功能
//調(diào)用所有寫(xiě)好的函數(shù)
void Wordassembly(string fileContent) {
vector<string> lines = split(fileContent, '\n');
string resultText;
for (string &line: lines) {
string currentToken;
currentToken.clear();
for (int i = 0; i < line.length(); i++) {
currentToken += line[i];
//處理符號(hào)
if(!currentToken.empty()){
if(isSymbol(currentToken, symbols)||isOperator(currentToken, operators)){
process_Token_op_or_sym(currentToken, i, line, operators, symbols, resultText);
}
//處理空格
if (isblank(currentToken, i, line)) {
continue;
}
// 處理注釋
if (isComment(currentToken)) {
process_Comment(currentToken, i, line, resultText);
continue;
}
//處理數(shù)字
if (isdigit(currentToken)) {
process_digit(currentToken, i, line, resultText);
continue;
}
// 首先嘗試將token識(shí)別為標(biāo)識(shí)符
if (issigned(currentToken)) {
process_signed(currentToken, i, line, resultText);
continue;
}
}
}
}
// 輸出結(jié)果
cout << resultText << endl;
}
最終程序
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <cctype>
#include <sstream>
#include <fstream>
using namespace std;
set<string> keywords = { "asm", "auto", "bool", "break", "case", "catch", "char",
"class", "const", "continue", "default", "delete", "do", "double",
"else", "enum", "except", "explicit", "extern", "false", "finally",
"float", "for", "friend", "goto", "if", "inline", "int",
"long", "mutable", "namespace", "new", "operator", "private", "protected",
"public", "register", "return", "short", "signed", "sizeof", "static",
"struct", "string", "switch", "template", "this", "throw", "true",
"try", "typedef", "typename", "union", "unsigned", "using", "virtual",
"void", "while", "main", "std", "cin", "cout", "endl",
"scanf", "printf", "include", "define", "iostream.h", "iostream", "stdio.h"
};
set<string> symbols = { "$", "&", "|", "#", "<",
"<=", "=", ">", ">=", "<>",
"<<", "==", "!=", "&&", "||",
"!", ";", ".", "(", ")", "{", "}", ">>"};
set<string> operators = { "+", "-", "*", "/", "++", "--", "^", "|", "%" };
vector<string> split(const string &s, char delimiter) {
vector<string> tokens;
string token;
istringstream tokenStream(s);
while (getline(tokenStream, token, delimiter)) {
tokens.push_back(token);
}
return tokens;
}
//處理簡(jiǎn)三類(lèi)
bool isKeyword(const string& token, const set<string>& keywords) {
return keywords.find(token) != keywords.end();
}
bool isSymbol(const string& token, const set<string>& symbols) {
return symbols.find(token) != symbols.end();
}
bool isOperator(const string& token, const set<string>& operators) {
return operators.find(token) != operators.end();
}
void process_Token_keywords(string& currentToken, const set<string>& keywords, string& resultText) {
if (!currentToken.empty()) {
if (isKeyword(currentToken, keywords)) {
resultText += currentToken + " 關(guān)鍵字\n";
currentToken.clear();
}
}
}
void process_Token_op_or_sym(string& currentToken, int& i, string& line, const set<string>& op, const set<string> &sym, string &resultText){
bool isComment = false;//可能匹配到注釋符號(hào)
if(isSymbol(currentToken, sym)){//在symbols里找到了
//對(duì)兩個(gè)符號(hào)的特殊處理
if(currentToken[0] == '<'){//列舉<開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '<'||line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + " 特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '>'){//列舉>開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + " 特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '='){//列舉=開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + " 特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 運(yùn)算符號(hào)\n";//這里比較特殊，請(qǐng)注意
currentToken.clear();
}
}
else if(currentToken[0] == '!'){//列舉!開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '=')){
currentToken += line[i + 1];
resultText += currentToken + " 特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '&'){//列舉!開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '&')){
currentToken += line[i + 1];
resultText += currentToken + " 特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '|'){//列舉!開(kāi)頭的特殊符號(hào)
if(i + 1 < line.size() && (line[i + 1] == '|')){
currentToken += line[i + 1];
resultText += currentToken + " 特殊符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 特殊符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '\"'){//處理string
currentToken.clear();
if(i + 1 < line.size()){//跳過(guò)前面的”
i++;
}
while(i < line.size() && line[i] != '"'){
currentToken += line[i];
i++;
}
if(i + 1 < line.size()){//跳過(guò)后面的“
i++;
}
resultText += currentToken + " 字符串\n";
currentToken.clear();
}
else{
resultText += currentToken + " 特殊符號(hào)\n";
currentToken.clear();
}
}//end if
else if(isOperator(currentToken, op)){//在operator里找到了
//對(duì)包含兩個(gè)符號(hào)的特殊處理
if(currentToken[0] == '+'){
if(i + 1 < line.size() && (line[i + 1] == '+')){
currentToken += line[i + 1];
resultText += currentToken + " 運(yùn)算符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 運(yùn)算符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '-'){
if(i + 1 < line.size() && (line[i + 1] == '-')){
currentToken += line[i + 1];
resultText += currentToken + " 運(yùn)算符號(hào)\n";
i++;//表示往前多讀了一個(gè)
currentToken.clear();
}
else{
resultText += currentToken + " 運(yùn)算符號(hào)\n";
currentToken.clear();
}
}
else if(currentToken[0] == '/'){
if(i + 1 < line.size() && (line[i + 1] == '/' || line[i + 1] == '*')){//處理注釋的情況
isComment = true;
}
else{
resultText += currentToken + " 運(yùn)算符號(hào)\n";
currentToken.clear();
}
}
else{
resultText += currentToken + " 運(yùn)算符號(hào)\n";
currentToken.clear();
}
}//end else-if
}
bool isblank(string& currentToken, int& i, string& line){
//是空格
if(i < line.size() && (line[i] == ' ' || line[i] == '\t' || line[i] == '\n' || line[i] == '\r' || line[i] == '\f' || line[i] == '\v')){
currentToken.clear();
while(i < line.size() && (line[i] == ' ' || line[i] == '\t' || line[i] == '\n' || line[i] == '\r' || line[i] == '\f' || line[i] == '\v')){//跳過(guò)多個(gè)空格
i++;
}
i--;
return true;//表示有空格，且分離完成
}
//不是空格
return false;
}
//處理注釋
bool isComment(string& currentToken){
if(currentToken == "http://" || currentToken == "/*"){
return true;
}
return false;
}
void process_Comment(string& currentToken, int& i, string& line, string& resultText){
currentToken.clear();//因?yàn)槲也恍枰@示注釋符
bool is_break = false;
if(i + 1 < line.size()){//跳過(guò)當(dāng)前字符
i++;
}
for(;i < line.size(); i++){
if(line[i] == '*'){
if(i + 1 < line.size() && line[i + 1] == '/'){
resultText += currentToken + "注釋\n";
i++;
currentToken.clear();
is_break = true;
break;
}
}
currentToken += line[i];
}
if(!is_break){
resultText += currentToken + "注釋\n";
currentToken.clear();
}
}
// 檢查是否為數(shù)字或正負(fù)號(hào)
bool isdigit(const string& currentToken){
if(currentToken.empty())
return false;
char firstChar = currentToken[0];
return std::isdigit(firstChar);
}
// 處理數(shù)字
void process_digit(string& currentToken, int& i, const string& line, string& resultText){
bool is_alpha = false;
i++;//因?yàn)閏urrentToken已經(jīng)獲得了line[i]
while(i < line.length() && (std::isdigit(line[i]) || line[i] == '.' || line[i] == 'e' || line[i] == 'E' || line[i] == '-' || line[i] == '+' ||(line[i - 1] == '0' && (line[i] == 'x' || line[i] == 'X')))) {
//先處理0x的情況
if(line[i - 1] == '0' && (line[i] == 'x' || line[i] == 'X')){//吃掉0x
currentToken += line[i];
i++;
}
// 如果遇到可能是標(biāo)識(shí)符的字符，停止處理數(shù)字
if (isalpha(line[i]) && line[i] != 'e' && line[i] != 'E') {
is_alpha = true;
break;
}
if(i + 1 < line.size() && line[i + 1] == '_'){
is_alpha = true;
break;
}
currentToken += line[i];
i++;
}//end while
i--;
if(is_alpha == false){
resultText += currentToken + " 數(shù)字\n";
currentToken.clear();
}
}
//識(shí)別標(biāo)識(shí)符，把處理keyword放在處理標(biāo)識(shí)符的里面
bool issigned(const string& currentToken){
if(currentToken.empty())
return false;
char firstChar = currentToken[0];
return std::isalpha(firstChar) || firstChar == '_';
}
//處理標(biāo)識(shí)符
void process_signed(string& currentToken, int& i, const string& line, string& resultText){
string longestMatch;
currentToken.clear();//同樣是因?yàn)閏urrentToken已經(jīng)提前讀入了一個(gè)用于判斷，所以我們要把它倒回去
string tempToken = currentToken;
int tempIndex = i;
while(tempIndex < line.length() && (std::isdigit(line[tempIndex]) || std::isalpha(line[tempIndex]) || line[tempIndex] == '_')) {
tempToken += line[tempIndex];
if(isKeyword(tempToken, keywords)){
longestMatch = tempToken;
}
tempIndex++;
}
if(!longestMatch.empty()){
resultText += longestMatch + " 關(guān)鍵字\n";
currentToken.clear();
i = --tempIndex;//回退一個(gè)字符
} else {
while(i < line.length() && (std::isdigit(line[i]) || std::isalpha(line[i]) || line[i] == '_')) {
currentToken += line[i];
i++;
}
i--;//回退一個(gè)字符
resultText += currentToken + " 標(biāo)識(shí)符\n";
currentToken.clear();
}
}
//調(diào)用所有寫(xiě)好的函數(shù)
void Wordassembly(string fileContent) {
vector<string> lines = split(fileContent, '\n');
string resultText;
for (string &line: lines) {
string currentToken;
currentToken.clear();
for (int i = 0; i < line.length(); i++) {
currentToken += line[i];
//處理符號(hào)
if(!currentToken.empty()){
if(isSymbol(currentToken, symbols)||isOperator(currentToken, operators)){
process_Token_op_or_sym(currentToken, i, line, operators, symbols, resultText);
}
//處理空格
if (isblank(currentToken, i, line)) {
continue;
}
// 處理注釋
if (isComment(currentToken)) {
process_Comment(currentToken, i, line, resultText);
continue;
}
//處理數(shù)字
if (isdigit(currentToken)) {
process_digit(currentToken, i, line, resultText);
continue;
}
// 首先嘗試將token識(shí)別為標(biāo)識(shí)符
if (issigned(currentToken)) {
process_signed(currentToken, i, line, resultText);
continue;
}
}
}
}
// 輸出結(jié)果
cout << resultText << endl;
}
int main(int argc, const char * argv[]) {
// 打開(kāi)文件
ifstream file("/Users/chaixichi/Desktop/學(xué)習(xí)資料/大三上/C++lab1/C++lab1/test.cpp"); //將文件名替換為打開(kāi)的文件路徑
// 查看是否可以打開(kāi)文件
if (!file) {
cout << "Unable to open file";
exit(1);
}
//將文件中讀到的字符串存入fileContent
string fileContent((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());
// //測(cè)試split
// vector<string>test = split(fileContent, '\n');
// for(int i = 0; i < test.size() ;i++){
// cout<<test[i]<<endl;
// }
Wordassembly(fileContent);
return 0;
}執(zhí)行結(jié)果
這玩意主要是摳細(xì)節(jié)比較煩，實(shí)現(xiàn)原理還是蠻簡(jiǎn)單的，就是讀完文件后，逐個(gè)字符遍歷，暴力枚舉所有情況，看一個(gè)字符匹配一次所有情況。
如果遇到一些識(shí)別不了的關(guān)鍵字，看看set里面有沒(méi)有，沒(méi)有的話給它加上就能成了。
還是詞法分析器比較惡心
詞法分析器
實(shí)驗(yàn)內(nèi)容
設(shè)計(jì)一個(gè)應(yīng)用軟件，以實(shí)現(xiàn)將正則表達(dá)式-->NFA--->DFA-->DFA最小化-->詞法分析程序
（1）正則表達(dá)式應(yīng)該支持單個(gè)字符，運(yùn)算符號(hào)有： 連接、選擇（|）、閉包（*）、括號(hào)（）、可選（?? ）
?（2）讀入一行（一個(gè)）或多行（多個(gè)）正則表達(dá)式（可保存、打開(kāi)正則表達(dá)式文件）
?（3）需要提供窗口以便用戶(hù)可以查看轉(zhuǎn)換得到的NFA（用狀態(tài)轉(zhuǎn)換表呈現(xiàn)即可）
?（4）需要提供窗口以便用戶(hù)可以查看轉(zhuǎn)換得到的DFA（用狀態(tài)轉(zhuǎn)換表呈現(xiàn)即可）
?（5）需要提供窗口以便用戶(hù)可以查看轉(zhuǎn)換得到的最小化DFA（用狀態(tài)轉(zhuǎn)換表呈現(xiàn)即可）
?（6）需要提供窗口以便用戶(hù)可以查看轉(zhuǎn)換得到的詞法分析程序（該分析程序需要用C/C++語(yǔ)言描述）
? （7）擴(kuò)充正則表達(dá)式的運(yùn)算符號(hào)，如?? [ ] 、 正閉包（+） 等。
實(shí)驗(yàn)思路
程序首先可以識(shí)別正則表達(dá)式，然后將正則表達(dá)式變?yōu)镹FA，將NFA去空+合成等價(jià)得到DFA，再合成等價(jià)的到最小化DFA，最后由DFA生成詞法分析程序。
個(gè)人理解本實(shí)驗(yàn)是浴簾想讓我們做一個(gè)輸入自己制定的詞法規(guī)則（輸入正則表達(dá)式），然后輸出這個(gè)詞法規(guī)則對(duì)應(yīng)的詞法分析器。
本次實(shí)驗(yàn)使用Thompson's構(gòu)造法來(lái)生成NFA，然后使用了子集構(gòu)造法來(lái)從NFA生成DFA。
部分理論知識(shí)
以下是在做實(shí)驗(yàn)產(chǎn)生的一些疑惑的解答。
1、為什么NFA引入了空串和分支？它們分別有什么作用？
我們知道，出現(xiàn)NFA是因?yàn)橹苯訉?xiě)出DFA有些困難或麻煩，比如：
考慮串：=、< =和=給出的記號(hào)。其中每一個(gè)都是一個(gè)固定串，但下圖不是一個(gè)正確的DFA，因?yàn)镈FA每一個(gè)狀態(tài)的下一個(gè)狀態(tài)都是確定的，不能存在分支。
所以最終會(huì)把剛才的圖合成為下圖，這樣才是一個(gè)DFA(給出一個(gè)狀態(tài)和字符，則通常肯定會(huì)有一個(gè)指向單個(gè)的新?tīng)顟B(tài)的唯一轉(zhuǎn)換)：
?
清晰地表示空串匹配同樣很有用，有時(shí)會(huì)使NFA比DFA更直觀且更容易表示。
比如說(shuō)表示正則表達(dá)式中的可選部分（即出現(xiàn)0次或1次的部分）。例如，對(duì)于正則表達(dá)式a?b（表示b前面可以有0個(gè)或1個(gè)a），又比如說(shuō)表示正則表達(dá)式中的重復(fù)部分（即出現(xiàn)0次或多次的部分）。例如，對(duì)于正則表達(dá)式（a｜b)*?？梢宰约簞?dòng)手畫(huà)圖嘗試一下。
2、最小化DFA，應(yīng)如何分割不同的非終結(jié)集，終結(jié)集？
首先回到原因，也就是我們?yōu)槭裁匆袲FA最小化？
說(shuō)白了就是需要效率，所以要把DFA冗余的地方剔除，使程序跑得更快。
明白了原因，我們就知道該怎么做了：最小化DFA就是要剔除DFA冗余的部分；1、合并等價(jià)狀態(tài)（如果兩個(gè)狀態(tài)對(duì)于所有可能的輸入，都轉(zhuǎn)移到相同（或等價(jià)）的狀態(tài)，那么這兩個(gè)狀態(tài)就被稱(chēng)為等價(jià)狀態(tài)）2、刪除無(wú)效狀態(tài)（無(wú)法達(dá)到的狀態(tài)，或者從這些狀態(tài)無(wú)法到達(dá)任何終止?fàn)顟B(tài)）。
問(wèn)題又來(lái)了，我們應(yīng)該如何判斷等價(jià)狀態(tài)/無(wú)效狀態(tài)？
等價(jià)狀態(tài)的判斷：
首先，將所有的狀態(tài)分為兩個(gè)集合，一個(gè)是終止?fàn)顟B(tài)，另一個(gè)是非終止?fàn)顟B(tài)。然后，反復(fù)細(xì)化這些集合，對(duì)于每個(gè)集合和每個(gè)輸入符號(hào)，如果集合中的狀態(tài)在該輸入符號(hào)下轉(zhuǎn)移到的狀態(tài)不在同一個(gè)集合中，那么就將這個(gè)集合分為兩個(gè)子集。反復(fù)進(jìn)行這個(gè)過(guò)程，直到所有的集合都不能再被分割。最后，每個(gè)集合中的狀態(tài)就是等價(jià)狀態(tài)，可以被合并。
舉個(gè)例子：
具體該如何判斷是否分割：比如說(shuō)我有兩個(gè)等價(jià)集合：{2, 4} {1, 3}，現(xiàn)在我開(kāi)始分割{2, 4}等價(jià)集合，2輸入a走到1，4輸入a走到3，此時(shí)因?yàn)?，3都在一個(gè)等價(jià)集合中，我們可以看作2,4輸入a后都走到了同一個(gè)狀態(tài)，所以我不分割{2, 4}集合。
但如果2輸入a走到4，4輸入a走到3，他們的終點(diǎn)4，3不屬于同一個(gè)等價(jià)集合，也就是它們不等價(jià)，此時(shí)我分割{2,4}集合為{2}, {4}。
1、首先開(kāi)始假設(shè)非終結(jié)態(tài)和終結(jié)態(tài)分別都等價(jià)，構(gòu)造等價(jià)集合：
非終結(jié)：{0, 1, 2}? 終結(jié)：{3, 4, 5, 6}
2、開(kāi)始觀察非終結(jié)集合是否等價(jià)
輸入a:
0 -> 1(屬于集合{0, 1 ,2})
1 ->3(屬于集合{3, 4, 5, 6})
2 -> 1(屬于集合{0, 1, 2})
所以此時(shí)0，2等價(jià)，3不等價(jià)于0，1，分割
此時(shí)非終結(jié)：{0, 2} {1} 終結(jié)：{3, 4, 5, 6}
輸入b:
0 -> 2(屬于集合{0, 1 ,2})
1 ->2(屬于集合{0, 1, 2})
2 -> 5(屬于集合{3，4，5，6})
所以此時(shí)2不等價(jià)于0，再分割
此時(shí)非終結(jié)：{0} {1} {2} 終結(jié)：{3, 4, 5, 6}
3、開(kāi)始觀察終結(jié)集合是否等價(jià)
輸入a:
3 -> 3(屬于集合{3, 4, 5, 6})
4 ->6(屬于集合{3, 4, 5, 6})
5 -> 6(屬于集合{3, 4, 5, 6})
6 -> 3(屬于集合{3, 4, 5, 6})
所以此時(shí)3,4,5,6等價(jià)，不分割
此時(shí)非終結(jié)：{0} {1} {2} 終結(jié)：{3, 4, 5, 6}
輸入b
......(不贅述了)
最終得到的最小化DFA結(jié)果：非終結(jié)：{0} {1} {2} 終結(jié)：{3, 4, 5, 6}
A= {0}（初態(tài)）、B = {1}、C = {2}、D = {3，4，5，6}?（終態(tài)）
無(wú)效狀態(tài)的判斷：
首先，從初始狀態(tài)開(kāi)始，標(biāo)記所有可以到達(dá)的狀態(tài)。然后，從所有的終止?fàn)顟B(tài)開(kāi)始，標(biāo)記所有可以到達(dá)的狀態(tài)。最后，那些沒(méi)有被標(biāo)記的狀態(tài)就是無(wú)效狀態(tài)，可以被刪除。（廣搜或深搜）
3、詞法分析器的工作
說(shuō)白了，詞法分析器作用如下：
1、讀源程序，識(shí)別源程序里的符號(hào)分別是什么。比如‘+’是運(yùn)算符加，abc123是一個(gè)標(biāo)識(shí)符，識(shí)別完成后，把它的識(shí)別結(jié)果放到符號(hào)表里。
2、光把識(shí)別結(jié)果放到符號(hào)表里可不行，語(yǔ)法分析器仍然不知道源程序是什么意思，所以詞法分析器還需要把源程序一個(gè)詞一個(gè)詞地切開(kāi)，并按順序發(fā)給語(yǔ)法分析器，語(yǔ)法分析器按順序接受，并查看符號(hào)表這個(gè)詞到底是什么意思，然后查看目前讀到的東西是否符合語(yǔ)法。
3、過(guò)濾掉源程序的注釋和空白。
重點(diǎn)代碼和分析
1、讀文件，逐行處理
（本實(shí)驗(yàn)可能出現(xiàn)多行正則表達(dá)式，浴簾讓我們把不同行的表達(dá)式用‘｜’相連），所以把實(shí)驗(yàn)一的代碼抄下來(lái)，做一些改動(dòng)。
（1）將不同行用‘｜’連接，且‘｜’不放在最后一行的末尾，使最終的fileContent只有一行。
（2）如果遇到兩個(gè)相連的字符，如ab，在中間添加‘&’，表示‘連接’。
#include <stdio.h>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <fstream>
#include "scanner.hpp"
#include "Lex.hpp"
using namespace std;
vector<string> split(const string &s, char delimiter) {
vector<string> tokens;
string token;
istringstream tokenStream(s);
while (getline(tokenStream, token, delimiter)) {
tokens.push_back(token);
}
return tokens;
}
int main(int argc, const char * argv[]) {
// 打開(kāi)文件
ifstream file("/Users/chaixichi/Desktop/學(xué)習(xí)資料/大三上/C++lab1/C++lab2/test2.cpp"); //將文件名替換為打開(kāi)的文件路徑
// 查看是否可以打開(kāi)文件
if (!file) {
cout << "Unable to open file";
exit(1);
}
//將文件中讀到的字符串不同行間加‘｜’合成為一行
string temp((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());
// //測(cè)試split
// vector<string>test = split(fileContent, '\n');
// for(int i = 0; i < test.size() ;i++){
// cout<<test[i]<<endl;
// }
vector<string> split_temp = split(temp, '\n');
string fileContent_temp, fileContent;
for(auto &t : split_temp){
if(t != split_temp.back()){
fileContent_temp += t + '|';
}
else{
fileContent_temp += t;
}
}
//將相連兩個(gè)字符中間加上'&'
for(int i = 0; i < fileContent_temp.size(); i++){
if(i + 1 < temp.size() && std::isalpha(fileContent_temp[i]) && std::isalpha(fileContent_temp[i + 1])){
fileContent += fileContent_temp[i];
fileContent += '&';
}
else{
fileContent += fileContent_temp[i];
}
}
//測(cè)試fileContent,最終處理結(jié)果存在fileContent里
cout<<fileContent;
return 0;
}現(xiàn)在我們?cè)趂ileContent里保存了我們處理后的正則表達(dá)式。
2、識(shí)別正則表達(dá)式&生成NFA
即使知道Thompson算法，實(shí)現(xiàn)由正則表達(dá)式轉(zhuǎn)換到NFA也有些無(wú)從下手。
但仔細(xì)想想，識(shí)別正則表達(dá)式，就是要把它的標(biāo)識(shí)符和運(yùn)算符拆開(kāi)，并確定運(yùn)算順序。
那我們應(yīng)該如何確定運(yùn)算順序？
所用數(shù)據(jù)結(jié)構(gòu)如下：
cclass MyGraph{
public:
int mVexNum;//頂點(diǎn)數(shù)目
int mEdgeNum;//邊的數(shù)目
//頂點(diǎn)（所有狀態(tài)）集合
vector<char> mMatrix[100][100];//鄰接矩陣，對(duì)應(yīng)的值為轉(zhuǎn)移條件，就是字母，默認(rèn)都是空''，表示未連接
public:
MyGraph();//默認(rèn)構(gòu)造函數(shù)
void printMyGraph(); //打印輸出圖內(nèi)容
void addEdge(int a, int b, char edgeCondition); //增加一條邊，邊上的值為轉(zhuǎn)換的條件
vector<char> getEdgeValue(int a ,int b);
};
class NFA{//只有一個(gè)結(jié)束狀態(tài)
public:
vector<int> mVexs;//NFA節(jié)點(diǎn)集合，存儲(chǔ)的是節(jié)點(diǎn)的序號(hào),位置的信息并沒(méi)有存儲(chǔ)內(nèi)容
MyGraph NFAGraph;//NFA圖的結(jié)構(gòu)
int startStatus;//開(kāi)始狀態(tài)的序號(hào)
int endStatus;//終止?fàn)顟B(tài)的序號(hào)
};
//給NFA棧中的元素的定義的一個(gè)結(jié)構(gòu)，存儲(chǔ)的是起點(diǎn)和終點(diǎn)的信息。
struct node{
public:
int nArray[2];//nArray[0]為起點(diǎn)，nArray[1]為終點(diǎn)
node(int a[2]){//構(gòu)造函數(shù)
for(int i =0;i<2;i++)
nArray[i] = a[i];
}
};
class Lex{
public:
NFA lexNFA;//NFA結(jié)構(gòu)
DFA lexDFA;//DFA結(jié)構(gòu)
stack <char> operatorStack;//操作符棧
stack <node> NFAStatusPointStack;//NFA棧中的NFA的起始點(diǎn)序號(hào)，0的位置代表起點(diǎn)，1的位置代表終點(diǎn)
vector<char> alphabet;//字母表，存儲(chǔ)是正則表達(dá)式中的字母
......
}重點(diǎn)1:Thompson算法，即用代碼實(shí)現(xiàn)Thompson算法（下面這幾張圖）
（1）創(chuàng)造最基本NFA
創(chuàng)造這個(gè)最基本的NFA，我們需要：創(chuàng)建兩個(gè)新節(jié)點(diǎn)，創(chuàng)建一條新邊，確定這條邊的起點(diǎn)和終點(diǎn)
創(chuàng)建新節(jié)點(diǎn)時(shí)，我們需要：記錄新節(jié)點(diǎn) + 設(shè)置起點(diǎn)終點(diǎn)
創(chuàng)建新邊時(shí)，我們需要：增加一條對(duì)邊的連接，邊的條件為我們輸入的字符
void Lex::createBasicNFA(char ch){
//據(jù)字母創(chuàng)建最基本NFA的操作
int startPoint = lexNFA.mVexs.size() + 1; //分配的節(jié)點(diǎn)序號(hào)是以前節(jié)點(diǎn)序號(hào)+1
int endPoint = startPoint + 1;
lexNFA.NFAGraph.addEdge(startPoint,endPoint,ch); //增加一個(gè)邊對(duì)邊的連接，邊的條件是轉(zhuǎn)換條件，就是該字符。
lexNFA.NFAGraph.mVexNum = lexNFA.NFAGraph.mVexNum+2; //增加兩個(gè)節(jié)點(diǎn)
lexNFA.NFAGraph.mEdgeNum++; //邊數(shù)加1
//添加到節(jié)點(diǎn)數(shù)組中
lexNFA.mVexs.push_back(startPoint);
lexNFA.mVexs.push_back(endPoint);
int newNFAStatusPoint[2];
newNFAStatusPoint[0] = startPoint;
newNFAStatusPoint[1] = endPoint;
NFAStatusPointStack.push(node(newNFAStatusPoint));
//起點(diǎn)終點(diǎn)設(shè)置
lexNFA.startStatus = startPoint;
lexNFA.endStatus = endPoint;
}（2）或‘｜’的運(yùn)算：
創(chuàng)造這個(gè)NFA，我們需要：創(chuàng)建兩個(gè)新節(jié)點(diǎn)，創(chuàng)建4條新邊（空輸入），確定這四條新邊的起點(diǎn)和終點(diǎn)
類(lèi)比（1），我們可以得出以下代碼：
void Lex::selectorCharacterOperation(){
//獲取棧頂兩個(gè)元素，注意，第一個(gè)獲取的元素為右式，因?yàn)闂：筮M(jìn)先出
int rightNFA[2];
for(int i = 0; i < 2;i++){
rightNFA[i] = NFAStatusPointStack.top().nArray[i];
}
NFAStatusPointStack.pop();
int leftNFA[2];
for(int i = 0; i < 2;i++){
leftNFA[i] = NFAStatusPointStack.top().nArray[i];
}
NFAStatusPointStack.pop();
//創(chuàng)建兩個(gè)新節(jié)點(diǎn)
int newStartPoint1 = lexNFA.mVexs.size() + 1;
int newStartPoint2 = newStartPoint1 + 1;
//比著圖連接
lexNFA.NFAGraph.addEdge(newStartPoint1, leftNFA[0], 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(newStartPoint1, rightNFA[0], 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(leftNFA[1], newStartPoint2, 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(rightNFA[1], newStartPoint2, 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.mVexNum = lexNFA.NFAGraph.mVexNum+2; //節(jié)點(diǎn)數(shù)目加2
lexNFA.NFAGraph.mEdgeNum = lexNFA.NFAGraph.mEdgeNum + 4; //邊的數(shù)目加4
//節(jié)點(diǎn)添加到節(jié)點(diǎn)數(shù)組中
lexNFA.mVexs.push_back(newStartPoint1);
lexNFA.mVexs.push_back(newStartPoint2);
//將新的NFA壓入NFA棧中
int newNFAStatusPoint[2];
newNFAStatusPoint[0] = newStartPoint1;
newNFAStatusPoint[1] = newStartPoint2;
NFAStatusPointStack.push(newNFAStatusPoint);
//設(shè)置起點(diǎn)終點(diǎn)
lexNFA.startStatus = newStartPoint1;
lexNFA.endStatus = newStartPoint2;
}3、‘&’與的運(yùn)算
只多了一條空轉(zhuǎn)移的邊
個(gè)人覺(jué)得是容易設(shè)坑的題，因?yàn)樗雌饋?lái)很簡(jiǎn)單，只連一條邊即可，但其實(shí)不是這么做的。
4、‘*’閉包的運(yùn)算
void Lex::repeatCharacterOperation(){
//獲取棧頂?shù)谝粋€(gè)元素
int top1NFA[2];//開(kāi)始和結(jié)束
for(int i = 0; i < 2;i++){
top1NFA[i] = NFAStatusPointStack.top().nArray[i];
}
NFAStatusPointStack.pop();
//創(chuàng)建兩個(gè)新的節(jié)點(diǎn)
int newStartPoint1 = lexNFA.mVexs.size() + 1;
int newStartPoint2 = newStartPoint1 + 1;
lexNFA.NFAGraph.addEdge(newStartPoint1, newStartPoint2, 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(newStartPoint1, top1NFA[0], 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(top1NFA[1], newStartPoint2, 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(top1NFA[0], top1NFA[1], 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.mVexNum = lexNFA.NFAGraph.mVexNum + 2;//節(jié)點(diǎn)數(shù)+2
lexNFA.NFAGraph.mEdgeNum = lexNFA.NFAGraph.mEdgeNum + 4;//節(jié)點(diǎn)數(shù)+4
//添加到節(jié)點(diǎn)數(shù)組中
lexNFA.mVexs.push_back(newStartPoint1);
lexNFA.mVexs.push_back(newStartPoint2);
//將新的NFA壓入NFA棧中
int newNFAStatusPoint[2];
newNFAStatusPoint[0] = newStartPoint1;
newNFAStatusPoint[1] = newStartPoint2;
NFAStatusPointStack.push(node(newNFAStatusPoint));
//起點(diǎn)終點(diǎn)設(shè)置
lexNFA.startStatus = newStartPoint1;
lexNFA.endStatus = newStartPoint2;
}5、‘+’正閉包的運(yùn)算
正閉包比起閉包，少了一個(gè)空運(yùn)算
void Lex::repeat1CharacterOperation(){
//彈出一個(gè)元素
int topNFA[2];
for(int i = 0; i < 2;i++){
topNFA[i] = NFAStatusPointStack.top().nArray[i];
}
//創(chuàng)建兩個(gè)新節(jié)點(diǎn)
int newStartPoint1 = lexNFA.mVexs.size() + 1;
int newStartPoint2 = newStartPoint1 + 1;
//比著圖連接
lexNFA.NFAGraph.addEdge(newStartPoint1, topNFA[0], 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(topNFA[1], newStartPoint2, 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(topNFA[1], topNFA[0], 'E');//空轉(zhuǎn)移
//新節(jié)點(diǎn)入節(jié)點(diǎn)數(shù)組
lexNFA.mVexs.push_back(newStartPoint1);
lexNFA.mVexs.push_back(newStartPoint2);
//新NFA入棧
int newNFAStatusPoint[2];
newNFAStatusPoint[0] = topNFA[0];
newNFAStatusPoint[1] = topNFA[1];
NFAStatusPointStack.push(node(newNFAStatusPoint));
//記錄起點(diǎn)和終點(diǎn)，在全局范圍內(nèi)跟蹤NFA的起點(diǎn)和終點(diǎn)
lexNFA.startStatus = newStartPoint1;
lexNFA.endStatus = newStartPoint2;
}6、‘？’一次或不做的運(yùn)算
void Lex::once_or_no_CharacterOperation(){
//彈出一個(gè)元素
int topNFA[2];
for(int i = 0; i < 2;i++){
topNFA[i] = NFAStatusPointStack.top().nArray[i];
}
//創(chuàng)建兩個(gè)新節(jié)點(diǎn)
int newStartPoint1 = lexNFA.mVexs.size() + 1;
int newStartPoint2 = newStartPoint1 + 1;
//比著圖連接
lexNFA.NFAGraph.addEdge(newStartPoint1, topNFA[0], 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(topNFA[1], newStartPoint2, 'E');//空轉(zhuǎn)移
lexNFA.NFAGraph.addEdge(newStartPoint1, newStartPoint2, 'E');//空轉(zhuǎn)移
//新節(jié)點(diǎn)入節(jié)點(diǎn)數(shù)組
lexNFA.mVexs.push_back(newStartPoint1);
lexNFA.mVexs.push_back(newStartPoint2);
//新NFA入棧
int newNFAStatusPoint[2];
newNFAStatusPoint[0] = topNFA[0];
newNFAStatusPoint[1] = topNFA[1];
NFAStatusPointStack.push(node(newNFAStatusPoint));
//記錄起點(diǎn)和終點(diǎn)，在全局范圍內(nèi)跟蹤NFA的起點(diǎn)和終點(diǎn)
lexNFA.startStatus = newStartPoint1;
lexNFA.endStatus = newStartPoint2;
}順序總結(jié)：
（1）根據(jù)運(yùn)算符彈出NFA
（2）創(chuàng)建新節(jié)點(diǎn)，創(chuàng)建新邊
（3）將新節(jié)點(diǎn)入節(jié)點(diǎn)數(shù)組
（4）將新NFA入棧（起點(diǎn)&終點(diǎn)）
（5）追蹤總NFA的起點(diǎn)和終點(diǎn)
重點(diǎn)2:由正則表達(dá)式生成NFA狀態(tài)轉(zhuǎn)移表
（1）生成NFA圖
本實(shí)驗(yàn)中使用到的正則表達(dá)式運(yùn)算符優(yōu)先級(jí)如下：
| 最優(yōu)先 | （） |
| 次優(yōu)先 | *、+、？ |
| 次次優(yōu)先 | 連接（&） |
| 最后 | ｜ |
該算法能夠直接掃描正則表達(dá)式并正確地計(jì)算運(yùn)算順序，主要是因?yàn)樗褂昧艘粋€(gè)運(yùn)算符棧來(lái)保存遇到的運(yùn)算符，并且在遇到新的運(yùn)算符時(shí)，會(huì)根據(jù)運(yùn)算符的優(yōu)先級(jí)來(lái)決定如何處理運(yùn)算符棧。
具體來(lái)說(shuō)，當(dāng)遇到一個(gè)新的運(yùn)算符時(shí)，會(huì)比較這個(gè)運(yùn)算符和運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)：
（1）如果新的運(yùn)算符的優(yōu)先級(jí)高于棧頂運(yùn)算符的優(yōu)先級(jí)，或者運(yùn)算符棧為空，或者棧頂運(yùn)算符是'('，則將新的運(yùn)算符壓入運(yùn)算符棧。
（2） 如果新的運(yùn)算符的優(yōu)先級(jí)等于或低于棧頂運(yùn)算符的優(yōu)先級(jí)，則會(huì)從運(yùn)算符棧中彈出運(yùn)算符，并執(zhí)行相應(yīng)的操作，直到棧頂運(yùn)算符的優(yōu)先級(jí)低于新的運(yùn)算符的優(yōu)先級(jí)，或者運(yùn)算符棧為空，或者棧頂運(yùn)算符是'('。然后，將新的運(yùn)算符壓入運(yùn)算符棧。
這樣，就可以保證在沒(méi)有括號(hào)改變優(yōu)先級(jí)的情況下，高優(yōu)先級(jí)的運(yùn)算符總是先于低優(yōu)先級(jí)的運(yùn)算符執(zhí)行，從而得到正確的運(yùn)算順序。
（3）此外，這個(gè)算法還使用了一個(gè)NFA棧來(lái)保存構(gòu)建過(guò)程中的中間結(jié)果。每當(dāng)從運(yùn)算符棧中彈出一個(gè)運(yùn)算符并執(zhí)行相應(yīng)的操作時(shí)，都會(huì)從NFA棧中彈出相應(yīng)數(shù)量的NFA，并將操作的結(jié)果壓入NFA棧。這樣，就可以保證在處理復(fù)雜的正則表達(dá)式時(shí)，總是先處理子表達(dá)式，然后再處理父表達(dá)式。
若當(dāng)前不是一個(gè)運(yùn)算符，創(chuàng)造一個(gè)最基本的NFA。
所以，雖然這個(gè)算法在掃描正則表達(dá)式時(shí)并沒(méi)有顯式地標(biāo)記運(yùn)算順序，但是通過(guò)使用運(yùn)算符棧和NFA棧，它能夠隱式地確定并遵循正確的運(yùn)算順序。
該算法在計(jì)算過(guò)程中，順便處理了連接符‘&’添加的問(wèn)題，比如在正則表達(dá)式（a|b)*a中，應(yīng)該將其變?yōu)?a|b)*&a,顯式地表示連接，ab變?yōu)閍&b，顯式地表示連接。
void Lex::getNFA(string regexInput){
unsigned long strlen = regexInput.length();
char ch;
//掃描正則表達(dá)式，建立運(yùn)算符棧和NFA棧
for(unsigned long i = 0; i < strlen; i++){
ch = regexInput[i];
if(isOperator(ch)){//是運(yùn)算符
switch(ch){
case '*':{
repeatCharacterOperation();
//如果下一個(gè)字符是字母或左括號(hào)，需要添加連接符
if((i + 1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){
operatorStack.push('&');
}
}break;
case '+':{
repeat1CharacterOperation();
//如果下一個(gè)字符是字母或左括號(hào)，需要添加連接符
if((i + 1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){
operatorStack.push('&');
}
}break;
case '?':{
once_or_no_CharacterOperation();
//如果下一個(gè)字符是字母或左括號(hào)，需要添加連接符
if((i + 1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){
operatorStack.push('&');
}
}break;
case '|':{
if(operatorStack.empty()){
cout<<"運(yùn)算符棧為空！"<<endl;
}
else{
ch = operatorStack.top();
while(ch != '('){//這里需要注意
if(ch == '&'){
joinerCharacterOperation();
}
else{
break;
}
operatorStack.pop();
ch = operatorStack.top();
}
}
operatorStack.push('|');//入棧
}break;
case '(':{
operatorStack.push(ch);
}
case ')':{
ch = operatorStack.top();
while(ch != '('){
switch(ch){
case '&':
joinerCharacterOperation();
break;
case '|':
selectorCharacterOperation();
break;
default:
break;
}
operatorStack.pop();
ch = operatorStack.top();
}//end while
operatorStack.pop();//移除棧內(nèi)左括號(hào)
//如果下一個(gè)字符是字母或者是左括號(hào)，需要添加連接符
if((i+1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){
operatorStack.push('&');
}
}break;
default:
cout<<"ok"<<ch<<endl;
break;
}//end switch
}//end if
else{//不是運(yùn)算符
auto flag = true;//是否添加到字母表中
for(int i = 0; i < alphabet.size(); i++){
if (ch == alphabet[i])
flag = false;
}
if(flag){
alphabet.push_back(ch);
}
//建立一個(gè)基本的NFA
createBasicNFA(ch);
//如果下一個(gè)字符是字母的話，就向符號(hào)棧中加入一個(gè)連接符&
if(i+1 <strlen && (!isOperator(regexInput[i+1]) || regexInput[i+1] == '(')){
operatorStack.push('&');
}
}//end else
}//end for
//對(duì)最終的NFA棧和運(yùn)算符棧進(jìn)行處理（如果不為空）
while(!operatorStack.empty()){
ch = operatorStack.top();
switch (ch) {
case '|':
selectorCharacterOperation();
break;
case '&':
joinerCharacterOperation();
break;
default:
break;
}
operatorStack.pop();
}
}總結(jié)：每一步都保證高優(yōu)先級(jí)的先運(yùn)算，要么不入棧直接運(yùn)算，要么把它留在棧頂。正則表達(dá)式遍歷結(jié)束后繼續(xù)運(yùn)算棧中剩下的元素。
最終我們得到了正則表達(dá)式字符表，NFA圖（NFA鄰接表）。
（2）生成NFA狀態(tài)轉(zhuǎn)移表
在正式開(kāi)始生成狀態(tài)轉(zhuǎn)移表之前，我們需要了解兩個(gè)問(wèn)題：
1、當(dāng)獲取一個(gè)狀態(tài)轉(zhuǎn)移時(shí)，我們需要知道什么？
我們需要知道三條信息：
【從哪個(gè)狀態(tài)出發(fā)、輸入是什么、到達(dá)哪個(gè)狀態(tài)】
2、最終生成的狀態(tài)轉(zhuǎn)移表長(zhǎng)什么樣？
| 狀態(tài)/輸入字符 | a | b |
| 1 | 1狀態(tài)輸入字符a所到達(dá)的狀態(tài) | 1狀態(tài)輸入字符b所到達(dá)的狀態(tài) |
| 2 | 2狀態(tài)輸入字符a所到達(dá)的狀態(tài) | 2狀態(tài)輸入字符b所到達(dá)的狀態(tài) |
為了生成狀態(tài)轉(zhuǎn)移表，我們需要獲得：
輸入字符集（在剛才生成NFA圖時(shí)，我們獲得的字母表就是輸入字符集）
狀態(tài)集
了解了這些問(wèn)題，我們就可以生成NFA狀態(tài)轉(zhuǎn)移表了
鄰接矩陣生成相關(guān)函數(shù)：
class NFA{
......
MyGraph NFAGraph;//存儲(chǔ)NFA的圖結(jié)構(gòu)
......
}
//默認(rèn)構(gòu)造函數(shù),初始邊和頂點(diǎn)數(shù)目都為0
MyGraph::MyGraph():mVexNum(0),mEdgeNum(0){
for(int i =0;i<100;i++){
for(int j =0;j<100;j++){
mMatrix[i][j].push_back('^') ;
}
}
}
//增加一條邊 a：節(jié)點(diǎn)名稱(chēng)、b：另一個(gè)節(jié)點(diǎn)名稱(chēng)、edgeCondition ：邊上的值，即轉(zhuǎn)換條件
void MyGraph::addEdge(int a, int b, char edgeCondition){
if (mMatrix[a][b].at(0) == '^'){
mMatrix[a][b].clear();
}
bool flag = true;
for (int i = 0; i < mMatrix[a][b].size() ; ++i) {
if (mMatrix[a][b].at(i) == edgeCondition){
flag = false;
break;
}
}
if (flag){//若沒(méi)有這樣的邊
mMatrix[a][b].push_back(edgeCondition);//加入
}
}最終得到的鄰接矩陣mMatrix長(zhǎng)這樣：
| 到達(dá)\出發(fā) | 1 | 2 | 3 |
| 1 | a | a | |
| 2 | b | E(空狀態(tài)) | |
| 3 | b |
橫著的表頭表示從哪個(gè)狀態(tài)出發(fā)，豎著的表頭表示到達(dá)哪個(gè)狀態(tài)，中間表示從xx狀態(tài)出發(fā)，到xx狀態(tài)，需要輸入xx
與狀態(tài)轉(zhuǎn)移表StatusMatrix作對(duì)比：
| 狀態(tài)/輸入字符 | a | b | E(空字符) |
| 1 | 1狀態(tài)輸入字符a所到達(dá)的狀態(tài) | 1狀態(tài)輸入字符b所到達(dá)的狀態(tài) | 1狀態(tài)輸入空字符所到達(dá)的狀態(tài) |
| 2 | 2狀態(tài)輸入字符a所到達(dá)的狀態(tài) | 2狀態(tài)輸入字符b所到達(dá)的狀態(tài) | 2狀態(tài)輸入空字符所到達(dá)的狀態(tài) |
| 3 | ..... | .... | ...... |
我們發(fā)現(xiàn)，逐列遍歷mMatrix即可把它轉(zhuǎn)化成狀態(tài)轉(zhuǎn)移表
比如說(shuō)，第一列代表從狀態(tài)1出發(fā)，我們看到第一列第一行，即，mMatrix[0][0] == 'a'，把它放到對(duì)應(yīng)狀態(tài)轉(zhuǎn)移表的位置StatusMatrix[0][0]，StatusMatrix[0][0] == 0，即代表從狀態(tài)1出發(fā)，輸入a（在狀態(tài)轉(zhuǎn)移表中，以a在字母表中的下標(biāo)代替a)，到達(dá)狀態(tài)1
代碼就不贅述了，就是一個(gè)遍歷的問(wèn)題。
3、NFA轉(zhuǎn)DFA
采用子集構(gòu)造法從NFA轉(zhuǎn)DFA，我愿稱(chēng)其為，瘋狂地求ε閉包。
我們知道，NFA比DFA多的東西就是空轉(zhuǎn)移&分支，所以將NFA轉(zhuǎn)換為DFA，就是把空轉(zhuǎn)移和分支去掉，能合并的合并。
此處需要引入一個(gè)等價(jià)集合的概念，即，某個(gè)節(jié)點(diǎn)在經(jīng)歷ε閉包運(yùn)算后，所得到的集合，我們稱(chēng)它為等價(jià)集合。
用一道具體的題目舉例：
我們可以清楚地看到，這幅NFA圖從狀態(tài)0開(kāi)始，但是它的初始狀態(tài)不僅僅是狀態(tài)0，應(yīng)該是從狀態(tài)0，經(jīng)過(guò)一個(gè)或多個(gè)ε所達(dá)到的狀態(tài)集合
（1）所以上圖初始狀態(tài)集合為：{0, 1, 2, 4, 7}，記為集合A，它是一個(gè)等價(jià)集合。
該NFA的字母表是{a, b}
（2）我們先向集合A中輸入狀態(tài)a，看它經(jīng)過(guò)一個(gè)a（期間可經(jīng)過(guò)多個(gè)ε）后，得到的集合
{1, 2, 3, 4, ?6, 7，8},記為集合B，它是一個(gè)等價(jià)集合，表示向等價(jià)集合A中輸入一個(gè)a后，所能到達(dá)的終點(diǎn)集合。
（3）我們?cè)傧蚣螦中輸入狀態(tài)b，看它經(jīng)過(guò)一個(gè)a（期間可經(jīng)過(guò)多個(gè)ε）后，得到的集合
{1, 2,?4, 5, 6, 7},記為集合C，它是一個(gè)等價(jià)集合。
（4）我們?cè)傧蚣螧中輸入狀態(tài)a，看它經(jīng)過(guò)一個(gè)a（期間可經(jīng)過(guò)多個(gè)ε）后，得到的集合
{1, 2, 3, 4, ?6, 7, 8},與集合B相同，沒(méi)有產(chǎn)生新的集合。
（5）我們?cè)傧蚣螧中輸入狀態(tài)b，看它經(jīng)過(guò)一個(gè)b（期間可經(jīng)過(guò)多個(gè)ε）后，得到的集合
{1, 2, 3, 4, 5，6, 7，9},產(chǎn)生新的集合D，它是一個(gè)等價(jià)集合。
.......不斷地嘗試，直到再也無(wú)法出現(xiàn)新的集合
最終得到：
用圖3-35生成的DFA圖
也就是說(shuō)，我們將問(wèn)題轉(zhuǎn)化為，按照剛才的ε閉包運(yùn)算規(guī)則，從初始狀態(tài)集合開(kāi)始，根據(jù)字母表（輸入的狀態(tài)表）不斷嘗試生成新集合，并對(duì)新集合進(jìn)行ε閉包運(yùn)算，直到不生成新集合，最后生成圖3-35的表即可。
ε閉包運(yùn)算，以下代碼把它拆成兩部分來(lái)實(shí)現(xiàn)。
第一部分是計(jì)算能從NFA的狀態(tài)數(shù)組statusArray中的某個(gè)狀態(tài)s開(kāi)始只通過(guò)E轉(zhuǎn)換到達(dá)的NFA狀態(tài)元素。
第二部分是能夠從NFA的狀態(tài)數(shù)組statusArray中的某個(gè)狀態(tài)出發(fā)，通過(guò)條件為condition轉(zhuǎn)換到達(dá)的NFA狀態(tài)集合。
將生成步驟總結(jié)如下：
（1）輸入狀態(tài)數(shù)組，將狀態(tài)數(shù)組壓入resultArray和statusArray。
（2）將statusArray里的元素一個(gè)個(gè)出棧，直到statusArray里為空，每出棧一個(gè)元素（狀態(tài)），在鄰接表里尋找是否有：由出棧狀態(tài)輸入指定字符（‘E’/condition）后達(dá)到的狀態(tài)，如果有，將達(dá)到的狀態(tài)壓入statusArray和resultArray。
（3）將resultArray去重，返回，返回的resultArray就是輸入的狀態(tài)集合輸入（‘E’/condition）所能到達(dá)的狀態(tài)集合。
//DFA：能從NFA的狀態(tài)數(shù)組statusArray中的某個(gè)狀態(tài)s開(kāi)始只通過(guò)E轉(zhuǎn)換到達(dá)的NFA狀態(tài)元素
vector<int> Lex::e_closure(vector<int> statusArray){
vector<int> resultsArray;//存放狀態(tài)數(shù)組的E轉(zhuǎn)換集合
stack<int> statusStack;//存放遞歸過(guò)程中的狀態(tài)，當(dāng)該棧為空時(shí)，遞歸結(jié)束
for(int i = 0; i < statusArray.size(); i++){
statusStack.push(statusArray[i]);//初始化狀態(tài)棧
resultsArray.push_back(statusArray[i]);//狀態(tài)本身也可以通過(guò)空轉(zhuǎn)換到本身，所以要將自身添加到結(jié)果數(shù)組
}
while(!statusStack.empty()){
int status = statusStack.top();
statusStack.pop();
for(int i = 1; i < lexNFA.mVexs.size() + 1; i++){
if(i == status){//查看以當(dāng)前狀態(tài)為起點(diǎn)的鄰接表
for(int j = 1; j < lexNFA.mVexs.size() + 1; j++){
if(lexNFA.NFAGraph.getEdgeValue(i, j).at(0) == 'E'){//若轉(zhuǎn)移條件為‘E’
statusStack.push(j);
resultsArray.push_back(j);
}
}
}
}//end for
}//end while
//去除重復(fù)元素
sort(resultsArray.begin(), resultsArray.end());
resultsArray.erase(unique(resultsArray.begin(), resultsArray.end()));
return resultsArray;
}
//DFA:能夠從NFA的狀態(tài)數(shù)組statusArray中的某個(gè)狀態(tài)出發(fā)，通過(guò)條件為condition轉(zhuǎn)換到達(dá)的NFA狀態(tài)集合
vector<int> Lex::nfaMove(vector<int> statusArray, char condition){
vector<int> resultArray;//結(jié)果數(shù)組
stack<int> statusStack;//狀態(tài)棧
//狀態(tài)集入棧
for(int i = 0 ; i < statusArray.size(); i++){
resultArray.push_back(statusArray[i]);
statusStack.push(statusArray[i]);
}
//開(kāi)始找
for(int i = 1; i < lexNFA.mVexs.size(); i++){
if(statusArray[i] == i){
for(int j = 1; j < lexNFA.mVexs.size(); i++){
if(lexNFA.NFAGraph.getEdgeValue(i, j).at(0) == condition){
resultArray.push_back(j);
statusStack.push(j);
}
}
}
}//end for
//去重
sort(resultArray.begin(), resultArray.end());
resultArray.erase(unique(resultArray.begin(), resultArray.end()));
return resultArray;
}那這兩個(gè)函數(shù)應(yīng)該如何調(diào)用，以模擬手動(dòng)的計(jì)算過(guò)程？
回想一下我們手動(dòng)的運(yùn)算順序：先利用ε閉包生成初始狀態(tài)集合，然后向初始狀態(tài)集合里依次投入字母表中的元素，試圖生成一個(gè)新的集合，生成新的集合后，我們向這個(gè)集合里依次投入字母表中的元素，試圖生成一個(gè)新的集合，直到最終無(wú)法生成新集合為止。
（1）利用ε閉包生成初始狀態(tài)集合。
void Lex::getDFA(){
//給DFA節(jié)點(diǎn)開(kāi)頭位置加一個(gè)空元素占位
lexDFA.mVexs.emplace_back(0);
vector<int> initStatus;
initStatus.push_back(lexNFA.startStatus);
vector<int> initStatusTrans(e_closure(vector<int>(initStatus)));//生成初始狀態(tài)集合
//給DFA創(chuàng)建第一個(gè)節(jié)點(diǎn)
int newDFAStartPoint = lexDFA.DFAGraph.mVexNum + 1;
lexDFA.DFAGraph.mVexNum++;//節(jié)點(diǎn)數(shù)+1
//DFA起點(diǎn)確定
lexDFA.startStatus = newDFAStartPoint;
stack<int> DFAStatusStack;//DFA狀態(tài)棧
DFAStatusStack.push(newDFAStartPoint);
lexDFA.mVexs.push_back(initStatus);//NFA起點(diǎn)的等價(jià)集合為DFA的起點(diǎn)
.........
}（2）根據(jù)初始狀態(tài)集合，計(jì)算DFA
首先要解決的問(wèn)題是，我們應(yīng)該如何判斷什么時(shí)候停止？即，什么時(shí)候不再產(chǎn)生新?tīng)顟B(tài)。
答案是利用一個(gè)DFAStatusStack，當(dāng)我們生成一個(gè)集合，嘗試入棧時(shí)，判斷該集合是否在我們已經(jīng)生成的DFA中，若是，則不壓入。
直到DFAStatusStack為空，即不再產(chǎn)生新的集合需要運(yùn)算。
void Lex::getDFA() {
//給DFA節(jié)點(diǎn)開(kāi)頭位置加一個(gè)空元素占位
lexDFA.mVexs.emplace_back(0);
vector<int> initStatus;
initStatus.push_back(lexNFA.startStatus);
vector<int>initStatusTrans(e_closure(vector<int>(initStatus)));
//給DFA創(chuàng)建第一個(gè)節(jié)點(diǎn)
int newDFAStartPoint = lexDFA.DFAGraph.mVexNum + 1;
lexDFA.DFAGraph.mVexNum ++;//節(jié)點(diǎn)數(shù)加1
lexDFA.startStatus = newDFAStartPoint;
stack<int> DFAStatusStack;//存儲(chǔ)還沒(méi)有經(jīng)過(guò)字母表轉(zhuǎn)換的DFA狀態(tài), DFA狀態(tài)棧,這個(gè)棧只需要存儲(chǔ)DFA的序號(hào)就可以了，沒(méi)存儲(chǔ)DFA節(jié)點(diǎn)對(duì)應(yīng)的NFA集合，
DFAStatusStack.push(newDFAStartPoint);
lexDFA.mVexs.push_back(initStatusTrans);//NFA起點(diǎn)的E轉(zhuǎn)換集合賦值給DFA的第一個(gè)節(jié)點(diǎn)
while (!DFAStatusStack.empty()){
int topDFAStack = DFAStatusStack.top();
DFAStatusStack.pop();
for (int i = 0; i < alphabet.size() ; ++i) { //對(duì)字母表的每個(gè)元素都需要作為轉(zhuǎn)換條件
vector<int> tempArray = e_closure(nfaMove(lexDFA.mVexs[topDFAStack],alphabet[i]));
if (tempArray.empty()){//如果轉(zhuǎn)換產(chǎn)生的NFA集合為空，跳過(guò)該次轉(zhuǎn)換即可
continue;
}
int position = isDFAStatusRepeat(tempArray);//判斷新生成DFA狀態(tài)是否已經(jīng)存在了，如果已經(jīng)存在，返回該狀態(tài)在節(jié)點(diǎn)的位置
if (position == -1){//這個(gè)是新生成的DFA狀態(tài)，沒(méi)有重復(fù)
int tempDFAStatusNode = lexDFA.DFAGraph.mVexNum + 1;
lexDFA.DFAGraph.mVexNum ++;//節(jié)點(diǎn)數(shù)加1
if (isEndDFAStatus(tempArray)){
lexDFA.endStatus.push_back(tempDFAStatusNode);
}
lexDFA.mVexs.push_back(tempArray);//把NFA集合賦值給DFA的狀態(tài)
DFAStatusStack.push(tempDFAStatusNode);//把新產(chǎn)生的DFA狀態(tài)加入到DFA棧中
position = tempDFAStatusNode;
}
//連接節(jié)點(diǎn)，產(chǎn)生邊
lexDFA.DFAGraph.addEdge(topDFAStack,position,alphabet[i]);
lexDFA.DFAGraph.mEdgeNum ++;
}
}
}
//判斷是否是DFA的終止?fàn)顟B(tài)，只要包含了NFA的終止?fàn)顟B(tài)的DFA狀態(tài)都是終止?fàn)顟B(tài)
bool Lex::isEndDFAStatus(vector<int> nfaArray){
for (int i = 0; i < nfaArray.size(); ++i) {
if (lexNFA.endStatus == nfaArray[i]){
return true;
}
}
return false;
}
//判斷新產(chǎn)生的DFA狀態(tài)是否已經(jīng)存在DFA狀態(tài)表中
int Lex::isDFAStatusRepeat(vector<int> a){
int position = -1;
for (int i = 1; i < lexDFA.mVexs.size()+1; ++i) {
if (a == lexDFA.mVexs[i]){
position = i;
break;
}
}
return position;
}有同學(xué)可能會(huì)疑惑，為什么只在生成開(kāi)始狀態(tài)集的時(shí)候調(diào)用了一次空運(yùn)算（e-closure），其他集合都在用nfaMove生成，那是因?yàn)樵谏蒒FA鄰接表時(shí)，空串不影響最終抵達(dá)的狀態(tài)。
4、最小化DFA
在手動(dòng)計(jì)算中，在得到DFA后，首先劃分非終結(jié)態(tài)和終結(jié)態(tài)集合，然后嘗試字母表中所有輸入，試圖再次分割非終結(jié)態(tài)和終結(jié)態(tài)集合。
例：假設(shè)我有一個(gè)非終結(jié)態(tài)集合（是一個(gè)等價(jià)集合）{1, 2, 3, 4},一個(gè)終結(jié)態(tài)集合（是一個(gè)等價(jià)集合）{5, 6}
我的字母表是{a, b}
(1)嘗試向非終結(jié)態(tài)集合{1, 2, 3, 4},輸入a
1輸入a到2? ? ?2輸入a到2? ?? ?3輸入a到1? ? ? 4輸入a到3
最終得到的終點(diǎn)集合為{2,1,3}，因?yàn)樗鼘儆谖覀兊牡葍r(jià)集合，不劃分。
(2)嘗試向非終結(jié)態(tài)集合{1, 2, 3, 4},輸入b
1輸入a到6? ? ?2輸入a到2? ?? ?3輸入a到5? ? ? 4輸入a到3
最終得到的終點(diǎn)集合為{2,3,5,6}，其中{2,3}屬于{1, 2, 3, 4},{5, 6}屬于{5,6}
所以劃分非終態(tài)集合{1, 2, 3, 4}為{1, 3},{2, 4}
(3)嘗試向終結(jié)態(tài)集合{5， 6},輸入a
。。。。。。。以此類(lèi)推
所以，我們代碼模擬的就是，找到非終結(jié)集合、終結(jié)集合，然后向其中逐個(gè)輸入字母表，得到終點(diǎn)集，判斷終點(diǎn)集是否屬于同一個(gè)等價(jià)集合，如果不是，按照終點(diǎn)集劃分，如果是，不劃分。
首先，將DFA的狀態(tài)分為兩類(lèi)：終止?fàn)顟B(tài)和非終止?fàn)顟B(tài)。這兩類(lèi)狀態(tài)被分別存儲(chǔ)在endPointArray和noEndPointArray中。
將這兩個(gè)數(shù)組被添加到dividedArrays中，這是 一個(gè)對(duì) 的數(shù)組，其中每個(gè)對(duì)的第一個(gè)元素是一個(gè)狀態(tài)數(shù)組，第二個(gè)元素是一個(gè)布爾值，表示該狀態(tài)數(shù)組是否可以進(jìn)一步劃分。
void Lex::minimizeDFA(){
vector<int> noEndPointArray;//非終止?fàn)顟B(tài)集合
vector<int> endPointArray(lexDFA.endStatus);//終止?fàn)顟B(tài)集合
//初始化非終止?fàn)顟B(tài)集合
for(int i = 0; i < lexDFA.mVexs.size(); i++){
if(!isInDFAEndStatus(i)){//不在終止?fàn)顟B(tài)集合里
noEndPointArray.push_back(i);
}
}
vector<pair<vector<int>, bool>> dividedArrays;//first存儲(chǔ)的是劃分的集合，second存儲(chǔ)的是該劃分集合是否可繼續(xù)劃分
dividedArrays.emplace_back(noEndPointArray, true);
dividedArrays.emplace_back(endPointArray, true);
...........
}然后，代碼進(jìn)入一個(gè)循環(huán)，直到所有的狀態(tài)數(shù)組都不能進(jìn)一步劃分為止。在每次循環(huán)中，代碼會(huì)遍歷dividedArrays中的每個(gè)狀態(tài)數(shù)組。對(duì)于每個(gè)狀態(tài)數(shù)組，代碼會(huì)遍歷字母表中的每個(gè)字母，然后對(duì)狀態(tài)數(shù)組中的每個(gè)狀態(tài)，找到通過(guò)當(dāng)前字母轉(zhuǎn)換后的狀態(tài)，并找到這個(gè)狀態(tài)所在的狀態(tài)數(shù)組的序號(hào)。然后，根據(jù)這些序號(hào)，將當(dāng)前狀態(tài)數(shù)組進(jìn)一步劃分。
這部分代碼有些長(zhǎng)，我想還是把它拆開(kāi)看吧
首先是：在每次循環(huán)中，代碼會(huì)遍歷dividedArrays中的每個(gè)狀態(tài)數(shù)組。對(duì)于每個(gè)狀態(tài)數(shù)組，代碼會(huì)遍歷字母表中的每個(gè)字母，然后對(duì)狀態(tài)數(shù)組中的每個(gè)狀態(tài)，找到通過(guò)當(dāng)前字母轉(zhuǎn)換后的狀態(tài)，并找到這個(gè)狀態(tài)所在的狀態(tài)數(shù)組的序號(hào)。
定義一些要用到的數(shù)據(jù)結(jié)構(gòu)：
void Lex::minimizeDFA(){
vector<int> noEndPointArray;//非終止?fàn)顟B(tài)集合
vector<int> endPointArray(lexDFA.endStatus);//終止?fàn)顟B(tài)集合
//初始化非終止?fàn)顟B(tài)集合
for(int i = 0; i < lexDFA.mVexs.size(); i++){
if(!isInDFAEndStatus(i)){//不在終止?fàn)顟B(tài)集合里
noEndPointArray.push_back(i);
}
}
vector<pair<vector<int>, bool>> dividedArrays;//first存儲(chǔ)的是待劃分的集合，second存儲(chǔ)的是該劃分集合是否可繼續(xù)劃分
dividedArrays.emplace_back(noEndPointArray, true);
dividedArrays.emplace_back(endPointArray, true);
bool flag = true;
while(flag){
for(int j = 0; j < dividedArrays.size(); j++){//對(duì)劃分的每個(gè)集合進(jìn)行操作
int canNotBeDivided = 0;//標(biāo)記是否當(dāng)前集合可以被劃分,1為不可
if(dividedArrays[j].first.size() == 1){//該集合元素只有一個(gè)，必不可劃分
dividedArrays[j].second = false;
continue;
vector<int> arrayNumVector;//存放DFA狀態(tài)經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的結(jié)果集
vector<pair<int, int>> statusMap;//存放每個(gè)節(jié)點(diǎn)結(jié)果集序號(hào) 該節(jié)點(diǎn)本身序號(hào)
}
}//end for j
}//end while
}然后，正式開(kāi)始對(duì) 待劃分 的每個(gè)集合進(jìn)行操作（逐個(gè)嘗試輸入字母表中的符號(hào)，記錄結(jié)果集，查看結(jié)果集是否在一個(gè)等價(jià)集合中）
j循環(huán)，嘗試對(duì)劃分的每個(gè)集合進(jìn)行操作
i循環(huán)，當(dāng)前劃分的集合嘗試逐個(gè)輸入字符表
k循環(huán)，對(duì)當(dāng)前劃分的集合嘗試輸入當(dāng)前字符，逐個(gè)記錄當(dāng)前劃分的集合元素序號(hào) 到 當(dāng)前劃分的集合輸入當(dāng)前字符后所到達(dá)的狀態(tài)屬于的等價(jià)集合 的映射
//最小化DFA
void Lex::minimizeDFA(){
.........
vector<pair<vector<int>, bool>> dividedArrays;//first存儲(chǔ)的是待劃分的集合，second存儲(chǔ)的是該劃分集合是否可繼續(xù)劃分
dividedArrays.emplace_back(noEndPointArray, true);
dividedArrays.emplace_back(endPointArray, true);
bool flag = true;
while(flag){
for(int j = 0; j < dividedArrays.size(); j++){//對(duì)劃分的每個(gè)集合進(jìn)行操作
int canNotBeDivided = 0;//標(biāo)記是否當(dāng)前集合可以被劃分,1為不可
if(dividedArrays[j].first.size() == 1){//該集合元素只有一個(gè)，必不可劃分
dividedArrays[j].second = false;
continue;
}
vector<int> arrayNumVector;//存放DFA狀態(tài)經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的結(jié)果集
vector<pair<int, int>> statusMap;//存放每個(gè)節(jié)點(diǎn)結(jié)果集序號(hào) 該節(jié)點(diǎn)本身序號(hào)
for(int i = 0; i < alphabet.size(); i++){
for(int k = 0; k < dividedArrays[j].first.size(); k++){
//獲取待劃分集合的每個(gè)元素轉(zhuǎn)換狀態(tài)屬于的集合序號(hào)
int transStatus = lexDFA.getTargetStatus(dividedArrays[j].first[k], alphabet[i]);
//看我們當(dāng)前得到的轉(zhuǎn)換狀態(tài)屬于哪個(gè)待劃分集合
int statusInArrayNum = getContainPosition(transStatus, dividedArrays);
if(statusInArrayNum == -1){//沒(méi)有轉(zhuǎn)換結(jié)果，也就是當(dāng)前元素?zé)o法接收alpha[i]
arrayNumVector.push_back(statusInArrayNum);
}
else{//當(dāng)前元素可以接收alpha[i]
if(!isContain(statusInArrayNum, arrayNumVector)){//避免結(jié)果集中狀態(tài)重復(fù)
arrayNumVector.push_back(statusInArrayNum);
}
}
statusMap.emplace_back(statusInArrayNum, dividedArrays[j].first[k]);//將元素轉(zhuǎn)換狀態(tài)屬于的集合序號(hào) 該元素本身序號(hào)壓入
}//end for k
}//end for i
}//end for j
}//end while
}拿到這個(gè)映射后，我們就可以根據(jù)這個(gè)映射劃分集合了，將映射到相同等價(jià)集合的元素劃為一個(gè)集合
看起來(lái)有些復(fù)雜，其實(shí)整體的思路如下
（1）設(shè)定一個(gè)數(shù)組，arrayNumVector，用于存放當(dāng)前DFA狀態(tài)集經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的結(jié)果集，不斷嘗試向當(dāng)前DFA狀態(tài)集中放入字母，如果集合元素?zé)o法接受當(dāng)前字母，記為-1，入arrayNumVector，如果可以接收，記接收后轉(zhuǎn)換到的狀態(tài)，入arrayNumVector。
順便設(shè)定一個(gè)Map,statusMap，記錄當(dāng)前元素輸入當(dāng)前字母后，它的轉(zhuǎn)換后的狀態(tài)屬于我們劃分的哪個(gè)集合。（劃分集合號(hào)，當(dāng)前狀態(tài)）
（2）得到當(dāng)前DFA狀態(tài)集經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的結(jié)果集arrayNumVector，當(dāng)前狀態(tài)與劃分的集合的映射statusMap后，開(kāi)始判斷是否要?jiǎng)澐帧?/p>
若結(jié)果集只有一個(gè)元素，無(wú)論如何都不需要?jiǎng)澐?，如果有多個(gè)元素，檢查statusMap判斷是否要?jiǎng)澐帧?/p>
遍歷statusMap，將當(dāng)前集合號(hào)相同 的狀態(tài)劃入一個(gè)數(shù)組，如果最后得到的數(shù)組與已有的劃分集合相同，將當(dāng)前在看的劃分集合標(biāo)記為false，表示不能再劃分。
如果最后得到的數(shù)組與已有的劃分集合不同，壓入劃分集合，刪除劃分集合中當(dāng)前在看的劃分集合，表示當(dāng)前集合已經(jīng)劃分為壓入的劃分集合。
（3）遍歷劃分集合數(shù)組，若都為false，表示都不能劃分，劃分結(jié)束，退出劃分循環(huán)，開(kāi)始合并DFA等價(jià)狀態(tài)。
void Lex::minimizeDFA(){
......
vector<pair<vector<int>, bool>> dividedArrays;//first存儲(chǔ)的是待劃分的集合，second存儲(chǔ)的是該劃分集合是否可繼續(xù)劃分
dividedArrays.emplace_back(noEndPointArray, true);
dividedArrays.emplace_back(endPointArray, true);
bool flag = true;
while(flag){
for(int j = 0; j < dividedArrays.size(); j++){//對(duì)劃分的每個(gè)集合進(jìn)行操作
int canNotBeDivided = 0;//標(biāo)記是否當(dāng)前集合可以被劃分,1為不可
if(dividedArrays[j].first.size() == 1){//該集合元素只有一個(gè)，必不可劃分
dividedArrays[j].second = false;
continue;
}
vector<int> arrayNumVector;//存放DFA狀態(tài)經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的結(jié)果集
vector<pair<int, int>> statusMap;//存放每個(gè)節(jié)點(diǎn)結(jié)果集序號(hào) 該節(jié)點(diǎn)本身序號(hào)
for(int i = 0; i < alphabet.size(); i++){
for(int k = 0; k < dividedArrays[j].first.size(); k++){
//獲取待劃分集合的每個(gè)元素轉(zhuǎn)換狀態(tài)屬于的集合序號(hào)
int transStatus = lexDFA.getTargetStatus(dividedArrays[j].first[k], alphabet[i]);
//看我們當(dāng)前得到的轉(zhuǎn)換狀態(tài)屬于哪個(gè)待劃分集合
int statusInArrayNum = getContainPosition(transStatus, dividedArrays);
if(statusInArrayNum == -1){//沒(méi)有轉(zhuǎn)換結(jié)果，也就是當(dāng)前元素?zé)o法接收alpha[i]
arrayNumVector.push_back(statusInArrayNum);
}
else{//當(dāng)前元素可以接收alpha[i]
if(!isContain(statusInArrayNum, arrayNumVector)){//避免結(jié)果集中狀態(tài)重復(fù)
arrayNumVector.push_back(statusInArrayNum);
}
}
statusMap.emplace_back(statusInArrayNum, dividedArrays[j].first[k]);//將元素轉(zhuǎn)換狀態(tài)屬于的集合序號(hào) 該元素本身序號(hào)壓入
}//end for k
if(arrayNumVector.size() == 1){//DFA狀態(tài)經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的結(jié)果集只有1個(gè)
canNotBeDivided++;
continue;//不劃分，看下一個(gè)字母
}
else{//開(kāi)始劃分
for(int l = 0; l < arrayNumVector.size(); l++){
vector<int> tempArray;
for(int k = 0; k < statusMap.size(); i++){
if(arrayNumVector[l] == -1 && statusMap[k].first == -1){
statusMap[k].first = -2;//-2代表刪除狀態(tài)
tempArray.push_back(statusMap[k].second);
break;
}
else{
if(statusMap[k].first == arrayNumVector[l]){//根據(jù)集合序號(hào)劃分
tempArray.push_back(statusMap[k].second);
}
}
dividedArrays.emplace_back(tempArray, true);
}//end k
auto iter = dividedArrays.begin() + j;
dividedArrays.erase(iter);
j--;
break;//當(dāng)前集合結(jié)束，調(diào)到下一個(gè)位置的集合，因?yàn)閯h除了該元素，其他元素前移一位,所以j--
}//end l
}
}//end for i
if(canNotBeDivided == alphabet.size()){
dividedArrays[j].second = false;
}
}//end for j
//判斷是否結(jié)束循環(huán)，如果劃分集合下面所有集合都不可分就推出循環(huán)
flag = false;
for(int m = 0; m < dividedArrays.size(); m++){
if(dividedArrays[m].second == true){
flag = true;
break;
}
}//end for m
}//end while
}合并DFA等價(jià)狀態(tài)：遍歷劃分集合，把每個(gè)劃分集合都合成為一個(gè)點(diǎn)，合成后給每個(gè)點(diǎn)分配編號(hào)
void Lex::mergeTwoNode(int a,int b){
for (int i = 1; i < lexDFA.mVexs.size()+1 ; ++i) {
if (i == b){
for (int j = 1; j < lexDFA.mVexs.size()+1 ; ++j) {
if (lexDFA.DFAGraph.getEdgeValue(b,j).at(0) != '^'){
if (j == b){
lexDFA.DFAGraph.addEdge(a,a,lexDFA.DFAGraph.getEdgeValue(b,j).at(0));
} else{
lexDFA.DFAGraph.addEdge(a,j,lexDFA.DFAGraph.getEdgeValue(b,j).at(0));
}
lexDFA.DFAGraph.deleteEdge(b,j);
lexDFA.mVexs[b] = vector<int>();
}
}
} else{
for (int j = 1; j < lexDFA.mVexs.size() + 1; ++j) {
if (j == b && lexDFA.DFAGraph.getEdgeValue(i,b).at(0)!='^'){
lexDFA.DFAGraph.addEdge(i,a,lexDFA.DFAGraph.getEdgeValue(i,b).at(0));
lexDFA.DFAGraph.deleteEdge(i,j);
lexDFA.mVexs[b] = vector<int>();
break;
}
}
}
}
}
void Lex::minimizeDFA() {
vector<int> noEndPointArray;//非終止態(tài)節(jié)點(diǎn)集合
vector<int> endPointArray(lexDFA.endStatus);
//非終止?fàn)顟B(tài)集合
for (int i = 1; i < lexDFA.mVexs.size(); ++i) {
if (!isInDFAEndStatus(i)){
noEndPointArray.push_back(i);
}
}//初始化非終止節(jié)點(diǎn)集合
cout << endl;
//終止?fàn)顟B(tài)集合
for (int n = 0; n < endPointArray.size(); ++n) {
cout << endPointArray[n] << " ";
}
cout << endl;
vector<pair<vector<int>,bool>> dividedArrays;//first存儲(chǔ)的是劃分的集合，second存儲(chǔ)的是該劃分集合是否可繼續(xù)劃分
dividedArrays.emplace_back(noEndPointArray, true);
dividedArrays.emplace_back(endPointArray, true);
bool flag = true;
while(flag){
for (int j = 0; j < dividedArrays.size(); ++j) {//對(duì)劃分的每個(gè)集合進(jìn)行操作
cout << endl;
int canNotBeDivided = 0;//經(jīng)過(guò)一次字母表的轉(zhuǎn)換，如果該集合的轉(zhuǎn)換狀態(tài)只有一個(gè)，說(shuō)明該集合不能被該字母區(qū)分，該變量+1
if (dividedArrays[j].first.size() == 1){
dividedArrays[j].second = false;//如果集合元素只有一個(gè)，賦值為false，即不可再劃分
continue;
}
for (int i = 0; i < alphabet.size() ; ++i) {
for (int m = 0; m < dividedArrays[j].first.size(); ++m) {
cout << dividedArrays[j].first[m] << " ";
}
cout << "當(dāng)前字母為" << alphabet[i] << endl;
vector<int> arrayNumVector;//存放DFA狀態(tài)經(jīng)過(guò)某個(gè)字母轉(zhuǎn)換到的集合序號(hào)的數(shù)組
//first 為轉(zhuǎn)換狀態(tài)屬于的集合序號(hào)，second DFA起點(diǎn)的狀態(tài)節(jié)點(diǎn)
vector<pair<int,int>> statusMap;//存放了每個(gè)節(jié)點(diǎn)的轉(zhuǎn)換后屬于的集合序號(hào)——該節(jié)點(diǎn)本身序號(hào)
for (int k = 0; k < dividedArrays[j].first.size(); ++k) { //獲取到該集合的每個(gè)元素的轉(zhuǎn)換狀態(tài)屬于的集合序號(hào)
int transStatus = lexDFA.getTargetStatus(dividedArrays[j].first[k],alphabet[i]);//獲取節(jié)點(diǎn)的轉(zhuǎn)換DFA節(jié)點(diǎn)
int statusInArrayNum = getContainPosition(transStatus,dividedArrays);//轉(zhuǎn)換狀態(tài)屬于的集合序號(hào)
if(statusInArrayNum == -1){//必須進(jìn)行劃分，這個(gè)時(shí)候雖然沒(méi)有轉(zhuǎn)換結(jié)果，所以需要將集合序號(hào)人為設(shè)置一個(gè)唯一的數(shù)
statusInArrayNum = -1;
arrayNumVector.push_back(statusInArrayNum);
}else{
if (!isContain(statusInArrayNum,arrayNumVector)){//防止集合序號(hào)的重復(fù)
arrayNumVector.push_back(statusInArrayNum);//將集合序號(hào)加入到集合序號(hào)數(shù)組中
}
}
statusMap.emplace_back(statusInArrayNum,dividedArrays[j].first[k]);//將集合序號(hào)————對(duì)于的DFA狀態(tài)組壓入
}
if (arrayNumVector.size() == 1){
canNotBeDivided ++ ;
continue;
}else{
for (int m = 0; m < arrayNumVector.size(); ++m) {
}
for (int l = 0; l < arrayNumVector.size(); ++l) {//進(jìn)行劃分
vector<int> tempArray;
for (int k = 0; k < statusMap.size(); ++k) {
if (arrayNumVector[l] == -1 && statusMap[k].first == -1){//key為-1.說(shuō)明是一定要?jiǎng)澐值? //刪除該元素
statusMap[k].first = -2;//-2代表刪除狀態(tài)
tempArray.push_back(statusMap[k].second);
break;
} else{
if (statusMap[k].first == arrayNumVector[l]){//根據(jù)集合序號(hào)進(jìn)行劃分
tempArray.push_back(statusMap[k].second);
}
}
}
cout << endl;
dividedArrays.emplace_back(tempArray, true);
}
auto iter = dividedArrays.begin()+j;
dividedArrays.erase(iter);
j--;
break;//當(dāng)前集合結(jié)束，調(diào)到下一個(gè)位置的集合，因?yàn)閯h除了該元素，其他元素前移一位,所以j--
}
}//end i
if (canNotBeDivided == alphabet.size()){
dividedArrays[j].second = false;//如果一個(gè)集合經(jīng)過(guò)轉(zhuǎn)換后還是該集合本身，該集合無(wú)需再進(jìn)行劃分
}
}//end j
//判斷是否結(jié)束循環(huán)，如果劃分集合下面的所有集合都不可劃分就退出循環(huán)
flag = false;
for (int m = 0; m < dividedArrays.size(); ++m) {
if (dividedArrays[m].second == true){
flag = true;
break;
}
}
}
//合并DFA等價(jià)狀態(tài)
for (int j1 = 0; j1 < dividedArrays.size(); ++j1) {
if (dividedArrays[j1].first.size() > 1){//只要每個(gè)集合的大小大于1，說(shuō)明有需要合并的
int represent = dividedArrays[j1].first[0];
for (int i = 1; i < dividedArrays[j1].first.size(); ++i) {//除了第一個(gè)節(jié)點(diǎn)，其他節(jié)點(diǎn)都和第一個(gè)節(jié)點(diǎn)合并
mergeTwoNode(represent,dividedArrays[j1].first[i]);//合并這兩個(gè)節(jié)點(diǎn)
}
}
}
}5、生成C語(yǔ)言詞法分析程序
程序長(zhǎng)這樣
開(kāi)整！
得到了最簡(jiǎn)DFA后，我們就可以生成C語(yǔ)言詞法分析程序了
通過(guò)最簡(jiǎn)DFA，我們可以獲得：1、狀態(tài)數(shù) 2、字母表 3、每個(gè)狀態(tài)輸入字母表后轉(zhuǎn)換到的位置文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-844536.html
根據(jù)這些信息，我們就可以生成詞法分析程序了！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-844536.html
void Lex::generateCCode(MyGraph myGraph){
string tag1 =" ";
string tag2 =" ";
string tag3 =" ";
string text="#include<stdio.h> \r\n\r\nint main(){\r\n"
+ tag1 + "int stateID = 1;\r\n"
+ tag1 + "int toexit = 0;\r\n"
+ tag1 + "while(!toexit){\r\n"
+ tag2 + "char ch = gettoken();\r\n"
+ tag2 + "switch(stateID){ //不可變部分\r\n\r\n"
+ tag3 + "http://可變部分\r\n";
string result = "";
int num = myGraph.mVexNum+1;
for(int i = 1; i<num; i ++){
int flag_case=1;
int flag_else=0;
int flag_elseif = 0;
for(int j = 0; j<num; j++){
if (myGraph.getEdgeValue(i,j).at(0) != '^'){
if(flag_case = 1){
result += tag3 + "case " + to_string(i) + ":\r\n";
flag_case = 0;
flag_else++;
}
for (int k = 0; k <myGraph.getEdgeValue(i,j).size() ; ++k) {
if(flag_elseif==0){
result += tag3 + "if(ch == " + myGraph.getEdgeValue(i,j).at(k) + ") stateID = "
+ to_string(j) + ";\r\n";
flag_elseif ++;
}
else{
result += tag3 + "else if(ch == " + myGraph.getEdgeValue(i,j).at(k) + ") stateID = "
+ to_string(j) + ";\r\n";
}
}
}
if(flag_else!=0 && j == num-1){
result += tag3 + "else toexit = 1;\r\n"
+ tag3 + "break;\r\n\r\n";
}
}
}
text += result + tag3 + string("default:\r\n") + tag3 + "toexit = 1;\r\n" + tag3 +"break;\r\n";
text += tag2 + "}\r\n"
+ tag1 + "}\r\n"
"}\r\n";
}到了這里，關(guān)于編譯原理C++單詞拼裝器&詞法分析器實(shí)驗(yàn)思路的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
