ll1.cpp

本程序作为计算机学院编译原理课程试验的一部分

/************************************************************************/
/*		            Arther:         涂靖								*/
/*		            StudentNumber:  1050320124                          */
/*		            ClassName:      编译原理                            */
/*		            Program:        LL1语法分析							*/
/*		            Data:			2008.4.12                           */
/*
文件说明：
	Vset.txt			  非终结符文件
	Tset.txt			  终结符文件
	Grammar.txt			  语法文件
	Sentence.txt		  句型文件
	Ana_table.txt		  分析表文件									*/
/************************************************************************/
//------------------------头文件--------------------------------
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

//------------------------宏定义--------------------------------
#define END_SYM      0                 //空
#define MAX_SYM_LEN  20                //符号最大长度
#define MAX_SET_NUM  100               //集合最大数量
#define MAX_BODY_LEN 100               //产生式右部最大长度
#define MAX_GRA_NUM  100               //文法最大数目
#define MAX_SEN_NUM  200               //句型中符号最大数目
#define MAX_STACK_NUM 50               //栈大小
#define MAX_GRA_BODY_LEN  6            //文法句子右部最大长度

//-----------------------函数声明--------------------------------
void readingrammar();                  //从文件读入文法
void outputgrammar();                  //输出文法
void find_empty_position();            //找到空在非终结符集合中的位置
void cal_first_set();                  //计算first集函数(调用cal_first()函数)
void cal_first(int first_vn_num);      //计算每个非终结符的first集函数
void output_first_set();               //输出first集
void cal_follow_set();                 //计算follow集函数(调用cal_follow()函数)
void cal_follow(int follow_vn_num);    //计算每一个非终结符的follow集函数
void output_follow_set();              //输出follow函数
void construct_analyse_table();        //构建分析表
void output_analyse_table();           //输出分析表
void readintsentence();                //从文件读入要分析的句型
void analyse();                        //分析函数
//------------------------数据结构声明------------------------------------

struct symbol{//每个标示符(关键子)的结构
	char sym[MAX_SYM_LEN];  //存储标示符
	int code;               //存储标示符的编码
};

struct grammar{//每句文法的机构(注意:存储的都是符号编码后的数字)
	int head;               //左部
	int body[MAX_BODY_LEN]; //右部
	int body_len;           //右部长度
	int first[MAX_SET_NUM]; //本句文法的first集
	int first_len;          //本句文法的first集长度
};

struct ele{//(first or follow)集合元素(编码)   
	int vn;                 //集合元素对应的非终结符
	int vt[MAX_SET_NUM];    //集合元素对应的终结符集合
	int vt_len;             //终结符集合个数
	int flag_empty;         //标志first集中是否含空
	int flag_cla;           //标志集合是否已经被计算过
};

struct analyse_ele{//分析表的元素(编码)
	int head;               //对应句子的左部
	int body[MAX_BODY_LEN]; //对应句子的右部
	int body_len;           //右部长 
	int flag;               //标志该元素在分析表是否为空
};

//------------------------全局变量声明------------------------------------
//文件指针,分别为非终结符文件,终结符文件,语法文件,句型文件和分析表文件指针
FILE *vfp, *tfp, *gfp, *sfp, *afp;         
struct symbol vset[MAX_SET_NUM];         //非终结符集合
struct symbol vtset[MAX_SET_NUM];         //终结符集合
struct symbol vtset_for_ana[MAX_SET_NUM]; //分析表中终结符集合
struct symbol sentence[MAX_SEN_NUM];      //存储从文件读入的要分析的句型
int vset_num;              //非终结符个数
int vtset_num;              //终结符个数
int vtset_for_ana_num;      //分析表中终结符个数
int sen_sym_num;            //要分析的句型中标示符个数
struct grammar gra_list[MAX_GRA_NUM];      //存储文法
int gra_lis_num;            //文法句子的数目
struct ele first_set[MAX_SET_NUM];   //first集
struct ele follow_set[MAX_SET_NUM];  //follow集
int first_set_num;          //first集中元素个数
int follow_set_num;         //follow集中元素个数
int empty_position;         //空的在终结符集合中位置
struct analyse_ele analyse_table[MAX_SET_NUM][MAX_SET_NUM]; //分析表
int row_num;    //分析表的行数
int col_num;    //分析表的列数
int analyse_stack[MAX_STACK_NUM];     //分析栈
int top;        //栈顶

