#include<stdio.h>#include<stdlib.h>#include<string.h>#define HIGHER 1#define LOWER -1#define EQUAL 0#define TRUE 1#define FALSE 0#define OPER_NUM 50 //默认算符数目#define VN_NUM 50 //默认非终结符数目#define MAX_BUFFER 128 //每行输入行最大长度#define MAX_GRA_NUM 20 //最大文法数目#define EMPTY -2 //算符优先表初始值，表示这对算符没有优先关系#define STACK_SIZE 64typedef struct{char c; //非终极符符号int firstvt[OPER_NUM]; //firstvt集，保存算符在oper_list中的下标int fir_n,last_n;int lastvt[OPER_NUM];}vn_t;int prior_table[OPER_NUM][OPER_NUM];char oper_list[OPER_NUM];int oper_num = 0;vn_t vn_list[VN_NUM];int vn_num = 0;char *grammar[MAX_GRA_NUM][2];int gra_num = 0;char start_vn;char stack[STACK_SIZE];int top = 0;void get_input(char *buf);int buf_deal(char* buf);void get_FIRVT_LASTVT(int vn_n);int create_table();void init_table();int analyze(char *sentence);void display_table();void display_fir_lastvt();int get_oper(char c); //得到算符c的数组下标没有返回-1int get_vn(char c); //得到非终结符c的数组下标，没有返回-1int is_vn(char a){return (('A'<=a&&a<='Z')?1:0);}int get_oper(char c){int i;for(i = 0; i < oper_num; ++i)if(oper_list[i] == c)return i;return -1;}int get_vn(char c){int i;for(i = 0; i < vn_num; ++i)if(vn_list[i].c == c)return i;return -1;}char reduce(int start, int end, int size) //规约{char *tar, *g, t1, t2, left;int i, j =0, gi, ti, cn = 0;int same;tar = (char *)malloc(sizeof(char)*MAX_BUFFER);if(!tar){printf("Allocation fails.\n");exit(-1);}for(i = start; i <= end; ++i) //将此最左素短语的终结符存入tar字符串{if(!is_vn(stack[i]))tar[j++] = stack[i];}tar[j++] = '\0';for(i = 0; i < gra_num; ++i){g = grammar[i][1];gi = 0;ti = 0;same = FALSE;t1 = g[gi];t2 = tar[ti];while (t1 != '\0'){if(t2 == '\0' && !is_vn(t1)){same = FALSE;break;}if(!is_vn(t1)){if(t1 != t2){same = FALSE;break;}t2 = tar[++ti];same = TRUE;}t1= g[++gi];}if(same && t2 == '\0')break;}if(i == gra_num){printf("无法找到相应文法！\n");return FALSE;}left = grammar[i][0][0];return vn_list[get_vn(left)].c;}int analyze(char *sentence){char r, c,new_vn;int i = 0, k = 0, j, pi, printi = 1, cou = 1; //i是sentence[]和stack[]的索引int r_index, s_index, pre_index;printf("\n\n规约过程如下表所示：\n");printf("--------------------------------------\n");stack[top++] = '#';printf("序号\t符号栈\t最左素短语\t规约\t\n");do{r = sentence[i++];if((r_index = get_oper(r)) == -1){printf("Error : 您输入的字符不在文法定义中！\n");flushall();c = getchar();flushall();return FALSE;}if(!is_vn(stack[k])){j = k;s_index = get_oper(stack[j]);}else{j = k - 1;s_index = get_oper(stack[j]);}while(prior_table[s_index][r_index] == HIGHER){do{pre_index = s_index;if(!is_vn(stack[j-1])){j--;s_index = get_oper(stack[j]);}else{j -= 2;s_index = get_oper(stack[j]);}}while(prior_table[s_index][pre_index] != LOWER);printf(" %d\t", cou++);for(pi = 0; pi < top; ++pi){printf("%c",stack[pi]);}printf(" \t");for(pi = j + 1; pi <= k; ++pi){if (pi == j+1)printf(" %c",stack[pi]);elseprintf("%c",stack[pi]);}if((new_vn = reduce(j + 1, k, k - j)) == 0){return FALSE;}printf("\t\t %c\n",new_vn);k = j + 1; //规约最左素短语stack[k] = new_vn;top = k + 1;}if(prior_table[s_index][r_index] == LOWER || prior_table[s_index][r_index] == EQUAL){stack[++k] = r;top++;}else{printf("Error : 您输入的句型有错误！\n");return FALSE;}}while(r != '#');printf("--------------------------------------\n");return TRUE;}int buf_deal(char *buf){int i = 2,count = 0;char pre = buf[0], now;char *left_g, *right_g, *new_buf;left_g = (char *)malloc(sizeof(char)*2);right_g = (char *)malloc(sizeof(char)*(MAX_BUFFER-2));if(!left_g || !right_g){printf("Allocation fails.\n");exit(-2);}if(is_vn(pre)){if(get_vn(pre) == -1){vn_list[vn_num].c = pre;vn_list[vn_num].fir_n = 0;vn_list[vn_num].last_n = 0;vn_num++;}left_g[count] = pre;count++;left_g[count] = '\0';}elsereturn FALSE;if(buf[1] != '-' || buf[2] != '>')return FALSE;pre = buf[2];count = 0;while((now = buf[++i]) != '\0'){if(now != '|'){right_g[count] = now;count++;if(is_vn(now) && is_vn(pre))return FALSE;if(is_vn(now)){if(get_vn(now) == -1){vn_list[vn_num].c = now;vn_list[vn_num].fir_n = 0;vn_list[vn_num].last_n = 0;vn_num++;}elsecontinue;}else{if(get_oper(now) == -1){oper_list[oper_num] = now;oper_num++;}elsecontinue;}pre = now;}else{right_g[count] = '\0';grammar[gra_num][0] = left_g;grammar[gra_num][1] = right_g;gra_num++;break;}}if(buf[i] == '\0'){right_g[count] = '\0';grammar[gra_num][0] = left_g;grammar[gra_num][1] = right_g;gra_num++;}else{new_buf = (char *)malloc(sizeof(char)*MAX_BUFFER);new_buf[0] = left_g[0];new_buf[1] = '-';new_buf[2] = '>';strcpy(&new_buf[3],&buf[++i]);return buf_deal(new_buf);}return TRUE;}int create_table(){int gi = 0, ti, ni, fi, li, i;char *ng, t,next, next1;int t_index,n_index, n_index1, n_vn, t_vn;vn_t temp;for(gi = 0; gi < gra_num; ++gi ){ng = grammar[gi][1];t = ng[0];ti = 0;t_index = get_oper(t);next = ng[1];ni = 1;n_index = get_oper(next);while(next != '\0'){if(t_index != -1 && n_index != -1){if (prior_table[t_index][n_index] == EMPTY)prior_table[t_index][n_index] = EQUAL;else{printf("%c与%c有多种优先关系！\n",oper_list[t_index],oper_list[n_index]);return FALSE;}}else if(t_index != -1 && n_index == -1 && ng[ni+1] != '\0'){next1 = ng[ni+1];n_index1 = get_oper(next1);if(prior_table[t_index][n_index1] == EMPTY)prior_table[t_index][n_index1] = EQUAL;else{printf("%c与%c有多种优先关系！\n",oper_list[t_index],oper_list[n_index1]);return FALSE;}prior_table[t_index][oper_num - 1] = -3;prior_table[oper_num - 1][n_index1] = -3;}if (t_index != -1 && n_index == -1){n_vn = get_vn(next);temp = vn_list[n_vn];for(fi = 0; fi < temp.fir_n; fi++){if(prior_table[t_index][temp.firstvt[fi]] == EMPTY)prior_table[t_index][temp.firstvt[fi]] = LOWER;else{printf("%c与%c有多种优先关系！\n",oper_list[t_index],oper_list[temp.firstvt[fi]]);return FALSE;}}}else if(t_index == -1 && n_index != -1){n_vn = get_vn(t);temp = vn_list[n_vn];for(fi = 0; fi < st_n; fi++){if(prior_table[stvt[fi]][n_index] == EMPTY)prior_table[stvt[fi]][n_index] = HIGHER;else{printf("%c与%c有多种优先关系！\n",oper_list[fi],oper_list[n_index]);return FALSE;}}}t = ng[++ti];next = ng[++ni];t_index = get_oper(t);n_index = get_oper(next);}}for(i = 0; i < oper_num - 1; ++i){if(prior_table[oper_num - 1][i] != -3)prior_table[oper_num - 1][i] = LOWER;}for(i = 0; i < oper_num - 1; ++i){if(prior_table[i][oper_num - 1] != -3)prior_table[i][oper_num - 1] = HIGHER;}prior_table[oper_num - 1][oper_num - 1] = EQUAL;return TRUE;}void display_fir_lastvt(){int i, j;for (i = 0; i < vn_num; ++i){printf("FIRSTVT\(%c\) = { ", vn_list[i].c);for(j = 0; j < vn_list[i].fir_n; ++j){if (j == vn_list[i].fir_n - 1)printf(" %c ",oper_list[vn_list[i].firstvt[j]]);elseprintf(" %c ,",oper_list[vn_list[i].firstvt[j]]);}printf("}\n");printf("LASTVT\(%c\) = { ", vn_list[i].c);for(j = 0; j < vn_list[i].last_n; ++j){if (j == vn_list[i].last_n - 1)printf(" %c ",oper_list[vn_list[i].lastvt[j]]);elseprintf(" %c ,",oper_list[vn_list[i].lastvt[j]]);}printf("}\n\n");}}void display_table(){int i,j;printf("\n\t算符");for(i = 0; i < oper_num; ++i)printf("\t%c",oper_list[i]);printf("\n");for(i = 0; i < oper_num; ++i){printf("\t%c",oper_list[i]);for(j = 0; j <oper_num; ++j){if(prior_table[i][j] == 1)printf("\t>");else if(prior_table[i][j] == -1)printf("\t<");else if(prior_table[i][j] == 0)printf("\t=");elseprintf("\tNO");}printf("\n");}}void firstvt(int vn){int i, j, t, c_index, v_i, orin, pre = -1;char *ng, c;for(i = 0; i < gra_num; ++i){if (grammar[i][0][0] == vn_list[vn].c){ng = grammar[i][1];c = ng[0];if((c_index = get_oper(c)) != -1){vn_list[vn].firstvt[vn_list[vn].fir_n++] = c_index;continue;}else{v_i = get_vn(c);if(v_i != vn && v_i != pre){if(vn_list[v_i].fir_n == 0 )firstvt(v_i);orin = vn_list[vn].fir_n;vn_list[vn].fir_n += vn_list[v_i].fir_n;t = 0;for(j = orin; j < vn_list[vn].fir_n; ++j ){vn_list[vn].firstvt[j] = vn_list[v_i].firstvt[t++];}}pre = v_i;if(ng[1] != '\0'){vn_list[vn].firstvt[vn_list[vn].fir_n++] = get_oper(ng[1]);}}}}}void lastvt(int vn){int i, j, t, c_index, v_i, orin, ni = 0, pre = -1;char *ng, c;for(i = 0; i < gra_num; ++i){if (grammar[i][0][0] == vn_list[vn].c){ng = grammar[i][1];ni = 0; //每次对新语法搜索时初始化位置。