预测分析表程序报告

1、m第欷天2嘻再慌课程实验报告课程名称：编译原理教程实验项目名称： 预测分析表方法专业班级：吓、"0、姓名：r、"0、学号：吓、吓、卜"0、指导教师：吓、宀 兀成时间：2011 年*月* 日计算机科学与工程系实验78预测分析表方法一、实验目的理解预测分析表方法的实现原理。二、实验内容：编写一通用的预测法分析程序，要求有一定的错误处理能力，岀错后能够使 程序继续运行下去，直到分析过程结束。可通过不同的文法(通过数据表现)进 行测试。三、实验内容提示1. 算法数据构造：(1) 预测分析表的构造方法1构造正规式数组:char p1010二“e->te' ”，

2、” e' -+te' ”， (正规式可只存储右半部分，如e->te'可存储为te',正规式中的符号可替换， 如可将e，改为m )构造预测分析表：int analyze_table10 10 = /数组元素值存放正规式的编号，-1表示出错(2) 预测分析表的构造方法2可使用三维数组charanalyzc_tablce101010=或char*analyze_table1010=2. 针对预测分析表构造方法1的查预测分析表的方法提示：(1) 查非终结符表得到非终结符的序号nol(2) 查终结符表得到终结符的序号no2(3) 根据nol和no2查预测分析表得到对

3、应巫规式的序号 no3=analyze_tablenol no2,如果 no3=-l 表示出错。(4) 根据no3查找对应的正规式fano3(5) 对正规式进行处理3 错误处理机制紧急方式的错误恢复方法(抛弃某些符号，继续向下分析)(1) 栈顶为非终结符a,串中当前单词属于follow (a),则从栈中弹出a(此时可认为输入串中缺少a表示的结构)，继续分析。错误编号为1(2) 栈顶为非终结符a,串中当前单词不属于follow (a),则可使串指针下移一个位置(认为输入串屮当前单词多余)，继续分析。错误编号为2(3) 栈顶为终结符，且不等于串中当前单词，则从栈中弹出此终结符(认为输入串中缺少当前

4、单词)或者将串指针下移一个位置(认为串中当前单词多 余)。在程序中可选择上述两种 观点中的一种进行处理。错误编号34 增加了错误处理的预测分析程序预测分析程序的算法：将”和文法开始符依次压入栈中；把第一个输入符号读入a；do 把栈顶符号弹出并放入x中； if(xevt)if (x=a)将下一输入符号读入a; else error (3); else if (mx, a = “xfyly2yk” )按逆序依次把yk、yk-l>、yl压入栈中；输出“x->yly2yk” ;else if ag fol low (x) error (1) ; else error (2)； whilc(

5、x!= )三.实验要求给定算术表达式文法，编写程序。 测试数据：1. 算术表达式文法e-te'e， f +te'-te，£t-> ft't， ->*ft，/ ft'%ft£f-> (e)idnum给定一符合该文法的句子，如id+id*id$,运行预测分析程序，给出分 析过程和每一步的分析结果。2. 作业3. 10文法 四.方法实现源程序：# include<stdio.h># include<string>#include<stdlib.h># include<iostream>

6、;using namespace std;#define maxsize 100typedef char datatype;typedef struct/定义栈datatype datafmaxsize; int top;jseqstack;seqstack *s;int sign=0;int numl,num2,num3;终结符表int length_vn=5;/非终结符个数 charvt15，呻”丁 int length_vt=10; 终结符个数charfa155=“tmt+tm“,”tm”,”“,“fn“,“”,” *fn“,'7fn“,“fn”,”(e)“,“i”,“n”; 产

7、生式表 1:e->tm,2:m->+tm,3：m->-tm,4:m-> ,5:e- >fn,6:n-> ,7:n>*fn,&f>/fn,9:f>%fn,1 0:f->(e),ll:f->i,12:f->n/m=e*,n=t',i=id,n=numchar vn10"5=”e”,”m”,”t”,”n”,"f”;/ 非 charpa1510=“e>tm”,”m>+tm“,“m>tm”, nm-> 空空“,“n->*fn“,”f->/fn：f>%fn”