//***************************主函数**********************************
int main()
{
	//打开文件
	if ((vfp = fopen("Vset.txt","r"))==NULL)
	{
		printf("open file:vsetFile error.\n");
		return 0;
	}
	if ((tfp = fopen("Tset.txt","r"))==NULL)
	{
		printf("open file:vtsetFile error.\n");
		return 0;
	}
	if ((gfp = fopen("Grammar.txt","r"))==NULL)
	{
		printf("open file:grammarFile error.\n");
		return 0;
	}
	
	if((sfp = fopen("Sentence.txt", "r"))==NULL)
	{
		printf("open file:test_sentenceFile error.");
		return 0;
	}
	readingrammar();           //从文件读入文法
	outputgrammar();           //把文法输出到标准输出	
	find_empty_position();     //找到空在终结符集合中的位置
	cal_first_set();           //计算文法的first集
	output_first_set();        //输出文法的first集
	cal_follow_set();          //计算文法的follow集
	output_follow_set();       //输出文法的follow集
	construct_analyse_table(); //构造文法的分析表
	output_analyse_table();    //输出分析表到文件
	readintsentence();         //从文件读入要分析的句型
	analyse();                 //对要分析的句型进行分析,并输出分析要用到的文法语句序列
	
	fclose(vfp);				//关闭文件
	fclose(tfp);
	fclose(gfp);
	fclose(sfp);
	
	return 0;
}

//*****************************函数实现过程******************************

void readingrammar()	  //读入文法
{
	int vnindex = 0;
	char ch1;
	while (!feof(vfp))    //读入文法中的非终结符 
	{
		int v=0;
		ch1=fgetc(vfp);
		do{	
			vset[vnindex].sym[v]=ch1;
			v++;
			ch1=fgetc(vfp);
		}while(isalnum(ch1));
		vset[vnindex].sym[v]='\0';
		vset[vnindex].code = -(vnindex+1);//对非终结符编码
 		vnindex++;
	}
	vset_num = vnindex;   //得到文法中非终结符个数
	
	int vtindex = 0;
	char ch2;
	while (!feof(tfp))    //读入文法中的终结符 
	{
		int v=0;
		ch2=fgetc(tfp);
		do{	
			vtset[vtindex].sym[v]=ch2;
			v++;
			ch2=fgetc(tfp);
		}while(isalnum(ch2));
		vtset[vtindex].sym[v]='\0';
		vtset[vtindex].code = (vtindex+1);//对终结符编码
		vtindex++;
	}
	vtset_num = vtindex;   //得到文法中终结符个数
	
	int grmindex = 0;      //文法句子计数
	char ch;
	char buffer[MAX_SYM_LEN]="";
	int gra_col_num=0;     //文法列计数
	while(!feof(gfp))
	{
		ch = fgetc(gfp);
		if (ch == ' ' )    //空格
			;
		else if(ch=='-' && fgetc(gfp) == '>') //->
			;
		else if (isalpha(ch))   //字母
		{
			int j = 0;
			int flag=0;
			do 
			{
				buffer[j] = ch;
				ch = fgetc(gfp);
				j++;
			} while(isalnum(ch));
			buffer[j]='\0';
			ungetc(ch,gfp);
			int i;
			for (i=0; i<vtset_num; i++)
			{
				if ((strcmp(buffer,vtset[i].sym))==0)
				{
					flag=1;
					break;
				}
			}
			if(flag==1)        //终结符
			{
				if (i<vtset_num)
				{
					if (gra_col_num == 0)
					{
						gra_list[grmindex].head = vtset[i].code;
						gra_col_num++;
					}
					else
					{
						gra_list[grmindex].body[gra_col_num-1] = vtset[i].code;
						gra_col_num++;
					}					
				}
				else
				{
					printf("vt error\n");
				}
			}
			else              //非终结符
			{
				for (i=0; i<vset_num; i++)
				{
					if ((strcmp(buffer,vset[i].sym))==0)
					{
						break;
					}
				}
				if (i<vset_num)	
				{
					if (gra_col_num == 0)
					{
						gra_list[grmindex].head = vset[i].code;
						gra_col_num++;
					}
					else
					{
						gra_list[grmindex].body[gra_col_num-1] = vset[i].code;
						gra_col_num++;
					}
				}
				else
				{
					printf("%d vn error\n",grmindex);
				}
			}		
		}
		else if (ch == '\n' || feof(gfp))  //回车或文件结束
		{
			gra_list[grmindex].body_len = gra_col_num - 1;
			grmindex ++;
			gra_col_num = 0; //列计数置0
		}
		else  //操作符
		{
			if (ch=='<'||ch=='>')  //< 或>号,有可能下个是=号
			{
				char ch1;
				ch1=fgetc(gfp);
				if (ch1=='=')
				{
					buffer[0]=ch;
					buffer[1]=ch1;
					buffer[2]='\0';
				}
				else
				{
					ungetc(ch1,gfp);
					buffer[0]=ch;
					buffer[1]='\0';
				}
			}
			else   //其他为单操作符
			{
				buffer[0] = ch;
				buffer[1] ='\0';
			}
			int i;
			for (i=0; i<vtset_num; i++)
			{
				if ((strcmp(buffer,vtset[i].sym))==0)
				{
					break;
				}
			}
			if (i<vtset_num)	
			{
				if (gra_col_num == 0)
				{
					gra_list[grmindex].head = vtset[i].code;
					gra_col_num++;
				}
				else
				{
					gra_list[grmindex].body[gra_col_num-1] = vtset[i].code;
					gra_col_num++;
				}
			}
			else
			{
				printf("%d op error\n",grmindex);
			}			
		}
	}
	gra_list[grmindex].body_len = gra_col_num - 1; //得到句子右部长度
	grmindex++;
	gra_lis_num = grmindex;   //得到文法句子数
}

