?? ll1.cpp
字號:
if (first_set[first_vn_num].vn==gra_list[i].head)//如果左部是當前要求first集的非終結符
{
int l=0;
while(l<gra_list[i].body_len) //對句子的右部每個字符(編碼)
{
if (gra_list[i].body[l]>0) //如果是終結符
{
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<first_set_num; j++) //找到此非終結符在first集數組中的位置
if (first_set[j].vn==gra_list[i].body[l])
break;
if (first_set[j].flag_cla==1) //如果該非終結符的first集已經計算過,則加到當前要求的非終結符的first中
{
for (int k=0; k<first_set[j].vt_len; k++)
{
first_set[first_vn_num].vt[first_set[first_vn_num].vt_len]=first_set[j].vt[k];
first_set[first_vn_num].vt_len++;
if(first_set[j].vt[k]==vtset[empty_position].code) //如果該非終結符的first集中有空,則置當前要求的非終結符的first集的空標志為1
{
first_set[first_vn_num].flag_empty=1;
}
gra_list[i].first[gra_list[i].first_len]=first_set[j].vt[k]; //附加把每個句子的first集求得
gra_list[i].first_len++;
}
break;
}
else if(first_set[j].flag_empty==1) //如果該終結符的first集中有空
l++; //看右部的下一個符號
else //否則,遞歸計算該非終結符的first集
cal_first(j);
}
}
}
}
first_set[first_vn_num].flag_cla=1; //當前非終結符的first集合求完后,置已經求過標志為1
}
//函數:輸出first集
void output_first_set()
{
printf("first set:\n------------------------------\n");
for (int i=0; i<first_set_num; i++)
{
printf("%s-> ",vset[-first_set[i].vn-1].sym);
for (int j=0; j<first_set[i].vt_len;j++)
printf("%s ", vtset[first_set[i].vt[j]-1].sym);
printf("\n");
}
printf("==============================\n");
}
//函數:求文法的follow集
void cal_follow_set()
{
vtset[vtset_num].sym[0]='#'; //把#符加到終結符集合中
vtset[vtset_num].sym[1]='\0';
vtset[vtset_num].code= vtset_num+1;
vtset_num = vtset_num+1;
for (int i=0; i<vset_num; i++) //初始化存儲follow集的數據結構
{
follow_set[i].vn=vset[i].code;
follow_set[i].flag_cla=0;
follow_set[i].flag_empty=first_set[i].flag_empty;
follow_set[i].vt_len=0;
}
follow_set_num=vset_num;
for (int j=0; j<follow_set_num; j++) //如果follow集沒計算完
if (follow_set[j].flag_cla==0) //如果該非終結符的follow集沒計算過
cal_follow(j); //遞歸計算該非終結符的follow集
}
//函數:計算每個非終結符A的follow集的遞歸函數
void cal_follow(int follow_vn_num)
{
if (follow_vn_num==0) //如果是文法開始符合,把#符加到其follow集中
{
follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=END_SYM;//#
follow_set[follow_vn_num].vt_len++;
}
for (int i=0; i<gra_lis_num; i++) //對文法的每條句子
{
int q;
for (q=0; q<gra_list[i].body_len; q++) //對該句子右部的每個符號(編碼)
{
if (gra_list[i].body[q]!=follow_set[follow_vn_num].vn) //找到要求的非終結符A
continue;
else //找到了
{
for(; q<gra_list[i].body_len-1;q++) //不到該句子右部的尾部
{
if (gra_list[i].body[q+1]>0)//如果非終結符A的后一個符號為終結符
{
int flag_exist=0;
for(int p=0; p<follow_set[follow_vn_num].vt_len; p++) //判斷該終結符是否已經在非終結符A的follow集中
{
if (follow_set[follow_vn_num].vt[p]==gra_list[i].body[q+1])
{
flag_exist=1;
break;
}
}
if(flag_exist==0) //不在,加到非終結符A的follow集中
{
follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=gra_list[i].body[q+1];
follow_set[follow_vn_num].vt_len++;
}
break;
}
else //為非終結符B
{
int n;
for (n=0; n<first_set_num; n++) //找到其在first集中的位置
if(first_set[n].vn==gra_list[i].body[q+1])
break;
for (int m=0; m<first_set[n].vt_len; m++) //把所有非終結符B的first集中的元素(出去空)加到非終結符A的follow集中
{
int flag_exist=0;
for(int p=0; p<follow_set[follow_vn_num].vt_len; p++) //判斷該終結符是否已經在非終結符A的follow集中
{
if (follow_set[follow_vn_num].vt[p]==first_set[n].vt[m])
{
flag_exist=1;
break;
}
}
if ((first_set[n].vt[m]!=vtset[empty_position].code)&&(flag_exist==0)) //不在且該該終結符不為空,加到非終結符A的follow集中
{
follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=first_set[n].vt[m];
follow_set[follow_vn_num].vt_len++;
}
}
if (first_set[n].flag_empty==1) //如果終結符B的first集中含有空,則繼續看該文法句子右部的下一個符號
continue;
else //如果終結符B的first集中無空,找下一個該句子中下一個非終結符A
break;
}
}
if (q>=gra_list[i].body_len-1) //如果到了句子右部的尾部,說明非終結符A在該句子的尾部或A后的符號都可空
{
int r;
for (r=0; r<follow_set_num; r++) //找到該句子左部的非終結符D在follow集中的位置
if (follow_set[r].vn == gra_list[i].head)
break;
if((follow_set[r].vn!=follow_set[follow_vn_num].vn)&&(follow_set[r].flag_cla==0)) //如果D與A不等,且D的follow集合未計算過,遞歸計算D的follow集
cal_follow(r);
if (follow_set[r].flag_cla==1) //如果D的follow集計算過,把D的follow集中的元素付給A的follow集
{
int s;
for (s=0; s<follow_set[r].vt_len;s++)
{
int p;
int flag_exist=0;
for(p=0; p<follow_set[follow_vn_num].vt_len; p++) //判斷A的follow集中是否已經存在D的follow集中的元素
{
if (follow_set[follow_vn_num].vt[p]==follow_set[r].vt[s])
{
flag_exist=1;
break;
}
}
if (flag_exist==0) //不存在,復制
{
follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=follow_set[r].vt[s];
follow_set[follow_vn_num].vt_len++;
}
}
}
}
}
}
}
follow_set[follow_vn_num].flag_cla=1; //當前非終結符A的follow集合求完后,置已經求過標志為1
}
//函數:輸出follow集
void output_follow_set()
{
printf("follow set:\n------------------------------\n");
for (int i=0; i<follow_set_num; i++)
{
printf("% s->", vset[-follow_set[i].vn-1].sym);
for (int j=0; j<follow_set[i].vt_len; j++)
{
if(follow_set[i].vt[j]==END_SYM)//#
printf("# ");
else
printf("%s ",vtset[follow_set[i].vt[j]-1].sym);
}
printf("\n");
}
printf("==============================\n");
}
//函數:構造分析表
void construct_analyse_table()
{
int count=0;
for(int s=0; s<vtset_num; s++) //構建用于分析表的終結符集合,去除空,加入#,其中#符的編碼為0
{
int flag=0;
if(s!=empty_position)
{
if(s!=vtset_num-1)
{
strcpy(vtset_for_ana[count].sym,vtset[s].sym);
vtset_for_ana[count].code=vtset[s].code;
}
else
{
vtset_for_ana[count].sym[0]='#';
vtset_for_ana[count].sym[1]='\0';
vtset_for_ana[count].code=END_SYM;
}
flag=1;
}
if(flag==1)
count++;
}
vtset_for_ana_num=count;
row_num = vset_num; //確定分析表的行列
col_num = vtset_for_ana_num;
for(int r=0; r<row_num; r++) //初始化分析表
{
for(int j=0; j<col_num; j++)
{
analyse_table[r][j].flag=0;
analyse_table[r][j].body_len=0;
}
}
int tmp_row; //臨時行列變量,表示分析表行列
int tmp_col;
for(int i=0; i<gra_lis_num; i++) //對文法的每條句子S
{
int k;
for(k=0; k<vset_num; k++) //找到其左部非終結符在非終結符集合中的位置
if(gra_list[i].head==vset[k].code)
break;
tmp_row=k; //把其位置付給臨時行變量
int flag=0;
for(int j=0; j<gra_list[i].first_len; j++) //對應每條句子的first集中的每個元素
{
if(gra_list[i].first[j]==vtset[empty_position].code) //如果為空,標志置1
flag=1;
else //不為空
{
int l;
for(l=0; l<vtset_for_ana_num; l++) //找到其在分析表終結符集合中的位置
{
if(gra_list[i].first[j]==vtset_for_ana[l].code)
break;
}
tmp_col=l; //把其在分析表終結符集合中的位置付給臨時列變量
analyse_table[tmp_row][tmp_col].head=gra_list[i].head; //把該句子S存儲到分析表的對應行列中,并置表項存在標志為1
analyse_table[tmp_row][tmp_col].flag=1;
for(int m=0; m<gra_list[i].body_len; m++)
{
analyse_table[tmp_row][tmp_col].body[analyse_table[tmp_row][tmp_col].body_len]=gra_list[i].body[m];
analyse_table[tmp_row][tmp_col].body_len++;
}
}
}
if(flag==1) //如果該句子的first集中有空
{
int j;
for(j=0; j<follow_set_num; j++) //找到該句子左部非終結符A在follow集中的位置
if(gra_list[i].head==follow_set[j].vn)
break;
int m; //把該句子左部非終結符在follow集中的位置付給行臨時變量
for(m=0; m<follow_set[j].vt_len; m++) //對非終結符A的follow集中的每個元素a
{
int l;
for(l=0; l<vtset_for_ana_num; l++) //找到a在分析表非終結符集合中的位置
if(follow_set[j].vt[m]==vtset_for_ana[l].code)
break;
tmp_col=l; //把a在分析表非終結符集合中的位置付給臨時列變量
analyse_table[tmp_row][tmp_col].head=gra_list[i].head; //把該句子S存儲到分析表的對應行列中,并置表項存在標志為1
analyse_table[tmp_row][tmp_col].flag=1;
for(int n=0; n<gra_list[i].body_len; n++)
{
analyse_table[tmp_row][tmp_col].body[analyse_table[tmp_row][tmp_col].body_len]=gra_list[i].body[n];
analyse_table[tmp_row][tmp_col].body_len++;
}
}
}
}
}
//函數:輸出分析表到文件
void output_analyse_table()
{
if ((afp = fopen("Ana_table.txt","w"))==NULL) //打開要輸出到的文件
{
printf("open file:vsetFile error.\n");
exit(0);
}
for(int r=0; r<col_num; r++) //輸出分析表終結符
{
if(vtset_for_ana[r].code==0)
fprintf(afp," # ");
else
fprintf(afp," %4s ",vtset_for_ana[vtset_for_ana[r].code-1].sym);
}
fprintf(afp,"\n");
for(int i=0; i<row_num; i++) //每一行
{
fprintf(afp,"%5s ",vset[-vset[i].code-1].sym); //輸出分析表非終結符
for(int j=0; j<col_num; j++) //該行的每一列
{
if(analyse_table[i][j].flag==1) //如果表項存在
{
fprintf(afp,"%4s->",vset[-analyse_table[i][j].head-1].sym); //輸出句子的左部
int k;
for(k=0; k<analyse_table[i][j].body_len; k++) //輸出句子的右部
{
if(analyse_table[i][j].body[k]<0) //如果是非終結符
fprintf(afp,"%4s ",vset[-analyse_table[i][j].body[k]-1].sym);
else //終結符
fprintf(afp,"%4s ",vtset[analyse_table[i][j].body[k]-1].sym);
}
for(; k<MAX_GRA_BODY_LEN; k++) //填補空白
fprintf(afp," ");
}
else
fprintf(afp," "); //填補空白
}
fprintf(afp,"\n");
}
fclose(afp);
}
//函數:分析給定的句型
void analyse()
{
top=0;
analyse_stack[top++]=END_SYM;//把#壓入棧中
analyse_stack[top++]=-1; //把開始符號壓入棧中
int senindex=0;
int tmp_vn,tmp_vt; //臨時終結符,非終結符
int tmp_row,tmp_col; //臨時行,列變量
printf("analyse sequence:\n------------------------------\n");
while(analyse_stack[top-1]!=END_SYM) //如果棧不為空
{
if(analyse_stack[top-1]>=0) //如果棧頂元素為終結符
{
for(int r=0; r<top; r++) //輸出當前棧中符號
{
if(analyse_stack[r]==END_SYM)
printf("# ");
else if(analyse_stack[r]<0)
printf("%s ",vset[-analyse_stack[r]-1].sym);
else
printf("%s ",vtset[analyse_stack[r]-1].sym);
}
printf("\n");
if(analyse_stack[top-1]==vtset[empty_position].code) //如果其為空,彈出
top--;
else if(analyse_stack[top-1]==sentence[senindex].code)//如果其和輸入指針指向的輸入符號相同
{
top--; //彈出
senindex++; //輸入指針指向下一個輸入符號
}
else //否則,錯誤退出
{
printf("error !!\n");
exit(0);
}
}
else //棧頂元素為非終結符
{
for(int r=0; r<top; r++) //輸出當前棧中符號
{
if(analyse_stack[r]==END_SYM)
printf("# ");
else if(analyse_stack[r]<0)
printf("%s ",vset[-analyse_stack[r]-1].sym);
else
printf("%s ",vtset[analyse_stack[r]-1].sym);
}
tmp_vn=analyse_stack[top-1];
tmp_vt=sentence[senindex].code;
int i;
for(i=0; i<vset_num; i++) //找到其在非終結符集合中的位置
if(tmp_vn==vset[i].code)
break;
tmp_row=i; //把其在非終結符集合中的位置付給臨時行變量
int j;
for(j=0; j<vtset_for_ana_num; j++) //找到輸入指針指向的終結符在終結符集合中的位置
{
if(tmp_vt==vtset_for_ana[j].code)
break;
}
tmp_col=j; //把輸入指針指向的終結符在終結符集合中的位置付給臨時列變量
if(analyse_table[tmp_row][tmp_col].flag==1) //如果臨時行變量和臨時列變量對應的表項存在
{
top--; //彈出棧頂元素
int m=analyse_table[tmp_row][tmp_col].body_len;
for(; m>0; 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<analyse_table[tmp_row][tmp_col].body_len; k++)
{
if(analyse_table[tmp_row][tmp_col].body[k]<0) //非終結符
printf("%s ",vset[-analyse_table[tmp_row][tmp_col].body[k]-1].sym);
else //終結符
printf("%s ",vtset[analyse_table[tmp_row][tmp_col].body[k]-1].sym);
}
printf("\n");
}
else //否則,出錯退出
{
printf("error:analyse table is empty\n");
exit(0);
}
}
}
printf("==============================\n");
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -