




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、精选优质文档-倾情为你奉上实验三 算符优先分析算法的设计与实现(8学时)一、 实验目的根据算符优先分析法,对表达式进行语法分析,使其能够判断一个表达式是否正确。通过算符优先分析方法的实现,加深对自下而上语法分析方法的理解。二、 实验要求1、输入文法。可以是如下算术表达式的文法(你可以根据需要适当改变): EE+T|E-T|TTT*F|T/F|FF(E)|i2、对给定表达式进行分析,输出表达式正确与否的判断。程序输入/输出示例:输入:1+2;输出:正确输入:(1+2)/3+4-(5+6/7);输出:正确输入:(1-2)/3+4输出:错误输入:1+2-3+(*4/5)输出:错误三、实验步骤1、参考
2、数据结构char *VN=0,*VT=0;/非终结符和终结符数组char firstvtNN,lastvtNN,tableNN;typedef struct /符号对(P,a)char Vn;char Vt; VN_VT;typedef struct /栈 VN_VT *top; VN_VT *bollow; int size;stack;2、根据文法求FIRSTVT集和LASTVT集给定一个上下文无关文法,根据算法设计一个程序,求文法中每个非终结符的FirstVT 集和LastVT 集。算符描述如下:/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF n
3、ot FP,a then begin FP,a = true; /(P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P和终结符 a do FP,a = false for 对每个形如 Pa或 PQa的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈,记为(Q,a) for 对每条形如 PQ的产生式 do insert(P,a) end; end.同理,可构造计算LASTVT的算法。3、构造算符优先分析表依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下:for 每个形
4、如 P->X1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi < a ; if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 ; end4、构造总控程序 算法描述如下: stack S; k = 1; /符号栈S
5、的使用深度 Sk = # REPEAT 把下一个输入符号读进a中; If Sk VT then j = k else j = k-1; While Sj > a do Begin Repeat Q = Sj; if Sj-1 VT then j = j-1 else j = j-2 until Sj < Q; 把Sj+1Sk归约为某个N,并输出归约为哪个符号; K = j+1; Sk = N; end of while if Sj < a or Sj = a then begin k = k+1; Sk = a end else error /调用出错诊察程序 until a
6、 = #5、对给定的表达式,给出准确与否的分析过程6、给出表达式的计算结果。(本步骤可选作)四、实验报告要求1.写出编程思路、源代码(或流程图);2.写出上机调试时发现的问题,以及解决的过程;3.写出你所使用的测试数据及结果;4.谈谈你的体会。5.上机8小时,完成实验报告2小时。五、源代码 #include<iostream.h>#include<string.h>#include<stdio.h>typedef struct char R; char r;
7、; int flag;array;typedef struct char E; char e;charLode;typedef struct charLode *base; int top;charstack;char str8080,arr8080,brr8080;array F20;int m,kk,p,ppp,FF=1;char r10;int crr2020,FLAG=
8、0;char ccrr1120,ccrr2201;void Initstack(charstack &s)/定义栈 s.base=new charLode20; s.top=-1;void push(charstack &s,charLode w) /入栈 s.top+; s.bases.top.E=w.E; s.bases.top.e=w.e;void pop(char
9、stack &s,charLode &w) /出栈 w.E=s.bases.top.E; w.e=s.bases.top.e; s.top-;int IsEmpty(charstack s) /判断是否到栈顶 if(s.top=-1) return 1; &
10、#160; else return 0;int IsLetter(char ch) /判断是不是大写字母(非终结符) if(ch>='A'&&ch<='Z') return 1; else re
11、turn 0;/judge1是判断是否是算符文法:若产生式中含有两个相继的非终结符则不是算符文法int judge1(int n) int j=3,flag=0; for(int i=0;i<=n;i+) while(strij!='0')
12、0; char a=strij; char b=strij+1; if(IsLetter(a)&&IsLetter(b) /两个非终结符相连,不是算符文法
13、60; flag=1; break;
14、160; else j+;
15、 if(flag=1) /根据flag设定返回值 return 0; else &
16、#160; return 1;/judge2是判断文法G是否为算符优先文法:若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n) for(int i=0;i<=n;i+) if(stri3=''|FLAG=1)/''代表空
17、160; cout<<"文法G不是算符优先文法!"<<endl; FF=0; break;
18、160; if(i>n) cout<<"文法G是算符优先文法!"<<endl;/search1是查看存放终结符的数组r中是否含有重复的终结符int search1(cha
19、r r,int kk,char a) for(int i=0;i<kk;i+) if(ri=a) break; if(i=kk)
20、160; return 0; else return 1;/createF函数是用F数组存放每个终结符与非终结符和组合,并且值每队的标志位为0;F数组是一个结构体void createF(int n) int k=0,i=1;char g;
21、60; char t10;/t数组用来存放非终结符 t0=str00; while(i<=n) if(tk!=stri0)
22、 k+; tk=stri0; g=tk; i+;
23、0; else i+; kk=0; char c; for(i=0;i<=n;i+) int j=3;
24、0;while(strij!='0') c=strij; if(IsLetter(c)=0)
25、160; if(!search1(r,kk,c) rkk=c; &
26、#160; kk+;/r数组用来存放终结符 j+; &
27、#160; m=0; for(i=0;i<k;i+) for(int j=0;j<kk-1;j+) Fm.R=ti;
28、 Fm.r=rj; Fm.flag=0; m+; /search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1void search(charLode
29、w) for(int i=0;i<m;i+) if(Fi.R=w.E&&Fi.r=w.e) Fi.flag=1;break;
30、160; void FirstVT(int n)/求FirstVT charstack sta; charLode w; int i=0; Initstack(sta); while(i<=n) int k=3;
31、 w.E=stri0; char a=strik; char b=strik+1; if(!IsLetter(a) /产生式的后选式的第一个字符就是终结符的情况
32、60; w.e=a; push(sta,w); search(w);
33、; i+; else if(IsLetter(a)&&b!='0'&&!IsLetter(b) /产生式的后选式的第一个字符是非终结符的情况
34、; w.e=b; push(sta,w); search(w); &
35、#160; i+; else i+; charLode ww; while(!IsEmpty(sta) &
36、#160; pop(sta,ww); for(i=0;i<=n;i+) w.E=stri0; if(stri3
37、=ww.E&&stri4='0') w.e=ww.e;
38、 push(sta,w); search(w); break;
39、160; p=0;int k=1;i=1; while(i<m) if(Fi-1.flag=1)
40、 arrp0=Fi-1.R; arrpk=Fi-1.r; while(Fi.flag=0&&i<m)
41、160; i+; if(Fi.flag=1) if(Fi.R=arrp0)
42、160; k+; else arrpk+1='0'p+;k=1; i+; &
43、#160; void LastVT(int n)/求LastVT charstack sta; charLode w; for(int i=0;i<m;i+) Fi.flag=0; i=0; Initstack(sta);
44、 while(i<=n) int k=strlen(stri); w.E=stri0; char a=strik-1; char b=strik-2;
45、; if(!IsLetter(a) w.e=a; push(sta,w);
46、160; search(w); i+; else if(IsLetter(a)&&!IsLetter(b)
47、160; w.e=b; push(sta,w); search(w);
48、0; i+; else i+; charLode ee; while(!IsEmpty(sta)
49、0; pop(sta,ee); for(i=0;i<=n;i+) w.E=stri0; if(stri3=ee
50、.E&&stri4='0') w.e=ee.e;
51、60;push(sta,w); search(w); int k=1;i=1
52、; ppp=0; while(i<m) if(Fi-1.flag=1) brrppp0=Fi-1.R;
53、0; brrpppk=Fi-1.r; while(Fi.flag=0&&i<m) i+;
54、160; if(Fi.flag=1) if(Fi.R=arrppp0) k+;
55、 else brrpppk+1='0'ppp+;k=1; i+; void createYXB(int n)/构造优先表 int i,
56、j; for(j=1;j<=kk;j+) ccrr10j=rj-1; for( i=1;i<=kk;i+) ccrr2i0=ri-1; for(i=1;i<=kk;i+) &
57、#160;for(j=1;j<=kk;j+) crrij=0; int I=0,J=3; while(I<=n) &
58、#160; if(strIJ+1='0') /扫描右部 I+;
59、 J=3; else
60、0; while(strIJ+1!='0') &
61、#160; char aa=strIJ; char bb=strIJ+1; &
62、#160; if(!IsLetter(aa)&&!IsLetter(bb)/优先及等于的情况,用1值表示等于
63、; for(i=1;i<=kk;i+)
64、160; if(ccrr2i0=aa) break;
65、 for(j=1;j&l
66、t;=kk;j+)
67、60; if(ccrr10j=bb) break; &
68、#160; if(crrij=0)
69、160; crrij=1; else &
70、#160; FLAG=1;
71、 I=n+1;
72、 J+; if(!IsLetter(aa)&&IsLetter(bb)&&str
73、IJ+2!='0'&&!IsLetter(strIJ+2)/优先及等于的情况
74、 for(i=1;i<=kk;i+)
75、60; if(ccrr2i0=aa) break; &
76、#160; for(int j=1;j<=kk;j+) &
77、#160;
78、if(ccrr10j=strIJ+2) break;
79、; if(crrij=0)
80、 crrij=1; else
81、; FLAG=1;
82、0; I=n+1;
83、0; if(!IsLetter(aa)&&IsLetter(bb)/优先及小于的情况,用2值表示小于
84、60; for(i=1;i<=kk;i+) &
85、#160; if(aa=ccrr2i0)
86、0; break;
87、0; for(j=0;j<=p;j+)
88、60; if(bb=arrj0)
89、160; break;
90、160; for(int mm=1;arrjmm!='0'mm+) &
91、#160; for(int pp=1;pp<=kk;pp+)
92、0; if(ccrr10pp=arrjmm)
93、60; break;
94、60; if(crripp=0)
95、60; crripp=2;
96、 else FLAG=1;I=n+1;
97、
98、 J+;
99、60; if(IsLetter(aa)&&!IsLetter(bb)/优先及大于的情况,用3值表示大于 &
100、#160; for(i=1;i<=kk;i+)
101、0; if(ccrr10i=bb) break;
102、160; for(j=0;j<=ppp;j+)
103、;
104、;if(aa=brrj0) break;
105、; for(int mm=1;brrjmm!='0'mm+)
106、; for(int pp=1;pp<=kk;pp+)
107、160;
108、160; if(ccrr2pp0=brrjmm) break; &
109、#160; &
110、#160; if(crrppi=0) crrppi=3;
111、0; else FLAG=1;I=n+1;
112、0; J+; &
113、#160; /judge3是用来返回在归约过程中两个非终结符相比较的值int judge3(char s,char a) int i=1,j=1; while(ccrr2i0!=s) i+;
114、; while(ccrr10j!=a) j+; if(crrij=3) return 3; else if(crrij=2) &
115、#160; return 2; else if(crrij=1) return 1;
116、60; else return 0;void print(char s,char STR20,int q,int u,int ii,int k)/打印归约的过程 cout<<u<<"
117、160; " for(int i=0;i<=k;i+) cout<<si; cout<<" " for(i=q;i<=ii;i+)
118、60; cout<<STR0i; cout<<" "void process(char STR20,int ii)/对输入的字符串进行归约的过程 cout<<"步骤"<<" "<<"符号栈&
119、quot;<<" "<<"输入串"<<" "<<"动作"<<endl; int k=0,q=0,u=0,b,i,j; char s40,a; sk='#'
120、; print(s,STR,q,u,ii,k); cout<<"预备"<<endl; k+; u+; sk=STR0q; q+; print(s,STR,q,u,ii,k); cout<<"移进&quo
121、t;<<endl; while(q<=ii) a=STR0q; if(!IsLetter(sk) j=k; else j=k-1;
122、160; b=judge3(sj,a); if(b=3)/大于的情况进行归约 while(IsLetter(sj-1)
123、0; j-; for(i=j;i<=k;i+) si='0'
124、0;k=j; sk='N' u+; print(s,STR,q,u,ii,k);
125、60; cout<<"归约"<<endl; else if(b=2|b=1)/小于或等于的情况移进
126、60; k+; sk=a; u+; q+; &
127、#160; print(s,STR,q,u,ii,k); if(s0='#'&&s1='N'&&s2='#') cout<<"接受"&
128、lt;<endl; else cout<<"移进"<<endl; else
129、; cout<<"出错"<<endl; break; if(s0='#'&&s1='N
130、39;&&s2='#') cout<<"归约成功"<<endl; else cout<<"归约失败"<<endl;void main() int n,i,j; cout<<"请输入你要定义的文法G的产生式的个数n:"
131、 cin>>n; cout<<"请输入文法产生式:"<<endl; for(i=0;i<n;i+) gets(stri); j=strlen(stri);
132、; strij='0' stri0='Q' /最末行添加扩展 stri1='-' stri2='>' stri3='
133、;#' stri4=str00; stri5='#' cout<<"你定义的产生式如下:"<<endl; stri6='0' for(i=0;i<=n;i+) cout<<s
134、tri<<endl; if(judge1(n)=0) /判断文法G是否为算符文法 cout<<"文法G不是算符文法!"<<endl; if(judge1(n)=1) cout<<"文法G是算符文法!"<<endl; createF(n); FirstVT(n); LastVT(n);
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 水务运行管理模式创新计划
- 加强供应链管理的具体计划
- 急诊工作的秘诀计划
- 提升信息技术应用能力的方法计划
- 汽车故障诊断技术 课件 学习任务9、10 车辆转向沉重故障的检修、传动轴异响故障的检修
- 蒙班一日流程
- 质量管理寓言
- 2024年新人教版一年级上册数学 三 认识立体图形 第3课时 认识立体图形
- 安全技术防范培训
- 上学期学习总结
- DLT 5285-2018 输变电工程架空导线(800mm以下)及地线液压压接工艺规程
- 消防员训练伤的预防及恢复课件
- 研发综合项目管理新规制度
- GB/T 43860.1220-2024触摸和交互显示第12-20部分:触摸显示测试方法多点触摸性能
- 密封条范文模板(A4打印版)
- 大学生生涯发展报告新能源汽车
- 医疗机构制剂管理规范
- JBT 11699-2013 高处作业吊篮安装、拆卸、使用技术规程
- JJG 257-2007浮子流量计行业标准
- 电力系统中的谐振过电压
- 2023年 新版评审准则质量记录手册表格汇编
评论
0/150
提交评论