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

算术表达式的语法及语义分析程序设计概述1.1设计题目算术表达式的语法及语义分析程序设计。1.2设计目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.3设计任务内容(1)利用递归下降分析方法和思想对某些语句进行语法分析与语义分析，生成相应的中间代码。(2)学会正确运用语法规则，并能应用所学的方法解决存在的问题，给出语法分析方法及中间代码形式的描述、文法和属性文法的设计。2设计环境与工具本课程设计程序采用VC+开发，其可执行文件能在Window界面上运行良好。3设计原则3.1语法分析方法采用递归下降分析方法进行语法分析。3.2中间代码形式描述在描述中间代码的时候，应用四元式。3.3文法和属性文法设计算术表达式的文法：无符号整数 数字数字标识符 字母字母数字表达式项加法运算符项项 因子乘法运算符因子因子 标识符无符号整数（表达式）加法运算符 乘法运算符 4简要分析与概要设计4.1简要分析首先应该把用文字表示的文法改写为数学符号。（其中关于无符号整数和标识符，由于可以在词法分析的过程中给以确定，所以就不必抽象其表达式。）设：indentifer：标识符digit :无符号整数E：表达式T：项F：因子则一个简单的术表达式的文法G1中包含以下产生式：E - E+E | E-E | E*E | E/E | (E) | indentifer | digit为了明确运算符的优先权（括号的优先权高于乘除法，乘除法的优先权高于加减法），可改写文法G1如下：改写后的文法G2:E - E+T | E-T | TT - T*F | T/F | FF - (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)（8）F - indentifer | digit4.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_disp();coutendl-语义分析结束-endl;/*主函数*void main()/主函数int len;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*语法分析开始*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 ) )advance();strcpy(F_name,cifa_p-word);strcpy(E_name,F_name);E1();if (strcmp(cifa_p-word,) = 0 ) )advance();strcpy(F_name,E_name);return (1);elsecoutERRORtype = 1 | cifa_p-type = 2)strcpy(F_name,cifa_p-word);advance();return (1);else return 0;int T1()/T - F*T | F/T | Fyuyi *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 = +count;T_name2 = 0;strcpy(p-result,T_name);yuyi_add(p);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);elsestrcpy(T_name,F_name);return(1);int E1()/E - T+E | T-E | Tyuyi *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)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);elsestrcpy(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_head;coutnext);cout的递归分析过程如下：endl;coutendl-endl;coutt步骤tt产生式endl;advance();n = E();if (n = 0)couttftt输入串不是该文法的一个句子！endl;coutendl-语法分析结束-endl;return (0);else if (n = 1)couttftt输入串是该文法的一个句子！endl;coutendl-语法分析结束-next = p ;yuyi_end = p;return yuyi_head;void yuyi_sys_disp() /输出四元式链表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);elsecoutERRORtype = 1 | cifa_p-type = 2)/数字或是标识符couttf+tt 标识符|无符号整数 *FS | /FS | 子函数int t,g;if (strcmp(cifa_p-word,*) = 0)couttf+tt *FSword,/) = 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 +TGword,-) = 0)couttf+tt -TGword,) = 0 | strcmp(cifa_p-word,#) = 0)couttf+tt +|-TG 子函数int t,g;if (strcmp(cifa_p-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 = ) tempi+ = ;tempi = 0;type = 4;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 = )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 = 4;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 cifa_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();notock();cout-endl词法分析结果如下：endl;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 != ) couttemp接错误后缀，出错 next = NULL;p - type = type;strcpy(p-word,temp);cifa_add(p);return (1);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 != ; &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)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 | Tint T1();/T - F*T | F/T | Fint F1();/F - (E) | 标识符 | 无符号整数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 |子函数int T();/ T - FS 子函数int S();/ S - *FS | /FS | 子函数int F();/ F - (E) | 标识符 | 无符号整数 子函数int yufa_main();/语法分析主函数cifa *cifa_add(cifa *p);/在分析结果列表尾添加一个新接点void cifa_disp(cifa *cifa_head);/输出词法分析结果void GetChar();/取字符void notock();/去掉空格int alph(void); /识别标识符int number(void);/识别数字int test(void);/识别相关符号int cifa_main();/词法分析主函数#include#include#include#include#include#include#include#include#include#includecharstr100;/输入的算术表达式字符串charch;intnn=0;/字符串计数器intf=0;charcount=0;/四元式临时变量计数器/*词法分析部分数据结构及函数定义*struct cifa/词法结构体int type;/类型char word10;/字符串内容cifa *next;cifa *cifa_head,*cifa_end,*cifa_p; /cifa队列1 语言子集的词法描述：设文法GE:E := E + T | TT := T * F | FF := (E) | i2程序的功能按照文法符号（终结符和非终结符）的优先关系确定句柄，通过不断的归约，或是移进来进行分析。3算法描述算符优先分析的基本思想是只规定算符(广义为终结符之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子，解决了前面提到的两个问题，即： 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 = strlen(str);strlen = #;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 !=