编译原理课程设计--算术表达式的语法分析及语义分析程序设计.doc

编译原理课程设计课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题 目: 算术表达式的语法分析及语义分析程序设计1目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2设计内容及要求 算术表达式的文法：（1） 选择算符优先分析法完成以上任务，中间代码选用逆波兰式。（2） 写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3.课程设计报告书的内容应包括：（1）设计题目、班级、学号、姓名、完成日期；（2）给出算术表达式的语法分析和语义分析的设计。（3）简要的分析与概要设计；（4）详细的算法描述；（5）源程序清单；（6）给出软件的测试方法和测试结果；（7）设计的评价、收获与体会。时间安排：第18周，周1-周3下午，周5全天指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日1 课设要求设计题目 算术表达式转换成逆波兰式（用算符优先分析法）1.1课程设计的目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。1.2 设计内容及要求 算术表达式的文法：无符号整数 数字数字标志符 字母字母数字表达式 项加法运算符项项 因子乘法运算符因子因子 标志符无符号整数（表达式）加法运算符 乘法运算符 1.选择算符优先分析法完成以上任务，中间代码选用逆波兰式。2.写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，3.完成分析程序设计。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。2 摘要一个新的语言的出现，必然会有与之配套的编译器的产生。编译器对于一个语言的重要性不言而喻。编译过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成这六个阶段。而语法分析和语义分析是最关键的核心部分。要做好一个编译器必须要懂得如何根据构造的文法来识别出它的语法和语义。语法分析的方法很多，而比较容易懂的就有算符优先分析法，本次课设的主题就是要弄懂算符优先分析发。学习制作编译器不仅会让你弄懂这门课，还会让你提高写代码的能力，特别是写出高效，可靠性好的代码。关键字：算术表达式，算符优先文法，逆波兰式3 引言逆波兰式又叫做后缀表达式，它的用途很多，譬如做计算器的时候可以对算术表达式采用这种形式来表示，从而可以很容易的来进行计算。在编译原理中，生成中间代码的步骤里，逆波兰式也是中间代码的一种表示形式。算符优先分析法是自底向上进行语法分析的一种方式。自底向上分析的思想就是对输入的符号串自左向右的进行扫描，并将输入符逐个移入一个后进先出栈，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串时，就用该产生式左部的非终结符代替相应右部的文法符号串，这一步叫做规约。重复这一过程直到规约到栈中只剩文法的开始符号时则规约成功，也就确认了这个输入串是文法的句子。算符优先法规定了算符之间的优先关系，通过先于关系识别句柄尾，通过后于关系识别句柄头，以此来进行规约。4 正文4.1 需求分析 要通过算符优先分析方法进行将算术表达式转换成为逆波兰式，首先要经过词法分析，然后是语法分析，通过规约来输出算术表达式的逆波兰式。故先要求出每个非终结符的firstvt()集和lastvt()集，然后求出终结符的算符优先矩阵，最后以此来规约。因此程序应该能够提供输入一个任意的算符优先文法，并可以对输入的文法进行判断，还可以对文法进行改写，便于后面的分析。自动求出每个非终结符的firstvt()集和lastvt()集，自动构造终结符的优先矩阵，然后自动规约，输出逆波兰式。4.2 理论基础算符优先分析法是自底向上分析法法的一种，它的工作原理是先求出文法中每个非终结符的firstvt()集和lastvt()集，通过文法中每个产生式的右部非终结符所处的位置来确定每个非终结符之间的优先关系。譬如s-aab，则a后于a的lastvt()集规约，也后于a的firstvt()集规约。然后求出非终结符的算符优先矩阵，根据矩阵所确定的优先关系进行规约。为了将算符优先分析方法与输出逆波兰式联系起来，首先要明白算符优先方法规约的每一步是如何进行的，在确定某个终结符要规约时，应该将它保存起来，然后在最后输出这一串符号，即为所求的逆波兰式。4.3 总体设计先改写文法，在求各个非终结符的firstvt()集和lastvt()集，确定优先关系矩阵后就进行规约。系统流程图如下：开始输入文法文法是否正确改写文法y求每个非终结符的firstvt()集和lastvt()集求算符优先矩阵规约成功输出逆波兰式结束ynn所要用到的数据结构及自定义函数如下：char data2020; /算符优先关系char s100; /模拟符号栈s char lable20; /文法终极符集char input100; /文法输入符号串char string2010; /用于输入串的分析int k; char a; int j; char q; int r; /文法规则个数int r1; int m,n,n; /转化后文法规则个数char st1030; /用来存储文法规则char first1010; /文法非终结符firstvt集char last1010; /文法非终结符lastvt集int fflag10=0; /标志第i个非终结符的firstvt集是否已求出int lflag10=0; /标志第i个非终结符的lastvt集是否已求出int deal(); /对输入串的分析int zhongjie(char c); /判断字符c是否是终极符int xiabiao(char c); /求字符c在算符优先关系表中的下标void out(int j,int k,char *s); /打印s栈void firstvt(char c); /求非终结符c的firstvt集void lastvt(char c); /求非终结符c的lastvt集void table(); /创建文法优先关系表char shuchu10;/存储逆波兰式4.4 详细设计4.4.1 判断文法是否正确要对输入的文法进行判断是否为算符文法。首先判断文法是否为上下文无关文法，然后判断是否为算符文法。判断的过程比较简单，先看每个产生式的左部是否为非终结符（在这里人为规定大写字母表示非终结符，且不用进行判断），然后看产生式的右部是否有两个非终结符挨在一起的，若挨在一起，则不是算符文法，否则就是算符文法。4.4.2 改写文法 若产生式的右部有形如s-a+b|a-b的产生式，则应该改写为两条产生式：(1)s-a+b；(2)s-a-b；按此方式对文法改写后输出到屏幕上。4.4.3求每个非终结符的firstvt()集和lastvt()集对firstvt()集的构造可以根据以下两条规则构造：(1)若有产生式a-ba.或a-a.，则a属于firstvt(a)；(2)若a属于firstvt(b)且有产生式a-b.则有a属于firstvt(a)部分代码如下：if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;if(stim+1!=c)firstvt(stim+1);for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;tn;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;同样lastvt()集也可以按照类似的方式构造。4.4.4 求算符优先矩阵构造算符优先关系表。算符优先矩阵在本程序中的作用是最大的，算符优先关系表是一个二维数组，用来存放任意两个终结符之间的优先关系。首先构造表头，通过扫描所有产生式将终结符不重复的存放在一个一维数组中并置为优先关系表的行和列，并将优先关系表其他内容全部初始化为空。接着遍历所有产生式，找出任意两个终结符之间存在的关系（可以没有关系），并判断任意两终结符是否至多存在一种优先关系，如发现优先关系表不为空，则证明该文法不是算符优先文法，否则，将相应的关系填入到相应的行列对应的单元中。部分代码如下：for(i=0;ix;i+)for(j=1;textij+1!=0;j+)if(zhongjie(textij)&zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+1);datamn=;if(textij+2!=0&zhongjie(textij)&zhongjie(textij+2)&!zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+2);datamn=;if(zhongjie(textij)&!zhongjie(textij+1)/终结符和非终结符相接，用后于关系填表for(k=0;kr;k+)if(stk0=textij+1)break;m=xiabiao(textij);for(t=0;tfirstk0;t+)n=xiabiao(firstkt+1);datamn=;if(!zhongjie(textij)&zhongjie(textij+1)/非终结符和终结符相接，用先于关系填表for(k=0;kr;k+)if(stk0=textij)break;n=xiabiao(textij+1);for(t=0;t;4.4.5 输出逆波兰式要想在规约的时候输出算术表达式的逆波兰式，确定规约的终结符后，用一个字符数组将这些终结符存起来，在规约成功输出这些字符串即为所求的逆波兰式部分代码如下：if(dataxy=)if(lablex!=) shuchusize+=lablex;/将要规约的终结符存起来out(1,k,s);printf(%c,a);out(i+1,z,input);printf(规约n);5 调试及运行结果更换文法后：6 心得体会本次课程设计相对来来说不是很容易的，它的要求比较高，要将编译原理中所学的很多知识联系起来，并且要有比较良好的编程能力。一开始看到题目的时候我也是没什么头绪，理不清思路，不明白为什么将算术表达式转换为逆波兰式与算符优先分析法有何种联系。没办法，我只好在书本中寻找灵感，在看到确定了算符优先矩阵之后，每一步规约的终结符按先后顺序连接起来刚好是逆波兰式。按照这个想法，我开始有了大概的规划，然后照着这个想法去做，终于做好了。课程设计与一般的实验不同，与在课堂上学习理论知识更加不同，它是考查学习成果的一种手段，更加是检验你的能力和水平的一种方式。将理论与实践结合起来才是王道。当然，我的程序也存在着不足，没有进行词法分析，只是简单的默认了所输入的符号串都符合规定。通过本次课程设计，不仅加强了我对编译原理的认识，掌握了很多知识，更加让我明白了动手能力的重要性。在未来学习的道路上，应该继续发扬这种精神，将实践进行到底！7 源代码#include stdio.h#include stdlib.h#include iostream.hchar data2020; /算符优先关系char s100; /模拟符号栈s char lable20; /文法终极符集char input100; /文法输入符号串char string2010; /用于输入串的分析int k; char a; int j; char q; int r; /文法规则个数int r1; int m,n,n; /转化后文法规则个数char st1030; /用来存储文法规则char first1010; /文法非终结符firstvt集char last1010; /文法非终结符lastvt集int fflag10=0; /标志第i个非终结符的firstvt集是否已求出int lflag10=0; /标志第i个非终结符的lastvt集是否已求出int deal(); /对输入串的分析int zhongjie(char c); /判断字符c是否是终极符int xiabiao(char c); /求字符c在算符优先关系表中的下标void out(int j,int k,char *s); /打印s栈void firstvt(char c); /求非终结符c的firstvt集void lastvt(char c); /求非终结符c的lastvt集void table(); /创建文法优先关系表char shuchu10;/存储逆波兰式void main()int i,j,k=0; printf(请输入文法规则数：);scanf(%d,&r);printf(请输入文法规则：n);for(i=0;ir;i+)scanf(%s,sti); /存储文法规则，初始化firstvt集和lastvt集*/ firsti0=0; /*firsti0和lasti0分别表示sti0非终极符的firstvt集和lastvt集中元素的个数*/lasti0=0;for(i=0;ir;i+) /判断文法是否合法for(j=0;stij!=0;j+)if(sti0z)printf(不是算符文法!n); exit(-1);if(stij=a&stij=a&stij+1=z)printf(不是算符文法!n); exit(-1); for(i=0;ir;i+)/for(j=0;stij!=0;j+)if(stijz)&stij!=-&stij!=&stij!=|)lablek+=stij;lablek=#;lablek+1=0; table();/printf(每个非终结符的firstvt集为：n); /输出每个非终结符的firstvt集for(i=0;ir;i+)printf(%c: ,sti0);for(j=0;jfirsti0;j+)printf(%c ,firstij+1);printf(n);printf(每个非终结符的lastvt集为：n); /输出每个非终结符的lastvt集for(i=0;ir;i+)printf(%c: ,sti0);for(j=0;jlasti0;j+)printf(%c ,lastij+1);printf(n);printf(算符优先分析表如下:n);for(i=0;lablei!=0;i+) printf(t%c,lablei);printf(n); for(i=0;ik+1;i+)printf(%ct,lablei);for(j=0;jk+1;j+)printf(%ct,dataij);printf(n);printf(请输入文法输入符号串以#结束:);scanf(%s,input); deal();cout逆波兰式为：;for(i=0;lablei!=0;i+) coutshuchui0;/coutendl;void table()char text2010;/存储改写后的文法int i,j,k,t,l,x=0,y=0;int m,n;x=0;for(i=0;ir;i+)firstvt(sti0);lastvt(sti0);for(i=0;i;elsetextxy=stij;y+;textxy=0;x+;y=0;r1=x;/printf(转化后的文法为:n);for(i=0;ix;i+) /输出转化后的文法规则串printf(%sn,texti);for(i=0;i后的转化文法，用于最后的规约)*/stringi0=texti0;for(j=3,l=1;textij!=0;j+,l+)stringil=textij;stringil=0;for(i=0;ix;i+)for(j=1;textij+1!=0;j+)if(zhongjie(textij)&zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+1);datamn=;if(textij+2!=0&zhongjie(textij)&zhongjie(textij+2)&!zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+2);datamn=;if(zhongjie(textij)&!zhongjie(textij+1)/终结符和非终结符相接，用后于关系填表for(k=0;kr;k+)if(stk0=textij+1)break;m=xiabiao(textij);for(t=0;tfirstk0;t+)n=xiabiao(firstkt+1);datamn=;if(!zhongjie(textij)&zhongjie(textij+1)/非终结符和终结符相接，用先于关系填表for(k=0;kr;k+)if(stk0=textij)break;n=xiabiao(textij+1);for(t=0;t;m=xiabiao(#);/#后于所有的终结符规约for(t=0;tfirst00;t+)n=xiabiao(first0t+1);datamn=;n=xiabiao(#);/for(t=0;t;datann=;void firstvt(char c) /求firstvt集int i,j,k,m,n;for(i=0;ir;i+)/找出是第i个非终结符if(sti0=c)break;if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;if(stim+1!=c)firstvt(stim+1);for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;tn;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;void lastvt(char c) /求lastvt集int i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(lflagi=0)n=lasti0+1;m=0;doif(stim+1=0|stim+1=|)if(zhongjie(stim)lastin=stim;n+;elseif(zhongjie(stim-1)lastin=stim-1;n+;if(stim!=c)lastvt(stim);for(j=0;jr;j+)if(stj0=stim)break;for(k=0;klastj0;k+)int t;for(t=0;t)if(lablex!=) shuchusize+=lablex;/将要规约的终结符存起来out(1,k,s);printf(%c,a);out(i+1,z,input);printf(规约n);doq=sj;if(zhongjie(sj-1)j=j-1;else j=j-2;x=xiabiao(sj);y=xiabiao(q);while(