void outputgrammar()		  //输出文法
{
	printf("==============================\n");
	printf("grammar:\n------------------------------\n");
	for (int i=0; i<gra_lis_num;i++)
	{
		printf("%s-> ",vset[-gra_list[i].head-1].sym);
		for (int j=0; j<gra_list[i].body_len; j++)
		{
			if(gra_list[i].body[j]<0)
				printf("%s ",vset[-gra_list[i].body[j]-1].sym);
			else
				printf("%s ",vtset[gra_list[i].body[j]-1].sym);
		}
		printf("\n");
	}
	printf("==============================\n");
}


void readintsentence()			//读入句型
{
	char ch='\0';
	sen_sym_num=0;  
	while(!feof(sfp)&&ch!='#')
	{
		ch = fgetc(sfp);
		if(ch==' '||ch=='\n'||ch=='\t')
			;
		else if(isalpha(ch))  //字母
		{
			int i=0;
			int flag=0;
			do
			{
				sentence[sen_sym_num].sym[i]=ch;
				i++;
				ch = fgetc(sfp);
			}while(isalnum(ch));
			ungetc(ch,sfp);
			if (ch=='#')
			{
				ch='\0';
			}
			sentence[sen_sym_num].sym[i]='\0';
			for(int j=0; j<vtset_for_ana_num; j++)
			{
				if((strcmp(sentence[sen_sym_num].sym,vtset_for_ana[j].sym))==0)
				{
					sentence[sen_sym_num].code=vtset_for_ana[j].code;
					flag=1;
					break;
				}
			}
			sen_sym_num++;
			if(flag==0)
			{
				printf("the sentence is not belong to this grammar\n");
				exit(0);
			}
		}
		else //非字母
		{
			int flag=0;
			sentence[sen_sym_num].sym[0]=ch;
			sentence[sen_sym_num].sym[1]='\0';
			for(int j=0; j<vtset_for_ana_num; j++)
			{
				if((strcmp(sentence[sen_sym_num].sym,vtset_for_ana[j].sym))==0)
				{
					sentence[sen_sym_num].code=vtset_for_ana[j].code;
					flag=1;
					break;
				}
			}
			sen_sym_num++;
			if(flag==0)
			{
				printf("the sentence is not belong to this grammar\n");
				exit(0);
			}
		}
	}
}

//函数：找到空在终结符集合（数组）中的位置
void find_empty_position()
{
	int i;
	for (i=0; i<vtset_num; i++)
		if ((strcmp("#", vtset[i].sym))==0)
			break;
	empty_position = i;
}
//函数:计算first集
void cal_first_set()
{
	for (int i=0; i<vtset_num; i++) //初始化
	{
		first_set[i].vn=vset[i].code;
		first_set[i].flag_cla=0;
		first_set[i].flag_empty=0;
		first_set[i].vt_len=0;
		for (int j=0; j<gra_lis_num; j++)
			if (gra_list[j].head==first_set[i].vn)
				if (gra_list[j].body[0]==vtset[empty_position].code)
					first_set[i].flag_empty=1;
	}
	first_set_num=vset_num;
	for (int k=0; k<vtset_num; k++)  //如果first集没计算完
		if (first_set[k].flag_cla==0)//如果该first集没有计算过
			cal_first(k);   //递归计算该非终结符的first集
}

//函数:计算每个非终结符的first集的递归函数
void cal_first(int first_vn_num)
{
	for(int i=0; i<gra_lis_num; i++)//对文法的每个句子
	{