编译原理 - LR(1)分析法：C/C++实现

#include<stdio.h> #include<string.h> #include<stdlib.h> /* ACTION表*/ char *action_table[10][3]={"S3","S4",NULL, NULL,NULL,"acc", "S6","S7",NULL, "S3","S4",NULL, "r3","r3",NULL, NULL,NULL,"r1", "S6","S7",NULL, NULL,NULL,"r3", "r2","r2",NULL, NULL,NULL,"r2"}; /* GOTO表*/ int goto_table[10][2]={1,2, 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0}; char vt[3]={'a','b','#'}; /*存放终结符*/ char vn[2]={'S','B'}; /*存放非终结符*/ struct Production{ //产生式类型定义 char alp; //大写字符 char array[10]; //产生式右边字符 int length; //字符个数 }; Production production[4]; //存放产生式 int statueStack[10]; //状态栈 char symbolStack[10]; //符号栈 char input_string[10]; //输入串 int statueStackPointer = -1; //状态栈的指针 int symbolStackPointer = -1; //符号栈的指针 int inputStringPointer = 0; //输入串的指针 int input_string_length = 0; //输入串的长度 int proce = 1; bool input_judge(); void printAll(); void analyse(); void init(); int main(){ bool input_right = false; while(!input_right){ input_right = input_judge(); } init(); printf("步骤\t\t状态栈\t\t符号栈\t\t输入串\t\t"); printf("Action\t\t"); printf("Goto\n"); printAll(); analyse(); } void printAll(){ printf("%d\t\t",proce++); for(int i=0; i<=statueStackPointer;i++){ //输出状态栈 printf("%d",statueStack[i]); } printf("\t\t"); for(int i=0; i<=symbolStackPointer;i++){ /*输出符号栈*/ printf("%c",symbolStack[i]); } printf("\t\t"); for(int i=inputStringPointer; i<input_string_length;i++){ /*输出输入栈*/ printf("%c",input_string[i]); } printf("\t\t"); } void analyse(){ int stop = 0; while(!stop){ char store[10]; char input = input_string[inputStringPointer]; //获取输入串的第一个字符 int col = -1; int row = statueStack[statueStackPointer]; /*查action表*/ if(input=='a'){ col=0; } if(input=='b'){ col=1; } if(input=='#'){ col=2; } if(action_table[row][col]==NULL){ printf("err\n"); exit(0); } else{ strcpy(store,action_table[row][col]); } if(strcmp(store,"acc")==0){ printf("acc\n"); stop = 1; break;//结束 } /*移进*/ else if(store[0]=='S'){ statueStack[++statueStackPointer]=store[1]-'0'; symbolStack[++symbolStackPointer]=input_string[inputStringPointer]; inputStringPointer+=1; printf("%s\n",store); printAll(); } /*归约*/ else if(store[0]=='r'){ int col = -1; int index=store[1]-'0'; if(production[index].alp=='S'){ col=0; } else if(production[index].alp=='B'){ col=1; } else{ printf("err"); exit(0); } int length = production[index].length; //表达式的字符长度 statueStackPointer-=length; //状态栈出栈 symbolStackPointer-=length; //符号栈出栈 int row = statueStack[statueStackPointer]; //获取状态栈在出栈操作后的栈顶状态 statueStack[++statueStackPointer]=goto_table[row][col]; //goto表中的状态进入状态栈 symbolStack[++symbolStackPointer]=production[index].alp; //表达式的左边的大写字母进入符号栈 printf("%s\t\t",store); printf("%d\n",goto_table[row][col]); printAll(); } else{ printf("err!\n"); exit(0); } } } void init(){ struct Production a1,a2,a3,a4; a1.alp = 'E'; strcpy(a1.array,"S"); a1.length = 1; a2.alp = 'S'; a2.length = 2; strcpy(a3.array,"BB"); a3.alp = 'B'; a3.length = 2; strcpy(a3.array,"aB"); a4.alp = 'B'; a4.length = 1; strcpy(a4.array,"b"); production[0] = a1; production[1] = a2; production[2] = a3; production[3] = a4; statueStack[++statueStackPointer] = 0; //0 symbolStack[++symbolStackPointer] = '#';//# } bool input_judge(){ int j=0; char ch; printf("Input："); while(true){ ch = getchar(); if(ch=='\n'){ break; } input_string[j++] = ch; } for(int i=0; i<j; i++){ ch = input_string[i]; if(!((ch=='a')||(ch=='b'))){ printf("输入有误\n"); return false; } } input_string[j++] = '#'; input_string_length = j; return true; }