预测分析表方法
一、实验目的
理解预测分析表方法的实现原理。 二、实验内容：
编写一通用的预测法分析程序，要求有一定的错误处理能力，出错后能够使程序继续运行下去，直到分析过程结束。可通过不同的文法（通过数据表现）进行测试。
三、实验步骤
1．算法数据构造：
构造终结符数组：char Vt[10][5]={“id”,”+”……}； 构造非终结符数组：char Vn[10]={ };
构造follow集数组：char *follow[10][10]={ } (可将follow集与预测分析表合并存放)
数据构造示例（使用的预测分析表构造方法1）：
/*data1.h简单算术表达式数据*/
char VN[10][5]={\,\,\,\,\}; //非终结符表 int
char VT[15][5]={\,\,\,\,\,\}; //终结符表 int
char Fa[15][10]={\,\,\,\,\,\,\,\}; //产生式表:0:E->TE' 1:E'->+TE' 2:E'->空
// 3:T->FT' 4:T'->*FT' 5:T'->空 6:F->(E) 7:F->id int
analysis_table[10][11]={0,-1,-1,0,-2,-2,0,0,0,0,0,
-1,1,-1,-1,2,2,0,0,0,0,0, 3,-2,-1,3,-2,-2,0,0,0,0,0, -1,5, 4,-1,5, 5,0,0,0,0,0, 7,-2,-2,6,-2,-2,0,0,0,0,0};
length_vt=6; //终结符的个数 length_vn=5; //非终结符的个数
//预测分析表,-1表示出错，-2表示该行终结符的follow集合，用于错误处理，正数表示产生式在数组Fa中的编号，0表示多余的列。
（1） 预测分析表的构造方法1
给文法的正规式编号：存放在字符数组中，从0开始编号，正规式的编号即为该正规式在数组中对应的下标。如上述Fa数组表示存储产生式。
构造正规式数组：char P[10][10]={“E->TE’”,”E’->+TE’”,……..}; (正规式可只存储右半部分，如E->TE’可存储为TE’ ，正规式中的符号可替换，如可将E’改为M )
构造预测分析表：int analyze_table[10][10]={ } //数组元素值存放正规式的编号，-1表示出错
（2）预测分析表的构造方法2 可使用三维数组
Char analyze_table[10][10][10]={ }
1
或
Char *analyze_table[10][10]={ }
2．针对预测分析表构造方法1的查预测分析表的方法提示：
（1） 查非终结符表得到非终结符的序号no1 （2） 查终结符表得到终结符的序号no2
（3） 根据no1和no2查预测分析表得到对应正规式的序号
no3=analyze_table[no1][no2] ，如果no3=-1 表示出错。
（4） 根据no3查找对应的正规式Fa[no3] （5） 对正规式进行处理
3．错误处理机制
紧急方式的错误恢复方法（抛弃某些符号，继续向下分析） （1）栈顶为非终结符A，串中当前单词属于FOLLOW（A），则从栈中弹出A（此时可认为输入串中缺少A表示的结构），继续分析。 ---------错误编号为1
（2）栈顶为非终结符A，串中当前单词不属于FOLLOW（A），则可使串指针下移一个位置（认为输入串中当前单词多余），继续分析。----------错误编号为2
（3）栈顶为终结符，且不等于串中当前单词，则从栈中弹出此终结符（认为输入串中缺少当前单词）或者将串指针下移一个位置（认为串中当前单词多余）。在程序中可选择上述两种 观点中的一种进行处理。-------------错误编号3
因此error（）函数的编写方式可按如下方式处理 Error（int errornum） {
If（errornum==1）……………… Else if（errornum==2）…………… Else ………………..
//或者可用choose case语句处理 }
4．增加了错误处理的预测分析程序预测分析程序的算法：
将“#”和文法开始符依次压入栈中；
把第一个输入符号读入a； do{
把栈顶符号弹出并放入x中； if(x∈VT) {
if(x＝＝a) 将下一输入符号读入a; else error(3); } else
if(M[x,a]＝“x→y1y2…yk”) {
按逆序依次把yk、yk?1、…、y1压入栈中; 输出“x→y1y2…yk”; }
2
else if a?follow（x）error(1); else error（2）； //在前述的数据定义中查表为-2表示a?follow（x） }while(x!=“#”)
给定算术表达式文法，编写程序。 测试数据：
1．算术表达式文法
E→TE’
E’ → +TE’|- TE’|ε T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε F→(E) |id|num
给定一符合该文法的句子，如id+id*id$，运行预测分析程序，给出分析过程和每一步的分析结果。
输出形式参考下图（$为结束符）：
3
#include
char VN[5]={'E','e','T','t','F'}; //非终结符表 int length_vn=5; //非终结符的个数
char VT[10]={'*','l','m','+','-','(',')','i','n','#'}; //终结符表 l->/ m->% i->id n->num int length_vt=10; //终结符的个数
char Fa[12][6]={\//产生式表:0:E->Te 1:e->+Te 2:e->-Te 3:e->空
char F[12][6]={\int analysis_table[5][10]={-2,-2,-2,-2,-2,0,-1,0,0,-1, -2,-2,-2,1,2,-2,3,-2,-2,3, -2,-2,-2,-1,-1,4,-1,4,4,-1, 5,6,7,8,8,-2,8,-2,-2,8, -1,-1,-1,-1,-1,9,-1,10,11,-1}; # else
char VN[4]={'A','Z','B','Y'}; //非终结符表 int length_vn=4; //非终结符的个数
char VT[5]={'a','l','d','b','#'}; //终结符表 int length_vt=5; //终结符的个数
4
char Fa[6][6]={\
char F[6][6]={\int analysis_table[4][5]={0,-2,-1,-2,-1, 1,-2,2,-2,2, -2,-1,3,-2,-2, -2,5,-2,4,-2}; # endif
char stack[50]; int top=-1;
void initscanner() //程序初始化：输入并打开源程序文件 { int i=0; FILE *fp; if((fp=fopen(\ { printf(\ exit(0); } char ch=fgetc(fp); while(ch!=EOF) { aa[i]=ch; i++; ch=fgetc(fp); } fclose(fp); }
void push(char a) { top++; stack[top]=a; }
char pop() { return stack[top--]; }
int includevt(char x) { for(int i=0;i 5