#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<fstream>
#include<string>
#include<cmath>
using namespace std;
struct token//token結構體
{
	int code;
	int num;
	token *next;
};
token *token_head,*token_tail;//token隊列
struct number//number結構體
{
	int num;
	int value;
	number *next;
};
number *number_head,*number_tail;//number隊列
struct str//string結構體
{
	int num;
	string  word;
	str *next;
};
str *string_head,*string_tail;//string隊列
struct ivan//表達式結構體
{
	char left;
	string right;
	int len;
};
ivan css[20];//20個表達式
struct pank//action表結構體
{
	char sr;
	int state;
};
pank action[46][18];//action表
int go_to[46][11];//go_to表
struct ike//分析棧結構體，雙鏈
{
	ike *pre;
	int num;
	int word;
	ike *next;
};
ike *stack_head,*stack_tail;//分析棧首尾指針

void scan();//按字符讀取源文件
int judge(char ch);//判斷輸入字符的類型
void out1(char ch);//寫入token.txt
void out2(char ch,string word);//寫入number.txt
void out3(char ch,string word);//寫入string.txt
void input1(token *temp);//插入結點到隊列token
void input2(number *temp);//插入結點到隊列number
void input3(str *temp);//插入結點到隊列string
void output();//輸出三個隊列的內容
void outfile();//輸出三個隊列的內容到相應文件中
void yufa_initialize();//初始化語法分析數據結構
int yufa_main(int a);//語法分析主體部分
int ID1(int a);//給輸入字符編號，轉化成action表列編號
string ID10(int i);//給輸入字符反編號
int ID2(char ch);//給非終結狀態編號，轉化成go_to表列編號
int ID20(char ch);//給非終結狀態編號
char ID21(int j);//給非終結狀態反編號
void add(ike *temp);//給ike分析棧鏈表增加一個結點
void del();//給ike分析棧鏈表刪除一個結點

