2022年算术表达式的语法及语义分析程序设计 .pdf

《2022年算术表达式的语法及语义分析程序设计 .pdf》由会员分享，可在线阅读，更多相关《2022年算术表达式的语法及语义分析程序设计 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算术表达式的语法及语义分析程序设计概述1.1设计题目算术表达式的语法及语义分析程序设计。1.2设计目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.3设计任务内容(1)利用递归下降分析方法和思想对某些语句进行语法分析与语义分析，生成相应的中间代码。(2)学会正确运用语法规则，并能应用所学的方法解决存在的问题，给出语法分析方法及中间代码形式的描述、文法和属性文法的设计。2 设计环境与工具本课程设计程序采用VC+开发，其可执行文件能在Window界面上运行良好。3 设计原则3.1语法分析方法采用递归下降分析方

2、法进行语法分析。3.2中间代码形式描述在描述中间代码的时候，应用四元式。3.3文法和属性文法设计算术表达式的文法：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 22 页 -无符号整数数字 数字 标识符字母 字母数字 表达式 项 加法运算符项 项因子 乘法运算符因子 因子标识符无符号整数（表达式）加法运算符乘法运算符4 简要分析与概要设计4.1简要分析首先应该把用文字表示的文法改写为数学符号。（其中关于无符号整数和标识符，由于可以在词法分析的过程中给以确定，所以就不必抽象其表达式。）设：indentifer：标识符 digit:无符号整数 E：表达式 T：项 F：因子则一个简单的

3、术表达式的文法G1中包含以下产生式：E-E+E|E-E|E*E|E/E|(E)|indentifer|digit为了明确运算符的优先权（括号的优先权高于乘除法，乘除法的优先权高于加减法），可改写文法G1 如下：改写后的文法 G2:E-E+T|E-T|T T-T*F|T/F|F F-(E)|indentifer|digit为了避免左递归的发生，可进一步将文法改成：文法 GE：（1）E-+|-TG（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 22 页 -（8）F-indentifer|d

4、igit4.2概要设计由于程序在执行的过程中分为词法、语法、语义，故在程序设计的时候也按照这种方式，把整个程序分成三个大的部分，即词法分析部分，语法分析部分和语义分析部分。而且在各个部分的内部采用模块化设计，再分成各个小块，各自完成其相对应的功能。5源程序清单void yuyi_main()/语义分析主函数 cifa_p=cifa_head;yuyi_head=new yuyi;yuyi_head-next=NULL;yuyi_end=yuyi_head;coutnext);cout 语义分析产生的四元式如下：endl;coutendl-endl;advance();E1();yuyi_sys

