python版本(词法分析器整合预测分析表): 编译原理预测分析表一篇解决你所有问题(python版)
实验 预测分析表方法
一、实验目的
理解预测分析表方法的实现原理。
二、实验内容
编写一通用的预测法分析程序,要求有一定的错误处理能力,出错后能够使程序继续运行下去,直到分析过程结束。可通过不同的文法(通过数据表现)进行测试。
三、实验内容提示
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"};
//产生式表: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集合,用于错误处理
(1) 预测分析表的构造方法1 给文法的正规式编号:存放在字符数组中,从0开始编号,正规式的编号即为该正规式在数组中对应的下标。 构造正规式数组: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][10]={ }
2.针对预测分析表构造方法1的查找方法提示:
(1) 查非终结符表得到非终结符的序号no1 (2) 查终结符表得到终结符的序号no2 (3) 根据no1和no2查正规式表得到对应正规式的序号no3=analyze_table[no1][no2] ,如果no3=-1 表示出错。 (4) 根据no3查找对应的正规式P[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 afollow(x)error(1 ); else error(2);
}while(x!=“#”)
三.实验要求 给定算术表达式文法,编写程序。 测试数据: 1.算术表达式文法
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num
给定一符合该文法的句子,如id+id*id#,运行预测分析程序,给出分析过程和每一步的分析结果。 输出形式参考下图:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200425154116898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTI1MDg5,size_16,color_FFFFFF,t_70)
四、编写实验报告
实验分析:
1.将原算术表达式方法改写为LL(1)文法为:
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num
2.求出每个非终结符的FIRST和FOLLOW集;
非终结符FIRETFOLLOWE{ (,id,num }{ #,) }E’{ +,-,ε }{ #,) }T{(,id,num}{ +,-,#,) }T’{ *,/,%,ε }{ +,-,#,) }F{ (,id,num }{ *,/,%,+,-,# ,)}
3.构造预测分析表
坐标0123456789非\终结符*/%+-()idnum#0 Eerror(2)error(2)error(2)error(2)error(2)E→ TE’error(1)E→ TE’E→ TE’error(1)1 E’error(2)error(2)error(2)E’ → +TE’E’ → -TE’error(2)E’ → εerror(2)error(2)E’ → ε2 Terror(2)error(2)error(2)error(1)error(1)T→FT’error(1)T→FT’T→FT’error(1)3 T’T’ →*FT’T’ →/FT’T’ →%FT’T’ →εT’ →εerror(2)T’ →εerror(2)error(2)T’ →ε4 Ferror(1)error(1)error(1)error(1)error(1)F→(E)error(1)F→idF→numerror(1)
4.绘制编程流程图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200425165536823.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTI1MDg5,size_16,color_FFFFFF,t_70)
5.c++代码实现
#include
#include
#include
#include
using namespace std;
#define TT 0
char aa[20]=" ";//用来存储从txt文件中读取的字符串
int pp=0;//用来标记字符
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]={"Te","+Te","-Te","NULL","Ft","*Ft","nFt","mFt","NULL","(E)","i","n"};
//产生式表 :0:E->Te 1:e->+Te 2:e->-Te 3:e->空
char F[12][6]={"E->","E'->","E'->","E'->","T->","T'->","T'->","T'->","T'->","F->","F->","F->"};
//构造预测分析表,-1表示出错,-2表示该行终结符的follow集合,用于错误处理
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};
char stack[50];
int top=-1;
// 程序初始化:输入并打开源程序文件
void initscanner()
{
int i=0;
FILE *fp;
if((fp=fopen("a.txt","r"))==NULL){
printf("Open error!");
exit(0);
}
char ch=fgetc(fp);
while(ch!=EOF){
aa[i]=ch;//将字符依次存入aa数组
i++;
ch=fgetc(fp);
}
fclose(fp);
}
//字符入栈
void push(char a)
{
top++;
stack[top]=a;
}
//字符出栈 ,弹出栈顶元素
char pop()
{
return stack[top--];
}
//字符x是否是终结符
int includevt(char x)
{
for(int i=0;i
int i,j;
//非终结符
for(i=0;i
// printf("%s\t\t",stack);
if(flag==0)
x=pop(); //把栈顶符号弹出并放入 x 中
flag=0;
printf("%c\t\t\t\t%c\t\t",x,a);
//如果a是终结符
if(includevt(a)==1)
{
if(includevt(x)==1)
{
if(x==a)
{
if(a=='#')
{
flagg=1;
printf(" 结束 \n");
}
else printf(" 匹配终结符 %c\n",x);
pp++;
a=aa[pp]; //将下一输入符号读入 a;
}
else
{
flag=1;
printf(" 出错 ,跳过 %c\n",a);
pp++;
a=aa[pp];
}
}
//存在该表达式
else if(includean(x,a)>=0)
{
//获取分析表对应坐标数据
int h=includean(x,a);
printf(" 展开非终结符 %s%s\n",F[h],Fa[h]);
int k;
for(k=0;k
while(k!=0) //按逆序依次把 yk、yk?1、 , 、 y1 压入栈中
{
k--;
push(Fa[h][k]);
}
}
}
//-1表示出错
else if(includean(x,a)==-1)
{
flag=1;
printf(" 出错 ,从栈顶弹出 %c\n",x);
x=pop();
}
//
else
{
flag=1;
printf(" 出错 ,跳过 %c\n",a);
pp++;
a=aa[pp];
}
}
else
{
flag=1;
printf(" 出错 ,跳过 %c\n",a);
pp++;
a=aa[pp];
}
}while(x!='#');
if(flagg==0)
{
printf("%c\t\t\t%c\t",x,a);
printf(" 结束 \n");
}
}
int main()
{
printf(" 语法分析工程如下 :\n");
initscanner();
cout |