2021级浴帘实验
本文只涉及功能实现的思路,针对期末复习,不涉及制作操作界面。
C++单词拼装器
实验内容
1. 把C++源代码中的各类单词(记号)进行拼装分类。
C++语言包含了几种类型的单词(记号):标识符,关键字,数(包括整数、浮点数),字符串、注释、特殊符号(分界符)和运算符号等【详细的单词类别及拼装规则见另外的文件说明】。
2. 打开一个C++源文件,列出所有可以拼装的单词(记号)。
最后呈现的内容:
# 特殊符号
20.26 数字
-21.567 数字
abc123 标识符
_ad 标识符
if 关键字
实验思路
实现这个拼装器,就会想到正则表达式。
为什么会涉及到正则表达式?
我们知道,要实现拼装器的功能,需要识别关键字,特殊符号,运算符号,这三类是C++完全规定好的,比较好识别,我称其为简三类。
另外三类我称其为难三类,它们是标识符,数,注释,这三类C++只是给了一个书写规则,并没有具体规定它是什么,这个时候,我们就要用到正则表达式去匹配这三类,看它们是否符合书写规则。
C++单词拼装器可以看作是词法分析器的一个前导实验,因为此时DFA和NFA还没学利索,所以还不能用正则表达式来匹配难三类(真正的词法分析需要:正则表达式-->NFA--->DFA-->DFA最小化-->词法分析),故本实验暂时用if-else if-else来枚举各种情况。
代码
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) {//若文件打开失败,返回错误 cout << "Unable to open file"; exit(1); } //将文件内容读到字符串fileContent里 string fileContent((istreambuf_iterator<char>(file)), istreambuf_iterator<char>()); ........ return 0;}
2、需要逐行逐个读输入,如果当前读到的不符合当前类型,保存并回退一个字符。
比如说:我现在正在处理的串为:22.04 + 23.88,现在我的currentToken里有22.04,当前类型为digit,继续往后读,读到了‘+’,‘+’类型为symbol,所以digit结束并保存currentToken到resultToken中,别忘记把‘+’放回去,等待下一轮的读取。
第一步:实现逐行处理,写一个split函数,它的功能是输入一串字符,把这串字符逐行切割,并将切割结果逐行存储在tokens里,返回tokens。
vector<string> split(const string &s, char delimiter) {//delimiter为切割这个串的字符 vector<string> tokens; string token; istringstream tokenStream(s); while (getline(tokenStream, token, delimiter)) { tokens.push_back(token); } return tokens;}
第二步:实现逐个处理
void Wordassembly(string fileContent) { ............. vector<string> lines = split(fileContent, '\n');//返回切好的tokens string resultText;//用来存储处理结果 for (string &line: lines){//逐行处理 string currentToken; ......... for (int i = 0; i < line.length(); ++i) {//逐个处理 char currentChar = line[i]; ........... } }}
第三步:如果当前读到的不符合当前类型,保存并回退一个字符。
目前程序的实现方式是:读我要分析的文件,将它保存在fileContent里 -> 用自己写的split函数逐行切割fileContent,以便实现逐行处理 -> 逐行逐个处理
⚠️为防止对部分代码产生疑惑,此处为代码逐个字符处理逻辑的简述:
本代码中实现的逻辑是,currentToken先读一个line[i]进去,然后再判断currentToken究竟与什么匹配,在每个尝试匹配的函数中,都会从line[i]开始向后枚举(i++),逐个被currentToken接收,直到line[i]不是当前类型的字符,所以在进入时我们需要清空currentToken,防止line[i]被接收两次。
比如说:currentToken读了一个line[0] = '1'进去,进入匹配流程,匹配到它是一个数字,所以进入处理数字的函数,此时i = 0,此时currenToken = "1"。
因为这个数字可能是1,也可能是123313,所以我们需要不停往后看(i++),边看currentToken边接收当前字符,直到当前字符不是一个数字为止。
我的逻辑是从i开始看,在本例中,就是从i = 0开始看。所以我需要在开始看之前,先清空已经记录下line[0]的currenToken,防止它读入两次line[0]。
我们注意到,逻辑需要i++到直到当前字符不是一个数字为止,当前字符虽然不是一个数字,我们也不能把它丢掉,所以在每次匹配后我们还要把不是当前类型的当前字符塞回去(i--),再进行下一轮的匹配。
例:
void process_digit(string& currentToken, int& i ,string& line);void Wordassembly(string fileContent) { ............. vector<string> lines = split(fileContent, '\n');//返回切好的tokens string resultText;//用来存储处理结果 for (string &line: lines){//逐行处理 string currentToken;//记录识别完成的字符 ......... for (int i = 0; i < line.length(); ++i) {//逐个处理 currentToken += line[i];//我们目前在看的字符 if(currentToken 是dight类型){ 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 + "数字\n"; currentToken.clear();//清空currentToken i--;//回退一个字符}
3、简三类的处理
第一步:将可以识别的简三类分别放在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 = { "+", "-", "*", "/", "++", "--", "^", "|", "%" };
第二步:开始处理,找set里有没有对应的简三类(第一个读到的是字母,找keywords里有没有,第一个读到的是符号,找symbols/operate里有没有),如果有,保存结果。
void Wordassembly(string fileContent) { vector<string> lines = split(fileContent, '\n'); string resultText;//保存结果 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);//处理符号和运算符 }}
//处理keywordbool 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 + " 关键字\n"; currentToken.clear(); } }}
//处理运算符和其他符号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里找到了 //对两个符号的特殊处理 if(currentToken == "<"){//列举<开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '<'||line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + "特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "特殊符号\n"; currentToken.clear(); } } else if(currentToken == ">"){//列举>开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + "特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "特殊符号\n"; currentToken.clear(); } } else if(currentToken == "="){//列举=开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + "特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "运算符号\n";//这里比较特殊,请注意 currentToken.clear(); } } else if(currentToken == "!"){//列举!开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + "特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "特殊符号\n"; currentToken.clear(); } } else if(currentToken == "&"){//列举!开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '&')){ currentToken += line[i + 1]; resultText += currentToken + "特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "特殊符号\n"; currentToken.clear(); } } else if(currentToken == "|"){//列举!开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '|')){ currentToken += line[i + 1]; resultText += currentToken + "特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "特殊符号\n"; currentToken.clear(); } } else{ resultText += currentToken + "特殊符号\n"; currentToken.clear();} }//end if else if(isOperator(currentToken, op)){//在operator里找到了 //对包含两个符号的特殊处理 if(currentToken == "+"){ if(i + 1 < line.size() && (line[i + 1] == '+')){ currentToken += line[i + 1]; resultText += currentToken + "运算符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "运算符号\n"; currentToken.clear(); } } else if(currentToken == "-"){ if(i + 1 < line.size() && (line[i + 1] == '-')){ currentToken += line[i + 1]; resultText += currentToken + "运算符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + "运算符号\n"; currentToken.clear(); } } else{ resultText += currentToken + "运算符号\n"; currentToken.clear();} }//end else-if}
上述代码只是看起来多,核心思想就是:当我读到一个字符时,比如我读到了‘+’,它此时已经可以与operator匹配了,但我们要想到,它也可能是‘++’,所以我们需要枚举由两个符号组成的符号的情况,以完成正确的匹配。
4、简三类处理完毕,随后处理难三类
在正式开始处理前,需要考虑空格的问题,也就是说,我们分析的这串程序,也可以以空格作为不同类型的切分,比如说int a,它用空格把keyword和标识符分开了。
所以我们可以加入isblank()的处理,它的作用是:分离两个不同的类型,并忽略无意义的空格。
空格包括: '\f', '\r', '\t', '\v'。
在isblank里,需要先把currentToken清空一次,因为在本程序的逻辑里,currentToken在输入到isblank函数里之前,就已经获得了line[i],若这个line[i]是一个空格,我们就需要把currentToken里的空格给倒掉,防止影响后续程序的判断。
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')){//跳过多个空格 i++; } i--; return true;//表示有空格,且分离完成 } //不是空格 return false;}
处理注释:此处分为单行和多行
我们发现,注释的识别与运算符识别有重合,所以我们需要在运算符识别里添加处理注释的情况,字符串的识别与特殊符号识别有重合,所以我们需要在特殊符号识别里添加处理注释的情况。
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;//可能匹配到注释符号 ........ if(isSymbol(currentToken, sym)){//在symbols里找到了 ...... else if(currentToken == "\""){//处理string currentToken.clear(); if(i + 1 < line.size()){//跳过前面的” i++; } while(i < line.size() && line[i] != '"'){ currentToken += line[i]; i++; } if(i + 1 < line.size()){//跳过后面的“ 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 + "运算符号\n"; currentToken.clear(); } } ....... }//end else-if}
string处理完毕,接下来要处理注释
bool isComment(string& currentToken){ if(currentToken == "//" || currentToken == "/*"){ return true; } return false;}void process_Comment(string& currentToken, int& i, string& line, string& resultText){ currentToken.clear();//因为我不需要显示注释符 bool is_break = false; if(i + 1 < line.size()){//跳过当前字符 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(); } }
处理数字:数字有浮点数,正负号,0x,指数(e, E)
我们注意到,需要处理标识符中有数字的情况。
// 检查是否为数字或正负号bool isdigit(const string& currentToken){ if(currentToken.empty()) return false; char firstChar = currentToken[0]; return std::isdigit(firstChar);}// 处理数字void process_digit(string& currentToken, int& i, const string& line, string& resultText){ bool is_alpha = false; i++;//因为currentToken已经获得了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++; } // 如果遇到可能是标识符的字符,停止处理数字 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 + " 数字\n"; currentToken.clear(); }}
处理标识符
如果currentToken第一个是字母或者下划线,它就有可能是标识符,我们注意到,关键字属于标识符,所以把关键字处理也放到标识符处理中。
注意,我们需要让keyword遵守最长匹配原则,实现最长匹配原则,程序需要在遇到一个可能的关键字时继续向前查看,直到确定没有更长的匹配可能。
比如说double,不要匹配成do 关键字 uble 标识符
//识别标识符,把处理keyword放在处理标识符的里面bool issigned(const string& currentToken){ if(currentToken.empty()) return false; char firstChar = currentToken[0]; return std::isalpha(firstChar) || firstChar == '_';}//处理标识符void process_signed(string& currentToken, int& i, const string& line, string& resultText){ string longestMatch; currentToken.clear();//同样是因为currentToken已经提前读入了一个用于判断,所以我们要把它倒回去 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 + " 关键字\n"; currentToken.clear(); i = --tempIndex;//回退一个字符 } else { while(i < line.length() && (std::isdigit(line[i]) || std::isalpha(line[i]) || line[i] == '_')) { currentToken += line[i]; i++; } i--;//回退一个字符 resultText += currentToken + " 标识符\n"; currentToken.clear(); }}
调用写好的所有功能
//调用所有写好的函数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]; //处理符号 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; } //处理数字 if (isdigit(currentToken)) { process_digit(currentToken, i, line, resultText); continue; } // 首先尝试将token识别为标识符 if (issigned(currentToken)) { process_signed(currentToken, i, line, resultText); continue; } } } } // 输出结果 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;}//处理简三类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 + " 关键字\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;//可能匹配到注释符号 if(isSymbol(currentToken, sym)){//在symbols里找到了 //对两个符号的特殊处理 if(currentToken[0] == '<'){//列举<开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '<'||line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + " 特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 特殊符号\n"; currentToken.clear(); } } else if(currentToken[0] == '>'){//列举>开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '>'||line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + " 特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 特殊符号\n"; currentToken.clear(); } } else if(currentToken[0] == '='){//列举=开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + " 特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 运算符号\n";//这里比较特殊,请注意 currentToken.clear(); } } else if(currentToken[0] == '!'){//列举!开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '=')){ currentToken += line[i + 1]; resultText += currentToken + " 特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 特殊符号\n"; currentToken.clear(); } } else if(currentToken[0] == '&'){//列举!开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '&')){ currentToken += line[i + 1]; resultText += currentToken + " 特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 特殊符号\n"; currentToken.clear(); } } else if(currentToken[0] == '|'){//列举!开头的特殊符号 if(i + 1 < line.size() && (line[i + 1] == '|')){ currentToken += line[i + 1]; resultText += currentToken + " 特殊符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 特殊符号\n"; currentToken.clear(); } } else if(currentToken[0] == '\"'){//处理string currentToken.clear(); if(i + 1 < line.size()){//跳过前面的” i++; } while(i < line.size() && line[i] != '"'){ currentToken += line[i]; i++; } if(i + 1 < line.size()){//跳过后面的“ i++; } resultText += currentToken + " 字符串\n"; currentToken.clear(); } else{ resultText += currentToken + " 特殊符号\n"; currentToken.clear(); } }//end if else if(isOperator(currentToken, op)){//在operator里找到了 //对包含两个符号的特殊处理 if(currentToken[0] == '+'){ if(i + 1 < line.size() && (line[i + 1] == '+')){ currentToken += line[i + 1]; resultText += currentToken + " 运算符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 运算符号\n"; currentToken.clear(); } } else if(currentToken[0] == '-'){ if(i + 1 < line.size() && (line[i + 1] == '-')){ currentToken += line[i + 1]; resultText += currentToken + " 运算符号\n"; i++;//表示往前多读了一个 currentToken.clear(); } else{ resultText += currentToken + " 运算符号\n"; currentToken.clear(); } } else if(currentToken[0] == '/'){ if(i + 1 < line.size() && (line[i + 1] == '/' || line[i + 1] == '*')){//处理注释的情况 isComment = true; } else{ resultText += currentToken + " 运算符号\n"; currentToken.clear(); } } else{ resultText += currentToken + " 运算符号\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')){//跳过多个空格 i++; } i--; return true;//表示有空格,且分离完成 } //不是空格 return false;}//处理注释bool isComment(string& currentToken){ if(currentToken == "//" || currentToken == "/*"){ return true; } return false;}void process_Comment(string& currentToken, int& i, string& line, string& resultText){ currentToken.clear();//因为我不需要显示注释符 bool is_break = false; if(i + 1 < line.size()){//跳过当前字符 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(); } }// 检查是否为数字或正负号bool isdigit(const string& currentToken){ if(currentToken.empty()) return false; char firstChar = currentToken[0]; return std::isdigit(firstChar);}// 处理数字void process_digit(string& currentToken, int& i, const string& line, string& resultText){ bool is_alpha = false; i++;//因为currentToken已经获得了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++; } // 如果遇到可能是标识符的字符,停止处理数字 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 + " 数字\n"; currentToken.clear(); }}//识别标识符,把处理keyword放在处理标识符的里面bool issigned(const string& currentToken){ if(currentToken.empty()) return false; char firstChar = currentToken[0]; return std::isalpha(firstChar) || firstChar == '_';}//处理标识符void process_signed(string& currentToken, int& i, const string& line, string& resultText){ string longestMatch; currentToken.clear();//同样是因为currentToken已经提前读入了一个用于判断,所以我们要把它倒回去 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 + " 关键字\n"; currentToken.clear(); i = --tempIndex;//回退一个字符 } else { while(i < line.length() && (std::isdigit(line[i]) || std::isalpha(line[i]) || line[i] == '_')) { currentToken += line[i]; i++; } i--;//回退一个字符 resultText += currentToken + " 标识符\n"; currentToken.clear(); }}//调用所有写好的函数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]; //处理符号 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; } //处理数字 if (isdigit(currentToken)) { process_digit(currentToken, i, line, resultText); continue; } // 首先尝试将token识别为标识符 if (issigned(currentToken)) { process_signed(currentToken, i, line, resultText); continue; } } } } // 输出结果 cout << resultText << endl;}int main(int argc, const char * argv[]) { // 打开文件 ifstream file("/Users/chaixichi/Desktop/学习资料/大三上/C++lab1/C++lab1/test.cpp"); //将文件名替换为打开的文件路径 // 查看是否可以打开文件 if (!file) { cout << "Unable to open file"; exit(1); } //将文件中读到的字符串存入fileContent string fileContent((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());// //测试split// vector<string>test = split(fileContent, '\n');// for(int i = 0; i < test.size() ;i++){// cout<<test[i]<<endl;// } Wordassembly(fileContent); return 0;}
执行结果
这玩意主要是抠细节比较烦,实现原理还是蛮简单的,就是读完文件后,逐个字符遍历,暴力枚举所有情况,看一个字符匹配一次所有情况。
如果遇到一些识别不了的关键字,看看set里面有没有,没有的话给它加上就能成了。
还是词法分析器比较恶心
词法分析器
实验内容
设计一个应用软件,以实现将正则表达式-->NFA--->DFA-->DFA最小化-->词法分析程序
(1)正则表达式应该支持单个字符,运算符号有: 连接、选择(|)、闭包(*)、括号()、可选(? )
(2)读入一行(一个)或多行(多个)正则表达式(可保存、打开正则表达式文件)
(3)需要提供窗口以便用户可以查看转换得到的NFA(用状态转换表呈现即可)
(4)需要提供窗口以便用户可以查看转换得到的DFA(用状态转换表呈现即可)
(5)需要提供窗口以便用户可以查看转换得到的最小化DFA(用状态转换表呈现即可)
(6)需要提供窗口以便用户可以查看转换得到的词法分析程序(该分析程序需要用C/C++语言描述)
(7)扩充正则表达式的运算符号,如 [ ] 、 正闭包(+) 等。
实验思路
程序首先可以识别正则表达式,然后将正则表达式变为NFA,将NFA去空+合成等价得到DFA,再合成等价的到最小化DFA,最后由DFA生成词法分析程序。
个人理解本实验是浴帘想让我们做一个输入自己制定的词法规则(输入正则表达式),然后输出这个词法规则对应的词法分析器。
本次实验使用Thompson's构造法来生成NFA,然后使用了子集构造法来从NFA生成DFA。
部分理论知识
以下是在做实验产生的一些疑惑的解答。
1、为什么NFA引入了空串和分支?它们分别有什么作用?
我们知道,出现NFA是因为直接写出DFA有些困难或麻烦,比如:
考虑串:=、< =和=给出的记号。其中每一个都是一个固定串,但下图不是一个正确的DFA,因为DFA每一个状态的下一个状态都是确定的,不能存在分支。
所以最终会把刚才的图合成为下图,这样才是一个DFA(给出一个状态和字符,则通常肯定会有一个指向单个的新状态的唯一转换):
![](http://zhangshiyu.com/zb_users/upload/2024/04/20240406114530171237513033007.png)
![](http://zhangshiyu.com/zb_users/upload/2024/04/20240406114531171237513118811.png)
清晰地表示空串匹配同样很有用,有时会使NFA比DFA更直观且更容易表示。
比如说表示正则表达式中的可选部分(即出现0次或1次的部分)。例如,对于正则表达式a?b(表示b前面可以有0个或1个a),又比如说表示正则表达式中的重复部分(即出现0次或多次的部分)。例如,对于正则表达式(a|b)*。可以自己动手画图尝试一下。
2、最小化DFA,应如何分割不同的非终结集,终结集?
首先回到原因,也就是我们为什么要把DFA最小化?
说白了就是需要效率,所以要把DFA冗余的地方剔除,使程序跑得更快。
明白了原因,我们就知道该怎么做了:最小化DFA就是要剔除DFA冗余的部分;1、合并等价状态(如果两个状态对于所有可能的输入,都转移到相同(或等价)的状态,那么这两个状态就被称为等价状态)2、删除无效状态(无法达到的状态,或者从这些状态无法到达任何终止状态)。
问题又来了,我们应该如何判断等价状态/无效状态?
等价状态的判断:
首先,将所有的状态分为两个集合,一个是终止状态,另一个是非终止状态。然后,反复细化这些集合,对于每个集合和每个输入符号,如果集合中的状态在该输入符号下转移到的状态不在同一个集合中,那么就将这个集合分为两个子集。反复进行这个过程,直到所有的集合都不能再被分割。最后,每个集合中的状态就是等价状态,可以被合并。
举个例子:
具体该如何判断是否分割:比如说我有两个等价集合:{2, 4} {1, 3},现在我开始分割{2, 4}等价集合,2输入a走到1,4输入a走到3,此时因为1,3都在一个等价集合中,我们可以看作2,4输入a后都走到了同一个状态,所以我不分割{2, 4}集合。
但如果2输入a走到4,4输入a走到3,他们的终点4,3不属于同一个等价集合,也就是它们不等价,此时我分割{2,4}集合为{2}, {4}。
1、首先开始假设非终结态和终结态分别都等价,构造等价集合:
非终结:{0, 1, 2} 终结:{3, 4, 5, 6}
2、开始观察非终结集合是否等价
输入a:
0 -> 1(属于集合{0, 1 ,2})
1 ->3(属于集合{3, 4, 5, 6})
2 -> 1(属于集合{0, 1, 2})
所以此时0,2等价,3不等价于0,1,分割
此时非终结:{0, 2} {1} 终结:{3, 4, 5, 6}
输入b:
0 -> 2(属于集合{0, 1 ,2})
1 ->2(属于集合{0, 1, 2})
2 -> 5(属于集合{3,4,5,6})
所以此时2不等价于0,再分割
此时非终结:{0} {1} {2} 终结:{3, 4, 5, 6}
3、开始观察终结集合是否等价
输入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})
所以此时3,4,5,6等价,不分割
此时非终结:{0} {1} {2} 终结:{3, 4, 5, 6}
输入b
......(不赘述了)
最终得到的最小化DFA结果:非终结:{0} {1} {2} 终结:{3, 4, 5, 6}
A= {0}(初态)、B = {1}、C = {2}、D = {3,4,5,6} (终态)
无效状态的判断:
首先,从初始状态开始,标记所有可以到达的状态。然后,从所有的终止状态开始,标记所有可以到达的状态。最后,那些没有被标记的状态就是无效状态,可以被删除。(广搜或深搜)
3、词法分析器的工作
说白了,词法分析器作用如下:
1、读源程序,识别源程序里的符号分别是什么。比如‘+’是运算符加,abc123是一个标识符,识别完成后,把它的识别结果放到符号表里。
2、光把识别结果放到符号表里可不行,语法分析器仍然不知道源程序是什么意思,所以词法分析器还需要把源程序一个词一个词地切开,并按顺序发给语法分析器,语法分析器按顺序接受,并查看符号表这个词到底是什么意思,然后查看目前读到的东西是否符合语法。
3、过滤掉源程序的注释和空白。
重点代码和分析
1、读文件,逐行处理
(本实验可能出现多行正则表达式,浴帘让我们把不同行的表达式用‘|’相连),所以把实验一的代码抄下来,做一些改动。
(1)将不同行用‘|’连接,且‘|’不放在最后一行的末尾,使最终的fileContent只有一行。
(2)如果遇到两个相连的字符,如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[]) { // 打开文件 ifstream file("/Users/chaixichi/Desktop/学习资料/大三上/C++lab1/C++lab2/test2.cpp"); //将文件名替换为打开的文件路径 // 查看是否可以打开文件 if (!file) { cout << "Unable to open file"; exit(1); } //将文件中读到的字符串不同行间加‘|’合成为一行 string temp((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());// //测试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; } } //将相连两个字符中间加上'&' 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]; } } //测试fileContent,最终处理结果存在fileContent里 cout<<fileContent; return 0;}
现在我们在fileContent里保存了我们处理后的正则表达式。
2、识别正则表达式&生成NFA
即使知道Thompson算法,实现由正则表达式转换到NFA也有些无从下手。
但仔细想想,识别正则表达式,就是要把它的标识符和运算符拆开,并确定运算顺序。
那我们应该如何确定运算顺序?
所用数据结构如下:
cclass MyGraph{public: int mVexNum;//顶点数目 int mEdgeNum;//边的数目 //顶点(所有状态)集合 vector<char> mMatrix[100][100];//邻接矩阵,对应的值为转移条件,就是字母,默认都是空'',表示未连接public: MyGraph();//默认构造函数 void printMyGraph(); //打印输出图内容 void addEdge(int a, int b, char edgeCondition); //增加一条边,边上的值为转换的条件 vector<char> getEdgeValue(int a ,int b);};class NFA{//只有一个结束状态public: vector<int> mVexs;//NFA节点集合,存储的是节点的序号,位置的信息并没有存储内容 MyGraph NFAGraph;//NFA图的结构 int startStatus;//开始状态的序号 int endStatus;//终止状态的序号};//给NFA栈中的元素的定义的一个结构,存储的是起点和终点的信息。struct node{public: int nArray[2];//nArray[0]为起点,nArray[1]为终点 node(int a[2]){//构造函数 for(int i =0;i<2;i++) nArray[i] = a[i]; }};class Lex{public: NFA lexNFA;//NFA结构 DFA lexDFA;//DFA结构 stack <char> operatorStack;//操作符栈 stack <node> NFAStatusPointStack;//NFA栈中的NFA的起始点序号,0的位置代表起点,1的位置代表终点 vector<char> alphabet;//字母表,存储是正则表达式中的字母 ......}
重点1:Thompson算法,即用代码实现Thompson算法(下面这几张图)
(1)创造最基本NFA
创造这个最基本的NFA,我们需要:创建两个新节点,创建一条新边,确定这条边的起点和终点
创建新节点时,我们需要:记录新节点 + 设置起点终点
创建新边时,我们需要:增加一条对边的连接,边的条件为我们输入的字符
void Lex::createBasicNFA(char ch){ //据字母创建最基本NFA的操作 int startPoint = lexNFA.mVexs.size() + 1; //分配的节点序号是以前节点序号+1 int endPoint = startPoint + 1; lexNFA.NFAGraph.addEdge(startPoint,endPoint,ch); //增加一个边对边的连接,边的条件是转换条件,就是该字符。 lexNFA.NFAGraph.mVexNum = lexNFA.NFAGraph.mVexNum+2; //增加两个节点 lexNFA.NFAGraph.mEdgeNum++; //边数加1 //添加到节点数组中 lexNFA.mVexs.push_back(startPoint); lexNFA.mVexs.push_back(endPoint); int newNFAStatusPoint[2]; newNFAStatusPoint[0] = startPoint; newNFAStatusPoint[1] = endPoint; NFAStatusPointStack.push(node(newNFAStatusPoint)); //起点终点设置 lexNFA.startStatus = startPoint; lexNFA.endStatus = endPoint;}
(2)或‘|’的运算:
创造这个NFA,我们需要:创建两个新节点,创建4条新边(空输入),确定这四条新边的起点和终点
类比(1),我们可以得出以下代码:
void Lex::selectorCharacterOperation(){ //获取栈顶两个元素,注意,第一个获取的元素为右式,因为栈后进先出 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(); //创建两个新节点 int newStartPoint1 = lexNFA.mVexs.size() + 1; int newStartPoint2 = newStartPoint1 + 1; //比着图连接 lexNFA.NFAGraph.addEdge(newStartPoint1, leftNFA[0], 'E');//空转移 lexNFA.NFAGraph.addEdge(newStartPoint1, rightNFA[0], 'E');//空转移 lexNFA.NFAGraph.addEdge(leftNFA[1], newStartPoint2, 'E');//空转移 lexNFA.NFAGraph.addEdge(rightNFA[1], newStartPoint2, 'E');//空转移 lexNFA.NFAGraph.mVexNum = lexNFA.NFAGraph.mVexNum+2; //节点数目加2 lexNFA.NFAGraph.mEdgeNum = lexNFA.NFAGraph.mEdgeNum + 4; //边的数目加4 //节点添加到节点数组中 lexNFA.mVexs.push_back(newStartPoint1); lexNFA.mVexs.push_back(newStartPoint2); //将新的NFA压入NFA栈中 int newNFAStatusPoint[2]; newNFAStatusPoint[0] = newStartPoint1; newNFAStatusPoint[1] = newStartPoint2; NFAStatusPointStack.push(newNFAStatusPoint); //设置起点终点 lexNFA.startStatus = newStartPoint1; lexNFA.endStatus = newStartPoint2;}
3、‘&’与的运算
只多了一条空转移的边
个人觉得是容易设坑的题,因为它看起来很简单,只连一条边即可,但其实不是这么做的。
4、‘*’闭包的运算
void Lex::repeatCharacterOperation(){ //获取栈顶第一个元素 int top1NFA[2];//开始和结束 for(int i = 0; i < 2;i++){ top1NFA[i] = NFAStatusPointStack.top().nArray[i]; } NFAStatusPointStack.pop(); //创建两个新的节点 int newStartPoint1 = lexNFA.mVexs.size() + 1; int newStartPoint2 = newStartPoint1 + 1; lexNFA.NFAGraph.addEdge(newStartPoint1, newStartPoint2, 'E');//空转移 lexNFA.NFAGraph.addEdge(newStartPoint1, top1NFA[0], 'E');//空转移 lexNFA.NFAGraph.addEdge(top1NFA[1], newStartPoint2, 'E');//空转移 lexNFA.NFAGraph.addEdge(top1NFA[0], top1NFA[1], 'E');//空转移 lexNFA.NFAGraph.mVexNum = lexNFA.NFAGraph.mVexNum + 2;//节点数+2 lexNFA.NFAGraph.mEdgeNum = lexNFA.NFAGraph.mEdgeNum + 4;//节点数+4 //添加到节点数组中 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)); //起点终点设置 lexNFA.startStatus = newStartPoint1; lexNFA.endStatus = newStartPoint2;}
5、‘+’正闭包的运算
正闭包比起闭包,少了一个空运算
void Lex::repeat1CharacterOperation(){ //弹出一个元素 int topNFA[2]; for(int i = 0; i < 2;i++){ topNFA[i] = NFAStatusPointStack.top().nArray[i]; } //创建两个新节点 int newStartPoint1 = lexNFA.mVexs.size() + 1; int newStartPoint2 = newStartPoint1 + 1; //比着图连接 lexNFA.NFAGraph.addEdge(newStartPoint1, topNFA[0], 'E');//空转移 lexNFA.NFAGraph.addEdge(topNFA[1], newStartPoint2, 'E');//空转移 lexNFA.NFAGraph.addEdge(topNFA[1], topNFA[0], 'E');//空转移 //新节点入节点数组 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)); //记录起点和终点,在全局范围内跟踪NFA的起点和终点 lexNFA.startStatus = newStartPoint1; lexNFA.endStatus = newStartPoint2;}
6、‘?’一次或不做的运算
void Lex::once_or_no_CharacterOperation(){ //弹出一个元素 int topNFA[2]; for(int i = 0; i < 2;i++){ topNFA[i] = NFAStatusPointStack.top().nArray[i]; } //创建两个新节点 int newStartPoint1 = lexNFA.mVexs.size() + 1; int newStartPoint2 = newStartPoint1 + 1; //比着图连接 lexNFA.NFAGraph.addEdge(newStartPoint1, topNFA[0], 'E');//空转移 lexNFA.NFAGraph.addEdge(topNFA[1], newStartPoint2, 'E');//空转移 lexNFA.NFAGraph.addEdge(newStartPoint1, newStartPoint2, 'E');//空转移 //新节点入节点数组 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)); //记录起点和终点,在全局范围内跟踪NFA的起点和终点 lexNFA.startStatus = newStartPoint1; lexNFA.endStatus = newStartPoint2;}
顺序总结:
(1)根据运算符弹出NFA
(2)创建新节点,创建新边
(3)将新节点入节点数组
(4)将新NFA入栈(起点&终点)
(5)追踪总NFA的起点和终点
重点2:由正则表达式生成NFA状态转移表
(1)生成NFA图
本实验中使用到的正则表达式运算符优先级如下:
最优先 | () |
次优先 | *、+、? |
次次优先 | 连接(&) |
最后 | | |
该算法能够直接扫描正则表达式并正确地计算运算顺序,主要是因为它使用了一个运算符栈来保存遇到的运算符,并且在遇到新的运算符时,会根据运算符的优先级来决定如何处理运算符栈。
具体来说,当遇到一个新的运算符时,会比较这个运算符和运算符栈顶的运算符的优先级:
(1)如果新的运算符的优先级高于栈顶运算符的优先级,或者运算符栈为空,或者栈顶运算符是'(',则将新的运算符压入运算符栈。
(2) 如果新的运算符的优先级等于或低于栈顶运算符的优先级,则会从运算符栈中弹出运算符,并执行相应的操作,直到栈顶运算符的优先级低于新的运算符的优先级,或者运算符栈为空,或者栈顶运算符是'('。然后,将新的运算符压入运算符栈。
这样,就可以保证在没有括号改变优先级的情况下,高优先级的运算符总是先于低优先级的运算符执行,从而得到正确的运算顺序。
(3)此外,这个算法还使用了一个NFA栈来保存构建过程中的中间结果。每当从运算符栈中弹出一个运算符并执行相应的操作时,都会从NFA栈中弹出相应数量的NFA,并将操作的结果压入NFA栈。这样,就可以保证在处理复杂的正则表达式时,总是先处理子表达式,然后再处理父表达式。
若当前不是一个运算符,创造一个最基本的NFA。
所以,虽然这个算法在扫描正则表达式时并没有显式地标记运算顺序,但是通过使用运算符栈和NFA栈,它能够隐式地确定并遵循正确的运算顺序。
该算法在计算过程中,顺便处理了连接符‘&’添加的问题,比如在正则表达式(a|b)*a中,应该将其变为(a|b)*&a,显式地表示连接,ab变为a&b,显式地表示连接。
void Lex::getNFA(string regexInput){ unsigned long strlen = regexInput.length(); char ch; //扫描正则表达式,建立运算符栈和NFA栈 for(unsigned long i = 0; i < strlen; i++){ ch = regexInput[i]; if(isOperator(ch)){//是运算符 switch(ch){ case '*':{ repeatCharacterOperation(); //如果下一个字符是字母或左括号,需要添加连接符 if((i + 1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){ operatorStack.push('&'); } }break; case '+':{ repeat1CharacterOperation(); //如果下一个字符是字母或左括号,需要添加连接符 if((i + 1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){ operatorStack.push('&'); } }break; case '?':{ once_or_no_CharacterOperation(); //如果下一个字符是字母或左括号,需要添加连接符 if((i + 1 < strlen)&&(regexInput[i+1] == '(' || !isOperator(regexInput[i+1]))){ operatorStack.push('&'); } }break; case '|':{ if(operatorStack.empty()){ cout<<"运算符栈为空!"<<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();//移除栈内左括号 //如果下一个字符是字母或者是左括号,需要添加连接符 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{//不是运算符 auto flag = true;//是否添加到字母表中 for(int i = 0; i < alphabet.size(); i++){ if (ch == alphabet[i]) flag = false; } if(flag){ alphabet.push_back(ch); } //建立一个基本的NFA createBasicNFA(ch); //如果下一个字符是字母的话,就向符号栈中加入一个连接符& if(i+1 <strlen && (!isOperator(regexInput[i+1]) || regexInput[i+1] == '(')){ operatorStack.push('&'); } }//end else }//end for //对最终的NFA栈和运算符栈进行处理(如果不为空) while(!operatorStack.empty()){ ch = operatorStack.top(); switch (ch) { case '|': selectorCharacterOperation(); break; case '&': joinerCharacterOperation(); break; default: break; } operatorStack.pop(); }}
总结:每一步都保证高优先级的先运算,要么不入栈直接运算,要么把它留在栈顶。正则表达式遍历结束后继续运算栈中剩下的元素。
最终我们得到了正则表达式字符表,NFA图(NFA邻接表)。
(2)生成NFA状态转移表
在正式开始生成状态转移表之前,我们需要了解两个问题:
1、当获取一个状态转移时,我们需要知道什么?
我们需要知道三条信息:
【从哪个状态出发、输入是什么、到达哪个状态】
2、最终生成的状态转移表长什么样?
状态/输入字符 | a | b |
1 | 1状态输入字符a所到达的状态 | 1状态输入字符b所到达的状态 |
2 | 2状态输入字符a所到达的状态 | 2状态输入字符b所到达的状态 |
为了生成状态转移表,我们需要获得:
输入字符集(在刚才生成NFA图时,我们获得的字母表就是输入字符集)
状态集
了解了这些问题,我们就可以生成NFA状态转移表了
邻接矩阵生成相关函数:
class NFA{ ...... MyGraph NFAGraph;//存储NFA的图结构 ......}//默认构造函数,初始边和顶点数目都为0MyGraph::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:节点名称、b:另一个节点名称、edgeCondition :边上的值,即转换条件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){//若没有这样的边 mMatrix[a][b].push_back(edgeCondition);//加入 }}
最终得到的邻接矩阵mMatrix长这样:
到达\出发 | 1 | 2 | 3 |
1 | a | a | |
2 | b | E(空状态) | |
3 | b |
横着的表头表示从哪个状态出发,竖着的表头表示到达哪个状态,中间表示从xx状态出发,到xx状态,需要输入xx
与状态转移表StatusMatrix作对比:
状态/输入字符 | a | b | E(空字符) |
1 | 1状态输入字符a所到达的状态 | 1状态输入字符b所到达的状态 | 1状态输入空字符所到达的状态 |
2 | 2状态输入字符a所到达的状态 | 2状态输入字符b所到达的状态 | 2状态输入空字符所到达的状态 |
3 | ..... | .... | ...... |
我们发现,逐列遍历mMatrix即可把它转化成状态转移表
比如说,第一列代表从状态1出发,我们看到第一列第一行,即,mMatrix[0][0] == 'a',把它放到对应状态转移表的位置StatusMatrix[0][0],StatusMatrix[0][0] == 0,即代表从状态1出发,输入a(在状态转移表中,以a在字母表中的下标代替a),到达状态1
代码就不赘述了,就是一个遍历的问题。
3、NFA转DFA
采用子集构造法从NFA转DFA,我愿称其为,疯狂地求ε闭包。
我们知道,NFA比DFA多的东西就是空转移&分支,所以将NFA转换为DFA,就是把空转移和分支去掉,能合并的合并。
此处需要引入一个等价集合的概念,即,某个节点在经历ε闭包运算后,所得到的集合,我们称它为等价集合。
用一道具体的题目举例:
我们可以清楚地看到,这幅NFA图从状态0开始,但是它的初始状态不仅仅是状态0,应该是从状态0,经过一个或多个ε所达到的状态集合
(1)所以上图初始状态集合为:{0, 1, 2, 4, 7},记为集合A,它是一个等价集合。
该NFA的字母表是{a, b}
(2)我们先向集合A中输入状态a,看它经过一个a(期间可经过多个ε)后,得到的集合
{1, 2, 3, 4, 6, 7,8},记为集合B,它是一个等价集合,表示向等价集合A中输入一个a后,所能到达的终点集合。
(3)我们再向集合A中输入状态b,看它经过一个a(期间可经过多个ε)后,得到的集合
{1, 2, 4, 5, 6, 7},记为集合C,它是一个等价集合。
(4)我们再向集合B中输入状态a,看它经过一个a(期间可经过多个ε)后,得到的集合
{1, 2, 3, 4, 6, 7, 8},与集合B相同,没有产生新的集合。
(5)我们再向集合B中输入状态b,看它经过一个b(期间可经过多个ε)后,得到的集合
{1, 2, 3, 4, 5,6, 7,9},产生新的集合D,它是一个等价集合。
.......不断地尝试,直到再也无法出现新的集合
最终得到:
用图3-35生成的DFA图
也就是说,我们将问题转化为,按照刚才的ε闭包运算规则,从初始状态集合开始,根据字母表(输入的状态表)不断尝试生成新集合,并对新集合进行ε闭包运算,直到不生成新集合,最后生成图3-35的表即可。
ε闭包运算,以下代码把它拆成两部分来实现。
第一部分是计算能从NFA的状态数组statusArray中的某个状态s开始只通过E转换到达的NFA状态元素。
第二部分是能够从NFA的状态数组statusArray中的某个状态出发,通过条件为condition转换到达的NFA状态集合。
将生成步骤总结如下:
(1)输入状态数组,将状态数组压入resultArray和statusArray。
(2)将statusArray里的元素一个个出栈,直到statusArray里为空,每出栈一个元素(状态),在邻接表里寻找是否有:由出栈状态输入指定字符(‘E’/condition)后达到的状态,如果有,将达到的状态压入statusArray和resultArray。
(3)将resultArray去重,返回,返回的resultArray就是输入的状态集合输入(‘E’/condition)所能到达的状态集合。
//DFA:能从NFA的状态数组statusArray中的某个状态s开始只通过E转换到达的NFA状态元素vector<int> Lex::e_closure(vector<int> statusArray){ vector<int> resultsArray;//存放状态数组的E转换集合 stack<int> statusStack;//存放递归过程中的状态,当该栈为空时,递归结束 for(int i = 0; i < statusArray.size(); i++){ statusStack.push(statusArray[i]);//初始化状态栈 resultsArray.push_back(statusArray[i]);//状态本身也可以通过空转换到本身,所以要将自身添加到结果数组 } while(!statusStack.empty()){ int status = statusStack.top(); statusStack.pop(); for(int i = 1; i < lexNFA.mVexs.size() + 1; i++){ if(i == status){//查看以当前状态为起点的邻接表 for(int j = 1; j < lexNFA.mVexs.size() + 1; j++){ if(lexNFA.NFAGraph.getEdgeValue(i, j).at(0) == 'E'){//若转移条件为‘E’ statusStack.push(j); resultsArray.push_back(j); } } } }//end for }//end while //去除重复元素 sort(resultsArray.begin(), resultsArray.end()); resultsArray.erase(unique(resultsArray.begin(), resultsArray.end())); return resultsArray;}//DFA:能够从NFA的状态数组statusArray中的某个状态出发,通过条件为condition转换到达的NFA状态集合vector<int> Lex::nfaMove(vector<int> statusArray, char condition){ vector<int> resultArray;//结果数组 stack<int> statusStack;//状态栈 //状态集入栈 for(int i = 0 ; i < statusArray.size(); i++){ resultArray.push_back(statusArray[i]); statusStack.push(statusArray[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; }
那这两个函数应该如何调用,以模拟手动的计算过程?
回想一下我们手动的运算顺序:先利用ε闭包生成初始状态集合,然后向初始状态集合里依次投入字母表中的元素,试图生成一个新的集合,生成新的集合后,我们向这个集合里依次投入字母表中的元素,试图生成一个新的集合,直到最终无法生成新集合为止。
(1)利用ε闭包生成初始状态集合。
void Lex::getDFA(){ //给DFA节点开头位置加一个空元素占位 lexDFA.mVexs.emplace_back(0); vector<int> initStatus; initStatus.push_back(lexNFA.startStatus); vector<int> initStatusTrans(e_closure(vector<int>(initStatus)));//生成初始状态集合 //给DFA创建第一个节点 int newDFAStartPoint = lexDFA.DFAGraph.mVexNum + 1; lexDFA.DFAGraph.mVexNum++;//节点数+1 //DFA起点确定 lexDFA.startStatus = newDFAStartPoint; stack<int> DFAStatusStack;//DFA状态栈 DFAStatusStack.push(newDFAStartPoint); lexDFA.mVexs.push_back(initStatus);//NFA起点的等价集合为DFA的起点 ......... }
(2)根据初始状态集合,计算DFA
首先要解决的问题是,我们应该如何判断什么时候停止?即,什么时候不再产生新状态。
答案是利用一个DFAStatusStack,当我们生成一个集合,尝试入栈时,判断该集合是否在我们已经生成的DFA中,若是,则不压入。
直到DFAStatusStack为空,即不再产生新的集合需要运算。
void Lex::getDFA() { //给DFA节点开头位置加一个空元素占位 lexDFA.mVexs.emplace_back(0); vector<int> initStatus; initStatus.push_back(lexNFA.startStatus); vector<int>initStatusTrans(e_closure(vector<int>(initStatus))); //给DFA创建第一个节点 int newDFAStartPoint = lexDFA.DFAGraph.mVexNum + 1; lexDFA.DFAGraph.mVexNum ++;//节点数加1 lexDFA.startStatus = newDFAStartPoint; stack<int> DFAStatusStack;//存储还没有经过字母表转换的DFA状态, DFA状态栈,这个栈只需要存储DFA的序号就可以了,没存储DFA节点对应的NFA集合, DFAStatusStack.push(newDFAStartPoint); lexDFA.mVexs.push_back(initStatusTrans);//NFA起点的E转换集合赋值给DFA的第一个节点 while (!DFAStatusStack.empty()){ int topDFAStack = DFAStatusStack.top(); DFAStatusStack.pop(); for (int i = 0; i < alphabet.size() ; ++i) { //对字母表的每个元素都需要作为转换条件 vector<int> tempArray = e_closure(nfaMove(lexDFA.mVexs[topDFAStack],alphabet[i])); if (tempArray.empty()){//如果转换产生的NFA集合为空,跳过该次转换即可 continue; } int position = isDFAStatusRepeat(tempArray);//判断新生成DFA状态是否已经存在了,如果已经存在,返回该状态在节点的位置 if (position == -1){//这个是新生成的DFA状态,没有重复 int tempDFAStatusNode = lexDFA.DFAGraph.mVexNum + 1; lexDFA.DFAGraph.mVexNum ++;//节点数加1 if (isEndDFAStatus(tempArray)){ lexDFA.endStatus.push_back(tempDFAStatusNode); } lexDFA.mVexs.push_back(tempArray);//把NFA集合赋值给DFA的状态 DFAStatusStack.push(tempDFAStatusNode);//把新产生的DFA状态加入到DFA栈中 position = tempDFAStatusNode; } //连接节点,产生边 lexDFA.DFAGraph.addEdge(topDFAStack,position,alphabet[i]); lexDFA.DFAGraph.mEdgeNum ++; } }}//判断是否是DFA的终止状态,只要包含了NFA的终止状态的DFA状态都是终止状态bool Lex::isEndDFAStatus(vector<int> nfaArray){ for (int i = 0; i < nfaArray.size(); ++i) { if (lexNFA.endStatus == nfaArray[i]){ return true; } } return false;}//判断新产生的DFA状态是否已经存在DFA状态表中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;}
有同学可能会疑惑,为什么只在生成开始状态集的时候调用了一次空运算(e-closure),其他集合都在用nfaMove生成,那是因为在生成NFA邻接表时,空串不影响最终抵达的状态。
4、最小化DFA
在手动计算中,在得到DFA后,首先划分非终结态和终结态集合,然后尝试字母表中所有输入,试图再次分割非终结态和终结态集合。
例:假设我有一个非终结态集合(是一个等价集合){1, 2, 3, 4},一个终结态集合(是一个等价集合){5, 6}
我的字母表是{a, b}
(1)尝试向非终结态集合{1, 2, 3, 4},输入a
1输入a到2 2输入a到2 3输入a到1 4输入a到3
最终得到的终点集合为{2,1,3},因为它属于我们的等价集合,不划分。
(2)尝试向非终结态集合{1, 2, 3, 4},输入b
1输入a到6 2输入a到2 3输入a到5 4输入a到3
最终得到的终点集合为{2,3,5,6},其中{2,3}属于{1, 2, 3, 4},{5, 6}属于{5,6}
所以划分非终态集合{1, 2, 3, 4}为{1, 3},{2, 4}
(3)尝试向终结态集合{5, 6},输入a
。。。。。。。以此类推
所以,我们代码模拟的就是,找到非终结集合、终结集合,然后向其中逐个输入字母表,得到终点集,判断终点集是否属于同一个等价集合,如果不是,按照终点集划分,如果是,不划分。
首先,将DFA的状态分为两类:终止状态和非终止状态。这两类状态被分别存储在endPointArray
和noEndPointArray
中。
将这两个数组被添加到dividedArrays
中,这是 一个对 的数组,其中每个对的第一个元素是一个状态数组,第二个元素是一个布尔值,表示该状态数组是否可以进一步划分。
void Lex::minimizeDFA(){ vector<int> noEndPointArray;//非终止状态集合 vector<int> endPointArray(lexDFA.endStatus);//终止状态集合 //初始化非终止状态集合 for(int i = 0; i < lexDFA.mVexs.size(); i++){ if(!isInDFAEndStatus(i)){//不在终止状态集合里 noEndPointArray.push_back(i); } } vector<pair<vector<int>, bool>> dividedArrays;//first存储的是划分的集合,second存储的是该划分集合是否可继续划分 dividedArrays.emplace_back(noEndPointArray, true); dividedArrays.emplace_back(endPointArray, true); ........... }
然后,代码进入一个循环,直到所有的状态数组都不能进一步划分为止。在每次循环中,代码会遍历dividedArrays
中的每个状态数组。对于每个状态数组,代码会遍历字母表中的每个字母,然后对状态数组中的每个状态,找到通过当前字母转换后的状态,并找到这个状态所在的状态数组的序号。然后,根据这些序号,将当前状态数组进一步划分。
这部分代码有些长,我想还是把它拆开看吧
首先是:在每次循环中,代码会遍历dividedArrays
中的每个状态数组。对于每个状态数组,代码会遍历字母表中的每个字母,然后对状态数组中的每个状态,找到通过当前字母转换后的状态,并找到这个状态所在的状态数组的序号。
定义一些要用到的数据结构:
void Lex::minimizeDFA(){ vector<int> noEndPointArray;//非终止状态集合 vector<int> endPointArray(lexDFA.endStatus);//终止状态集合 //初始化非终止状态集合 for(int i = 0; i < lexDFA.mVexs.size(); i++){ if(!isInDFAEndStatus(i)){//不在终止状态集合里 noEndPointArray.push_back(i); } } vector<pair<vector<int>, bool>> dividedArrays;//first存储的是待划分的集合,second存储的是该划分集合是否可继续划分 dividedArrays.emplace_back(noEndPointArray, true); dividedArrays.emplace_back(endPointArray, true); bool flag = true; while(flag){ for(int j = 0; j < dividedArrays.size(); j++){//对划分的每个集合进行操作 int canNotBeDivided = 0;//标记是否当前集合可以被划分,1为不可 if(dividedArrays[j].first.size() == 1){//该集合元素只有一个,必不可划分 dividedArrays[j].second = false; continue; vector<int> arrayNumVector;//存放DFA状态经过某个字母转换到的结果集 vector<pair<int, int>> statusMap;//存放每个节点结果集序号 该节点本身序号 } }//end for j }//end while}
然后,正式开始对 待划分 的每个集合进行操作(逐个尝试输入字母表中的符号,记录结果集,查看结果集是否在一个等价集合中)
j循环,尝试对划分的每个集合进行操作
i循环,当前划分的集合尝试逐个输入字符表
k循环,对当前划分的集合尝试输入当前字符,逐个记录当前划分的集合元素序号 到 当前划分的集合输入当前字符后所到达的状态属于的等价集合 的映射
//最小化DFAvoid Lex::minimizeDFA(){ ......... vector<pair<vector<int>, bool>> dividedArrays;//first存储的是待划分的集合,second存储的是该划分集合是否可继续划分 dividedArrays.emplace_back(noEndPointArray, true); dividedArrays.emplace_back(endPointArray, true); bool flag = true; while(flag){ for(int j = 0; j < dividedArrays.size(); j++){//对划分的每个集合进行操作 int canNotBeDivided = 0;//标记是否当前集合可以被划分,1为不可 if(dividedArrays[j].first.size() == 1){//该集合元素只有一个,必不可划分 dividedArrays[j].second = false; continue; } vector<int> arrayNumVector;//存放DFA状态经过某个字母转换到的结果集 vector<pair<int, int>> statusMap;//存放每个节点结果集序号 该节点本身序号 for(int i = 0; i < alphabet.size(); i++){ for(int k = 0; k < dividedArrays[j].first.size(); k++){ //获取待划分集合的每个元素转换状态属于的集合序号 int transStatus = lexDFA.getTargetStatus(dividedArrays[j].first[k], alphabet[i]); //看我们当前得到的转换状态属于哪个待划分集合 int statusInArrayNum = getContainPosition(transStatus, dividedArrays); if(statusInArrayNum == -1){//没有转换结果,也就是当前元素无法接收alpha[i] arrayNumVector.push_back(statusInArrayNum); } else{//当前元素可以接收alpha[i] if(!isContain(statusInArrayNum, arrayNumVector)){//避免结果集中状态重复 arrayNumVector.push_back(statusInArrayNum); } } statusMap.emplace_back(statusInArrayNum, dividedArrays[j].first[k]);//将元素转换状态属于的集合序号 该元素本身序号压入 }//end for k }//end for i }//end for j }//end while}
拿到这个映射后,我们就可以根据这个映射划分集合了,将映射到相同等价集合的元素划为一个集合
看起来有些复杂,其实整体的思路如下
(1)设定一个数组,arrayNumVector,用于存放当前DFA状态集经过某个字母转换到的结果集,不断尝试向当前DFA状态集中放入字母,如果集合元素无法接受当前字母,记为-1,入arrayNumVector,如果可以接收,记接收后转换到的状态,入arrayNumVector。
顺便设定一个Map,statusMap,记录当前元素输入当前字母后,它的转换后的状态属于我们划分的哪个集合。(划分集合号,当前状态)
(2)得到当前DFA状态集经过某个字母转换到的结果集arrayNumVector,当前状态与划分的集合的映射statusMap后,开始判断是否要划分。
若结果集只有一个元素,无论如何都不需要划分,如果有多个元素,检查statusMap判断是否要划分。
遍历statusMap,将当前集合号相同 的状态划入一个数组,如果最后得到的数组与已有的划分集合相同,将当前在看的划分集合标记为false,表示不能再划分。
如果最后得到的数组与已有的划分集合不同,压入划分集合,删除划分集合中当前在看的划分集合,表示当前集合已经划分为压入的划分集合。
(3)遍历划分集合数组,若都为false,表示都不能划分,划分结束,退出划分循环,开始合并DFA等价状态。
void Lex::minimizeDFA(){ ...... vector<pair<vector<int>, bool>> dividedArrays;//first存储的是待划分的集合,second存储的是该划分集合是否可继续划分 dividedArrays.emplace_back(noEndPointArray, true); dividedArrays.emplace_back(endPointArray, true); bool flag = true; while(flag){ for(int j = 0; j < dividedArrays.size(); j++){//对划分的每个集合进行操作 int canNotBeDivided = 0;//标记是否当前集合可以被划分,1为不可 if(dividedArrays[j].first.size() == 1){//该集合元素只有一个,必不可划分 dividedArrays[j].second = false; continue; } vector<int> arrayNumVector;//存放DFA状态经过某个字母转换到的结果集 vector<pair<int, int>> statusMap;//存放每个节点结果集序号 该节点本身序号 for(int i = 0; i < alphabet.size(); i++){ for(int k = 0; k < dividedArrays[j].first.size(); k++){ //获取待划分集合的每个元素转换状态属于的集合序号 int transStatus = lexDFA.getTargetStatus(dividedArrays[j].first[k], alphabet[i]); //看我们当前得到的转换状态属于哪个待划分集合 int statusInArrayNum = getContainPosition(transStatus, dividedArrays); if(statusInArrayNum == -1){//没有转换结果,也就是当前元素无法接收alpha[i] arrayNumVector.push_back(statusInArrayNum); } else{//当前元素可以接收alpha[i] if(!isContain(statusInArrayNum, arrayNumVector)){//避免结果集中状态重复 arrayNumVector.push_back(statusInArrayNum); } } statusMap.emplace_back(statusInArrayNum, dividedArrays[j].first[k]);//将元素转换状态属于的集合序号 该元素本身序号压入 }//end for k if(arrayNumVector.size() == 1){//DFA状态经过某个字母转换到的结果集只有1个 canNotBeDivided++; continue;//不划分,看下一个字母 } else{//开始划分 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代表删除状态 tempArray.push_back(statusMap[k].second); break; } else{ if(statusMap[k].first == arrayNumVector[l]){//根据集合序号划分 tempArray.push_back(statusMap[k].second); } } dividedArrays.emplace_back(tempArray, true); }//end k auto iter = dividedArrays.begin() + j; dividedArrays.erase(iter); j--; break;//当前集合结束,调到下一个位置的集合,因为删除了该元素,其他元素前移一位,所以j-- }//end l } }//end for i if(canNotBeDivided == alphabet.size()){ dividedArrays[j].second = false; } }//end for j //判断是否结束循环,如果划分集合下面所有集合都不可分就推出循环 flag = false; for(int m = 0; m < dividedArrays.size(); m++){ if(dividedArrays[m].second == true){ flag = true; break; } }//end for m }//end while }
合并DFA等价状态:遍历划分集合,把每个划分集合都合成为一个点,合成后给每个点分配编号
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;//非终止态节点集合 vector<int> endPointArray(lexDFA.endStatus); //非终止状态集合 for (int i = 1; i < lexDFA.mVexs.size(); ++i) { if (!isInDFAEndStatus(i)){ noEndPointArray.push_back(i); } }//初始化非终止节点集合 cout << endl; //终止状态集合 for (int n = 0; n < endPointArray.size(); ++n) { cout << endPointArray[n] << " "; } cout << endl; vector<pair<vector<int>,bool>> dividedArrays;//first存储的是划分的集合,second存储的是该划分集合是否可继续划分 dividedArrays.emplace_back(noEndPointArray, true); dividedArrays.emplace_back(endPointArray, true); bool flag = true; while(flag){ for (int j = 0; j < dividedArrays.size(); ++j) {//对划分的每个集合进行操作 cout << endl; int canNotBeDivided = 0;//经过一次字母表的转换,如果该集合的转换状态只有一个,说明该集合不能被该字母区分,该变量+1 if (dividedArrays[j].first.size() == 1){ dividedArrays[j].second = false;//如果集合元素只有一个,赋值为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 << "当前字母为" << alphabet[i] << endl; vector<int> arrayNumVector;//存放DFA状态经过某个字母转换到的集合序号的数组 //first 为转换状态属于的集合序号,second DFA起点的状态节点 vector<pair<int,int>> statusMap;//存放了每个节点的转换后属于的集合序号——该节点本身序号 for (int k = 0; k < dividedArrays[j].first.size(); ++k) { //获取到该集合的每个元素的转换状态属于的集合序号 int transStatus = lexDFA.getTargetStatus(dividedArrays[j].first[k],alphabet[i]);//获取节点的转换DFA节点 int statusInArrayNum = getContainPosition(transStatus,dividedArrays);//转换状态属于的集合序号 if(statusInArrayNum == -1){//必须进行划分,这个时候虽然没有转换结果,所以需要将集合序号人为设置一个唯一的数 statusInArrayNum = -1; arrayNumVector.push_back(statusInArrayNum); }else{ if (!isContain(statusInArrayNum,arrayNumVector)){//防止集合序号的重复 arrayNumVector.push_back(statusInArrayNum);//将集合序号加入到集合序号数组中 } } statusMap.emplace_back(statusInArrayNum,dividedArrays[j].first[k]);//将集合序号————对于的DFA状态组压入 } if (arrayNumVector.size() == 1){ canNotBeDivided ++ ; continue; }else{ for (int m = 0; m < arrayNumVector.size(); ++m) { } for (int l = 0; l < arrayNumVector.size(); ++l) {//进行划分 vector<int> tempArray; for (int k = 0; k < statusMap.size(); ++k) { if (arrayNumVector[l] == -1 && statusMap[k].first == -1){//key为-1.说明是一定要划分的 //删除该元素 statusMap[k].first = -2;//-2代表删除状态 tempArray.push_back(statusMap[k].second); break; } else{ if (statusMap[k].first == arrayNumVector[l]){//根据集合序号进行划分 tempArray.push_back(statusMap[k].second); } } } cout << endl; dividedArrays.emplace_back(tempArray, true); } auto iter = dividedArrays.begin()+j; dividedArrays.erase(iter); j--; break;//当前集合结束,调到下一个位置的集合,因为删除了该元素,其他元素前移一位,所以j-- } }//end i if (canNotBeDivided == alphabet.size()){ dividedArrays[j].second = false;//如果一个集合经过转换后还是该集合本身,该集合无需再进行划分 } }//end j //判断是否结束循环,如果划分集合下面的所有集合都不可划分就退出循环 flag = false; for (int m = 0; m < dividedArrays.size(); ++m) { if (dividedArrays[m].second == true){ flag = true; break; } } } //合并DFA等价状态 for (int j1 = 0; j1 < dividedArrays.size(); ++j1) { if (dividedArrays[j1].first.size() > 1){//只要每个集合的大小大于1,说明有需要合并的 int represent = dividedArrays[j1].first[0]; for (int i = 1; i < dividedArrays[j1].first.size(); ++i) {//除了第一个节点,其他节点都和第一个节点合并 mergeTwoNode(represent,dividedArrays[j1].first[i]);//合并这两个节点 } } }}
5、生成C语言词法分析程序
程序长这样
开整!
得到了最简DFA后,我们就可以生成C语言词法分析程序了
通过最简DFA,我们可以获得:1、状态数 2、字母表 3、每个状态输入字母表后转换到的位置
根据这些信息,我们就可以生成词法分析程序了!
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 + "//可变部分\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";}