automatism.cpp

本课程设计采用C语言进行编译原理实现课题有限自动机的应用

/*                字符
                  状态	d	e	＋	－	.  其它   #
                    S	S	A			B         S  
                    A	C		D	D	    
                    B	E				  
                    C	C				          C
                    D	C				    
                    E	E	Z			          E  
                    Z	C		D	D	          Z


			  字符
             状态    0 	 1	 2	 3	 4    5        6 
              0	     0	 1  -1  -1   2   -1        1   (最后一列的状态0：初态，1：终态）
              1		 3	-1   4   4  -1   -1        0
              2      5	-1	-1	-1	-1   -1        0
              3	     3	-1	-1	-1	-1   -1        1
              4	     3	-1	-1	-1	-1   -1        0
              5	     5	 6  -1  -1  -1   -1        1
              6	     3	-1   4   4	-1   -1        1

           f(S,d)=S    f(S,e)=A      f(S,.)=B   f(A,d)=C       f(A,－)=D      f(A,＋)=D   
		   f(B,d)=E    f(C,d)=C      f(D,d)=C   f(E,d)=E       f(E,e)=Z       f(Z,d)=C
		   f(Z,＋)=D   f(Z,－)=D
           
        在和序设计过程中，我们定义一二维数组来表示以上的整型数组f[7，6]＝－1，其初值为－1，
		具体对应上面的f表示为：
		   f[0][0]=0    f[0][1]=1      f[0][4]=2   f[1][0]=3       f[1][2]=4       f[1][3]=4
		   f[2][0]=5    f[3][0]=3      f[4][0]=3   f[5][0]=5       f[5][1]=6       f[6][0]=3
		   f[6][2]=4    f[6][3]=4
           
*/
#include<stdio.h>
#include<iostream.h>
#define MAX 100//定义输入串的最大长度
main()
{
      //数组f[][]为状态表，以整数组形式存放，0,1,2,3,4,5,6表示状态，-1表示没有此状态
      //  注：其中数组f[][6]列的0为非终态标识，1为终态标识，用来最终确定输入串是否为无符号实数

int f[7][7]={{0,1,-1,-1,2,-1,1},{3,-1,4,4,-1,-1,0},{5,-1,-1,-1,-1,-1,0},{3,-1,-1,-1,-1,-1,1},{3,-1,-1,-1,-1,-1,0},{5,6,-1,-1,-1,-1,1},{3,-1,4,4,-1,-1,1}};
char DataInput[MAX];      //输入缓冲区
int DataInputC[MAX];     //输入缓冲区的整数存放形式
int i,sub;              //sub用来作为更替数组的行无素，即实现状态的转换
char ynexit;           //用来判断是否结束测试
printf("程序功能：输入一个字符串，判断它是否是无符号定点实数。\n");
while(true)
{
 printf("请输入以\"#\"号结束的无空格字符串：");
 scanf("%s",&DataInput);
 i=0;//初始化
 while(DataInput[i]!='#'&&i<MAX)//此循环用来将输入串转化为整数的存放形式
 {
      if(DataInput[i]>='0'&&DataInput[i]<='9')
	     DataInputC[i]=0;
       else if(DataInput[i]=='e')
		 DataInputC[i]=1;
       else if(DataInput[i]=='+')
		 DataInputC[i]=2;
	   else if(DataInput[i]=='-')
		 DataInputC[i]=3;
	   else if(DataInput[i]=='.')
		 DataInputC[i]=4;
	   else 
		 DataInputC[i]=5;
       i++;
 }
 if(DataInput[i]=='#')
    DataInputC[i]=6;  
    i=0; 
 sub=f[0][0];
 while(DataInputC[i]!=6)//此循环用来通过对数组化的自动机判断输入串是否为无符号定点实数
 {    
    if(f[sub][DataInputC[i]]==-1)//如果转换后的状态是不可达状态则表明不被接受，反之继续转换到相应的状态
	{
		printf("不接受\n");break;
	}
	sub=f[sub][DataInputC[i]];
    i++;
 }
 if(f[sub][DataInputC[i]]==1)//输入串的尾部且自动机的状态为1时，此输入串为可接收的
    printf("接受\n");
 printf("继续测试吗：（Y/N）");
  if((ynexit=getchar())=='N'||(ynexit=getchar())=='n')
  {
	  break;
  }
}
return 0;
}