编译原理课设_王远

1、学 号：0121210680218课 程 设 计题 目二-十进制的语法分析及语义分析程序设计学 院计算机科学与技术学院专 业软件工程班 级软件zy1201班姓 名王远指导教师饶文碧2015年1月14日课程设计任务书学生姓名： 王远 专业班级： 软件zy1201班 指导教师： 饶文碧 工作单位： 计算机科学与技术学院题目: 二-十进制的语法分析及语义分析程序设计1目的通过设计、编制、调试语法及语义分析程序，加深对语法及语义分析原理的理解。2设计内容及要求（1）学号19-22的同学按顺序分别选择递归下降法、LL（1）、算符优先分析法（或简单优先法）、LR法完成以上任务。（2）如1题写出符合分析方法

2、要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。上机时间安排：序号阶段内容所需时间1消化资料、系统设计1天2编程、调试天3撰写报告1天合计天指导老师签名： 年 月 日目录1.系统描述11.1目的11.2设计内容11.3文法和翻译12.词法分析23.语法分析23.1递归子程序法概述23.1.1构造递归子程序的方法33.1.2非终结符对应的子程序44.属性文法74.1 文法和属性文法的描述75.词法、语法错误检测和处理76.用例分析87.个人总结98.源代码109. 参考文献15武汉理工大学编译原理课程设计二-十进制的语法分析

