预测分析 编译原理 实验报告

#include "LL1Analysis.h" bool IsInSet(char *set, int size, char ele) { int i = 0; for (int i = 0; i < size; i ++) { if (ele == set[i]) { return true; } } return false; }//IsInSet bool AllFinishYet(bool finishFlag[], int len) { int i = 0; for (i = 0; i < len; i ++) { if (finishFlag[i] == false) { return false; } } return true; }//AllFinishYet int GetID(char **set, int len, char ele) { int i = 0; for (i = 0; i < len; i ++) { if (ele == set[i][0]) { return i; } } }//GetID void GetAlternate(char *G, CharList *list) { int i = 4; CharList *p = NULL; p = list; list->ele = G[3]; while (G[i] != '\n') { if (G[i] == '|') { CharList *tempList = (CharList *)malloc(sizeof(CharList)); tempList->ele = G[++i]; tempList->next = NULL; p->next = tempList; p = p->next; } i ++; } }//GetAlternate bool FIRSTFinishYet(CharList *alternateList, char *Vn, int size) { CharList *p = NULL; if (IsInSet(Vn, size, alternateList->ele) == true) { return false; } p = alternateList; while (p->next != NULL) { if (IsInSet(Vn, size, p->ele) == true) { return false; } p = p->next; } return true; }//FIRSTFinishYet void InsertEle(CharList* list, char ele) { CharList *p = NULL; p = list; while (p->next != NULL) { p = p->next; } CharList *temp = (CharList *)malloc(sizeof(CharList)); temp->ele = ele; temp->next = NULL; p->next = temp; /*free(temp); temp = NULL;*/ }//InsertEle void PutIntoSet(char *set,CharList *list) { CharList *p = NULL; int i = 0; p = list; set[i++] = p->ele; while (p->next != NULL) { p = p->next; set[i++] = p->ele; } }//PutIntoSet void GetFIRST(char **G, int GNum, int GMaxLen, char **FIRST, int VnSize, int VtSize, char Vn[], char Vt[]) { int i = 0; int j = 0; int id = 0; bool *finishFlag = (bool *)malloc(sizeof(bool) * VnSize); CharList **alternateList = (CharList **)malloc(sizeof(CharList *) * VnSize); CharList *pA = NULL; for (i = 0; i < VnSize; i ++) { alternateList[i] = (CharList *)malloc(sizeof(CharList)); alternateList[i]->next = NULL; GetAlternate(G[i], alternateList[i]); } for (i = 0; i < VnSize; i ++) { finishFlag[i] = false; } for (i = 0; i < VnSize; i ++) { FIRST[i][0] = G[i][0]; } for (i = 0; i < VnSize; i ++) { finishFlag[i] = FIRSTFinishYet(alternateList[i], Vn, VnSize); } while (AllFinishYet(finishFlag, VnSize) == false) { for (i = 0; i < VnSize; i ++) { if (finishFlag[i] == false) { id = GetID(FIRST, VnSize, alternateList[i]->ele); pA = alternateList[id]; if (IsInSet(Vn, VnSize, pA->ele) == true) { alternateList[i]->ele = pA->ele; } else { alternateList[i]->ele = pA->ele; while (pA->next != NULL) { pA = pA->next; InsertEle(alternateList[i], pA->ele); } }// if else }//if }// for for (j = 0; j < VnSize; j ++) { if (finishFlag[j] == false) { finishFlag[j] = FIRSTFinishYet(alternateList[j], Vn, VnSize); } }//for }//while for (i = 0; i < VnSize; i ++) { PutIntoSet(FIRST[i], alternateList[i]); } }//GetFIRST bool HaveEpsilon(char *set) { int i = 0; while (set[i] != 0) { if (set[i] == '&') { return true; } } return false; } void GetFOLLOW(char **G, int GNum, int GMaxLen, char **FIRST, char **FOLLOW, int VnSize, int VtSize, char Vn[], char Vt[], char start) { int i = 0; int j = 0; CharList **alternateList = (CharList **)malloc(sizeof(CharList *) * VnSize); for (i = 0; i < VnSize; i ++) { FOLLOW[i][0] = G[i][0]; } for (i = 0; i < VnSize; i ++) { alternateList[i] = (CharList *)malloc(sizeof(CharList)); alternateList[i]->next = NULL; } alternateList[GetID(FOLLOW, VnSize, start)]->ele = '#';//算法第一步 for (i = 0; i < GNum; i ++) { if (IsInSet(G[i], GMaxLen, FOLLOW[0][0]) == true) { } } printf("%c \n", alternateList[0]->ele); } void SetFOLLOW(char **FOLLOW) { FOLLOW[0] = ")#\0"; FOLLOW[1] = ")#\0"; FOLLOW[2] = "+)#\0"; FOLLOW[3] = "+)#\0"; FOLLOW[4] = "*+)#\0"; } void FillAnalysisMFirst(char ***analysisM, int i, int j, char **G, int GMaxLen, char Vt[]) { int index = 0; int aIndex = 0; char temp = 0; analysisM[i][j][0] = G[i][0]; analysisM[i][j][1] = '-'; analysisM[i][j][2] = '>'; index = 2; aIndex = 3; if ((IsInSet(G[i], GMaxLen, '|')) == true) { while (G[i][++index] != Vt[j]) {} temp = G[i][index]; while ((temp != '|') && (temp != 0) && (index < GMaxLen) && (temp != '\n')) { analysisM[i][j][aIndex] = temp; index++; aIndex++; temp = G[i][index]; } analysisM[i][j][aIndex] = '\n'; } else { temp = G[i][++index]; while ((temp != 0) && (index < GMaxLen) && (temp != '\n')) { analysisM[i][j][aIndex++] = temp; index++; temp = G[i][index]; } analysisM[i][j][aIndex] = '\n'; } } void FillAnalysisMSecond(char ***analysisM, char **FOLLOW, int i, char Vt[], char n) { int j = -1; int id = -1; char temp = 0; while (FOLLOW[i][++j] != '\0') { id = -1; temp = FOLLOW[i][j]; if (temp == '#') { temp = '&'; } while (temp != Vt[++id]); analysisM[i][id][0] = n; analysisM[i][id][1] = '-'; analysisM[i][id][2] = '>'; analysisM[i][id][3] = '&'; analysisM[i][id][4] = '\n'; } } void GetAnalysisChartM(char ***analysisM, char **G, int GNum, int GMaxLen, char **FIRST, char **FOLLOW, int VnSize, int VtSize, char Vn[], char Vt[]) { int i = 0; int j = 0; for (i = 0; i < VnSize; i ++) { for (j = 0; j < VtSize; j ++) { if (Vt[j] != '&') { if ( (IsInSet(FIRST[i], VtSize, Vt[j])) == true ) { FillAnalysisMFirst(analysisM, i, j, G, GMaxLen, Vt); } } } } for (i = 0; i < VnSize; i++) { if (IsInSet(FIRST[i], VtSize, '&') == true) { FillAnalysisMSecond(analysisM, FOLLOW, i, Vt, G[i][0]); } } for (i = 0; i < VnSize; i++) { for (j = 0; j < VtSize; j++) { if ((analysisM[i][j][0] == '\n') || (analysisM[i][j][0] == '\0')) { if (Vt[j] == '&') { if (IsInSet(FOLLOW[i], VtSize, '#') == true) { analysisM[i][j][0] = 's'; analysisM[i][j][1] = 'y'; analysisM[i][j][2] = 'n'; analysisM[i][j][3] = 'c'; analysisM[i][j][4] = 'h'; analysisM[i][j][5] = '\n'; } } else { if ((IsInSet(FIRST[i], VtSize, Vt[j]) == true) || (IsInSet(FOLLOW[i], VtSize, Vt[j]) == true)) { analysisM[i][j][0] = 's'; analysisM[i][j][1] = 'y'; analysisM[i][j][2] = 'n'; analysisM[i][j][3] = 'c'; analysisM[i][j][4] = 'h'; analysisM[i][j][5] = '\n'; } } } } } } void Push(char *STACK, char ele) { int i = -1; while (STACK[++i] != '\0') { if (i == 99) { printf("STACK overflow! exit!\n"); exit(0); } } STACK[i] = ele; } char Pop(char *STACK) { int i = -1; char temp = 0; if (STACK[0] == '\0') { printf("The STACK is empty!\n"); return '\0'; } while (STACK[++i] != '\0') { if (i == 99) { temp = STACK[99]; STACK[99] = '\0'; return temp; } } temp = STACK[i - 1]; STACK[i - 1] = '\0'; return temp; } char GetTop(char *STACK) { int i = -1; if (STACK[0] == '\0') { printf("The STACK is empty!\n"); return '\0'; } while (STACK[++i] != '\0') { if (i == 99) { return STACK[99]; } } return STACK[i - 1]; } void error() {} void ShowSteps(int step, char *STACK, char *str, int strIndex, char *set) { char info[80] = {0}; int i = -1; int index = -1; strIndex --; info[++index] = ' '; info[++index] = ' '; info[++index] = ' '; if (step < 10)