//04級計算機（2）班 作者：承霖  完成時間：2006年4月26日 

#include <iostream.h>
#include "Stack.cpp"
#include "string.h"
#include <conio.h>

struct TABLE
{
	char NonTerminal;
	char Terminal;
	char *Producer;
//	string Producer;
}table[]={{'E','i',"TM"},{'E','(',"TM"},
		{'M','+',"+TM"},{'M',')',"ε"},{'M','#',"ε"},
		{'T','i',"FN"},{'T','(',"FN"},
		{'N','+',"ε"},{'N','*',"*FN"},{'N',')',"ε"},{'N','#',"ε"},
		{'F','i',"i"},{'F','(',"(E)"}}; //預測分析表數組
//實現函數列表
char VNonterminal[] = {'E','T','M','N','F'};//非終結符數組
char VTerminal[] = {'i','+','*','(',')'};   //終結符數組
char VTerminal1[] = {'i','+','*','(',')','#'}; //用于輸出預測表
void GramScanner(Stack<char> &stack);  //語法分析實現函數
bool IsTerminal(char c);               //判斷是否為終結符
void OutputError();                    //出錯處理
void ReversePush(char nonterminal,char termianl,Stack<char> &stack); //反序壓棧實現函數
bool IsInPredictTable(char nonterminal,char terminal);               //判斷是否在預測表中
int FindIndex(char nonterminal,char terminal);                       //查找對應項在預測表中的位置
void PrintResult(Stack<char>& stack,char* c,int index,char nonterminal);//打印輸出結果
bool IsNonterminal(char c);                                           //判斷是否為非終結符
void PrintPredictTable();                                              //打印預測表
//主函數
int main()
{
	Stack<char> stack;
	cout << "*************************所用的文法如下*********************************\n\n";
	cout<<"E->TM   S->+TM|ε  T->FN  P->*FN|ε  F->(E)|i  \n\n";
	cout << "*************************預測分析表如下*********************************\n\n";
	PrintPredictTable();
	GramScanner(stack);
	return 0;
}
//函數的實現區
void GramScanner(Stack<char> &stack)
{
	stack.Push('#');
	stack.Push('E');
	cout << "******************************輸入句型**********************************\n\n";
	cout << "Input the sentence:";
	
	char ch;
	char popchar;
	bool flag = true;
	int i = 0;	
	char sentence[20];
	while((ch = cin.get()) != '\n')
		sentence[i++] = ch;
	sentence[i] = '\0';
	cout << endl;
	cout << "分析已經完成,請按任意鍵查看結果" << endl;
	getch();
	char *p = sentence;
	ch = *p;
	cout << "\n**************************分析過程如下**********************************\n\n\n";
	cout << "步驟" << "\t\t" << "符號棧" << "\t\t" << "輸入串" << "\t\t" << "所用產生式" << endl;
	while(flag == true)
	{
		PrintResult(stack,p,FindIndex(popchar,ch),popchar);
		popchar = stack.Pop();
		
		if(IsTerminal(popchar))
		{
			if(popchar == ch)
			{
			//	ch = cin.get();
				*(p++) = ' ';
				ch = *p;
			}
			else
			{
				OutputError();
			}
		}
		else if(popchar == '#')
		{
			if(popchar == ch)
				flag = false;
			else 
			{
				OutputError();
			}
		}
		else if(IsInPredictTable(popchar,ch))
		{
			ReversePush(popchar,ch,stack);
			
		}
		else 
		 {
			 OutputError();
			 break;
		 }
	}
	cout << endl;
	cout << "******************************輸出完成**********************************"<<endl;
}
bool IsTerminal(char c)
{
	int n = sizeof(VTerminal)/sizeof(char);
	int i = 0;
	for(i = 0;i <= n;i++)
	{
		if(c == VTerminal[i])
			break;
	}
	if(i <= n)
		return true;
	else return false;
}
void OutputError()
{
	cout << "there is an error here!" << endl;
}

bool IsInPredictTable(char nonterminal,char terminal)
{
	if(FindIndex(nonterminal,terminal) != -1)
		return true;
	else return false;
}
void ReversePush(char nonterminal,char terminal,Stack<char> &stack)
{
	int i = FindIndex(nonterminal,terminal);
	if(strcmp(table[i].Producer,"ε") != 0) 
	{
		int len = strlen(table[i].Producer);
		char *temp;
		temp = new char[len + 1];
		strcpy(temp,table[i].Producer);
		for(int j = len-1;j >= 0;j--)
			stack.Push(temp[j]);
	}
}
int FindIndex(char nonterminal,char terminal)
{
	int i = 0;
	int n = sizeof(table)/sizeof(TABLE);
	for(;i <= n;i++)
	{
		if(nonterminal == table[i].NonTerminal && terminal == table[i].Terminal)
			break;
	}
	if(i <= n)
		return i;
	else return -1;
}
void PrintResult(Stack<char>& stack,char* c,int index,char nonterminal)
{
	static int i = 0;

	cout << i++ << "\t\t";
	stack.PrintElem();
	cout << "\t\t";
	cout << c;
	cout << "\t\t";
	if(index != -1 && IsNonterminal(nonterminal))
		cout << nonterminal << "->" << table[index].Producer;
	cout << endl;
}
bool IsNonterminal(char c)
{
	int n = sizeof(VNonterminal)/sizeof(char);
	int i = 0;
	for(i = 0;i <= n;i++)
	{
		if(c == VNonterminal[i])
			break;
	}
	if(i <= n)
		return true;
	else return false;
}
void PrintPredictTable()
{
	int n = sizeof(VTerminal1)/sizeof(char);
//	cout << n;
	cout << "\t";
	for(int i = 0;i < n;i++)
	{
		cout << VTerminal1[i];
		cout << "\t";
	}
	cout << endl;
	int m = sizeof(VNonterminal)/sizeof(char);
	for(i = 0;i < m;i++)
	{
		cout << VNonterminal[i];
		for(int j = 0;j < n;j++)
		{
			int index;
			cout << "\t";
			if(IsInPredictTable(VNonterminal[i],VTerminal1[j]))
			{
				index = FindIndex(VNonterminal[i],VTerminal1[j]);
				cout << VNonterminal[i] << "->" << table[index].Producer;
			}
		}
		cout << "\n\n";
	}
}