5、_disp();coutendl-语义分析结束-endl;/*主函数*void main()/主函数 int len;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 22 页 -int f=1;coutendl 请输入一个算术表达式(请在一行内完成输入且每个项的长度不大于10)：endl;gets(str);len=strlen(str);strlen=;coutendl;system(pause);coutendl;cout*词法分析开始*endl;f=cifa_main();if(f=0)return;coutendl;system(pause);coutendl;cout*

6、语法分析开始*endl;f=yufa_main();if(f=0)return;coutendl;system(pause);coutendl;cout*语义分析开始*endl;yuyi_main();coutendl;system(pause);cout(E)|标识符|无符号整数 if(strcmp(cifa_p-word,()=0)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 22 页 -advance();strcpy(F_name,cifa_p-word);strcpy(E_name,F_name);E1();if (strcmp(cifa_p-word,)=0)adv

7、ance();strcpy(F_name,E_name);return(1);else cout ERRORtype=1|cifa_p-type=2)strcpy(F_name,cifa_p-word);advance();return(1);else return 0;int T1()/T-F*T|F/T|F yuyi*p=new yuyi;F1();strcpy(p-op1,F_name);if(strcmp(cifa_p-word,*)=0)advance();T1();p-next=NULL;p-op=*;strcpy(p-op2,T_name);T_name0=t;T_name1=+

8、count;T_name2=0;strcpy(p-result,T_name);yuyi_add(p);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 22 页 -return(1);else if(strcmp(cifa_p-word,/)=0)advance();T1();p-next=NULL;p-op=/;strcpy(p-op2,T_name);T_name0=t;T_name1=+count;T_name2=0;strcpy(p-result,T_name);yuyi_add(p);return(1);else strcpy(T_name,F_name);return

9、(1);int E1()/E-T+E|T-E|T yuyi*p=new yuyi;T1();strcpy(p-op1,T_name);if(strcmp(cifa_p-word,+)=0)advance();E1();p-next=NULL;p-op=+;strcpy(p-op2,E_name);E_name0=t;E_name1=+count;E_name2=0;strcpy(p-result,E_name);yuyi_add(p);return(1);else if(strcmp(cifa_p-word,-)=0)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 22 页 -a

10、dvance();E1();p-next=NULL;p-op=-;strcpy(p-op2,E_name);E_name0=t;E_name1=+count;E_name2=0;strcpy(p-result,E_name);yuyi_add(p);return(1);else strcpy(E_name,T_name);return(1);int yufa_main()/语法分析主程序 int n;cifa*p=new cifa;strcpy(p-word,#);/对词法分析产生的结果链表进行处理 p-type=-1;p-next=NULL;cifa_add(p);cifa_p=cifa_h

11、ead;coutnext);cout 的递归分析过程如下：endl;coutendl-endl;coutt 步骤 tt产生式 endl;advance();n=E();if(n=0)couttftt输入串不是该文法的一个句子！endl;coutendl-语法分析结束-endl;return(0);else if(n=1)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 22 页 -couttftt输入串是该文法的一个句子！endl;coutendl-语法分析结束-next=p;yuyi_end=p;return yuyi_head;void yuyi_sys_disp()/输出四元

12、式链表 yuyi*p;p=yuyi_head-next;while(p!=NULL)cout(top,top1,top2,tresultt)next;cout(E)|标识符|无符号整数子函数 int m;if(strcmp(cifa_p-word,()=0)couttf+tt(E)word,)=0)advance();return(1);else cout ERRORtype=1|cifa_p-type=2)/数字或是标识符 couttf+tt 标识符|无符号整数 *FS|/FS|子函数 int t,g;if(strcmp(cifa_p-word,*)=0)couttf+tt*FSword,/

13、)=0)couttf+tt/FSword,+)=0|(strcmp(cifa_p-word,-)=0)|(strcmp(cifa_p-word,#)=0)|(strcmp(cifa_p-word,)=0)couttf+tt FS 子函数 int t,g;couttf+tt FSword,+)=0)couttf+tt+TG word,-)=0)couttf+tt-TG word,)=0|strcmp(cifa_p-word,#)=0)couttf+tt +|-TG 子函数 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 22 页 -int t,g;if(strcmp(cifa_p

14、-word,+)=0)|(strcmp(cifa_p-word,-)=0)advance();couttf+tt+|-TGendl;t=T();if(t=0)return(0);g=G();if(g=0)return(0);else return(1);void yufa_zfc_disp(cifa*p)/输出字符串 while(p!=NULL)coutword;p=p-next;/cout next;int test(void)/识别相关符号 char temp3;int i=0;int type;switch(ch)case;:/识别;tempi+=ch;GetChar();if(ch=)

15、tempi+=;tempi=0;type=4;break;case+:/识别+tempi+=ch;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 22 页 -GetChar();if(ch=)tempi+=;tempi=0;type=3;break;case-:/识别-tempi+=ch;GetChar();if(ch=)tempi+=;tempi=0;type=3;break;case*:/识别*tempi+=ch;GetChar();if(ch=)tempi+=;tempi=0;type=3;break;case/:/识别/tempi+=ch;GetChar();if(ch

16、=)tempi+=;tempi=0;type=3;break;case(:/识别(tempi+=ch;GetChar();if(ch=)tempi+=;tempi=0;type=4;名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 22 页 -break;case):/识别)tempi+=ch;GetChar();if(ch=)tempi+=;tempi=0;type=4;break;default:coutch;cout 无法识别，出错！next=NULL;p-type=type;strcpy(p-word,temp);cifa_add(p);return(1);int cif

17、a_main()/词法分析主函数 int f;cifa_head=new cifa;cifa_head-type=-1;cifa_head-next=NULL;cifa_end=cifa_head;cout 单词种类定义如下：endlendl;cout 标识符的种类编码1:endlendl;cout 常数的种类编码2:endlendl;cout 运算的种类编码3:+,-,*,/endlendl;cout 界限符的种类编码4:(,),;endl;GetChar();名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 22 页 -notock();cout-endl词法分析结果如下：e

18、ndl;while(nn=a&ch=A&ch=0&ch=9)f=number();/数字串else f=test();/其他符号 if(f=0)return(0);cifa_disp(cifa_head);coutendl-词法分析结束-endl;return(1);int number(void)/识别数字 int type=2;int i=0;char temp10;while(0=ch&ch=9)tempi=ch;i+;GetChar();tempi=0;if(ch=)notock();else if(ch!=&ch!=+&ch!=-&ch!=;&ch!=*&ch!=/&ch!=(&ch

19、!=)couttemp 接错误后缀，出错 next=NULL;p-type=type;strcpy(p-word,temp);cifa_add(p);return(1);名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 22 页 -int alph(void)/识别标识符 int i=0;char temp10;int type=1;tempi=ch;i+;GetChar();while(ch=a&ch=A&ch=0&ch=9)tempi=ch;i+;GetChar();tempi=0;if(ch=)notock();else if(ch!=&ch!=+&ch!=-&ch!=;&

20、ch!=*&ch!=/&ch!=(&ch!=)couttemp 接错误后缀，出错 next=NULL;p-type=type;strcpy(p-word,temp);cifa_add(p);return(1);cifa*cifa_add(cifa*p)/在分析结果列表尾添加一个新接点 cifa_end-next=p;cifa_end=cifa_end-next;return cifa_head;void cifa_disp(cifa*cifa_head)/输出词法分析结果 cifa*p;p=cifa_head-next;while(p!=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-

21、第 15 页，共 22 页 -cout(ttypet,twordt)next;void GetChar()/取字符 ch=strnn;nn+;void notock()/去掉空格 if(ch=)while(ch=)GetChar();char E_name10,T_name10,F_name10,temp_name10;/在求四元式的时候用来传递信息yuyi*yuyi_add(yuyi*p);/在四元式链表末添加一个结点void yuyi_sys_disp();/输出四元式链表int E1();/E-T+E|T-E|T int T1();/T-F*T|F/T|F int F1();/F-(E)

22、|标识符|无符号整数void yuyi_main();/语义分析主函数/*词法分析部分*/*语义分析部分数据结构及函数定义*struct yuyi /语义结构体 char op;/操作符 char op110;/第一个操作数 char op210;/第二个操作数 char result10;/结果 yuyi *next;yuyi*yuyi_head,*yuyi_end,*yuyi_q,*yuyi_vt;/yuyi队列/*语法分析部分函数定义*void advance();/取词法分析产生列表中的结点作语法分析int E();/E-+|-TG 子函数int G();/G-+TG|-TG|子函数i

23、nt T();/T-FS 子函数int S();/S-*FS|/FS|子函数int F();/F-(E)|标识符|无符号整数子函数int yufa_main();/语法分析主函数名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 22 页 -cifa*cifa_add(cifa*p);/在分析结果列表尾添加一个新接点void cifa_disp(cifa*cifa_head);/输出词法分析结果void GetChar();/取字符void notock();/去掉空格int alph(void);/识别标识符int number(void);/识别数字int test(void)

24、;/识别相关符号int cifa_main();/词法分析主函数#include#include#include#include#include#include#include#include#include#include char str100;/输入的算术表达式字符串char ch;int nn=0;/字符串计数器int f=0;char count=0;/四元式临时变量计数器/*词法分析部分数据结构及函数定义*struct cifa /词法结构体 int type;/类型 char word10;/字符串内容 cifa*next;cifa*cifa_head,*cifa_end,*ci

25、fa_p;/cifa 队列1语言子集的词法描述：设文法 GE:E:=E+T|T名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 22 页 -T:=T*F|F F:=(E)|i2程序的功能按照文法符号（终结符和非终结符）的优先关系确定句柄，通过不断的归约，或是移进来进行分析。3算法描述算符优先分析的基本思想是只规定算符(广义为终结符之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号

26、栈中的符号和剩余的输入符号构成句型的最左素短语。在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子，解决了前面提到的两个问题，即：1)可以只根据相邻运算符的优先关系，就能方便地并且唯一地确定归约的“句柄”；2)可以用来分析二义性文法所产生的语言。4源程序清单void main()cout 设文法 GE:endl;cout tE:=E+T|Tendl;cout tT:=T*F|Fendl;cout tF:=(E)|iendl;coutendl文法 GE合法句子举例:(i+i)*i;coutendl*endlendl;coutstr;len=s

27、trlen(str);strlen=#;名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 22 页 -coutendltt符号串 str 分析过程如下：endlendl;cout-endl;cout 符号栈 S t t 关系 t 输入流 t t 最左素短语 endl;opg();coutendlendl 按任意数字或字母键，回车退出!len;void opg(void)/分析过程 char l=;char ch1;char lsdy4;int i=0;int p;s0=#;cout s t t l t str;GetChar();while(ch!=#|sm-1!=E|s3!=)

28、if(l=)/移进 coutendl;push();else if(l=)/移进 cout)/寻找最左素短语 for(i=0;i 4;i+)lsdyi=;while(l!=A&sp-1=Z)ch1=sp-2;p=p-2;名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 22 页 -else ch1=sp-1;p=p-1;l=search(ch1,ch);fl=p+1;for(i=0;i (m-p-1);i+)/找到最左素短语的最左字符 lsdyi=s p+1;sp+1=;p+;lsdy i=sm-1;lsdy +i=0;sm-1=;m=fl;for(i=0;i=5;i+)/查找产

29、生式左部 if(strcmp(keyi,lsdy)!=0)ch=v i;push();cout tt lsdy endl;break;n-;else if(l=)/分析结束，不是文法句子 coutendl-endl;cout不是该文法的一个句子！endl;return;if(l=Y)/分析结束，是文法句子 coutendl-endl;coutendl输入字符串是该文法的一个句子！=A&ch1=Z)/如果不是非终结符，跳到前一个 ch1=sm-2;p=m-2;else p=m-1;l=search(ch1,ch);cout s t t lt str;coutendl-endl;coutendl输入字符串是该文法的一个句子！,Y,;char*key6=E+T,T,T*F,F,(E),i;char v6=E,E,T,T,F,F;char str100;int n=0;char ch;int m=1;int fl;char s20;int len;#include stdio.h#include ctype.h#include math.h#include iostream.h#include string.h 名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 22 页 -