3、及语义分析程序设计递归下降法1. 系统描述1.1目的通过设计、编制、调试语法及语义分析程序，加深对语法及语义分析原理的理解。并实现词法分析程序对单词序列的词法检查和分析。1.2设计内容（1）选择递归下降法进行语法分析和语义分析（2）写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。1.3文法和翻译正整数二进制自然数的正规式为: B =0 | (0|1) *正整数十进制自然数的正规式为： D =0 | (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*正小数二进制的正规式为：C=

4、(0 | 1) . (0 | 1)*正小数十进制的正规式为：E=(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* .(0|1|2|3|4|5|6|7|8|9)*二十进制自然数的文法GE如下:表 1.3.1 文法表产生式语法制导翻译方法2. 词法分析词法分析是计算机科学中将字符序列转换为单词（Token）序列的过程。进行语法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在

5、一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。简化设计、改进编译效率、增加编译系统的可移植性。词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。单词的分类主要分为五类：1. 关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。2. 标识符：用来表示程序中各种名字的字符串。3. 常 数：常数的类型一般有整型、实型、布尔型、文字型。4. 运算符：如+、 、*、/ 等。5. 界限符：如逗号、分号、括号等。这里将词法分析程序设计成一个

6、子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词。因为输入的就是以“#”结尾的二进制串，所以该程序的词法分析很简单，只需要一个符号数组和一个初始指向数组第一个元素地址的指针，就可以读出每一个单词。3.语法分析3.1递归子程序法概述递归子程序法是比较简单直观易于构造的一种语法分析方法。它要求满足LL（1）文法。它的实现思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某个非终结符有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。由于递归子程序法对每个过程可能存在

7、直接或间接递归调用，所以对某个过程在退出之前可能又被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。由于递归过程是遵循先进后出规律，所以通常开辟先进后出栈来处理。递归子程序法的缺点是：对文法要求高，必须满足LL（1）文法，当然在某些语言中个别产生式的推导当不满足LL（1）而满足LL(2)时，也可以采用多向前扫描一个符号的方法；它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，例如Pascal，C等编译系统常常采用的语法分析方法。由于该文法在正整数和正小数一起考虑时的文法并不是LL(1)文法，所以将正整数和正小数分别单独处理，最后在程序中综

8、合起来。程序分程序语句条件二进制串单词图3.1 语法调用关系图3.1.1构造递归子程序的方法为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写。（1）当遇到终结符a时，则编写语句if (当前读来的输入符号=a) 读下一个输入符号（2）当遇到非终结符A时，则编写语句调用 A( )（3）当遇到规则A 时，则编写语句if (当前读来的输入符号ÏFOLLOW(A) error( )；（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导。当前单词函数匹配单词进入分支读取下一个进入子函数计算属

9、性翻译模型决定顺序构建字母表生成中间代码图3.1.1 程序的调用结构和顺序图3.1.2非终结符对应的子程序产生式对应的语义是，即是显示S的值val是S的综合属性。实现程序如下：void E()cout<<"E->S-"<<endl;if(strchr(input,'.') = NULL)result=S2();elseresult=S1();cout<<endl;cout<<"*递归下降分析成功*"<<endl;cout<<"对应的十进制表示为：&qu

10、ot;<<"*"<<result<<"*"<<endl;inputstrchr(input,'#')-input='.'return;产生式对应的语义是，其中val和length都是综合属性。功能是调用正整数二进制转换函数，实现正小数二进制转换。实现程序如下：double S1()Attribute L1,L2,S;char *point1,*point2;point1=input;point2=strchr(input,'.')+1;inputstrchr(

11、input,'.')-input='#'cout<<"S->L1.L2-"<<endl;L1=L(point1);L2=L(point2);/语义规则s.val=L1.val+L2.val/2L2.length; S.value=L1.value+L2.value/(pow(2,(double)(L2.length);return S.value;产生式对应的语义为，val是S和L的综合属性。对正整数二进制进行转换，其子程序需要调用L（），为：double S2()Attribute Ll;cout<<

12、;"S->L-"<<endl;Ll=L(input);/语义规则s.val=L.val return Ll.value;非终结符L对应的产生式有：、。需要调用函数R（），其实现为：Attribute L(char *p)Attribute Ll,Rr;point=p;/产生式L->0R/语义规则：L.val=R.val;L.length=1+R.length; if( *point ='0')cout<<"L->0R-0"<<endl;point+;Rr=R();Ll.value=Rr

13、.value;Ll.length=1+Rr.length;return Ll;/产生式L->0R/语义规则：L.val=1*2R.length+R.val;L.length=1+R.length; else if(*point = '1')cout<<"L->1R-1"<<endl;point+;Rr=R();Ll.value=1*pow(2,(double)(Rr.length)+Rr.value;Ll.length=1+Rr.length;return Ll;非终结符R对应的产生式为：，其实现为：Attribute R

14、()Attribute Rr1,Rr;/产生式R->0R/语义规则:R.val=R1.val;R.length=1+R1.length; if(*point = '0')cout<<"R->0R-0"<<endl;point+;Rr1=R();Rr.value=Rr1.value;Rr.length=1+Rr1.length;return Rr;/产生式R->1R/语义规则：R.val=1*2R1.length+R1.val;R.length=1+R1.length; else if(*point = '1&

15、#39;)cout<<"R->1R-1"<<endl;point+;Rr1=R();Rr.value=1*pow(2,(double)(Rr1.length)+Rr1.value;Rr.length=1+Rr1.length;return Rr;/产生式R->EMPTY/*point是否包含在FOLLOW(R)集中 else if(*point = '#')cout<<"R->EMPTY-"<<endl;Rr.value=0;Rr.length=0;return Rr;el

16、se cout<<"error"<<endl;exit(0);4.属性文法对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。 一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。4.1 文法和属性文法的描述对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。 一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规

17、则附在文法的每个产生式上。形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中：G:是一个上下文无关文法；V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息；F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。5.词法、语法错误检测和处理对于输入的字符串需要进行检测，看是否符合词法、语法规则。如果符合则进行语法、语义分析；否则，报错，重新输入。对于错误的可能情况为：（1） 输入的单词不是1，0，.和终止符#，例如：1a2.01#；（2） 输入的字符串

18、没有终止符#，例如：101.101；（3） 输入的字符串小数点的个数大于1，例如：101.101#；（4） 输入的字符串以单词.结尾，例如：101.；（5） 输入有多个终止符#，将会进行警告，忽略第一个#后面的内容；（6） 输入的字符串以小数点.开头，将会进行警告，在小数点前面自动补0。如果出现了错误，则将不会进行语法、语义分析；如果出现了警告，则仍然进行语法、语义分析。6.用例分析用例一：输入的字符串中包含除0，1，.，#之外的字符：图6.1 用例一的运行结果图用例二：输入的字符串没有以终止符#结尾：图6.2 用例二的运行结果图用例三：输入的字符串的小数点的个数不止一个：图6.3 用例三运行

19、结果图用例四：输入的字符串以.开头和有多个终止符#：图6.4 用例四运行结果图用例五：输入的二进制串完全按照规定格式：图6.5 用例五运行结果图7.个人总结经过不断的查阅资料，终于完成本次编译原理的课程设计。运用了递归下降方法对二-十进制的语法分析及语义分析程序设计，通过本次实践我学会和领悟了许多：1. 良好的编程习惯如此重要在编写程序之前，要先写好自己的软件定义，软件流程图。对自己要做的事要有很清晰的了解，知道其中难点之所在。在编写程序时，要符合规范，详尽的中英文注释，模块化编程，程序要简洁，可读性和可修改性要强。在编写后，要进行不断的测试，降低程序的bug，增加程序的健壮性。2.工作计划不

20、可缺少每天早上打开工作计划，检查一下昨天的任务是不是已经完成，今天的工作又有哪些，搞清自己的工作方向。3学习理论知识要讲方法每次接触新课题时，就必须要学习新的知识。先要了解其框架，比较抽象，比较粗略，不需要精确，有一个思路即可，然后在做具体的设计时，遇到困难，再查查资料。具体、详细、精确的了解。如此反复可以事半功倍，提高效率。通过这次大作业，在这整个过程中我学到了很多东西，掌握了一些常用的开发技能,也发现了大量的问题，有些在设计过程中已经解决，有些还有待今后慢慢学习。只要学习就会有更多的问题，有更多的难点，但也会有更多的收获。8.源代码#include "iostream"

21、#include "string.h"#include "stdlib.h"#include "math.h"using namespace std;/*用递归下降方法二-十进制的语法分析及语义分析程序设计 分为正整数二进制和带小数点的二进制转换两部分 */char input255; /存储输入的二进制串 char *point; /指向当前单词的指针 double result; /存储二进制转换后的结果 typedef struct shuxingdouble value;int length; Attribute;Attrib

22、ute R();Attribute L(char *p);double S1();/带小数点的二进制转换部分 double S2();/正整数二进制转换部分void E();void hander_point();/处理小数点开头的情况 int error_handle();/简单的词法分析和语法分析 int main()char mark='Y'int error_flag;while(mark = 'Y' | mark = 'y')system("cls");cout<<"请输入二进制表达式，以#结束

23、"<<endl;cin>>input;point=input;error_flag=error_handle();cout<<endl<<"*"<<endl;if(error_flag = 0)E(); /开始递归下降分析 elsecout<<"请重新按正确格式输入二进制串"<<endl;cout<<endl<<"*继续输入二进制串?*(Y/N)"<<endl;cin>>mark;return

24、0;/*递归下降法* /产生式E->s print(s.val) void E()cout<<"E->S-"<<endl;if(strchr(input,'.') = NULL)result=S2();elseresult=S1();cout<<endl;cout<<"*递归下降分析成功*"<<endl;cout<<"对应的十进制表示为："<<"*"<<result<<"

25、*"<<endl;inputstrchr(input,'#')-input='.'return;/带小数点的二进制转换部分 /对应文法S->L.L; double S1()Attribute L1,L2,S;char *point1,*point2;point1=input;point2=strchr(input,'.')+1;inputstrchr(input,'.')-input='#'cout<<"S->L1.L2-"<<endl;

26、L1=L(point1);L2=L(point2);/语义规则s.val=L1.val+L2.val/2L2.length; S.value=L1.value+L2.value/(pow(2,(double)(L2.length);return S.value;/正整数二进制转换部分/对应文法S->L; double S2()Attribute Ll;cout<<"S->L-"<<endl;Ll=L(input);/语义规则s.val=L.val return Ll.value; Attribute L(char *p)Attribute

27、 Ll,Rr;point=p;/产生式L->0R/语义规则：L.val=R.val;L.length=1+R.length; if( *point ='0')cout<<"L->0R-0"<<endl;point+;Rr=R();Ll.value=Rr.value;Ll.length=1+Rr.length;return Ll;/产生式L->0R/语义规则：L.val=1*2R.length+R.val;L.length=1+R.length; else if(*point = '1')cout<

28、;<"L->1R-1"<<endl;point+;Rr=R();Ll.value=1*pow(2,(double)(Rr.length)+Rr.value;Ll.length=1+Rr.length;return Ll;Attribute R()Attribute Rr1,Rr;/产生式R->0R/语义规则:R.val=R1.val;R.length=1+R1.length; if(*point = '0')cout<<"R->0R-0"<<endl;point+;Rr1=R()

29、;Rr.value=Rr1.value;Rr.length=1+Rr1.length;return Rr;/产生式R->1R/语义规则：R.val=1*2R1.length+R1.val;R.length=1+R1.length; else if(*point = '1')cout<<"R->1R-1"<<endl;point+;Rr1=R();Rr.value=1*pow(2,(double)(Rr1.length)+Rr1.value;Rr.length=1+Rr1.length;return Rr;/产生式R->

30、;EMPTY/*point是否包含在FOLLOW(R)集中 else if(*point = '#')cout<<"R->EMPTY-"<<endl;Rr.value=0;Rr.length=0;return Rr;else cout<<"error"<<endl;exit(0);/简单的词法分析和语法分析 int error_handle()char *p;int point_flag,star_flag,error_flag,warn_flag;point_flag=0;star_

31、flag=0;error_flag=0;warn_flag=0;p=input;if(p0 = '.')warn_flag+;cout<<"warn "<<warn_flag<<" :二进制串以小数点.开头"<<endl;hander_point();/处理小数点开头的情况 while(*p != '0')if(*p != '0' && *p !='1' && *p!='.' && *p!='#')error_flag+;cout<<"error "<<error_flag<<" :输入的单词不是'0'或者'1'或者'.'"<<endl;if(*p