simpri.c

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

/*
20031401008 褚超

实验四 自底下上语法分析----简单优先分析方法
对指定好的上下文无关文法确定其简单优先关系矩阵，利用简单优先分析法对输入的任意串进行分析

本例中将文法规定为:
G[S]:
S->bAb
A->(B | a
B->Aa)

程序测试数据:b(aa)b   b((aa)a)b (任意符号文法的输入串均可)
其他输入将输出错误信息及出错地点

其他说明:本程序虽然限定了使用的文法,但是程序实现过程中是通过程序计算出简单优先关系.所以很容易能
拓广到能实现对任意输入文法进行简单优先分析.只需借鉴上次实验LL1中的获取任意文法的输入并保存到相应
的数据结构中即可.详细说明请参见实验报告。

*/

/*按字符出现的先后将表中的顺序定为 S	b	A	(	B	a	)	#*/

#include<stdio.h>
#include<stdlib.h>
#include <string.h>
#include <conio.h>
#define M 8	

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

/* 将矩阵转置 */
void getTrans(int a[M+1][M+1],int b[M+1][M+1])
{
	int i,j;
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			b[i][j]=a[j][i];
		}
	}
}

/* 计算两关系的并集 */
void getUnion(int a[M+1][M+1],int b[M+1][M+1])
{
	int i,j;

	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			a[i][j]=a[i][j] | b[i][j];
		}
	}
}

/*利用Warshall算法计算闭包*/
void getAdd(int a[M+1][M+1])
{
	int i,j,k;

	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			if (a[j][i]==0)
			{
				continue;
			}
			for (k=1;k<=M;k++)
			{
				if (a[i][k]==0)
				{
					continue;
				}
				a[j][k]=1;
			}
		}
	}
}

/* 计算两个关系的乘积 */

void getMult(int a[M+1][M+1],int b[M+1][M+1],int c[M+1][M+1])
{
	int i,j,k;
	
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			if (a[i][j]==1)
			{
				for (k=1;k<=M;k++)
				{
					if (b[j][k]==1)
					{
						c[i][k]=1;
					}
				}
			}
		}
	}
}

/* 对输入串进行扫描的主控程序 */
void doScan(int temp[M+1][M+1]);

/*返回字符在数组中的位置*/
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;
}

/*输出分析过程的函数*/
void print(char s[],int pri,char c,char str[],char act[])
{
	char ch;
	switch(pri) {
	case 0:
		ch='=';
		break;
	case 1:
		ch='>';
		break;
	case -1:
		ch='<';
		break;
	default:
		ch='?';
	}
	printf("%s\t%8c\t%6c  \t%8s\t%s\n",s,ch,c,str,act);

}

void main()
{
	int i,j;
	int first[M+1][M+1],equal[M+1][M+1],last[M+1][M+1];		/*下标0不使用*/

	int low[M+1][M+1],high[M+1][M+1];

	int temp[M+1][M+1],temp1[M+1][M+1];

	/*首先得出first,last矩阵和 相等关系*/

	/*对各个矩阵进行初始化*/
	for(i=1;i<=M;i++)
	{
		for(j=1;j<=M;j++)
		{
			first[i][j]=0;
			last[i][j]=0;
			equal[i][j]=0;
			low[i][j]=0;
			high[i][j]=0;
			temp1[i][j]=0;
			if (i==j)
			{
				temp[i][j]=1;
			}
			else
				temp[i][j]=0;
		}
	}

	equal[2][3]=equal[3][2]=equal[4][5]=equal[3][6]=equal[6][7]=1;
	first[1][2]=first[3][4]=first[3][6]=first[5][3]=1;
	last[1][2]=last[3][5]=last[3][6]=last[5][7]=1;	

	


	/* 计算First+ */
	getAdd(first);

	/* 计算小于关系 */
	getMult(equal,first,low);
	
	/* 计算First* */
	getUnion(first,temp);
	

	/* 计算Last+ */
	getAdd(last);

	/* 将Last+转置 */
	getTrans(last,temp);

	/* 计算大于关系 */
	getMult(temp,equal,temp1);	/*将中间结果先保存到temp1中*/
	getMult(temp1,first,high);

	/* 构造简单优先关系矩阵:结果存入temp中 */
	/*大于，等于，小于 关系分别用1,0,-1表示*/
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			if (equal[i][j]==1)
			{
				temp[i][j]=0;
			}
			else if (low[i][j]==1)
			{
				temp[i][j]=-1;
			}
			else if (high[i][j]==1)
			{
				temp[i][j]=1;
			}
			else
				temp[i][j]=-2;
		}
	}

	/* 对'#'的项的处理 */
	temp[1][8]=temp[2][8]=1;
	temp[8][1]=temp[8][2]=-1;
	temp[8][8]=0;

	doScan(temp);
}

void doScan(int temp[M+1][M+1])
{
	type G[4];
	char V[10];
	char str[20];		/*输入的待分析串*/
	char stack[20];		/*符号栈*/
	int top=-1,i=0;			/*栈顶指针 i为扫描指针*/
	char *p;
	int j,k,m=0;
	char s[20];

	strcpy(V,"SbA(Ba)#");

	G[0].origin='S';
	strcpy(G[0].array,"bAb");
	G[0].length=3;

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

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

	G[3].origin='B';
	strcpy(G[3].array,"Aa)");
	G[3].length=3;

	printf("请输入待分析的符号串(以'#'结束):");
	gets(str);


	printf("stack\tpriority\tcurrent\t\tstring\t\taction\n");

	stack[++top]='#';	/* '#'号入栈 */

	
	while (1)
	{

		if (top==1 && stack[top]=='S' && str[i]=='#')
		{
			/*输入串匹配*/
			p=&str[i];
			stack[top+1]='\0';			/*输出之前在栈后加上字符串结束符*/
			print(stack,temp[locate(V,'S')][locate(V,'#')],str[i],p,"接受");
			return;
		}

		/*将输入符号依次入栈,直到遇到栈顶符号大于下一符号的优先性*/
		while (temp[locate(V,stack[top])][locate(V,str[i])]!=1)
		{
			p=&str[i];
			stack[top+1]='\0';			/*输出之前在栈后加上字符串结束符*/
			print(stack,-1,str[i],p,"移进");
			stack[++top]=str[i++];
		}
		
		/*从句柄尾开始向前搜索句柄头*/
		j=top;
		while (j>0 && temp[locate(V,stack[j-1])][locate(V,stack[j])]!=-1)
		{
			j--;
		}


		m=0;					/*每次查找前先将m清0*/
		for (k=j;k<=top;k++)
		{
			/*将句柄暂存入s中*/
			s[m++]=stack[k];
		}
		s[m]='\0';

		for (j=0;j<4;j++)
		{
			if (strcmp(s,G[j].array)==0)
			{
				break;
			}
		}	
		if (j==4)		/*没找到则出错*/
		{
			/*输出错误*/
			p=&str[i];
			stack[top+1]='\0';			/*输出之前在栈后加上字符串结束符*/
			print(stack,1,str[i],p,"出错");
			exit(0);
		}
		
		/*输出归约*/
		p=&str[i];
		stack[top+1]='\0';			/*输出之前在栈后加上字符串结束符*/
		print(stack,1,str[i],p,"归约");

		/*用相应产生式的左部代替句柄*/
		top-=G[j].length;
		stack[++top]=G[j].origin;

	}
	
}