#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<fstream>
#include<string>
#include<cmath>
using namespace std;
struct token//token結(jié)構(gòu)體
{
	int code;//存放單詞的id號
	int num;//存放字符或數(shù)字出現(xiàn)的次數(shù)
	token *next;
};
token *token_head,*token_tail;//token隊列
struct number//number結(jié)構(gòu)體
{
	int num;//
	int value;//
	number *next;
};
number *number_head,*number_tail;//number隊列
struct str//string結(jié)構(gòu)體
{
	int num;//
	string  word;//
	str *next;
};
str *string_head,*string_tail;//string隊列
struct bds//表達式結(jié)構(gòu)體
{
	char left;//存放規(guī)則左部
	string right;//存放右部
	int len;//長度
};
bds css[20];//存放文法的20個表達式
struct SLR//action表結(jié)構(gòu)體
{
	char sr;//放符號
	int state;//放狀態(tài)
};
SLR action[46][18];//action表
int go_to[46][11];//go_to表
struct fxz//分析棧結(jié)構(gòu)體，雙鏈
{
	fxz *pre;//前指針
	int num;//狀態(tài)號
	int word;//字符號
	fxz *next;//后指針
};
fxz *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);//插入結(jié)點到隊列token
void input2(number *temp);//插入結(jié)點到隊列number
void input3(str *temp);//插入結(jié)點到隊列string
void output();//輸出三個隊列的內(nèi)容
void outfile();//輸出三個隊列的內(nèi)容到相應(yīng)文件中
void yufa_initialize();//初始化語法分析數(shù)據(jù)結(jié)構(gòu)
int yufa_main(int a);//語法分析主體部分
int ID1(int a);//給輸入字符編號，轉(zhuǎn)化成action表列編號
string ID10(int i);//給輸入字符反編號
int ID2(char ch);//給非終結(jié)狀態(tài)編號，轉(zhuǎn)化成go_to表列編號
int ID20(char ch);//給非終結(jié)狀態(tài)編號
char ID21(int j);//給非終結(jié)狀態(tài)反編號
void add(fxz *temp);//給fxz分析棧鏈表增加一個結(jié)點
void del();//給fxz分析棧鏈表刪除一個結(jié)點

FILE *fp;//文件
int wordcount;//標志符計數(shù)
int numcount;//整型常數(shù)計數(shù)
int err;//標志詞法分析結(jié)果正確或錯誤
int nl;//讀取行數(shù)
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;//初始化字符計數(shù)器
	numcount=0;//初始化常數(shù)計數(shù)器
	err=0;//初始化詞法分析錯誤標志
	nl=1;//初始化讀取行數(shù)
	yufa_initialize();//初始化語法分析數(shù)據(jù)結(jié)構(gòu)
	cout<<"此程序所用的文法如下："<<endl;
	//-------------------------------------------------------------
	
	
	for(int i=0;i<20;i++)//輸出文法
		{
		cout<<css[i].left<< "->"<<css[i].right;
		cout<<endl;
	}
//---------------------------------------------------------------------
	scan();//詞法分析
	
	if(err==0)
	{
		char m;
		cout<<"詞法分析完成，程序無詞法錯誤！"<<endl;
		cout<<"下邊將輸出結(jié)果，如果想要把分析結(jié)果保存到文本文檔中請輸入 y ,否則請輸入其它鍵：";
		cin>>m;
		output();
		if(m=='y')
		{
			cout<<"結(jié)果保存在token.txt、number.txt和sting.txt三個文件中"<<endl;
			outfile();
		}
	}
	
	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||flag==7)
			continue;//繼續(xù)向下讀
		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;//數(shù)字
	else if(('a'<=ch && ch<='z') || ('A'<=ch && ch<='Z'))
		flag=3;//字母
	else if(ch==' ')
		flag=4;//空格
	else if(feof(fp))
		flag=5;//結(jié)束
	else if(ch=='\n')
	{
		flag=6;//換行
		nl++;
	}
	else if(ch=='	')
		flag=7;//tab鍵
	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)//處理數(shù)字
{
	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)//如果后面為界符說明前面的數(shù)字串已經(jīng)結(jié)束
	{
		//處理數(shù)字

		numcount++;
		temp->code=26;
		temp->num=numcount;
		input1(temp);
		temp1->num=numcount;
		int i,num_value=0,num_length;//字符串轉(zhuǎn)化為數(shù)字
		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;//把數(shù)字的值賦給結(jié)點
		input2(temp1);//加入到數(shù)字鏈表中
		out1(ch);//處理此界符
	}
	else if(flag==2)//如果后面為數(shù)字
		out2(ch,word);//形成字符串
	else if(flag==3)//如果后面為字母報錯
	{
		err=1;
		cout<<nl<<"行  "<<"錯誤:數(shù)字后面跟字母!"<<endl;
		return;
	}
	else if(flag==4 || flag==5 || flag==6)//如果后面為空格換行或結(jié)束
	{
		numcount++;
		temp->code=26;
		temp->num=numcount;
		input1(temp);
		temp1->num=numcount;
		int i,num_value=0,num_length;//字符串轉(zhuǎn)化為數(shù)字
		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;//把數(shù)字的值賦給結(jié)點
		input2(temp1);//加入到數(shù)字鏈表中
		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=="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=="while")
				temp->code=35;
			else if(word=="do")
				temp->code=36;
			else if(word=="int")
				temp->code=37;//給關(guān)鍵字編碼
			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;