如果要进行递归下降分析，肯定少不了FIRST集，FOLLOW集，SELECT集和预测分析表。并根据预测分析表或者SELECT集判断该文法是不是LL（1）文法。
怎么求FIRST集？
下面的代码是第一版，不能输出语法分析树。
#include#define ERROR -1 //程序不能正确运行的返回值 char sym,a[50]; //sym临时存放一个字符，数组a存放输入的字符串 int ip=0; //字符数组下标 int A(); //函数声明 int B(); int C(); int X(); int Y(); void getNextSym() //取字符串中的下一个字符 { sym=a[++ip]; printf(" sym=%cn",sym); //输出当前字符 } //================================================ void main() //主函数 { int ret; //存放其他函数的返回值 while(1){ //下面这句输出语句对用户输入的字符串作出约束 printf("ninput length < 50,ending with'#'; '^#' to return!n"); ip=0; //字符数组下标 do{ scanf("%c",&sym);//输出的最后一个字符必须是# a[ip++]=sym; //将输入的字符串以数组的形式存放 }while(sym!='#'); //#作为结束的标志 if(a[0]=='^' && a[1]=='#') return; printf("......begin......n");//分析开始 ip=-1; //重新设置字符数组下标 getNextSym(); ret=A(); //只有函数A()返回值为0，才说明分析过程正确 if (ret != ERROR && sym=='#') //当所有函数正确执行并且分析到最后一个字符 printf("*****ACCEPT!!!*****n"); else printf("-----!ERROR!------n"); getchar(); } } //================================================ int A() { if(sym == '['){ //只有当输入的第一个字符为[，才能继续向下分析 printf("A->[Bn"); //输出文法对应的产生式 getNextSym(); //取下一个字符 if(B()==ERROR) //如果接下来的字符在文法中没有匹配的产生式 return ERROR; //结束分析过程 } else //如果第一个字符就不是[，结束分析过程 return ERROR; return 0; //分析成功，正常结束 } int B() { if(sym == 'a'||sym == 'b') //当字符是a或b时，才继续向下分析 { printf("B->X]Cn"); //输出文法对应的产生式 if(X()==ERROR) //如果接下来的字符在文法中没有匹配的产生式 return ERROR; //结束分析过程 if(sym != ']') //分析文法，此时的字符只有是]才能够继续分析 return ERROR; getNextSym(); if(C()==ERROR) //如果接下来的字符在文法中没有匹配的产生式 return ERROR; //结束分析过程 } else //如果当前字符不是a或b，结束分析过程 return ERROR; return 0; //分析成功，正常结束 } int C() //以下的程序都可以参考函数A和函数B的注释 { if(sym == 'a') { printf("C->aCn"); getNextSym(); if(C()==ERROR) return ERROR; } else if(sym == '#'){ //如果当前字符是#，说明字符串已经全部分析完了 printf("C-> n"); } else return ERROR; return 0; } int X() { if(sym == 'a') { printf("X->aYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else if(sym == 'b') { printf("X->bYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else return ERROR; return 0; } int Y() { if(sym == 'a') { printf("Y->aYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else if(sym == 'b') { printf("Y->bYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else if(sym == ']'){//这个地方比较关键，如果这个条件成立，因为此时已经把[取出来了 //所以返回到函数B就不用取这个字符了，直接到下一个字符 printf("Y-> n"); } else return ERROR; return 0; }
下面的代码是第二版，输出语法分析树。
#include#include #define ERROR -1 //程序不能正确运行的返回值 char sym,a[50];//sym临时存放一个字符，数组a存放输入的字符串 int ip=0; //字符数组下标 int A(); //函数声明 int B(); int C(); int X(); int Y(); int arr[100][100];//这个数组用于辅助打印语法分析树 int row;//arr数组的行 int col;//arr数组的列 int first_C;//如果是第一次到C函数，值是1，之后为0； void getNextSym() //取字符串中的下一个字符 { sym=a[++ip]; printf(" sym=%cn",sym); //输出当前字符 } //================================================ int main() //主函数 { int ret; //存放其他函数的返回值 while(1){ //下面这句输出语句对用户输入的字符串作出约束 int i=0; int j=0; memset(arr,' ',sizeof(arr)); //每次进入while循环就初始化数组全为空字符 row=0; col=0; first_C=1; //因为下面的二维数组中的元素无论在什么串里，只要串是正确的 //在打印的时候都是一样的，而错误的串又没必要输出语法分析树 //所以可以先存放到数组里 arr[0][3]='A'; arr[1][2]='/'; //表示父节点和子节点的从属关系 arr[1][4]='\'; //注意''是转义字符 arr[2][1]='['; arr[2][4]='B'; arr[3][3]='/'; arr[3][4]='|'; arr[3][5]='\'; arr[4][2]='X'; arr[4][4]=']'; arr[4][6]='C'; arr[5][1]='/'; arr[5][3]='\'; //arr[5][7]='\'; row=6;//在定义了上面数组元素后，数组的起始位置 col=0; printf("ninput length < 50,ending with'#'; '^#' to return!n"); ip=0; //字符数组下标 do{ scanf("%c",&sym); a[ip++]=sym; //将输入的字符串以数组的形式存放 }while(sym!='#'); //#作为结束的标志 if(a[0]=='^' && a[1]=='#') return 0; printf("......begin......n");//分析开始 ip=-1; //重新设置字符数组下标 getNextSym(); ret=A(); //只有函数A()返回值为0，才说明分析过程正确 if (ret != ERROR && sym=='#') //当所有函数正确执行并且分析到最后一个字符 { printf("*****ACCEPT!!!*****n"); for(i=0;i<30;i++) //打印语法分析树 { for(j=0;j<50;j++) { printf("%c",arr[i][j]); } printf("n"); } } else printf("-----!ERROR!------n"); getchar(); } return 0; } //================================================ int A() { if(sym == '['){ //只有当输入的第一个字符为[，才能继续向下分析 printf("A->[Bn"); //输出文法对应的产生式 getNextSym(); //取下一个字符 if(B()==ERROR) //如果接下来的字符在文法中没有匹配的产生式 return ERROR; //结束分析过程 } else //如果第一个字符就不是[，结束分析过程 return ERROR; return 0; //分析成功，正常结束 } int B() { if(sym == 'a'||sym == 'b') //当字符是a或b时，才继续向下分析 { printf("B->X]Cn"); //输出文法对应的产生式 if(X()==ERROR) //如果接下来的字符在文法中没有匹配的产生式 return ERROR; //结束分析过程 if(sym != ']') //分析文法，此时的字符只有是]才能够继续分析 return ERROR; getNextSym(); if(C()==ERROR) //如果接下来的字符在文法中没有匹配的产生式 return ERROR; //结束分析过程 } else //如果当前字符不是a或b，结束分析过程 return ERROR; return 0; //分析成功，正常结束 } int C() //以下的程序都可以参考函数A和函数B的注释 { if(first_C==1) //如果是第一次进入C函数，需要重新定位 { row=5; col=7; } if(sym == 'a') { first_C=0; //之后再进入C函数就不是第一次了，所以修改标记 arr[row][col]='\'; //接下来的四句代码就是画树和重新定位 arr[row+1][col+1]=sym; row+=2; col+=2; printf("C->aCn"); getNextSym(); if(C()==ERROR) return ERROR; } else if(sym == '#'){ //如果当前字符是#，说明字符串已经全部分析完了 arr[row][col]='\'; arr[row+1][col+1]='ε'; //空 printf("C-> n"); } else return ERROR; return 0; } int X() { if(sym == 'a') { arr[row][col]=sym; arr[row][col+3]='Y'; row+=1; col+=3; printf("X->aYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else if(sym == 'b') { arr[row][col]=sym; arr[row][col+3]='Y'; row+=1; col+=3; printf("X->bYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else return ERROR; return 0; } int Y() { if(sym == 'a') { arr[row][col-1]='/'; arr[row][col+1]='\'; row+=1; col-=2; arr[row][col]=sym; arr[row][col+3]='Y'; row+=1; col+=3; printf("Y->aYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else if(sym == 'b') { arr[row][col-1]='/'; arr[row][col+1]='\'; row+=1; col-=2; arr[row][col]=sym; arr[row][col+3]='Y'; row+=1; col+=3; printf("Y->bYn"); getNextSym(); if(Y()==ERROR) return ERROR; } else if(sym == ']'){//这个地方比较关键，如果这个条件成立，因为此时已经把[取出来了 //所以返回到函数B就不用取这个字符了，直接到下一个字符 arr[row+1][col]='|'; arr[row+2][col]='ε'; printf("Y-> n"); } else return ERROR; return 0; }
对于如何实现输出语法树，因为我的方法有局限性，这里就不再详谈了。
运行结果如下：（图片中的？实际是ε）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）