NFA.zip_Lexical Grammar_自动机

#include <iostream> #include <conio.h> #include <cstdio> #define CMAX 50 #define AMAX 50 using namespace std; void welcome() { cout<<"************************************************************"<<endl; cout<<" 正则表达式转换成NFA "<<endl; cout<<"************************************************************"<<endl; cout<<"请你输入正则表达式(如果输入的是#则表示字符串已经结束了)"<<endl; } int main() { int i,j; //循环变量 char tab[CMAX][CMAX];//存放NFA的有向弧线表 int k=0; //状态计数器 int t=0; //已经到达的状态(并非NFA的终态单元) int st0=0; //分支开始状态 int st1; //分支结束状态 int q=0; //标号值 char sym; //暂时保留正则表达式的一个字母 char a[AMAX]; //正规表达式的字母表 int stack[AMAX]; //堆栈 int top=0; int z=1; //初始化有向弧线表，令它为空 for(i=0;i<CMAX;i++) { for(j=0;j<CMAX;j++) tab[i][j]=0; } //初始化正规表达式的字母表 for(i=0;i<AMAX;i++) a[i]=0; //进入界面 welcome(); //接受键盘输入的字符串,如果输入'#'则表示结束输入 for(i=0;(i<CMAX)&&(a[i]!='#');i++) { cin>>a[i]; if (a[i]=='#') break; } //再将i赋值为0，表示从字母表的第一个字母开始考虑起 i=0; //一个while循环,当字母表没有到'#'时 while(a[i]!='#') {//如果其值为0－9、a-z、A-Z则再判断该字母的下一个字母是否为*，如果是，则将有向弧t-->k+1 //(边为&),k+1-->k+1(边为a[i]),k+1-->k+2(边为&)送入tab表中，k=k+2,t=k;否则，将弧t-->k+1 //送入tab中，k=k+1,t=k if(((a[i]>='0')&&(a[i]<='9'))||((a[i]>='A')&&(a[i]<='Z'))||((a[i]>='a')&&(a[i]<='z'))) { sym=a[i+1]; if(sym=='*') { tab[t][k+1]='&'; tab[k+1][k+1]=a[i]; tab[k+1][k+2]='&'; k=k+2;t=k; } else { tab[t][k+1]=a[i];k=k+1;t=k; } } //如果其值为|选择符号，那么判断q=0，真，终止状态为t,赋值q为1,已到达状态单元为分支开始状态 //否则，t-->st1(边为&),t=sto(已到达状态单元为分支开始状态) if(a[i]=='|') { if(q==0){st1=t;q=1;t=st0;} else{tab[t][st1]='&';t=st0;} } //如果其值为（左括号，那么将sto,st1,q压入STACK栈，将弧t-->k+1(边为&)送入tab if(a[i]=='(') { top=top+1;stack[top]=st0; top=top+1;stack[top]=st1; top=top+1;stack[top]=q; tab[t][k+1]='&'; k=k+1;t=k;st0=k;q=0; } //如果其值为）右括号，那么首先判断q是否为1，若真，将弧t-->st1(边的值为&)送入tab //将下一个符号送入sym,下一个如果为*,则将弧t-->sto(边的值为&),sto-->k+1(边的值为&) //送入tab,弹出stack顶端内容分别送入sto,st1,q if(a[i]==')') { if(q==1) {tab[t][st1]='&';t=st1;} sym=a[i+1]; if(sym=='*') {tab[t][st0]='&'; tab[st0][k+1]='&'; k=k+1;t=k; } q=stack[top];top=top-1; st1=stack[top];top=top-1; st0=stack[top];top=top-1; } i++; } //判断q为1否，真，将弧t-->st1(边值为&)送入tab中 if(q==1) {tab[t][st1]='&';t=st1;} for(i=0;i<20;i++)//输出状态，按照x-->y(边上的值为z）此格式输出 { for(j=0;j<20;j++) { if(tab[i][j]!=0) { cout<<i<<"-"<<tab[i][j]<<"->"<<j<<endl; } } } }