注：代码生成的项目集规范簇、ACTION GOTO表的顺序可能和课本、教材、参考答案的顺序不同，但这并不影响分析过程的正确性，毕竟机器是按规律办事的😄
主函数已经把功能分的很清晰，代码注释也很详细，如阅读代码，可先在主函数查看，再到子函数逐一查看
演示
演示所用文法和句子
文法
E->E-T
E->T
T->T*F
T->F
F->-F
F->a
待分析句子
a–a*a
(1)根据提示输入文法的个数
(2)输入文法
回车，然后依此输入文法
(3)扩展文法的生成、项目集规范簇的生成、ACTION GOTO表的生成
回车后扩展文法的生成、项目集规范簇的生成、ACTION GOTO表的生成
扩展文法
项目集规范簇
ACTION GOTO表
(3)分析句子
根据提示输入分析串
(4)生成分析过程
输入分析串后回车
思路
其实思路比较简单，只是实现起来较为繁琐。
1.输入文法
2.进行项目集规范簇的构建
（1）采用链表进行生成存储，因为生成个数不确定
（2）采用双重循环，外循环进行In的遍历，内循环进行项目的遍历
（3）结束条件为遍历到最后一个项目为止，也就是无法再生成
3.根据项目集规范簇生成ACTION表和GO表
（1）将输入的文法进行拆分为终结符与非终结符，非终结符做action表的行标，终结符做goto表的行标
（2）将项目集规范簇的In中的n做列标
（3）在action表中用正数代表移进，负数代表归约，999代表接受，goto表用数字代表是哪条文法
（4）双重循环遍历项目集规范簇进行action goto表的生成
（5）外循环遍历每个I，内循环查询这个I是哪些I生成的，因为一个I可以通过多个I生成
4.通过查找ACTION和GO表进行句子的分析
源代码
#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct GLR_CSS{ int num;//条的编号 char left;//产生式左边 char right[30];//产生式右边 int dot;//用于存储点的位置 struct GLR_CSS *next; }CSS; typedef struct GLR{ int I_01;//存放自己是I几 int I_02;//存放是经过I几通过输入c变换过来的 char c; //I01输入c到I02 struct GLR_CSS *css;//头指针 int num;//产生式的个数 struct GLR *next; }LR; char g[100][20]; int n;//文法的条数 char at[100];//存储终结符 int at_num=0; //用于记录at数组的长度 char gt[100];//存储非终结符 char gt_01[100][2];//第一个存储非终结符，第二个存储记录 int gt_num=0;//用于记录gt数组的长度 LR lr;//用于存储输入的文法 LR *I; LR *Ips;//存储头结点 LR *Ipf;//存储最后一个结点 int act_gt[100][100]; char str[100];//需要分析的输入串 int str_num;//分析串栈的指针 int fhz[100];//符号栈 int fhz_num;//符号栈的指针 //接收输入的文法 void get_g(){ int i; printf("请输入文法的条数："); scanf("%d",&n); getchar(); for(i=0;i<n;i++){ printf("(%d)",i+1); gets(g[i]); } } //查重action表 void action_01(char c){ if(at_num==0){//没有直接放 at[at_num]=c; at_num++; }else{//有，查重 int i; int flag=0; for(i=0;i<at_num;i++){ if(at[i]==c){ flag=1; } } if(flag==0){//没有 at[at_num]=c; at_num++; } } } //找出action表 void action(){//找action序列（非大写） int i; //遍历每一条 int j;//遍历每一条的每一个 int len; for(i=0;i<n;i++){ len=strlen(g[i]); for(j=0;j<len;j++){ if(g[i][j]=='-'&&g[i][j+1]=='>'){//排除->(排除箭头，也就是“定义为”) j++; continue; }else{ if(g[i][j]<65||g[i][j]>90){//终结符的范围 action_01(g[i][j]); //放入at数组，//该函数用于检测是否重复 } } } } at[at_num]='#'; at_num++; at[at_num]='\0'; } //查重goto表 void gotoo_01(char c){ if(gt_num==0){//没有直接放 gt[gt_num]=c; gt_num++; }else{//有，查重 int i; int flag=0; for(i=0;i<gt_num;i++){ if(gt[i]==c){ flag=1; } } if(flag==0){//没有 gt[gt_num]=c; gt_num++; } } } //找出goto表 void gotoo(){//找goto序列（大写） int i; //遍历每一条 int j;//遍历每一条的每一个 int len; for(i=0;i<n;i++){ len=strlen(g[i]); for(j=0;j<len;j++){ if(g[i][j]=='-'&&g[i][j+1]=='>'){//排除->(排除箭头，也就是“定义为”) j++; continue; }else{ if(g[i][j]>=65&&g[i][j]<=90){//非终结符的范围 gotoo_01(g[i][j]); //放入gt数组，//该函数用于检测是否重复 } } } } gt[gt_num]='\0'; } void init_gt_01(){ int i; for(i=0;i<gt_num;i++){ gt_01[i][0]=gt[i]; gt_01[i][1]=0;//未检测时为0； } } //测试，输出结构体 void f(CSS *p){ int i=1; while(p!=NULL){ printf("(%d)%c->%s\n",i,p->left,p->right); printf("点：%d\n",p->dot); p=p->next; i++; } } //将所有文法存储在lr变量中 void lr_save(){ lr.num=n;//存储初始文法的条数 int i,j; int len; CSS *cssp,*cssk,*csst; cssp=(CSS*)malloc(sizeof(CSS));//头结点 cssk=cssp; for(i=0;i<n;i++){ len=strlen(g[i]); csst=(CSS*)malloc(sizeof(CSS)); csst->num=i+1; //存储是第几条文法 csst->left=g[i][0];//存储左边 int k=0; for(j=3;j<len;j++){ csst->right[k]=g[i][j]; k++; } csst->right[k]='\0'; cssk->next=csst; cssk=cssk->next; } cssk->next=NULL; lr.css=cssp; //fff();//测试，输出函数 } //初始化I0;并初始头结点 void into_I0(){ //空结点 Ips=(LR*)malloc(sizeof(LR)); //临时结点 LR *Ipt; Ipt=(LR*)malloc(sizeof(LR)); //Ipt->num=1;//文法条数 //初始化第一个数据结点 Ipt->I_01=0;//I0 //定义语句的临时结点 ,和转移结点 CSS *csst,*csss; //定义遍历的结点 CSS *cssk; cssk=lr.css->next; //语句的第一个空结点 Ipt->css=(CSS*)malloc(sizeof(CSS)); csss=Ipt->css; //语句初始个数 Ipt->num=0; int bt=-1; / //E'->E bt++;//表达式的序号 csst =(CSS*)malloc(sizeof(CSS)); //表达式的序号 csst->num=bt; //点的位置 csst->dot=0; //表达式左边 csst->left='S'; //表达式右边 csst->right[0]=cssk->left; csst->right[1]='\0'; csss->next=csst; csss=csss->next; //cssk=cssk->next; Ipt->num++;//语句条数加1 / while(cssk!=NULL){ bt++;//表达式的序号 csst =(CSS*)malloc(sizeof(CSS)); //表达式的序号 csst->num=bt; //点的位置 csst->dot=0; //表达式左边 复制 csst->left=cssk->left; //表达式右边复制 strcpy(csst->right,cssk->right); csss->next=csst; csss=csss->next; cssk=cssk->next; Ipt->num++;//语句条数加1 } csss->next=NULL; Ips->next=Ipt;//头 Ipf=Ips->next;//指向尾巴 Ipf->next=NULL; //fff(); } int jc_gt_01(char c){//c处为0返回1，否则返回0 int i; for(i=0;i<gt_num;i++){ if(gt_01[i][0]==c){ if(gt_01[i][1]==0){ return 1; }else{ return 0; } } } return 0; } void fz_gt_01(int c){ int i; for(i=0;i<gt_num;i++){ if(gt_01[i][0]==c){ gt_01[i][1]=1; } } } void create_I(LR *lrr,CSS *css){ //清空gt_01数组 init_gt_01(); char s=css->right[css->dot];//当前移入的符号 //(1)遍历lrr结点所有表达式，生成新的I结点 //开辟I结点存储空间 LR *ln=(LR*)malloc(sizeof(LR)); ln->num=0;//文法初始条数 // 生成新表达式的csss CSS *csss,*csst; csss=(CSS*)malloc(sizeof(CSS));//头结点 ln->css=csss;//链上带头结点 csss->next=NULL; //遍历每条表达式的临时变量 CSS *lt=lrr->css->next; while(lt!=NULL){ if(lt->right[lt->dot]==s){//点后面是要移入的符号 csst=(CSS*)malloc(sizeof(CSS));//开辟一个表达式的存储空间 csst->next=NULL;//next复制NULL csst->left=lt->left; strcpy(csst->right,lt->right); csst->dot=lt->dot+1; csss->next=csst; csss=csss->next; ln->num++; } lt=lt->next; } //（2）判断新结点的每个表达式后是否是终结符，若不是则新添加 //csss目前指向最后一个 CSS *csss01=ln->css->next; CSS *csss02; //char pre='a'; while(csss01!=NULL){//循环目前生成的表达式 if(csss01->right[csss01->dot]>=65&&csss01->right[csss01->dot]<=90&&jc_gt_01(csss01->right[csss01->dot])==1){//非终结符判断条件 //printf("ssssssssssss\n"); csss02=Ips->next->css->next;//I0的所有表达式 while(csss02!=NULL){ if(csss02->left==csss01->right[csss01->dot]){ csst=(CSS*)malloc(sizeof(CSS));//开辟一个表达式的存储空间 csst->next=NULL;//next复制NULL csst->left=csss02->left; strcpy(csst->right,csss02->right); csst->dot=csss02->dot; csss->next=csst; csss=csss->next; ln->num++; } csss02=csss02->next; } fz_gt_01(csss01->right[csss01->dot]); } csss01=csss01->next; } //(3)查重 LR *Ipt01=Ips->next; CSS *csss03; CSS *csss04; int flag=0; while(Ipt01!=NULL){ if(Ipt01->num==ln->num){//语法条数相等才有相同的可能性 csss03=Ipt01->css->next; flag=0; while(csss03!=NULL){ csss04=ln->css->next; while(csss04!=NULL){ if(csss04->left==csss03->left&&csss04->dot==csss03->dot&&strcmp(csss03->right,csss04->right)==0){ flag++; } csss04=csss04->next; } csss03=csss03->next; } if(flag==ln->num){//重复了 return; } } Ipt01=Ipt01->next; } //加到末尾 ln->I_01=Ipf->I_01+1; ln->I_02=lrr->I_01; ln->c=s; Ipf->next=ln; Ipf=Ipf->next; Ipf->next=NULL; /*printf("-------------------\n"); printf("这是I(%d)\n",ln->I_01); printf("I(%d)输入%c变成\n",ln->I_02,ln->c); printf("表达式为:\n"); f(ln->css->next); printf("-------------------\n"); */ } //将所有项目I0---In列出 void lr_analyse(){ LR *Ipt_01;//用于遍历 LR *Ipt_02; //用于开辟新结点 CSS *csst_01;//遍历 CSS *csst_02; Ipt_01=Ips->next; // lr_analyse_exit()==1 while(1){//项目列表的最后一个所有语法的点都在最后面则退出 ,遍历I列表，每次一个 csst_01=Ipt_01->css->next;//In的第一个产生式子的位置 while(csst_01!=NULL){//当前I的第j个表达式点后移，产生新的 //移动点 // //printf("222222222\n"); if(csst_01->dot==strlen(csst_01->right)){//已经完了 csst_01=csst_01->next; continue; }else{ //printf("-------当前遍历的是I(%d)的%c->%s语句-------\n",Ipt_01->I_01,csst_01->left,csst_01->right); create_I(Ipt_01,csst_01);//传入当前I的所有表达式的头，和当前语句 } csst_01=csst_01->next; } //printf("11111111111122222222222222222222222222"); if(Ipt_01->I_01==Ipf->I_01){ break; }else{ Ipt_01=Ipt_01->next; //printf("11111111111111111111111111\n"); } } } void acc_form(){ act_gt[1][strlen(at)-1]=999; } //检测是不是lt02移入lt01->c,变成lt01 void goto_form_01(LR *lt01,LR *lt02,char c){ CSS *csst01; csst01=lt02->css->next;//lt02的第一条语句 //移入后的新语句头 CSS *csst02; csst02=(CSS*)malloc(sizeof(CSS)); csst02->next=NULL; //移动临时变量 CSS *csst03,*csst04; csst03=csst02; while(csst01!=NULL){ if(csst01->right[csst01->dot]==c){ //printf("77888888999\n"); //申请空间 csst04=(CSS*)malloc(sizeof(CSS)); //填写表达式左边数据 csst04->left=csst01->left; //右边数据 strcpy(csst04->right,csst01->right); //点 csst04->dot=csst01->dot+1; csst04->next=NULL; csst03->next=csst04; csst03=csst03->next; } csst01=csst01->next; } //查看csst02是否与lt01表达式相同 int flag=0; csst02=csst02->next; /*printf("=======这是csst02=======\n"); f(csst02); printf("=======这是csst02=======\n");*/ CSS *csst05; while(csst02!=NULL){ csst05=lt01->css->next; while(csst05!=NULL){ //printf("777777777\n"); if(csst05->left==csst02->left&&csst05->dot==csst02->dot&&strcmp(csst05->right,csst02->right)==0){ flag++; } csst05=csst05->next; } csst02=csst02->next; } //printf("flag==%d,lt01->num=%d\n",flag,lt01->num); if(flag==lt01->num){ //说明lt02移入c，变成lt01 //纵坐标 int h=lt02->I_01; //横坐标 int x; int i; for(i=0;i<gt_num;i++){ if(gt[i]==c){ x=i; } } act_gt[h][at_num+x]=lt01->I_01; } //移入 } void goto_form(){ //遍历除I0所有LR->c为大写的 LR *lt01; lt01=Ips->next->next;//I1 LR *lt02;//I0 while(lt01!=NULL){ if(lt01->c>=65&<01->c<=90){//lt01是由某个状态移入c变成的 lt02=Ips->next;//从I0，开始 while(lt02!=NULL){ //检测是不是lt02移入lt01->c,变成lt01 goto_form_01(lt01,lt02,lt01->c);//并填写goto表 lt02=lt02->next; } } lt01=lt01->next; } } void action_r_form_01(int h,CSS *csst){//(纵坐标,当前表达式)在I0中找到，并填表 CSS *csst01=Ips->next->css; while(csst01!=NULL){ if(csst01->left==csst->left&&strcmp(csst01->right,csst->right)==0){ int num=csst01->num*(-1);//编号 //填表 int i; for(i=0;i<at_num;i++){ act_gt[h][i]=num; } } csst01=csst01->next; } } void action_r_form(){ //遍历I1开始 //如果In的某条文法的点在最后，则在I0的css中找对应的编号 ，（除left=S的情况，因为这个是acc） LR *lt01=Ips->next->next; CSS *csst01; while(lt01!=NULL){ csst01=lt01->css->next; while(csst01!=NULL){ if(csst01->left!='S'&&csst01->dot==strlen(csst01->right)){ action_r_form_01(lt01->I_01,csst01);//在I0中找到，并填表 } csst01=csst01->next; } lt01=lt01->next; } } //检测是不是lt02移入lt01->c,变成lt01 void action_s_form_01(LR *lt01,LR *lt02,char c){ init_gt_01();//清空gt_01数组 CSS *csst01; csst01=lt02->css->next;//lt02的第一条语句 //移入后的新语句头 CSS *csst02; csst02=(CSS*)malloc(sizeof(CSS)); csst02->next=NULL; //移动临时变量 CSS *csst03,*csst04; csst03=csst02; while(csst01!=NULL){ if(csst01->right[csst01->dot]==c){ //printf("77888888999\n"); //申请空间 csst04=(CSS*)malloc(sizeof(CSS)); //填写表达式左边数据 csst04->left=csst01->left; //右边数据 strcpy(csst04->right,csst01->right); //点 csst04->dot=csst01->dot+1; csst04->next=NULL; csst03->next=csst04; csst03=csst03->next; //printf("%c",csst04->right[csst04->dot]); } //printf("qqqqqqqqqqqqqqqqqqqq\n"); csst01=csst01->next; } //将csst02中的非终结符在I0中找出,现在csst03所指最后一个表达式 CSS *csst02_01=csst02->next; while(csst02_01!=NULL){ char cc=csst02_01->right[csst02_01->dot]; if(cc>=65&&cc<=90&&jc_gt_01(cc)==1){ //遍历I0 CSS *cssi0=Ips->next->css->next; while(cssi0!=NULL){ if(cssi0->left==cc){ //申请空间 csst04=(CSS*)malloc(sizeof(CSS)); //填写表达式左边数据 csst04->left=cssi0->left; //右边数据 strcpy(csst04->right,cssi0->right); //点 csst04->dot=cssi0->dot; csst04->next=NULL; csst03->next=csst04; csst03=csst03->next; } cssi0=cssi0->next; } fz_gt_01(cc); } csst02_01=csst02_01->next; } //查看csst02是否与lt01表达式相同 int flag=0; csst02=csst02->next; /*printf("=======这是csst02=======\n"); f(csst02); printf("=======这是csst02=======\n");*/ /*if(lt01->I_01==3){ printf("这是I3,,I%d正在与他比较\n",lt02->I_01); printf("生成的东西为：\n"); f(csst02); printf("%c\n",lt01->c); }*/ CSS *csst05; while(csst02!=NULL){ csst05=lt01->css->next; while(csst05!=NULL){ //printf("777777777\n"); if(csst05->left==csst02->left&&csst05->dot==csst02->dot&&strcmp(csst05->right,csst02->right)==0){ flag++; } csst05=csst05->next; } csst02=csst02->next; } //printf("flag==%d,lt01->num=%d\n",flag,lt01->num); if(flag==lt01->num){ //说明lt02移入c，变成lt01 //纵坐标 int h=lt02->I_01; //横坐标 int x; int i; for(i=0;i<at_num;i++){ if(at[i]==c){ x=i; } } act_gt[h][x]=lt01->I_01; } //移入 } void action_s_form(){ //遍历除I0所有LR->c为非大写的，也就是终结符 LR *lt01; lt01=Ips->next->next;//I1 LR *lt02;//I0 while(lt01!=NULL){ if(lt01->c<65||lt01->c>90){//lt01是由某个状态移入c变成的 lt02=Ips->next;//从I0，开始 while(lt02!=NULL){ //检测是不是lt02移入lt01->c,变成lt01 action_s_form_01(lt01,lt02,lt01->c);//并填写goto表 lt02=lt02->next; } } lt01=lt01->next; } } void output_action_goto(){ int i; int j; int k; int q; int w; printf("--------ACTION-------------------GOTO-------\n"); printf(" 状态"); for(q=0;q<at_num;q++){ printf("%5c",at[q]); } for(k=0;k<gt_num;k++){//goto表的表头 printf("%5c",gt[k]); } printf("\n"); for(i=0;i<=Ipf->I_01;i++){ printf("%5d",i);//状态 //输出action表的值 for(w=0;w<at_num;w++){ if(act_gt[i][w]==999){ printf(" acc"); continue; } if(act_gt[i][w]<0){ printf(" R%d",act_gt[i][w]*-1); continue; } if(act_gt[i][w]>0){ printf(" S%d",act_gt[i][w]); continue; } printf("%5c",' '); } //输出goto表的值 for(j=0;j<gt_num;j++){ if(act_gt[i][at_num+j]==0){ printf("%5c",' '); }else{ printf("%5d",act_gt[i][at_num+j]); } } printf("\n"); } } void anction_goto_form(){ //(1)填写acc-->999 acc_form(); //(2) 填写goto()表，输入大写 goto_form(); //(3)填写r负数 action_r_form(); //printf("wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww\n"); //(4)填写s正数 action_s_form(); //printf("-----------------%d\n",lt->I_01); output_action_goto();//输出acion_goto表 } void output_lr_analyse(){ LR *lt=Ips->next; while(lt!=NULL){ printf("当前是I(%d),有%d条语句,输入字符是%c\n",lt->I_01,lt->num,lt->c); printf("语句为：\n"); f(lt->css->next); lt=lt->next; } } void get_string(){ printf("请输入分析串："); gets(str); str[strlen(str)+1]='\0'; str[strlen(str)]='#'; //puts(str); } int jc_lr_form(int h,char c){ int i; int flag=0;//记录是action表的内容还是goto表的内容 int x; //遍历action for(i=0;i<at_num;i++){ if(at[i]==c){ x=i; flag=1;//action表 break; } } for(i=0;i<gt_num;i++){ if(gt[i]==c){ x=at_num+i; flag=2; break; } } if(flag==1){//在action中 if(act_gt[h][x]>0&&act_gt[h][x]!=32){ //S return act_gt[h][x]; } if(act_gt[h][x]<0){ return act_gt[h][x]; //r } if(act_gt[h][x]==999){ //接受 return 9999; } if(act_gt[h][x]==32){ //出错 return 2222; } } if(flag==2){//说明在goto表中 if(act_gt[h][x]!=32){//状态转移 return act_gt[h][x]+1000; }else{ //出错 return 2222; } } if(flag==0){ //出错 return 2222; } } void out_fhz(){ printf("符号栈："); int i; for(i=0;i<=fhz_num;i++){ if(fhz[i]<=0){ printf("%d",fhz[i]*-1); }else{ //printf("ggggggggggggggggggggggggggggggggg"); printf("%c",fhz[i]); } } printf(" "); } void out_str(){ printf("当前输入："); int i; for(i=str_num;i<strlen(str);i++){ printf("%c",str[i]); } printf(" "); } //找标号为num的表达式 CSS* guiyue(int num){ CSS *p=Ips->next->css->next; while(p!=NULL){ if(p->num==num){ return p; } p=p->next; } } void lr_process(){ //初始符号栈#0 fhz[fhz_num]='#'; //printf("------>%c",fhz[fhz_num]); fhz_num++; fhz[fhz_num]=0*(-1);//状态（用负数来表示状态，将状态与符号区分开来） //fhz_num++; while(1){ //查看符号栈栈顶元素，和串的栈顶元素 //查分析表 int sr_num=jc_lr_form(fhz[fhz_num]*-1,str[str_num]);//(状态，输入) //sr_num==2222//出差错 if(sr_num==2222){ printf("出错，不可识别\n"); break; } //sr_num>0&&sr_num<1000 移进 if(sr_num>0&&sr_num<1000){ out_fhz();//输出栈内容 out_str(); //当前输入 if(sr_num==999){ printf("接收accept\n"); break; }else{ printf("移进：S%d\n",sr_num); } //先移入符号，再移入状态 //移入符号 fhz_num++;//符号栈指针+1 fhz[fhz_num]=str[str_num]; str_num++;//输入串指针后移 //移入状态 fhz_num++; fhz[fhz_num]=sr_num*-1; } if(sr_num<0){//归约 out_fhz();//输出栈内容 out_str(); //当前输入 //在I0中找标号为sr_num*-1的 //sr_num*-1,要归约的表达式 CSS *csst01=guiyue(sr_num*-1); printf("归约：R%d(%c->%s)\n",sr_num*-1,csst01->left,csst01->right); //fhz指针后移一位，换成csst01->left fhz_num=fhz_num-2*strlen(csst01->right)+1; fhz[fhz_num]=csst01->left; int zt=jc_lr_form(fhz[fhz_num-1]*-1,fhz[fhz_num]); //printf("%d\n",zt); if(zt>1000&&zt<2000){ fhz_num++; fhz[fhz_num]=(zt-1000)*-1; }else{ if(zt==9999){ printf("acc，接收\n"); break; }else{ printf("出错，不可识别\n"); break; } } } //sr_num==9999 //接受 if(sr_num==9999){ printf("acc，接收\n"); break; } } } int main(){ get_g();//文法的输入 action();//找action序列（非大写） gotoo();//找大写非终结符 init_gt_01();//初始化gt_01表 lr_save(); //存储输入的文法在变量lr中 into_I0();//初始化I0;并初始头结点 printf("===================开始分析=====================\n"); printf("=====================I(0)为=====================\n"); f(Ips->next->css->next); printf("================================================\n"); lr_analyse(); //项目集规范族 Ips是头指针 //清屏函数 //system("cls"); output_lr_analyse();//输出项目集 printf("======================ACTION GOTO表==========================\n"); anction_goto_form();//构造LR分析表，并输出 //输入分析串 get_string(); lr_process(); return 0; }