FILE *fp;//文件
int wordcount;//標志符計數
int numcount;//整型常數計數
int err;//標志詞法分析結果正確或錯誤
int nl;//讀取行數
void main()
{
	token_head=new token;
	token_head->next=NULL;
	token_tail=new token;
	token_tail->next=NULL;
	number_head=new number;
	number_head->next=NULL;
	number_tail=new number;
	number_tail->next=NULL;
	string_head=new str;
	string_head->next=NULL;
	string_tail=new str;
	string_tail->next=NULL;//初始化三個隊列的首尾指針
	wordcount=0;//初始化字符計數器
	numcount=0;//初始化常數計數器
	err=0;//初始化詞法分析錯誤標志
	nl=1;//初始化讀取行數
	scan();
	if(err==0)
	{
		char m;
		cout<<"詞法分析正確完成!"<<endl<<endl<<"下邊將輸出結果，如果將結果保存到文件中請輸入 y ，否則請輸入其它鍵：";
		cin>>m;
		output();
		if(m=='y')
		{
			cout<<"結果同時保存在token.txt、number.txt和sting.txt三個文件中，請打開查看"<<endl;
			outfile();
		}
	}
	yufa_initialize();//初始化語法分析數據結構
	token *temp;
	temp=new token;
	temp=token_head->next;
	int p,q;
	p=0;
	q=0;
	cout<<endl<<"下面開始語法分析："<<endl;
	while(temp!=NULL)
	{
		int w;
		w=ID1(temp->code);
		p=yufa_main(w);
		if(p==1) break;
		if(p==0)
			temp=temp->next;
		if(temp==NULL) q=1;
	}//語法分析
	if(q==1)
		while(1)
		{
			p=yufa_main(17);
			if(p==3) break;
		}//最后輸入$來完成語法分析
	cout<<endl;
	system("pause");
}
void scan()
{
	char ch;
	string word;
	char document[50];
	int flag=0;
	cout<<"請輸入源文件路徑及名稱:";
	cin>>document;
	cout<<endl;
	if((fp=fopen(document,"rt"))==NULL)
	{
		err=1;
		cout<<"無法找到該文件!"<<endl;
		return;
	}
	while(!feof(fp))
	{
		word="";
		ch=fgetc(fp);
		flag=judge(ch);
		if(flag==1)
			out1(ch);
		else if(flag==2)
			out2(ch,word);
		else if(flag==3)
			out3(ch,word);
		else if(flag==4 || flag==5 ||flag==6)
			continue;
		else
		{
			cout<<nl<<"行  "<<"錯誤:非法字符!  "<<ch<<endl;
			err=1;
		}
	}
	fclose(fp);
}
int judge(char ch)
{
	int flag=0;
	if(ch=='=' || ch=='+' || ch=='*' || ch=='>' || ch==':' || ch==';' || ch=='{' || ch=='}' || ch=='(' || ch==')')
		flag=1;//界符
	else if('0'<=ch && ch<='9')
		flag=2;//數字
	else if(('a'<=ch && ch<='z') || ('A'<=ch && ch<='Z'))
		flag=3;//字母
	else if(ch==' ')
		flag=4;//空格
	else if(feof(fp))
		flag=5;//結束
	else if(ch=='\n')
	{
		flag=6;//換行
		nl++;
	}
	else
		flag=0;//非法字符
	return(flag);
}
void out1(char ch)
{
	int id;
	switch(ch)
	{
	case '=' : id=1;break;
	case '+' : id=2;break;
	case '*' : id=3;break;
	case '>' : id=4;break;
	case ':' : id=5;break;
	case ';' : id=6;break;
	case '{' : id=7;break;
	case '}' : id=8;break;
	case '(' : id=9;break;
	case ')' : id=10;break;//界符編碼
	default : id=0;
	}
	token *temp;
	temp=new token;
	temp->code=id;
	temp->num=-1;
	temp->next=NULL;
	input1(temp);
	return;
}
void out2(char ch,string word)
{
	token *temp;
	temp=new token;
	temp->code=-1;
	temp->num=-1;
	temp->next=NULL;
	number *temp1;
	temp1=new number;
	temp1->num=-1;
	temp1->value=-1;
	temp1->next=NULL;
	int flag=0;
	word=word+ch;
	ch=fgetc(fp);
	flag=judge(ch);
	if(flag==1)
	{
		numcount++;
		temp->code=26;
		temp->num=numcount;
		input1(temp);
		temp1->num=numcount;
		int i,num_value=0,num_length;//字符串轉化為數字
		char *num_head;
		num_head=&word[0];
		num_length=strlen(num_head);
		for(i=num_length-1;i>=0;i--)
			num_value=num_value+(int(word[i])-48)*pow(10,(num_length-i-1));
		temp1->value=num_value;//把數字的值賦給結點
		input2(temp1);
		out1(ch);
	}
	else if(flag==2)
		out2(ch,word);//形成字符串
	else if(flag==3)
	{
		err=1;
		cout<<nl<<"行  "<<"錯誤:數字后面跟字母!"<<endl;
		return;
	}
	else if(flag==4 || flag==5 || flag==6)
	{
		numcount++;
		temp->code=26;
		temp->num=numcount;
		input1(temp);
		temp1->num=numcount;
		int i,num_value=0,num_length;//字符串轉化為數字
		char *num_head;
		num_head=&word[0];
		num_length=strlen(num_head);
		for(i=num_length-1;i>=0;i--)
			num_value=num_value+(int(word[i])-48)*pow(10,(num_length-i-1));
		temp1->value=num_value;//把數字的值賦給結點
		input2(temp1);
		return;
	}
	else
	{
		err=1;
		cout<<nl<<"行  "<<"錯誤:非法字符!  "<<ch<<endl;
		return;
	}
}
void out3(char ch,string word)
{
	token *temp;
	temp=new token;
	temp->code=-1;
	temp->num=-1;
	temp->next=NULL;
	str *temp1;
	temp1=new str;
	temp1->num=-1;
	temp1->word="";
	temp1->next=NULL;
	int flag=0;
	word=word+ch;
	ch=fgetc(fp);
	flag=judge(ch);
	if(flag==1 || flag==4 || flag==5 || flag==6)
	{
		if(word=="and" || word=="if" || word=="then" /*|| word=="else"*/ || word=="while" || word=="do" || word=="int")
		{
			if(word=="and")
				temp->code=31;
			else if(word=="if")
				temp->code=32;
			else if(word=="then")
				temp->code=33;
			//else if(word=="else")
			//	temp->code=34;
			else if(word=="while")
				temp->code=35;
			else if(word=="do")
				temp->code=36;
			else if(word=="int")
				temp->code=37;//關鍵字編碼
			input1(temp);
			if(flag==1)
				out1(ch);
			else if(flag==4 || flag==5 || flag==6)
				return;
		}
		else if(flag==1)
		{
			wordcount++;
			temp->code=25;
			temp->num=wordcount;
			input1(temp);
			temp1->num=wordcount;
			temp1->word=word;
			input3(temp1);
			out1(ch);
		}
		else if(flag==4 || flag==5 || flag==6)
		{
			wordcount++;
			temp->code=25;
			temp->num=wordcount;
			input1(temp);
			temp1->num=wordcount;
			temp1->word=word;
			input3(temp1);
		}
		return;
	}
	else if(flag==2 || flag==3)
		out3(ch,word);//形成字符串
	else
	{
		err=1;
		cout<<nl<<"行  "<<"錯誤:非法字符!  "<<ch<<endl;
		return;
	}
}
void input1(token *temp)
{
	if(token_head->next == NULL)
	{
		token_head->next=temp;
		token_tail->next=temp;
	}
	else
	{
		token_tail->next->next=temp;
		token_tail->next=temp;
	}
}
void input2(number *temp)
{
	if(number_head->next == NULL)
	{
		number_head->next=temp;
		number_tail->next=temp;
	}
	else
	{
		number_tail->next->next=temp;
		number_tail->next=temp;
	}
}
void input3(str *temp)
{
	if(string_head->next == NULL)
	{
		string_head->next=temp;
		string_tail->next=temp;
	}
	else
	{
		string_tail->next->next=temp;
		string_tail->next=temp;
	}
}
void output()
{
	cout<<"token表內容如下："<<endl;
	token *temp1;
	temp1=new token;
	temp1=token_head->next;
	while(temp1!=NULL)
	{
		cout<<temp1->code;
		if(temp1->num == -1)
		{
			cout<<endl;
		}
		else
		{
			cout<<"   "<<temp1->num<<endl;
		}