?? step2_clae_first_follow_select.c
字號:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DEBUG 1
#define MAX_SETENCE_LEN 2000
#define MAX_GRAM_LEN 255
#define MAX_ELE_NUM 40
#define MAX_GRAM_ELE_NUM 300
//--IO FILES--
FILE* grammerFile,* setenceFile;
char* grammerFileName="grammer.txt";
char* setenceFileName="setence.txt";
FILE* testFile;
char* testFileName="outputData.txt";
//---GLOBAL VARIABLES---
//--GRAMMER STRUCT --
typedef struct
{
char mSetence[MAX_GRAM_LEN];
}grammerElement;
grammerElement GrammerSet[MAX_GRAM_ELE_NUM];
grammerElement TmpGrammerSet[MAX_GRAM_ELE_NUM];
typedef struct
{
int len;
char ele[MAX_ELE_NUM];
}simpleGroup;
simpleGroup groupFirst[MAX_ELE_NUM];
simpleGroup groupFollow[MAX_ELE_NUM];
simpleGroup groupSelect[MAX_GRAM_LEN];
char analyseTable[MAX_ELE_NUM][MAX_ELE_NUM][MAX_GRAM_LEN];
char parseSetence[MAX_SETENCE_LEN];
int grammerNum;
char VTSet[MAX_ELE_NUM];
char VNSet[MAX_ELE_NUM];
int VNProduceZ[MAX_ELE_NUM];
int vtSetLen;
int vnSetLen;
void readInSetence();
void readInGrammer();
//---1. ELEMINATE LEFT RECURSIVE--
void outputGrammer();
void outputTmpGrammer(int len);
int hasLeftRecursive();
int eleminateLeftRecursive();
void bubbleSort();
//2.CAL INSIDUCE E,FIRST SET,FOLLOW SET,SELECT
void cal_ProductE();
void cal_first_set();
void cal_follow_set();
void cal_select_set();
int checkLL1_consTable();
//3.CONSTRUCT ANALYSE DIAGRAM,YOU CAN SAVE THIS DIAGRAM FOR LATER USE
//4.PARSE THE SETENCE.
void parsingSetence();
void topologySort(int** inMatrix,int* topSeqArr,int row,int col);
//STARTED SIGN
char startedSign;
void main()
{
int i;
//0.OPEN FILE ,READ IN SETENCE ,READING SETENCE AND REGISTER DATA.
if((grammerFile=fopen(grammerFileName,"rb"))==NULL)
{
fprintf(stderr,"open file:grammerFile error.\n");
return;
}
if((setenceFile=fopen(setenceFileName,"rb"))==NULL)
{
fprintf(stderr,"open file:setenceFile error.\n");
return;
}
if((testFile=fopen(testFileName,"wb"))==NULL)
{
fprintf(stderr,"open file:testFile error.\n");
return;
}
readInSetence();
readInGrammer();
printf("input grammer.\n");
outputGrammer();
bubbleSort();
printf("after bubble sort.\n");
outputGrammer();
fclose(grammerFile);
fclose(setenceFile);
//1.ELEMINATE LEFT RECURSIVE
if(hasLeftRecursive())
{
if(eleminateLeftRecursive()==-1)
return;
else
{
printf("\nafter eleminate left recursiv.\n");
outputGrammer();
}
}
//ADDED CODE
bubbleSort();
printf("after bubble sort.\n");
outputGrammer();
for(i=0;i<grammerNum;i++)
strcpy(TmpGrammerSet[i].mSetence,GrammerSet[i].mSetence);
//END OF ADDED CODE
//2.CAL INSIDUCE E,FIRST SET,FOLLOW SET,SELECT
cal_ProductE(); //TmpGrammerSet
cal_first_set(); //GrammerSet
cal_follow_set(); //GrammerSet
cal_select_set(); //GrammerSet
//3.CONSTRUCT ANALYSE DIAGRAM,YOU CAN SAVE THIS DIAGRAM FOR LATER USE
if(checkLL1_consTable())
{
//4.PARSE THE SETENCE.
parsingSetence();
}
fclose(testFile);
getchar();
}
void readInSetence()
{
fscanf(setenceFile,"%s\r\n",&parseSetence);
}
void readInGrammer()
{
char tmpChar;
char tmpStr[MAX_GRAM_LEN];
int tmpIndex;
int vtIndex,vnIndex;
int i,j;
tmpIndex=0;vtIndex=0;vnIndex=0;
fscanf(grammerFile,"%c\r\n",&startedSign);
while(!feof(grammerFile))
{
if(fscanf(grammerFile,"%c->%s\r\n",&tmpChar,&tmpStr)!=2)
break;
GrammerSet[tmpIndex].mSetence[0]=tmpChar;
GrammerSet[tmpIndex].mSetence[1]='\0';
strcat(GrammerSet[tmpIndex].mSetence,tmpStr);
tmpIndex++;
for(i=0;i<vnIndex;i++)
if(tmpChar==VNSet[i])
break;
if(i==vnIndex)//new VT SIGN;
{
VNSet[vnIndex]=tmpChar;
vnIndex++;
}
i=0;
while(tmpStr[i]!='\0')
{
if(!(tmpStr[i]>=65&&tmpStr[i]<=90))//NOT UPCASE CHAR(NOT Vn)
{
for(j=0;j<vtIndex;j++)
if(tmpStr[i]==VTSet[j])
break;
if(j==vtIndex)//new VT SIGN;
{
VTSet[vtIndex]=tmpStr[i];
vtIndex++;
}
}
i++;
}
}
VTSet[vtIndex]='\0';
VNSet[vnIndex]='\0';
vtSetLen=vtIndex;
vnSetLen=vnIndex;
grammerNum=tmpIndex;
}
void outputGrammer()
{
int i;
for(i=0;i<grammerNum;i++)
fprintf(stdout,"%s\n",GrammerSet[i].mSetence);
fprintf(stdout,"%s %d\n",VTSet,vtSetLen);
fprintf(stdout,"%s %d\n",VNSet,vnSetLen);
}
void outputTmpGrammer(int len)
{
int i;
for(i=0;i<len;i++)
fprintf(stdout,"%s\n",TmpGrammerSet[i].mSetence);
}
void bubbleSort()
{
int i,j;
char tmpChar;
char tmpStr[MAX_GRAM_LEN];
int flag;
//SORT VT
flag=0;
for(i=0;i<vtSetLen-1;i++)
{
for(j=0;j<vtSetLen-i-1;j++)
if(VTSet[j]>VTSet[j+1])
{
tmpChar=VTSet[j];
VTSet[j]=VTSet[j+1];
VTSet[j+1]=tmpChar;
flag=1;
}
if(flag==0)break;
}
//SORT VN
flag=0;
for(i=0;i<vnSetLen-1;i++)
{
for(j=0;j<vnSetLen-i-1;j++)//-->ADD ON startedSign's priority sort.
if((VNSet[j]>VNSet[j+1]||(VNSet[j]!=startedSign&&VNSet[j+1]==startedSign))&&VNSet[j]!=startedSign)
{
tmpChar=VNSet[j];
VNSet[j]=VNSet[j+1];
VNSet[j+1]=tmpChar;
flag=1;
}
if(flag==0)break;
}
//SORT GRAMMER
flag=0;
for(i=0;i<grammerNum-1;i++)
{
for(j=0;j<grammerNum-i-1;j++)
if((GrammerSet[j].mSetence[0]>GrammerSet[j+1].mSetence[0]||(GrammerSet[j].mSetence[0]!=startedSign&&GrammerSet[j+1].mSetence[0]==startedSign))&&GrammerSet[j].mSetence[0]!=startedSign)
{
strcpy(tmpStr,GrammerSet[j].mSetence);
strcpy(GrammerSet[j].mSetence,GrammerSet[j+1].mSetence);
strcpy(GrammerSet[j+1].mSetence,tmpStr);
flag=1;
}
if(flag==0)break;
}
}
int hasLeftRecursive()
{
int i,j;
for(i=0;i<grammerNum;i++)
{
if(GrammerSet[i].mSetence[0]==GrammerSet[i].mSetence[1])
break;
}
if(i<grammerNum)
{
printf("===grammer has left recursive.===\n");
return 1;
}
else
{
printf("===grammer has no left recursive===\n");
for(j=0;j<grammerNum;j++)
strcpy(TmpGrammerSet[j].mSetence,GrammerSet[j].mSetence);
return 0;
}
}
int eleminateLeftRecursive()
{
int i,j,k,l,m,n;
int GroupL[MAX_ELE_NUM],GroupT[MAX_ELE_NUM];
int GroupLLen,GroupTLen;
int GrammerSetIndex,preGrammerSetIndex;
char tmpNewSign;
int tmpIndex;
int dealed[MAX_GRAM_LEN];
int tmpVNLen;
int preVNSetLen;
char tweenGrammerSet[MAX_GRAM_ELE_NUM][MAX_GRAM_LEN];
int tweenIndex;//tweenArrLen;
//INIT
GrammerSetIndex=0;
preGrammerSetIndex=0;
tweenIndex=0;
for(i=0;i<MAX_GRAM_LEN;i++)
dealed[i]=0;
preVNSetLen=vnSetLen;
for(i=0;i<preVNSetLen;i++)//->Correct: for(i=0;i<vnSetLen;i++)
{
//To cal the Ai-> group len;
tmpVNLen=0;
for(j=preGrammerSetIndex;j<grammerNum;j++)
{
if(GrammerSet[j].mSetence[0]!=VNSet[i])
break;
else
tmpVNLen++;
}
//Replace Aj in all Ai->AjBeta
tweenIndex=0;
for(j=0;j<i;j++)
{
for(k=preGrammerSetIndex;k<grammerNum;k++)
{
//Exit control
if(GrammerSet[k].mSetence[0]!=VNSet[i])
break;
// if Has Ai->AjBeta ASSERT GrammerSet[k].mSetence[0]==VNSet[i]
if(GrammerSet[k].mSetence[1]==VNSet[j])
{
for(l=0;l<GrammerSetIndex;l++)
if(TmpGrammerSet[l].mSetence[0]==VNSet[j])
break;
//ASSERTION
if(l==GrammerSetIndex)
{
printf("error in eleminate l:replace part.\n");
return -1;
}
while(l<GrammerSetIndex&&TmpGrammerSet[l].mSetence[0]==VNSet[j])
{
//VNSet[i]->TmpGrammerSet[l].mSetence[1..end]+GrammerSet[i].mSetence[2..end];
tweenGrammerSet[tweenIndex][0]=VNSet[i];
m=1;
while(TmpGrammerSet[l].mSetence[m]!='\0')
{
tweenGrammerSet[tweenIndex][m]=TmpGrammerSet[l].mSetence[m];
m++;
}
n=2;
while(GrammerSet[k].mSetence[n]!='\0')
{
//->COREECT:GrammerSet[tmpIndex] -> GrammerSet[k]
tweenGrammerSet[tweenIndex][m]=GrammerSet[k].mSetence[n];
m++;
n++;
}
tweenGrammerSet[tweenIndex][m]='\0';
tweenIndex++;
l++; //->error correct,forget.
}
dealed[k]=1;
}
}
}
//-->ADDED : TO ELIMINATE THE NEW LEFT SELF RECURSIVE
//NO NEED ,USE A TWEEN STR DB IS OK
//if has Ai->AiBeta Ai->c,Replace it with:
//Ai->cAi' Ai'->BetaAi'|z;
//0 GET GroupL,GroupLLen,GroupT,GroupTLen;
//starting pos
for(k=preGrammerSetIndex;k<grammerNum;k++)//ASSUME GRAMMER SET HAS BEEN SORTED
{
//end pos
if(GrammerSet[k].mSetence[0]!=VNSet[i])
break;
if(!dealed[k])
{
strcpy(tweenGrammerSet[tweenIndex],GrammerSet[k].mSetence);
tweenIndex++;
}
}
GroupLLen=0;
GroupTLen=0;
for(k=0;k<tweenIndex;k++)//ASSUME GRAMMER SET HAS BEEN SORTED
{
//-->CORRECT :tweenGrammer[tweenIndex][0]
if(tweenGrammerSet[k][0]==tweenGrammerSet[k][1]) //GROUP L
{
GroupL[GroupLLen]=k;
GroupLLen++;
}
else //GROUP T
{
GroupT[GroupTLen]=k;
GroupTLen++;
}
}
if(GroupTLen==0)
{
printf("abort: illegal grammer.\n");
return -1;
}
if(GroupLLen>0)
{
//1.FIND NEW VN SIGN
for(k=65;k<=90;k++)
{
for(l=0;l<vnSetLen;l++)
{
if(VNSet[l]==k)
break;
}
if(l==vnSetLen)// k is a new ascii sign.
{
VNSet[vnSetLen]=k;
tmpNewSign=k;
vnSetLen++;
break; //-->CORRECT FORGET THIS
}
}
if(k==91)
{
printf("in ele left recursive,not enough new sign\n");
return -1;
}
//2.Replace : A->Ab ,A->a ==>A->aD ,D->bD ,D->z
//2.0 A->aD
for(k=0;k<GroupTLen;k++)
{ //VNSet[i]->GrammerSet[GroupT[k]].mSetemce[1 to n]+newSign;
TmpGrammerSet[GrammerSetIndex].mSetence[0]=VNSet[i];
tmpIndex=1;
while(tweenGrammerSet[GroupT[k]][tmpIndex]!='\0')
{
TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex]=tweenGrammerSet[GroupT[k]][tmpIndex];
tmpIndex++;
}
TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex]=tmpNewSign;
TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex+1]='\0';
GrammerSetIndex++;
}
//2.1 D->bD
for(k=0;k<GroupLLen;k++)
{
//NewSign->GrammerSet[GroupL[k]].mSetence[2 to n]+NewSign
TmpGrammerSet[GrammerSetIndex].mSetence[0]=tmpNewSign;
tmpIndex=2;
while(tweenGrammerSet[GroupL[k]][tmpIndex]!='\0')
{
TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex-1]=tweenGrammerSet[GroupL[k]][tmpIndex];
tmpIndex++;
}
TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex-1]=tmpNewSign;
TmpGrammerSet[GrammerSetIndex].mSetence[tmpIndex]='\0';
GrammerSetIndex++;
}
//2.2 D->z
TmpGrammerSet[GrammerSetIndex].mSetence[0]=tmpNewSign;
TmpGrammerSet[GrammerSetIndex].mSetence[1]='z';
TmpGrammerSet[GrammerSetIndex].mSetence[2]='\0';
GrammerSetIndex++;
}
else
{
//ASSERT GroupLLen==0
for(k=0;k<GroupTLen;k++)
{
strcpy(TmpGrammerSet[GrammerSetIndex].mSetence,tweenGrammerSet[k]);
GrammerSetIndex++;
}
}
if(DEBUG)
{
printf("\n====\n");
outputTmpGrammer(GrammerSetIndex);
}
//-->CORRECT preGrammerSetIndex+=GroupLLen+GroupTLen;
preGrammerSetIndex+=tmpVNLen;
}
//ADDED: IF Pre Grammer can't =>e
//After left recursive ,it should be can
for(i=0;i<vtSetLen;i++)
{
if(VTSet[i]=='z')
{
break;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -