no3.cpp

编译原理的语法

#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 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;//分析栈首尾指针
struct L//语义四元式的数据结构
{
	int k;
	string op;//操作符
	string op1;//操作数
	string op2;//操作数
	string result;//结果
	L *next;//语义四元式向后指针
	L *Ltrue;//回填true链向前指针
	L *Lfalse;//回填false链向前指针
};
L *L_four_head,*L_four_tail,*L_true_head,*L_false_head;//四元式链，true链，false链
struct symb//语义输入时符号表
{
	string word;//变量名称
	int addr;//变量地址
	symb *next;
};
symb *symb_head,*symb_tail;//语义符号链表

/*********************下面是与词法分析相关的一些函数的声明***************************/

void scan();//按字符读取源文件
void cifa_main();//词法分析主程序
int judge(char ch);//判断输入字符的类型
void out1(char ch);//写入token.txt
void out3(char ch,string word);//写入string.txt
void input1(token *temp);//插入结点到队列token
void input3(str *temp);//插入结点到队列string
void output();//输出三个队列的内容
void outfile();//输出三个队列的内容到相应文件中

/*********************下面是与语法分析相关的一些函数的声明***************************/

void yufa_main();//语法分析主程序
void yufa_initialize();//初始化语法分析数据结构
int yufa_SLR1(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分析栈链表删除一个结点

/*********************下面是与语义分析相关的一些函数的声明***************************/

void yuyi_main(int m);//语义分析主程序
void add_L_four(L *temp);//向四元式链中加一个结点
void add_L_true(L *temp);//向true链中加一个结点
void add_L_false(L *temp);//向false链中加一个结点
void add_symb(symb *temp);//向语义符号表链中加一个结点
void output_yuyi();//输出中间代码四元式和最后符号表
string newop(int m);//把数字变成字符串
string id_numtoname(int num);//把编号转换成相应的变量名
int lookup(string m);//变量声明检查

/*********************下面是一些全局变量的声明***************************/

FILE *fp;//文件指针
int wordcount;//标志符计数
int err;//标志词法分析结果正确或错误
int nl;//读取行数
int yuyi_linshi;//语义临时变量
string E_name,T_name,F_name,M_name,id_name,id1_name,id2_name,errword;//用于归约时名称传递和未声明变量的输出
int id_num,id1_num,id2_num,id_left,id_while,id_then,id_do;//用于记录一些特殊的字符位置信息

/****************************主程序开始**************************/

int main()
{
	cout<<"************************"<<endl;
	cout<<"*  说明：              *"<<endl;
	cout<<"*  第一部分：词法分析  *"<<endl;
	cout<<"*  第二部分：语法分析  *"<<endl;
	cout<<"*  第三部分：语义分析  *"<<endl;
	cout<<"************************"<<endl;
	cifa_main();//词法
	yufa_main();//语法
	output_yuyi();//语义
	cout<<endl;
	system("pause");
	return(0);
}

/****************************以上是主程序，以下是词法**************************/

void cifa_main()
{
	token_head=new token;
	token_head->next=NULL;
	token_tail=new token;
	token_tail->next=NULL;
	string_head=new str;
	string_head->next=NULL;
	string_tail=new str;
	string_tail->next=NULL;//初始化三个队列的首尾指针
	L_four_head=new L;
	L_four_head->next=NULL;
	L_four_tail=new L;
	L_four_tail->k=0;
	L_four_tail->next=NULL;
	L_true_head=new L;
	L_true_head->Ltrue=NULL;
	L_false_head=new L;
	L_false_head->Lfalse=NULL;
	symb_head=new symb;
	symb_head->next=NULL;
	symb_tail=new symb;
	symb_tail->next=NULL;
	yuyi_linshi=-1;
	id_num=0;
	wordcount=0;//初始化字符计数器
	err=0;//初始化词法分析错误标志
	nl=1;//初始化读取行数
	scan();
	if(err==0)
	{
		char m;
		output();
		cout<<"词法分析正确完成!"<<endl<<endl<<"如果将结果保存到文件中请输入 y ，否则请输入其它字母：";
		cin>>m;
		cout<<endl;
		if(m=='y')
		{
			outfile();
			cout<<"结果成功保存在token.txt和sting.txt两个文件中，请打开查看"<<endl;
			cout<<endl;
		}
	}
}
void scan()
{
	cout<<endl;
	system("pause");
	cout<<endl;
	char ch;
	string word;
	char document[50];
	int flag=0;
	cout<<"请输入源文件路径及名称:";
	cin>>document;
	cout<<endl;
	cout<<"************************"<<endl;
	cout<<"*  第一部分：词法分析  *"<<endl;
	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==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(('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 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;//关键字编码
			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 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;
		}
		temp1=temp1->next;
	}
	cout<<"符号表内容如下："<<endl;
	str *temp3;
	temp3=new str;
	temp3=string_head->next;
	while(temp3!=NULL)
	{
		cout<<temp3->num<<"   "<<temp3->word<<endl;
		temp3=temp3->next;
	}
}
void outfile()
{
	ofstream fout1("token.txt");//写文件
	ofstream fout3("string.txt");
	token *temp1;
	temp1=new token;
	temp1=token_head->next;
	while(temp1!=NULL)
	{
		fout1<<temp1->code;
		if(temp1->num == -1)
			fout1<<endl;
		else
			fout1<<"   "<<temp1->num<<endl;
		temp1=temp1->next;
	}
	str *temp3;
	temp3=new str;
	temp3=string_head->next;
	while(temp3!=NULL)
	{
		fout3<<temp3->num<<"   "<<temp3->word<<endl;
		temp3=temp3->next;
	}
}

/****************************以上是词法，以下是语法**************************/

void yufa_main()
{
	if(err==0)
	{
		system("pause");
		cout<<endl;
		cout<<"************************"<<endl;
		cout<<"*  第二部分：语法分析  *"<<endl;
		cout<<"************************"<<endl;
		yufa_initialize();//初始化语法分析数据结构
		token *temp;
		temp=new token;
		temp=token_head->next;
		int p,q;
		p=0;
		q=0;
		cout<<"语法分析过程如下："<<endl;
		while(temp!=NULL)
		{
			int w;
			w=ID1(temp->code);
			p=yufa_SLR1(w);
			if(p==1) break;
			if(p==0)
				temp=temp->next;
			if(temp==NULL) q=1;
		}//语法分析
		if(q==1)
			while(1)
			{
				p=yufa_SLR1(17);
				if(p==3) break;
			}//最后输入$来完成语法分析
	}
}
void yufa_initialize()
{	
	stack_head=new ike;
	stack_tail=new ike;
	stack_head->pre=NULL;
	stack_head->next=stack_tail;
	stack_head->num=0;
	stack_head->word='!';
	stack_tail->pre=stack_head;
	stack_tail->next=NULL;//初始化栈分析链表
	css[0].left='Q';
	css[0].right="P";
	css[1].left='P';
	css[1].right="id()L;R";
	css[2].left='L';
	css[2].right="L;D";
	css[3].left='L';
	css[3].right="D";
	css[4].left='D';
	css[4].right="id:int";
	css[5].left='E';
	css[5].right="E+T";
	css[6].left='E';
	css[6].right="T";
	css[7].left='T';
	css[7].right="T*F";
	css[8].left='T';
	css[8].right="F";
	css[9].left='F';
	css[9].right="(E)";
	css[10].left='F';
	css[10].right="id";
	css[11].left='B';
	css[11].right="B and B";
	css[12].left='B';
	css[12].right="id>id";
	css[13].left='M';
	css[13].right="id=E";
	css[14].left='S';
	css[14].right="if B then M";
	css[15].left='S';
	css[15].right="while B do M";
	css[16].left='S';
	css[16].right="M";
	css[17].left='N';
	css[17].right="N;S";
	css[18].left='N';
	css[18].right="S";
	css[19].left='R';
	css[19].right="{N}";
	int i,j;
	for(i=0;i<20;i++)
	{
		char *css_len;
		css_len=&css[i].right[0];
		css[i].len=strlen(css_len);
	}
	css[1].len=6;
	css[4].len=3;
	css[10].len=1;
	css[11].len=3;
	css[12].len=3;
	css[13].len=3;
	css[14].len=4;
	css[15].len=4;//初始化产生式
	for(i=0;i<46;i++)
	{
		for(j=0;j<18;j++)
			action[i][j].sr='#';
	}//初始化action表
	for(i=0;i<46;i++)
	{
		for(j=0;j<11;j++)
			go_to[i][j]=-1;
	}//初始化go_to表
	/****************************以下是给action表和go_to表赋初值************************/
	action[0][0].sr='s';action[0][0].state=2;
	action[1][17].sr='@';//结束
	action[2][1].sr='s';action[2][1].state=3;
	action[3][2].sr='s';action[3][2].state=4;
	action[4][0].sr='s';action[4][0].state=5;
	action[5][4].sr='s';action[5][4].state=6;
	action[6][11].sr='s';action[6][11].state=7;
	action[7][3].sr='r';action[7][3].state=4;
	action[8][3].sr='r';action[8][3].state=3;
	action[9][3].sr='s';action[9][3].state=10;
	action[10][0].sr='s';action[10][0].state=5;
	action[10][9].sr='s';action[10][9].state=13;
	action[11][17].sr='r';action[11][17].state=1;
	action[12][3].sr='r';action[12][3].state=2;
	action[13][0].sr='s';action[13][0].state=14;
	action[13][13].sr='s';action[13][13].state=23;
	action[13][15].sr='s';action[13][15].state=27;
	action[14][8].sr='s';action[14][8].state=15;
	action[15][0].sr='s';action[15][0].state=36;
	action[15][1].sr='s';action[15][1].state=41;
	action[16][6].sr='s';action[16][6].state=43;
	action[16][3].sr='r';action[16][3].state=13;
	action[16][10].sr='r';action[16][10].state=13;
	action[17][3].sr='s';action[17][3].state=19;