《编译原理课程设计算术表达式的语法分析及语义分析程序设计》由会员分享，可在线阅读，更多相关《编译原理课程设计算术表达式的语法分析及语义分析程序设计（24页珍藏版）》请在金锄头文库上搜索。
1、编译原理课程设计课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题 目: 算术表达式的语法分析及语义分析程序设计1目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2设计内容及要求 算术表达式的文法：（1） 选择算符优先分析法完成以上任务，中间代码选用逆波兰式。（2） 写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。3.课程设计报告书的内容应包括：（1）设计题目、班级、学号、姓名、完成日期；（
2、2）给出算术表达式的语法分析和语义分析的设计。（3）简要的分析与概要设计；（4）详细的算法描述；（5）源程序清单；（6）给出软件的测试方法和测试结果；（7）设计的评价、收获与体会。时间安排：第18周，周1-周3下午，周5全天指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日1 课设要求设计题目 算术表达式转换成逆波兰式（用算符优先分析法）1.1课程设计的目的课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论
3、知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。1.2 设计内容及要求 算术表达式的文法：无符号整数 数字数字标志符 字母字母数字表达式 项加法运算符项项 因子乘法运算符因子因子 标志符无符号整数（表达式）加法运算符 乘法运算符 1.选择算符优先分析法完成以上任务，中间代码选用逆波兰式。2.写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，3.完成分析程序设计
4、。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。2 摘要一个新的语言的出现，必然会有与之配套的编译器的产生。编译器对于一个语言的重要性不言而喻。编译过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成这六个阶段。而语法分析和语义分析是最关键的核心部分。要做好一个编译器必须要懂得如何根据构造的文法来识别出它的语法和语义。语法分析的方法很多，而比较容易懂的就有算符优先分析法，本次课设的主题就是要弄懂算符优先分析发。学习制作编译器不仅会让你弄懂这门课，还会让你提高写代码的能力，特别是写出高效，可靠性好的代码。关键字：算术表达式，算符优先文法，逆波兰式3 引言逆
5、波兰式又叫做后缀表达式，它的用途很多，譬如做计算器的时候可以对算术表达式采用这种形式来表示，从而可以很容易的来进行计算。在编译原理中，生成中间代码的步骤里，逆波兰式也是中间代码的一种表示形式。算符优先分析法是自底向上进行语法分析的一种方式。自底向上分析的思想就是对输入的符号串自左向右的进行扫描，并将输入符逐个移入一个后进先出栈，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可规约串时，就用该产生式左部的非终结符代替相应右部的文法符号串，这一步叫做规约。重复这一过程直到规约到栈中只剩文法的开始符号时则规约成功，也就确认了这个输入串是文法的句子。算符优先法规定了算符之间的优先关系，通过先于关系识
6、别句柄尾，通过后于关系识别句柄头，以此来进行规约。4 正文4.1 需求分析 要通过算符优先分析方法进行将算术表达式转换成为逆波兰式，首先要经过词法分析，然后是语法分析，通过规约来输出算术表达式的逆波兰式。故先要求出每个非终结符的FIRSTVT()集和LASTVT()集，然后求出终结符的算符优先矩阵，最后以此来规约。因此程序应该能够提供输入一个任意的算符优先文法，并可以对输入的文法进行判断，还可以对文法进行改写，便于后面的分析。自动求出每个非终结符的FIRSTVT()集和LASTVT()集，自动构造终结符的优先矩阵，然后自动规约，输出逆波兰式。4.2 理论基础算符优先分析法是自底向上分析法法的一
7、种，它的工作原理是先求出文法中每个非终结符的FIRSTVT()集和LASTVT()集，通过文法中每个产生式的右部非终结符所处的位置来确定每个非终结符之间的优先关系。譬如S-AaB，则a后于A的LASTVT()集规约，也后于A的FIRSTVT()集规约。然后求出非终结符的算符优先矩阵，根据矩阵所确定的优先关系进行规约。为了将算符优先分析方法与输出逆波兰式联系起来，首先要明白算符优先方法规约的每一步是如何进行的，在确定某个终结符要规约时，应该将它保存起来，然后在最后输出这一串符号，即为所求的逆波兰式。4.3 总体设计先改写文法，在求各个非终结符的FIRSTVT()集和LASTVT()集，确定优先关
8、系矩阵后就进行规约。系统流程图如下：开始输入文法文法是否正确改写文法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;
9、/用来存储文法规则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); /求非终
10、结符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的产生式，
11、则应该改写为两条产生式：(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;同样LAST
