?? 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++)//對文法的每個句子
{
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -