myopg.c

这是一段关于算符优先的源码

/*
实验五  自底下上语法分析----算符优先分析方法

程序测试数据:i+i*i (i-i)*i (使用任何该文法的句子即可)
其他输入串将输出错误信息及错误步骤
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>

#define M 7			/*M为终结符的个数*/

/*程序示例使用的文法*/
/*G[E]:E→E+T∣E-T∣T    
         T→T*F∣T/F∣F
         F→(E)∣i */

/*
S->#E#
E->E+T
E->T
T->T*F
T->F
F->P^F | P
P->(E)
P->i
*/

typedef struct type						/*产生式类型定义*/
{
	char left;						/*大写字符*/
	char right[5];						/*产生式右边字符*/
	int length;							/*字符个数*/
}type;

char VT[8],VN[8];	/*符号表*/
type G[9];
FILE *fp,*fout;

//若字符c不在s中，则将c加入s
void addIn1(char s[],char c,int *flag)
{
	int i,len,tag=1;
	len=strlen(s);
	for (i=0;i<len;i++)
	{
		if (s[i]==c)
		{
			tag=0;
			break;
		}
	}
	if (tag)
	{
		s[len]=c;
		s[len+1]='\0';
		*flag=1;
	}
}

void inputG(type G[])
{
    char infile[15] ;
	char ch;
	int i=0;
	int	j=0;
	int m,n=0;
	int flag=0;
	printf("Enter the infile name:");
	scanf("%s",infile);
	if((fp=fopen(infile,"r+"))==NULL) //r+表示打开可读写的文件
	{
		printf("\ncannot open infile \n");
		exit(0);
	}	
	ch=fgetc(fp);
	while(ch!=EOF) //用来判断文件结束的标记(end of file)
	{
		putchar(ch);
		ch=fgetc(fp);
	}
	fputc(' ',fp);
	rewind(fp); //使文件的位置指针重新返回文件的开头
    
	while((!feof(fp))&&(ch=fgetc(fp))!=EOF)
	{
		if(ch==' ')
		{  
		}
		else if(ch=='\n')
		{
			G[i].length=j;
			j=0;
			i++;
		}
		else if(ch=='-')
		{
			ch=fgetc(fp);
			if(ch=='>')
			{
				fseek(fp,-3,1);
                ch=fgetc(fp);
				G[i].left=ch;
                addIn1(VN,G[i].left,&flag);
				j--;
				fseek(fp,2,1);
			}
			else
			{
				fseek(fp,-2,1);
				ch=fgetc(fp);
                G[i].right[j]=ch;
				j++;
			}
		}
		else if(ch=='|')
		{   
			G[i].length=j;
			i++;
			j=0;
			n++;
			G[i].left=G[i-1].left;
            addIn1(VN,G[i].left,&flag);
		}
		else
		{
			G[i].right[j]=ch;
			j++;
		}
	}
    G[i].length=j;
    fclose(fp);
}

/*辅助函数,在一个字符串中查找某特定字符*/
int locate(char s[],char c)
{
	unsigned int i;
	for(i=0;i<strlen(s);i++)
	{
		if(c==s[i])
		{
			return i+1;
		}
	}
	return -1;
}

/*查找与已搜索出的短语对应的产生式,返回该产生式的序号*/
int Find(type G[],char s[],int m,int n)
{
	int i,j,flag;
	for (i=0;i<9;i++)					/*逐条扫描产生式*/
	{
		flag=0;
		for (j=m;j<=n;j++)
		{
			if(locate(VT,s[j])!=-1)
			{
				if (G[i].right[j-m]!=s[j])		/*只需匹配终结符*/
				{
					break;
				}
			}
		}
		if (j>n)		/*表明匹配成功*/
		{
			flag=1;
			break;
		}
	}
	if (flag)
	{
		return i;
	}
	return -1;
}

/*输出分析过程的函数*/
void print(char s[],int k,int tag,char str[],int i,char action[])
{
	char c;
	int j;
	switch(tag) {
	case -1:
		c='<';
		break;
	case 0:
		c='=';
		break;
	default:
		c='>';
	}
	for (j=1;j<=k;j++)
	{
		fprintf(fout,"%c",s[j]);
	}
	fprintf(fout,"\t%c\t\t%c\t\t%s\t\t%s\n",c,str[i],(str+i+1),action);
	
}

/*对输入串进行分析的主控函数*/
void doScan();

void doScan()
{
	int i=0,j,k,m;
	char str[10],S[20];		/*str为输入符号串 S为分析栈*/
	char a,b;
	char test;


	/*初始化有限关系矩阵*/
	int table[M+1][M+1]={{-2,-2,-2,-2,-2,-2,-2,-2},
	{-2,1,-1,-1,-1,-1,1,1},
	{-2,1,1,-1,-1,-1,1,1},
	{-2,1,1,-1,-1,-1,1,1},
	{-2,1,1,1,-2,-2,1,1},
	{-2,-1,-1,-1,-1,-1,0,-2},
	{-2,1,1,1,-2,-2,1,1},
	{-2,-1,-1,-1,-1,-1,-2,0}
	};

	/*初始化文法产生式*/

	inputG(G);
	scanf("%c",&test);
	printf("\n请输入待分析的文法符号串(以'#'号结束):");
	gets(str);
	for(m=0;m<strlen(str);m++)
	{
		if (locate(VT,str[m])==-1)
		{
			printf("\n输入串中有非法字符\n");
			exit(1);
		}
	}
	fout=fopen("output.txt","w");
	fprintf(fout,"stack\tpriority\tcurrent\t\tstring\t\taction\n");

	k=1;
	S[k]='#';
	
	while(1)
	{
		a=str[i];
		if(locate(VT,S[k])!=-1)	/*S[k]属于VT*/
		{
			j=k;
		}
		else
			j=k-1;
		if(table[locate(VT,S[j])][locate(VT,a)]==1)		/*S[j]优先于a*/
		{
			while(1)
			{
				b=S[j];
				if(locate(VT,S[j-1])!=-1)
				{
					j-=1;
				}
				else
					j-=2;
				if(table[locate(VT,S[j])][locate(VT,b)]==-1)
				{
					//归约
					if( (m=Find(G,S,j+1,k)) != -1 )
					{
						print(S,k,1,str,i,"归约");
						k=j+1;
						S[k]=G[m].left;
						break;
					}
					else
					{
						print(S,k,1,str,i,"错误");
						return;
					}
				}
			}
		}
		else if(table[locate(VT,S[j])][locate(VT,a)]==-1)	/*a优先与S[j]*/
		{
			//移进
			print(S,k,1,str,i,"移进");
			k++;
			S[k]=a;
			i++;
		}
		else if(table[locate(VT,S[j])][locate(VT,a)]==0)	/*a和S[j]优先性相同*/
		{
			if(table[locate(VT,S[j])][locate(VT,'#')]==0)	/*S[j]与'#'相等?*/
			{
				if(locate(VT,S[k])==-1 && str[i]=='#')
				{
					//输出成功信息
					print(S,k,0,str,i,"接受");
					return;
				}
				else
				{
					//输出错误信息
					print(S,k,0,str,i,"错误");
					return;
				}
			}
			else
			{
				//移进
				print(S,k,0,str,i,"移进");
				k++;
				S[k]=a;
				i++;
			}
		}
		else
		{
			//输出错误信息
			fprintf(fout,"error\n");
			return;
		}
	}
	fclose(fout);
}

void main()
{
	strcpy(VT,"+*^i()#");
	doScan();		
}