[编译原理实验] DFA的编程实现

实验任务

编写一个C语言程序，模拟实现DFA识别字符串的过程。

实验内容

DFA的输入；
DFA的存储与读写；
DFA的正确性检查；
DFA的语言集列表显示；
DFA的规则字符串判定；

DFA的正确性检查：

检查所有集合的元素的唯一性。
检查“开始状态”是否唯一，并是否包含在“状态集”中。
检查“接受状态集”是否为空，并是否包含在“状态集”中。
检查“状态转换表”是否满足DFA的要求。
检查“状态转换表”并非填满时的处理是否得当…

测试用例：

我们可以按照如下格式储存上图DFA信息：

3 // 字符集中的字符个数 (以下两行也可合并成一行)

/ * o // 以空格分隔的字符集。O代表任意非/和*的字符

5 // 状态个数 (以下两行也可合并成一行)

1 2 3 4 5 // 状态编号。

1 // 开始状态的编号。

1 // 结束状态个数。

5 // 结束状态的编号

2 -1 -1 // 状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态

-1 3 -1

-1 4 3

5 4 3

-1 -1 -1

输入待显示的字符串的最大长度N，输出以上定义的DFA的语言集中长度≤N的所有规则字符串。

将上图DFA信息保存成.dfa文件：

大概框架如图：

代码实现：

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

string inputString;           //要匹配的字符串
int numOfChar,numOfState,startState,endStateNum;
		char *characters;
		int *states;
		int *endState;
		int **transTable;
void read(){
	ifstream in("dfa_in3.dfa");
	
    if (in.is_open()) {                      // 有该文件
	//字符集 
	in>>numOfChar;
	characters=new char[numOfChar];
	for(int i=0;i<numOfChar;i++){
		in>>characters[i];
		for(int j=0;j<i;j++){
			if(characters[i]==characters[j]){
				cout<<"字符集重复" <<endl;
				return;
			}
		}
	}
	//状态集 
	in>>numOfState;
	states=new int[numOfState];
	for(int i=0;i<numOfState;i++){
		in>>states[i];
		for(int j=0;j<i;j++){
			if(states[i]==states[j]){
				cout<<"状态集重复" <<endl;
				return;
			}
		}
	}
	//开始状态 
	string startStateLine;//没处理好 
	getline(in,startStateLine);
	if(startStateLine.length()>1){
		cout<<"开始状态多于1个"<<endl;
		return;
	}
	bool startExit=false;
	in>>startState; 
	for(int i=0;i<numOfState;i++){//开始状态是否合法 
		if(startState==states[i])startExit=true;
	}
	if(!startExit){
		cout<<"开始状态错误"<<endl;
		return;
	}
	//结束状态集 
	in>>endStateNum;
	endState=new int[endStateNum];
	for(int i=0;i<endStateNum;i++){
		in>>endState[i];
		bool endExit=false;
		for(int j=0;j<numOfState;j++){//结束状态是否合法
			if(endState[i]==states[j])endExit=true;
		}
		if(!endExit){
		    cout<<"结束状态"<<endState[i]<<"错误"<<endl;
			return;
		}
	}
	//转换表 
	transTable=new int *[numOfState];
	for(int i=0;i<numOfState;i++){
		transTable[i]=new int[numOfChar];
		for(int j=0;j<numOfChar;j++){
			in>>transTable[i][j];
			bool transExit=false;//转换表中元素是否合法
			if(transTable[i][j]==-1) transExit=true;
			for(int k=0;k<numOfState;k++){
			    if(transTable[i][j]==states[k])transExit=true;
			}
			if(!transExit){
			    cout<<"转换表元素"<<transTable[i][j]<<"错误"<<endl;
			    return;
			}
		}
	}
  }
    
    else {   // 没有该文件
        cout << "没有这个文件" << endl;
        return;
    }
}
void printDFA(){
	cout<<"字符集:"<< endl;
	for(int i=0;i<numOfChar;i++){
		cout<<characters[i]<<" ";
	}
	cout<< endl;
	cout<<"状态集:"<< endl;
	for(int i=0;i<numOfState;i++){
		cout<<states[i]<<" ";
	}
	cout<< endl;
	cout<<"开始状态:"<<startState<< endl;
	cout<<"结束状态数:"<<endStateNum<< endl;
	cout<<"结束状态集:"<< endl;
	for(int i=0;i<endStateNum;i++){
		cout<<endState[i]<<" ";
	}
	cout<< endl;
	cout<<"状态转换表:"<< endl;
	for(int i=0;i<numOfState;i++){
    	for(int j=0;j<numOfChar;j++){
    		cout<<transTable[i][j]<<"　" ;
		}cout<< endl;
	}
}
void DFA(int n){
	int currState;//初始状态在状态表中的编号 
	for(int i=0;i<numOfState;i++){
		if(states[i]==startState) currState=i; 
	}
	for(int i=0;i<inputString.length();i++){
		bool isExit = false;int j=0;
		for(;j<numOfChar;j++){//判断字符是否存在 
			//if(inputString[i]=='?'){isExit = true;break;}else      暂不考虑通用字符 
			if(inputString[i]==characters[j]){
				isExit = true;break;
			}
		}
		if(isExit){//存在 
			//检测输入的字符是否能在当前状态转换表中匹配
			cout<<"当前所在状态："<<states[currState]<<" 当前接收字符："<<characters[j]<<endl; 
			cout<<"转至状态："<<currState<<" "<<j<<" "<<transTable[currState][j]<<endl<<endl; 
			if(transTable[currState][j]>0){
				for(int k=0;k<numOfState;k++){
					if(states[k]==transTable[currState][j]){
						currState=k;
if(i<n){			//长度小于n且能被接收的子字符串						
    for (int w = 0; w < endStateNum; w++){
        if (states[currState] == endState[w]){
            cout<< inputString.substr(0,i+1) << endl;
        }
    }
}
						break;//计算跳到哪个状态 
					}
				}
			}else{
				cout << "第"<<i+1<<"个字符"<<inputString[i]<<"出错，无法进行转换!" << endl;
			}
		}else{
			cout << "第"<<i+1<<"个字符"<<inputString[i]<<"出错，不存在字符集中!" << endl;
            return;
		}
	}
	bool accept = false; //判断当前状态是否在接收状态中
    for (int i = 0; i < endStateNum; i++){
        if (states[currState] == endState[i]){
            cout <<endl<< "匹配成功" << endl<<endl;
            accept = true;
        }
    }
    if (!accept) cout <<endl<< "字符串不在接受状态中" <<endl<< endl;
}


int main(){
	read();
	printDFA();
	cout << "输入需要验证的字符串：" << endl;
    while(cin >>inputString){
		cout<<"输入待显示的可接收字符串的最大长度N:"<<endl;
		int N;
		cin>>N;
		DFA(N);
    	cout << "输入需要验证的字符串：" << endl;
	} 
	delete []characters;
	delete []states;
	delete []endState;
	delete []transTable;
    system("pause");
	return 0;
}

代码测试：

测试用例1：