www.pudn.com > LL1.rar > LL1.cpp
/************************************************************************/
/* Arther: 涂靖 */
/* StudentNumber: 1050320124 */
/* ClassName: 编译原理 */
/* Program: LL1语法分析 */
/* Data: 2008.4.12 */
/*
文件说明：
Vset.txt 非终结符文件
Tset.txt 终结符文件
Grammar.txt 语法文件
Sentence.txt 句型文件
Ana_table.txt 分析表文件 */
/************************************************************************/
//------------------------头文件--------------------------------
#include
#include
#include
#include
//------------------------宏定义--------------------------------
#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') //< 或>号,有可能下个是=号
{
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 ",vset[-gra_list[i].head-1].sym);
for (int j=0; j0) //如果是终结符
{
first_set[first_vn_num].vt[first_set[first_vn_num].vt_len]=gra_list[i].body[l]; //加入当前要求的非终结符的first集
first_set[first_vn_num].vt_len++;
if(gra_list[i].body[l]==vtset[empty_position].code) //如果为空,当前要求的first集的空标志置1
first_set[first_vn_num].flag_empty=1;
gra_list[i].first[gra_list[i].first_len]=gra_list[i].body[l]; //附加把每个句子的first集求得,以便于构建分析表时使用
gra_list[i].first_len++;
break;
}
else //不是终结符
{
int j;
for (j=0; j ",vset[-first_set[i].vn-1].sym);
for (int j=0; j0)//如果非终结符A的后一个符号为终结符
{
int flag_exist=0;
for(int p=0; p=gra_list[i].body_len-1) //如果到了句子右部的尾部,说明非终结符A在该句子的尾部或A后的符号都可空
{
int r;
for (r=0; r", vset[-follow_set[i].vn-1].sym);
for (int j=0; j",vset[-analyse_table[i][j].head-1].sym); //输出句子的左部
int k;
for(k=0; k=0) //如果栈顶元素为终结符
{
for(int r=0; r0; m--) //把分析表中对应项的句子的右部从右到左压入栈中
{
analyse_stack[top++]=analyse_table[tmp_row][tmp_col].body[m-1];
}
printf("%15s->",vset[-analyse_table[tmp_row][tmp_col].head-1].sym); //输出分析表中对应项的句子
for(int k=0; k