opg.c

编译原理全套实验源代码。包括词法分析

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

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

20031401008  褚超
*/

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

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

/*程序示例使用的文法*/
/*
S->#E#
E->E+T
E->T
T->T*F
T->F
F->P^F | P
P->(E)
P->i
*/
char VT[8];	/*符号表*/

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

/*辅助函数,在一个字符串中查找某特定字符*/
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].array[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++)
	{
		printf("%c",s[j]);
	}
	printf("\t%c\t\t%c\t\t%s\t\t%s\n",c,str[i],(str+i+1),action);
	
}

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

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

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

	/*初始化有限关系矩阵*/
	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}
	};

	/*
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			printf("%3d",table[i][j]);
		}
		printf("\n");
	}
	getch();
	*/

	/*初始化文法产生式*/
	G[0].origin='S';
	strcpy(G[0].array,"#E#");
	G[0].length=3;

	G[1].origin='E';
	strcpy(G[1].array,"E+T");
	G[1].length=3;

	G[2].origin='E';
	strcpy(G[2].array,"T");
	G[2].length=1;

	G[3].origin='T';
	strcpy(G[3].array,"T*F");
	G[3].length=3;

	G[4].origin='T';
	strcpy(G[4].array,"F");
	G[4].length=1;

	G[5].origin='F';
	strcpy(G[5].array,"P^F");
	G[5].length=3;

	G[6].origin='F';
	strcpy(G[6].array,"P");
	G[6].length=1;

	G[7].origin='P';
	strcpy(G[7].array,"(E)");
	G[7].length=3;

	G[8].origin='P';
	strcpy(G[8].array,"i");
	G[8].length=3;

	printf("请输入待分析的文法符号串(以'#'号结束):");
	gets(str);
	for(m=0;m<strlen(str);m++)
	{
		if (locate(VT,str[m])==-1)
		{
			printf("\n输入串中有非法字符\n");
			exit(1);
		}
	}
	
	printf("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].origin;
						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
		{
			//输出错误信息
			printf("error\n");
			return;
		}
	}
}