编译原理实验报告材料(预测分析报告表方法)
- 格式:doc
- 大小:110.50 KB
- 文档页数:8
预测分析表方法
一、实验目的
理解预测分析表方法的实现原理。
二、实验内容:
编写一通用的预测法分析程序,要求有一定的错误处理能力,出错后能够使程序继续运行下去,直到分析过程结束。可通过不同的文法(通过数据表现)进行测试。
三、实验步骤
1.算法数据构造:
构造终结符数组:char Vt[10][5]={“id”,”+”……};
构造非终结符数组:char Vn[10]={ };
构造follow集数组:char *follow[10][10]={ } (可将follow集与预测分析表合并存放)
数据构造示例(使用的预测分析表构造方法1):
/*data1.h简单算术表达式数据*/
char VN[10][5]={"E","E'","T","T'","F"}; //非终结符表
int length_vn=5; //非终结符的个数
char VT[15][5]={"id","+","*","(",")","#"}; //终结符表
int length_vt=6; //终结符的个数
char Fa[15][10]={"TE'","+TE'","","FT'","*FT'","","(E)","id"};
//产生式表: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};
//预测分析表,-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]={ }
或
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”;
}
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$,运行预测分析程序,给出分析过程和每一步的分析结果。
输出形式参考下图($为结束符):