8、,”f->(e)”,“f ->idh；t->numh);int analysis_table 10ll=l,l,l,l,l,l,2,l,l,l,0,2,3, 1,-1,-1,-1,4,-1,-1,4,0,-2,-2,-1,-1,-1,5,-2,5,5,-1,0,6,6,7,&9,l,6,l,l,6,0,-2,-2,-2,-2,-2,10,-2,11,12,-1,0;预测分 析表/*char vt15 5=%',”b”,”d”,t,”#”;int length_vt=5;charvn10二“a”,”c”,”b”,“d”;int length_vn=4;charf

9、a155=”ac”,“abl”,”“,”dd“,“bd“,“”; char pa1510=,a->acm,c->abr,；,c->空 tb->dd“,”d>bd“,”d-> 空”;int analysis_table45=l-l,-2,-1,-1,2,-1,3,-1,3,-1 ,-l,4,-2,-l,1,5,1,6,1,；*/seqstack *init_seqstack()/ 栈初始化 printf(hs 间不足 n“); return null;elses->top=-l; return s;void push_seqstack(seqstack

10、*s,char x)入 栈讦(s->top=maxsize-l) printf('栈满，不能入栈! ");/retum 0;elses->top+; s->datas->topl=x;/return 1;char pop_seqstack(seqstack *s)岀栈if(s->top=-l)printfc栈空，不可出栈！ n);/ return 0；exit(o);)elsechar x=s->datas->top;s->top;return x;/seqstack *s; s=new seqstack; if(!s)data

11、type top_seqstack(seqstack *s) 取栈顶元素if(s->top=-l) return 0;elsereturn s->data fs->top ;int bufvt(char s)接收终结符并保存在vt数组中int i=0;while(i<15&&s!=rnr)if(vti0=s)return 1;elsei+；return 0;int bufvn(char s)接收非终结符并保存在vn数组中int i=0;while(i< 10&&s !=rnr)if(vni0=s)return 1;elsei+；re

12、turn 0;int vtt(char s) 终结符匹配 int i=();while(vti0!=s)i+；return i;int vnn(char s)非终结符匹配int i=0;while(vni0!=s&&i<length_vn) i+；if(i=length_vn)return -1;return i;void eitor(int eitornum,char x)if(errornum=l)printfc*第一种错误，弹出栈顶元 素n“)；pop_seqstack(s);else if(errornum=2)printfcf第二种错误，跳 过 cn”,x);e

13、lseif(x=#)printfc1第三种错误，弹出栈顶元素n");pop_seqstack(s);elseprintf(”第三种错误，指针下移弹出栈顶元素n“)；pop_seqstack(s);sign+;if(!bufvt(str2sign)&&!bufvn(x)void main()char strl20,str220;int i=0;printf(”请输入所要分析的文件名：“);scanf("%s",strl);file *fp;if(fp=fopen(strl ；'rn)=null)printf(”没有这个文件！ nh); exi

14、t(o);while(!feof(fp)str2i=fgetc(fp);i+；str2i=,0,;fclose(fp);lnit_seqstack();s->top 二 1;push_seqstack(s, '#*);push_seqstack(s,'e');char x;printf(h语法分析过程如下:nm);prhnf(”栈顶元素賊当前单词记号2 动作)；prin tf("= n”)；doprintf(h%cttt%sttt%s",x,str2lsign);printf("当前字符不合 法!);else if(bufvt(str

15、2sign) if(x=str2sign) printf(h%cttt%cttt",x,str2signj);printf(h匹配终结 符 %cn",str2sign);pop_seqstack(s); sign+;elsebufvn(x);num 1 =vtt(str2sign);num2=vnn(x);char arr 10; if(num2!=-l) n um3=analysis_tablenum2 numl;if(num3=-l)printf(h%cttt%cttt,x,str2sign);error(l,x);if(num3=-2)printf(m%cttt%ct

16、ttm,x,str2signj);x=top_seqstack(s); if(x=#)goto loop;elseerror(2,str2sign);sign+；elsepintfc%cttt%cttr,x,st2signd； printf(u 展 开非终结符s，继续nh,panum3-l);pop_seqstack(s);intj;for(j=0;j<5&&fanum3-lj!=,0,;j+)elseprintf("%cttt%cttt",x,str2sign);error(3,str2sig n);/pop_seqstack(s);arr j =f

17、anum3 -1 j ; int k; k=j-l;for(;k>=0;k-)while(x!二#);loop:pr i n tf(" %cttt%cttt", x ,str2 sign ); printf(”结束 n“); exit(o);push_seqstack(s,arrk);实验结果：1.文法一：鑑輕解文用席羅动作翳si豔1囂囂霧11吉吉吉寸吉宇口匣口士呈口摩呈口匣呈口忌呈口匣呈口 冬冬冬吉冬吉冬吉冬冬冬吉冬冬士 口冬冬吉冬冬吉冬冬 三三 hl、jji、jjxj二三 mmanll一 haulljxj 三 m 冬=二二 二二二二一纟tt纟ttt纟二一二一二一纟

18、二一三纟二二二纟二二二纟二一三e->tm.继纟卖 继续 符f-xd,继续符nxfn,继纟卖t->fn符fxe>.继纟卖 <符 e->tm_，继纟卖笆t->fn.继纟卖 特f-xd.继续寸n>tm匡t->fn.继续寺f-xd.继续文法一正确结果p aben. txt -记事本文件(£)編辑g)格式)i (i + i) #文法一正确句子动作h:xaben.txt当前单词记号臨驢餌文件各栈顶兀素纟纟纟纟纟纟t>_e纟纟纟纟纟纟素素 元元续续 顶顶继继 r>聲儼密n f:浄共浄； 知g;?;h至口瓦h至££:h座s;h匱呑產h