01-基础学习:课程:编译原理:实验:实验一:dfa编程实现代码
DFA编程实现代码
确定DFA的数据结构
定义DFA类
- dfa.h
#include<iostream> #include<fstream> #include<cstring> #include<cmath> #include<vector> using namespace std; //DFA类 class DFA{ public: DFA(){num_q=0;num_f=0;num_sigma=0;}; //构造函数 void input(); //DFA输入 void print_dfa(); //DFA输出 void judge(char *str); //DFA规则字符串判断 int simple_judge(char *str); //不显示信息的判断 void write(); //写五元组到文件 int read(); //从文件中读取五元组 int check(); //检查DFA的正确性 void collection(); //语言集列表 void get_str(int k,vector<char> v); //得到字母表的所有组合 int num_q; //状态个数 int num_sigma; //字符数 int num_f; //接受状态个数 private: char q[100]; char sigma[100]; char delta[100][100]; char q0; //起始状态 char f[100]; //接受状态集 };
DFA类实现
- dfa.cpp
#include "dfa.h" //输入DFA void DFA::input() { //输入状态集 cout<<"状态集:"; int i=0; do{ cin>>q[i]; i++; }while(getchar()!='\n'); num_q=i; //状态个数 i=0; //cout<<"num_q="<<num_q<<endl; //调试输出 //输入字母表 cout<<"字母表:"; do{ cin>>sigma[i]; i++; }while(getchar()!='\n'); num_sigma=i; //字符数 i=0; //cout<<"num_sigma="<<num_sigma<<endl; //输入转移矩阵 cout<<"转移函数:"<<endl; for(int i=0;i<num_q;i++) for(int j=0;j<num_sigma;j++) cin>>delta[i][j]; //起始状态 cout<<"起始状态:"; cin>>q0; //接受状态集 cout<<"接受状态集:"; do{ cin>>f[i]; i++; }while(getchar()!='\n'); num_f=i; //接受状态个数 i=0; //cout<<"num_f="<<num_f<<endl; } //输出DFA void DFA::print_dfa() { cout<<"您输入五元组为："<<endl; cout<<"{{"; for(int i=0;i<num_q;i++) { cout<<q[i]; if(i<num_q-1) cout<<","; } cout<<"},{"; for(int i=0;i<num_sigma;i++) { cout<<sigma[i]; if(i<num_sigma-1) cout<<","; } cout<<"},{"; for(int i=0;i<num_q;i++) for(int j=0;j<num_sigma;j++) { cout<<delta[i][j]; if(j+1==num_sigma) cout<<","; else cout<<" "; } cout<<"},"; cout<<q0<<",{"; for(int i=0;i<num_f;i++) { cout<<f[i]; if(i<num_f-1) cout<<","; } cout<<"}}"<<endl; } //DFA规则字符串判断 void DFA::judge(char *str) { int i=0; int str_lenght; //待测串长度 str_lenght=strlen(str); cout<<"您输入的字符串为:"; cout<<str<<endl; //找出q0在状态集中的位置 int loca_q0; for(loca_q0=0;i<num_q;loca_q0++) { if(q[loca_q0]==q0) break; } char tmp; tmp=q[loca_q0]; //最开始为起始状态 cout<<"\n状态转移过程为："<<endl; for(unsigned int j=0;j<str_lenght;j++) { //找出str[j]在字母表中的位置 int order=0; int flags=0; //标志是否在字母表中找到字符 for(order=0;order<num_sigma;order++) { if(str[j]==sigma[order]) { flags=1; //在字母表中找到字符 break; } } //如果字符不在字母表中，返回错误 if(flags!=1) { cout<<"DFA不接受该串(存在不在字母表中的字符)!"<<endl; return; } flags=0; //重置为0继续用于标志状态是否在状态集中 int i=0; //找出状态在状态集合中的位置 int locat=0; for(locat=0;locat<num_q;locat++) { if(tmp==q[locat]) { flags=1; break; } } //如果状态不在状态集中，返回错误 if(flags!=1) { cout<<"DFA不接受该串!(转移矩阵错误)"<<endl; return; } if(delta[locat][order]=='-') { cout<<"DFA不接受该串.(空状态)"<<endl; return; } else { //cout<<"order="<<order<<endl; cout<<"状态 "<<q[locat]<<" 经 "<<str[j]<<" 到状态 "<< delta[locat][order]<<endl; tmp=delta[locat][order]; //DFA运行 } } //DFA停止状态测试输出 cout<<"停止状态:"<<tmp<<endl; cout<<endl; for(int j=0;j<num_f;j++) { if(tmp==f[j]) cout<<"DFA接受"<<str<<" ? : YES"<<endl; else cout<<"DFA接受"<<str<<" ? : NO"<<endl; } } //写五元组到文件 void DFA::write() { ofstream out; out.open("data.dfa"); if(!out) { cout<<"文件打开错误!"<<endl; return; } //写入状态集 for(int i=0;i<num_q;i++) { out<<q[i]; if(i<num_q-1) out<<" "; } out<<endl; //写入字母表 for(int i=0;i<num_sigma;i++) { out<<sigma[i]; if(i<num_sigma-1) out<<" "; } out<<endl; //写入转移矩阵 for(int i=0;i<num_q;i++) { for(int j=0;j<num_sigma;j++) { out<<delta[i][j]; if((j+1)%num_sigma==0) out<<endl; else out<<" "; } } //写入初始状态 out<<q0<<endl; //写入接受状态集 for(int i=0;i<num_f;i++) { out<<f[i]; if(i<num_f-1) out<<" "; } out<<endl; out.close(); } //从文件中读取五元组 int DFA::read() { ifstream fin; fin.open("data.dfa"); if(!fin) { cout<<"打开data.dfa失败，请先执行步骤2"<<endl; return 0; } //输入状态集 int i=0; while(fin.get(q[i])) { if(q[i]==' ') continue; if(q[i]=='\n') break; cout<<q[i]<<" "; i++; } cout<<endl; num_q=i; //状态个数 i=0; //cout<<"num_q="<<num_q<<endl; //调试输出 //输入字母表 while(fin.get(sigma[i])) { if(sigma[i]==' ') continue; if(sigma[i]=='\n') break; cout<<sigma[i]<<" "; i++; } cout<<endl; num_sigma=i; //字符数 i=0; //cout<<"num_sigma="<<num_sigma<<endl; //输入转移矩阵 for(int i=0;i<num_q;i++) for(int j=0;j<num_sigma;j++) { if(delta[i][j]==' '||delta[i][j]=='\n') continue; fin>>delta[i][j]; cout<<delta[i][j]<<" "; if(j+1==num_sigma) cout<<endl; } //起始状态 fin>>q0; fin.get(); cout<<q0<<endl; //接受状态集 while(fin.get(f[i])) { if(f[i]==' ') continue; if(f[i]=='\n') break; cout<<f[i]<<" "; i++; } cout<<endl; num_f=i; //接受状态个数 i=0; //cout<<"num_f="<<num_f<<endl; return 1; } //DFA正确性检查 int DFA::check() { //检查状态集元素的唯一性 for(int i=0;i<num_q;i++) { for(int j=i+1;j<num_q;j++) { if(q[i]==q[j]) { cout<<"状态集元素不唯一！请检查输入"<<endl; return 0; } } } //检查字母表元素的唯一性 for(int i=0;i<num_sigma;i++) { for(int j=i+1;j<num_sigma;j++) { if(sigma[i]==sigma[j]) { cout<<"字母表元素不唯一! 请检查输入"<<endl; return 0; } } } //检查转移矩阵 int flags=0; for(int i=0;i<num_q;i++) { for(int j=0;j<num_sigma;j++) { for(int k=0;k<num_q;k++) { if((delta[i][j]==q[k])||(delta[i][j]=='-')) //转移矩阵元素在状态集中 { flags=1; break; } flags=0; //重置flags } if(flags!=1) { cout<<"转移矩阵中存在不在状态集或不为'-'的元素! 请检查输入"<<endl; return 0; } } } //检查开始状态是否在状态集中 flags=0; for(int i=0;i<num_q;i++) { if(q0==q[i]) { flags=1; break; } } if(flags!=1) { cout<<"起始状态不在状态集中! 请检查输入"<<endl; return 0; } //检查接受状态集是否唯一 for(int i=0;i<num_f;i++) { for(int j=i+1;j<num_f;j++) { if(f[i]==f[j]) { cout<<"接受状态集元素不唯一! 请检查输入"<<endl; return 0; } } } //检查接受状态集是否在状态集中 flags=0; for(int i=0;i<num_f;i++) { for(int j=0;j<num_q;j++) { if(f[i]==q[j]) { flags=1; break; } } if(flags!=1) { cout<<"接受状态集有元素不包含在状态集中! 请检查输入"<<endl; return 0; } } cout<<"各集合元素唯一...."<<endl; cout<<"开始状态唯一,并包含在状态集中...."<<endl; cout<<"接受状态集元素在状态集中...."<<endl; cout<<"状态转换表正确...."<<endl; cout<<"DFA 通过正确性检查"<<endl; return 1; } //不显示调试信息的DFA规则字符串判断 int DFA::simple_judge(char *str) { int i=0; int str_lenght; //待测串长度 str_lenght=strlen(str); //找出q0在状态集中的位置 int loca_q0; for(loca_q0=0;i<num_q;loca_q0++) { if(q[loca_q0]==q0) break; } char tmp; tmp=q[loca_q0]; //最开始为起始状态 for(unsigned int j=0;j<str_lenght;j++) { //找出str[j]在字母表中的位置 int order=0; int flags=0; //标志是否在字母表中找到字符 for(order=0;order<num_sigma;order++) { if(str[j]==sigma[order]) { flags=1; //在字母表中找到字符 break; } } //如果字符不在字母表中，返回错误 if(flags!=1) { return 0; } flags=0; //重置为0继续用于标志状态是否在状态集中 int i=0; //找出状态在状态集合中的位置 int locat=0; for(locat=0;locat<num_q;locat++) { if(tmp==q[locat]) { flags=1; break; } } //如果状态不在状态集中，返回错误 if(flags!=1) { return 0; } if(delta[locat][order]=='-') { return 0; } else { //cout<<"order="<<order<<endl; tmp=delta[locat][order]; //DFA运行 } } for(int j=0;j<num_f;j++) { if(tmp==f[j]) return 1; else return 0; } } //得到所字母表组成的所有字符串有列表 void DFA::get_str(int k,vector<char> v) { if(k>0) { for(int i=0;i<num_sigma;i++) { v.push_back(sigma[i]); if(k==1) { char *tmp; tmp=new char[v.size()+1]; for(int j=0;j<v.size();j++) { tmp[j]=v[j]; //cout<<v[j]; } tmp[v.size()]='\0'; //数组结束 if(simple_judge(tmp)) { cout<<tmp<<endl; } delete []tmp; } else { get_str(k-1,v); } v.pop_back(); } } } //显示语言集列表 void DFA::collection() { vector<char> v; int n; //字符串最大长度 cout<<"请输入字符串最大长度:"; cin>>n; cout<<"\n该DFA的语言集为:\n"; for(int i=1;i<n+1;i++) { get_str(i,v); v.clear(); } }
显示信息类
定义类：
- display.h
#include<iostream> using namespace std; //显示类 class Display{ public: void main_msg(); void dfa_in(); void dfa_rw(); };
实现类:
- display.cpp
//打印程序信息 #include "display.h" void Display::main_msg() { cout<<"========================================================="<<endl; cout<<" DFA实现 by annhe 11 Apr 2013 "<<endl; cout<<"========================================================="<<endl; cout<<"请选择操作: "<<endl; cout<<" 1.DFA的输入 "<<endl; cout<<" 2.DFA的存储与读写 "<<endl; cout<<" 3.DFA的正确性检查 "<<endl; cout<<" 4.DFA的语言集列表显示 "<<endl; cout<<" 5.DFA的规则字符串判定 "<<endl; cout<<" 0.退出系统 "<<endl; cout<<"========================================================="<<endl; } void Display::dfa_in() { cout<<"请输入DFA (格式：均以空格分隔)"<<endl; } void Display::dfa_rw() { cout<<"写入文件的格式为："<<endl; cout<<"==========================="<<endl; cout<<"a b c //状态集"<<endl; cout<<"0 1 //字母表"<<endl; cout<<"delta[a][b] //转移矩阵 - 表示出错状态"<<endl; cout<<"q0 //起始状态"<<endl; cout<<"f //接受状态集"<<endl; cout<<"==========================="<<endl; }
主函数
- main.cpp
#include "display.h" #include "dfa.h" #include <cstdlib> #include <string> void input_str(char *str); int main() { Display msg; //信息类 DFA adfa; //dfa类 char str[100]; //待测字符串 string choice;//设置为字符串型防止输入非法字符时死循环 do{ system("cls"); msg.main_msg(); cin>>choice; if(choice=="1") { msg.dfa_in(); //显示说明信息 adfa.input(); //输入dfa if(adfa.check()) //DFA正确性检查 adfa.print_dfa(); //输出dfa system("pause"); } else if(choice=="2") { msg.dfa_rw(); //显示说明信息 string tmp; //选择 cout<<"1.将内存中dfa数据写入data.dfa文件;\n2.输入dfa并写入data.dfa;\n3.读取data.dfa文件中的dfa"<<endl; cout<<"请选择:"; cin>>tmp; if(tmp=="1") { if(adfa.num_q==0) { cout<<"内存内容为空，您还没有输入过DFA，请先输入:"<<endl; adfa.input(); //输入dfa if(adfa.check()) //DFA正确性检查 { adfa.write(); //写dfa到文件 cout<<"DFA已成功写入data.dfa !"<<endl; } } else { adfa.write(); //写dfa到文件 cout<<"DFA已成功写入data.dfa !"<<endl; } } else if(tmp=="2") { adfa.input(); //输入dfa if(adfa.check()) //DFA正确性检查 { adfa.write(); //写dfa到文件 cout<<"DFA已成功写入data.dfa !"<<endl; } } else if(tmp=="3") { cout<<"文件data.dfa的内容为:"<<endl; if(adfa.read()) { if(adfa.check()) //DFA正确性检查 adfa.print_dfa(); //输出dfa } } else { cout<<"输入错误!"<<endl; break; } system("pause"); } else if(choice=="3") { string tmp; //选择 cout<<"1.使用内存中的DFA.\n2.使用data.dfa中的DFA\n3.输入DFA"<<endl; cout<<"请选择:"; cin>>tmp; if(tmp=="1") { if(adfa.num_q==0) { cout<<"内存内容为空，您还没有输入过DFA，请先输入:"<<endl; adfa.input(); //输入dfa adfa.print_dfa(); //输出dfa cout<<endl; adfa.check(); //DFA正确性检查 cout<<endl; } else { adfa.print_dfa(); //输出dfa cout<<endl; adfa.check(); //DFA正确性检查 cout<<endl; } } else if(tmp=="2") { cout<<"文件data.dfa的内容为:"<<endl; if(adfa.read()) { adfa.print_dfa(); //输出dfa cout<<endl; adfa.check(); //DFA正确性检查 cout<<endl; } } else if(tmp=="3") { adfa.input(); //输入DFA adfa.print_dfa(); //输出dfa adfa.check(); //DFA正确性检查 } else { cout<<"输入错误!"<<endl; break; } system("pause"); } else if(choice=="4") { string tmp; //选择 cout<<"1.使用内存中的DFA.\n2.使用data.dfa中的DFA\n3.输入DFA"<<endl; cin>>tmp; if(tmp=="1") { if(adfa.num_q==0) { cout<<"内存内容为空，您还没有输入过DFA，请先输入:"<<endl; adfa.input(); //输入dfa adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { adfa.collection(); //语言集列表 } } else { adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { adfa.collection(); //语言集列表 } } } else if(tmp=="2") { cout<<"文件data.dfa的内容为:"<<endl; if(adfa.read()) { adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { adfa.collection(); //语言集列表 } } } else if(tmp=="3") { adfa.input(); //输入DFA adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { adfa.collection(); //语言集列表 } } else { cout<<"输入错误!"<<endl; break; } system("pause"); } else if(choice=="5") { string tmp; //选择 cout<<"1.使用内存中的DFA.\n2.使用data.dfa中的DFA\n3.输入DFA"<<endl; cout<<"请选择:"; cin>>tmp; if(tmp=="1") { if(adfa.num_q==0) { cout<<"内存内容为空，您还没有输入过DFA，请先输入:"<<endl; adfa.input(); //输入dfa adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { input_str(str); //输入字符串 adfa.judge(str); //规则字符串判断 } } else { adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { input_str(str); //输入字符串 adfa.judge(str); //规则字符串判断 } } } else if(tmp=="2") { cout<<"文件data.dfa的内容为:"<<endl; if(adfa.read()) { adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { input_str(str); adfa.judge(str); //规则字符串判断 } } } else if(tmp=="3") { adfa.input(); //输入DFA adfa.print_dfa(); //输出dfa if(adfa.check()) //DFA正确性检查 { input_str(str); adfa.judge(str); //规则字符串判断 } } else { cout<<"输入错误!"<<endl; break; } system("pause"); } else if(choice=="0") { break; } else { cout<<"输入错误！"<<endl; system("pause"); } //adfa.release(); }while(1); system("pause"); return 0; } void input_str(char *str) { cout<<"请输入待测字符串:"; cin>>str; }
Makefile
- makefile
CC=g++ CCFLAGS=-Wall dfa:main.o dfa.o display.o clean: rm -rf *.o
01-基础学习/课程/编译原理/实验/实验一/dfa编程实现代码.txt · 最后更改: 2020/04/07 06:34 由 annhe
除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Noncommercial-Share Alike 4.0 International
