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

#include<stdio.h> #include<string.h> #define number_zjfu 6 //终结符的个数 #define unnumber_zjfu 5 //非终结符的个数 char stack1[100]; //分析栈 char stack2[100]; //剩余串，只读不进 char terminal_array[number_zjfu]={'i','+','*','(',')','#'}; //终结符 char non_terminal_array[unnumber_zjfu]={'E','G','T','S','F'}; //非终结符 struct Production{ //产生式类型定义 char origin; //大写字符 char array[10]; //产生式右边字符 int length; //字符个数 }; struct Production e,t,g,g1,s,s1,f,f1; //表示各产生式 Production analyseTable[10][10]; //预测分析表 int frist = 0; //输入串的指针 int last = 0; //分析栈的指针 int length_of_string; //输入串长度 char userF; //当前正在处理的输入串中的字符 char stacktop; //当前正在处理的栈顶的字符 int statue = 0; int proce = 1; void init(); void analyse(); void printStack(); void printRemainString(); bool input_string(); int main(){ //初始化 init(); bool input_correctly = false; while(!input_correctly){ input_correctly = input_string(); } stack1[last] = '#';//数组实现栈 ，栈底为# stack1[++last] = 'E'; //开始字符E和结束符#进栈 printf("步骤\t\t分析栈 \t\t剩余字符 \t\t产生式 \n"); while(!statue){ analyse(); } return 1; } bool input_string(){//用户输入串 int j=0; char ch; printf("终结符有：'i','+','*','(',')','#' \n"); printf("your input is:"); while(true){ ch = getchar(); if(ch=='\n'){ break; } stack2[j] = ch; j++; } for(int i=0; i<j; i++){//判断是否合法，以终结符做判断 ch = stack2[i]; if((ch!='i')&&(ch!='+')&&(ch!='*')&&(ch!='(')&&(ch!=')')){ printf("输入了非法的字符！请重新输入！\n"); return false; } } stack2[j] = '#';//加入#说明分析结束 length_of_string = j+1; //分析串长度 return true; } void init(){ e.origin='E'; strcpy(e.array,"TG"); e.length = 2; t.origin='T'; strcpy(t.array,"FS"); t.length = 2; g.origin='G'; strcpy(g.array,"+TG"); g.length = 3; g1.origin='G'; g1.array[0]='^'; g1.length = 1; s.origin='S'; strcpy(s.array,"*FS"); s.length = 3; s1.origin='S'; s1.array[0]='^'; s1.length = 1; f.origin='F'; strcpy(f.array,"(E)"); f.length = 3; f1.origin='F'; f1.array[0]='i'; f1.length = 1; for(int m=0; m<unnumber_zjfu; m++) //初始化分析表 for(int n=0; n<number_zjfu; n++) analyseTable[m][n].origin='N'; analyseTable[0][0]=e; analyseTable[0][3]=e; analyseTable[1][1]=g; analyseTable[1][4]=g1; analyseTable[1][5]=g1; analyseTable[2][0]=t; analyseTable[2][3]=t; analyseTable[3][1]=s1; analyseTable[3][2]=s; analyseTable[3][4]=s1; analyseTable[3][5]=s1; analyseTable[4][0]=f1; analyseTable[4][3]=f; } void analyse(){ stacktop = stack1[last]; //获取栈顶字符 userF = stack2[frist]; //获取用户输入串第一个字符 int logo = 0; //终结符标志 for(int j=0; j<number_zjfu; j++){ /*判断是否为终结符*/ if(stacktop==terminal_array[j]){ logo=1; break; } } if(logo==1){ //如果是终结符 if(stacktop=='#'&&userF=='#'){ //如果该终结符是#，说明输入串已经全部匹配完成。 printStack(); printRemainString(); statue=1; printf("acc!\n"); return ; } if(stacktop==userF){ //相等则匹配 printStack(); printRemainString(); printf("%c匹配\n",userF); frist++; last--; logo = 0; } else{ statue = 2; printStack(); printRemainString(); printf("error"); //输出产生式 return; } } else{ //查表 int row,column; for(int j=0; j<unnumber_zjfu; j++){ if(stacktop==non_terminal_array[j]){ row = j; //行号 break; } } for(int j=0; j<=number_zjfu; j++){ if(userF==terminal_array[j]){ column = j; //列号 break; } } Production cha = analyseTable[row][column]; if(cha.origin!='N'){ //如果对应的产生式不为空，说明可以继续分析 printStack(); printRemainString(); printf("%c->",cha.origin); //输出产生式 printf("%s\n",cha.array); //如果为非终结符，则栈顶的非终结符要去掉 last--; for(int j=(cha.length-1); j>=0; j--){ /*产生式逆序入栈*/ last++; stack1[last]=cha.array[j]; } if(stack1[last]=='^'){ last--; } } else{ //如果对应的产生式为N，则报错。 statue = 2; //状态为报错状态 printStack(); printRemainString(); printf("error"); //输出产生式 } return ; } } void printStack(){ //输出分析栈 printf("%d",proce++); printf("\t\t"); for(int a=0; a<=last; a++){ printf("%c",stack1[a]); } printf("\t\t"); } void printRemainString(){ //输出剩余串 for(int j=0; j<frist; j++){/*输出对齐符*/ printf(" "); } for(int j=frist; j<length_of_string; j++){ printf("%c",stack2[j]); } printf("\t\t\t"); }