/*
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;

	}
	
}