设计要求：对于任意输入的一个LL(1)文法，构造其预测分析表，并对指定输入串分析其是否为该文法的句子。
思路：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再根据FIRST和FOLLOW集合构造出预测分析表，并对指定的句子打印出分析栈的分析过程，判断是否为该文法的句子。
（1）求FIRST集的算法思想
如果产生式右部第一个字符为终结符，则将其计入左部first集
如果产生式右部第一个字符为非终结符
->求该非终结符的first集
->将该非终结符的非$first集计入左部的first集
->若存在$，则将指向产生式的指针右移
->若不存在$，则停止遍历该产生式，进入下一个产生式
->若已经到达产生式的最右部的非终结符，则将$加入左部的first集
处理数组中重复的first集中的终结符
（2）求FOLLOW集的算法思想
对于文法G中每个非终结符A构造FOLLOW(A)的办法是,连续使用下面的规则,直到每个FOLLOW不在增大为止. (1) 对于文法的开始符号S,置#于FOLLOW(S)中; (2) 若A->aBb是一个产生式,则把FIRST(b)\{ε}加至FOLLOW(B)中; (3) 若A->aB是一个产生式,或A->aBb是一个产生式而b=>ε(即ε∈FIRST(b))则把FOLLOW(A)加至FOLLOW(B)中
（3）生成预测分析表的算法思想
构造分析表M的算法是： (1) 对文法G的每个产生式A->a执行第二步和第三步; (2) 对每个终结符a∈FIRST(a),把A->a加至M[A,a]中; (3) 若ε∈FIRST(a),则把任何b∈FOLLOW(A)把A->a加至M[A,b]中; (4) 把所有无定义的M[A,a]标上出错标志.
（4）对符号串的分析过程
预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号行事的,对于任何(X,a),总控程序 每次都执行下述三种可能的动作之一; (1) 若X=a=”#”,则宣布分析成功,停止分析过程. (2) 若X=a≠”#”,则把X从STACK栈顶逐出,让a指向下一个输入符号. (3) 若X是一个非终结符,则查看分析表M,若M[A,a]中存放着关于X的一个产生式,那么,首先把X逐出STACK栈顶,然后 把产生式的右部符号串按反序一一推进STACK栈(若右部符号为ε,则意味着不推什么东西进栈).在把产生式的右部 符号推进栈的同时应做这个产生式相应得语义动作,若M[A,a]中存放着”出错标志”,则调用出错诊察程序ERROR.
语法：
S->a|^|(T)
T->SG
G->,SG|$
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<dos.h> char analyse[10]; //分析栈 char remain[10]; //剩余串 char vt[10] = { 'a','^','(',')',',','$','#'};//终结符 char vn[10] = { 'S','T','G' }; //非终结符 typedef struct shiZi //产生式 { char begin; //左边字符 char array[5]; //右边字符串 int length; //右边字符个数 } shiZi; shiZi e, e1, e2, e3, e4, e5; //6个产生式 shiZi table[10][10]; //定义预测分析表 void printStack(); //输出分析栈 void printRemain(); //输出剩余串 int j = 0, b = 0, top = 0; int l; //l为输入串长度 int main() { int m, n, k = 0, flag = 0, finish = 0; char ch, x; shiZi now; //目前使用的产生式 e.begin = 'S'; strcpy(e.array, "a"); e.length = 1; e1.begin = 'S'; strcpy(e1.array, "^"); e1.length = 1; e2.begin = 'S'; strcpy(e2.array, "(T)"); e2.length = 3; e3.begin = 'T'; strcpy(e3.array, "SG"); e3.length = 2; e4.begin = 'G'; strcpy(e4.array, ",SG"); e4.length = 3; e5.begin = 'G'; e5.array[0] = '$'; e5.length = 1; //初始化分析表 for (m = 0; m <= 2; m++) for (n = 0; n <= 5; n++) { table[m][n].begin = 'n'; } //手动填写分析表 table[0][0] = e;table[0][1] = e1;table[0][2] = e2; table[1][0] = e3;table[1][1] = e3;table[1][2] = e3; table[2][3] = e5;table[2][4] = e4; printf("文法G[S]\n"); printf("S->a|^|(T)\n"); printf("T->SG\n"); printf("G->,SG|$\n"); printf("请输入要分析的字符串(以'#'结尾):"); //读入字符串 do { scanf("%c", &ch); if ((ch != 'a') && (ch != ',') && (ch!='(')&&(ch!=')')&& (ch != '#')) { printf("输入串中有非法字符\n"); exit(1); } remain[j] = ch; j++; //字符串长度 } while (ch != '#'); l = j; ch = remain[0]; //当前字符 printf("%c",ch); analyse[top] = '#'; analyse[++top] = 'S'; //文法开始符号'S'进栈 printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n"); do { x = analyse[top--];//当前栈顶字符 printf("%d", k++); printf("\t\t"); for (j = 0; j <= 8; j++) if (x == vt[j]) //如果是终结符 { if (x == '#' && ch != '#') //没有输入字符但栈内仍有字符 ，则继续判断栈内字符是否可为空 { flag = 0; break; } else { flag = 1; //进入终结符的判断 break; } } if (flag == 1) { if (x == '#' && ch == '#') finish = 1;//结束 if (x == ch) { printStack(); printRemain(); if(x == '#' && ch == '#') //特殊情况，栈内、字符串全为'#' { printf("成功\n\n"); printf("合法字符串!"); } else //其他情况:字符匹配 { printf("%c匹配\n", ch); ch = remain[++b]; //next字符 flag = 0; } } else { printStack(); printRemain(); printf("%c无法匹配\n\n", ch);/*输出出错终结符*/ printf("非法字符串!"); exit(1); } } else //非终结符 { for (j = 0; j <= 2; j++) if (x == vn[j]) { m = j; //分析表中匹配某一非终结符，行 break; } for (j = 0; j <= 5; j++) if (ch == vt[j]) { n = j; //分析表中匹配某一字符，列 break; } now = table[m][n]; if (now.begin != 'n') //有产生式 { printStack(); printRemain(); printf("%c->", now.begin); //输出所用的产生式 for (j = 0; j<now.length; j++) printf("%c", now.array[j]); printf("\n"); for (j = (now.length - 1); j >= 0; j--) //产生式逆序入栈 analyse[++top] = now.array[j]; if (analyse[top] == '$') //为空则不进栈 top--; //指向下一个字符 } else { printStack(); printRemain(); printf("%c无法匹配\n", x); //输出无法匹配的非终结符 printf("非法字符串!"); exit(1); } } } while (finish == 0); } void printStack() { int a; for(a=0; a <= top+1; a++) printf("%c", analyse[a]); //输出栈内元素 printf("\t\t"); } void printRemain() { int j; for (j = 0; j<b; j++) printf(" "); //对齐 for (j = b; j <= l; j++) printf("%c", remain[j]); //输出剩余字符串 printf("\t\t\t"); }我这里是将预测分析表写死了，如果想看FIRST集和FOLLOW集怎么去写，可以看这个博主的。
https://blog.csdn.net/nk_test/article/details/51476663
https://blog.csdn.net/qq_41634294/article/details/89280090
