《编译原理》课程设计报告编译程序构造 .doc

目 录第一章 绪论21.1课程设计目的21.2课程设计要求21.3课程设计内容21.3.1课设题目21.3.2课设内容21.3.3具体要求21.3.4程序设计提示31.3.5测试数据31.4课程设计环境3第二章 设计方案32.1模块划分32.2模块调用关系图32.3每个模块流程图32.3.1词法分析模块流程图32.3.2语法分析模块流程图32.3.3主程序流程图3第三章 程序代码设计33.1数据结构设计33.2设计分析表33.3词法分析设计33.4语法和语义分析设计3第四章 程序测试和结果34.1程序测试34.2 运行结果3第五章 总结3参考文献3附录3源程序代码3程序使用说明书3第一章 绪论1.1课程设计目的编译原理课程设计是编译原理课程必不可少的一个环节，通过课程设计，加深对编译原理的教学内容的了解，以及实现编译原理各部分知识的融合。进而提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力。1.2课程设计要求1明确课设任务，复习与查阅有关资料2按要求完成课设内容，课设报告要求文字和图工整、思路清楚、正确。3注意增强程序界面的友好性。凡用户输入时，给出足够的提示信息使用户感到方便使用。4注意提高程序的可读性和可理解性：程序中应有适当的注释，变量命名应符合实际含义，程序结构清晰，易于阅读和理解。1.3课程设计内容1.3.1课设题目编译程序构造1.3.2课设内容涉及词法分析、自下而上语法分析程序的实现：SLR（1）分析器的实现以及生成中间代码。1.3.3具体要求根据LR分析算法构造SLR（1）分析程序，并完成语法分析动作（当需要一个单词时，调用词法分析程序获取），同时完成语义分析生成四元式输出。要求程序具有通用性，改变文法时只需改变程序的数据初值，无需改变程序主体；要求完成一条说明语句、一条算数表达式和赋值语句的翻译，生成中间代码。变量说明语句的文法及相应的语义子程序：.att表示数据类型属性，fill函数表示将单词id及其类别属性填写符号表。（0）SD； acc（1）Dint id fill（id，int）；D.att=int; （2）Dfloat id fill(id,float); D.att=float; （3）DD（1），id fill(id,D(1).att);D.att=D(1).att; 算数表达式和赋值语句的文法及相应的语义子程序。（1）Aid=E； p=lookup(id.name);emit（=, E.PALCE , _, p）; （2）EE(1)+T E.PALCE=newtemp(); emit(+，E(1).PALCE，T.PALCE，E.PALCE)（3）ET E.PALCE=T.PALCE;（4）TT(1)*F T.PALCE=newtemp(); emit(*，T(1).PALCE，F.PALCE，T.PALCE)（5）TF T.PALCE=F.PALCE;（6）F(E) F.PALCE=E.PALCE;（7）Fid P=LOOKUP(id.name)F.PALCE=P;构造其用于SLR（1）分析的识别活前缀的DFA以及action表和goto表。然后编程实现。（关于词法分析部分只需识别出与此文法相关的单词即可（+，*，（，），id，=）。1.3.4程序设计提示（1）分析栈设计时可以用一个栈完成，也可以设计三个栈：一个符号栈，一个状态栈，一个语义栈，则归约时，则需要在符号栈中退掉n个符号，在状态栈中退掉n个符号（n为产生式符号个数），语义栈中退掉n个符号对应的语义；（2）终结符表和非终结符表的组织和预测分析程序中相同（将符号对应到一个数字，表示在分析表中对应的下标）。（3）action表中的错误处理：简化的错误处理：当查找action表出现空白时，则当前单词无法移进和规约，可简单的认为当前单词为多余的单词，则抛弃当前单词，读下一单词继续分析。1.3.5测试数据作为程序测试数据，以赋值语句area=r*r+r$作为测试输入（源程序）。程序要求输出二元式序列、符号表、语法分析过程、四元式序列。假设AA.TXT的文件内容如下： int area，r； area=r*r+r；程序运行情况如下：请输入源文件名称：E：AA.TXT<回车>语法分析过程如下： 状态栈 符号栈 语义栈 动作说明源程序对应的二元式如下： （int，-） （id，0） （，-） （id，1） （；，-）（id，0）（=，）（id，1） （*，） （id，1） （+，） （id，1） （；，-）符号表如下：arear 源程序对应的四元式序列如下： （*，r，r，T1） （+，T1，r，T2） （=，T2，area）分析过程完成。1.4课程设计环境硬件环境：图书馆五楼计算机系软一实验室；软件环境：JCreator第二章 设计方案2.1模块划分 将系统模块划分为四个模块：数据结构模块，词法分析模块，SLR（1）分析程序模块和语义分析模块。输入或读取文件符号表获得代码进行词法分析二元式判断文法输出四元式表达式文法分析声明文法分析分析过程SLR（1）分析程序模块语义分析模块词法分析模块数据结构模块2.2模块调用关系图2.3每个模块流程图2.3.1词法分析模块流程图转化成单词数组获得代码结束，返回所有单词计数器小于单词个数获得单个单词关键字加入二元式表是标识符，加入符号表，加入二元式表计数器加12.3.2语法分析模块流程图初始化状态栈和符号栈判断当前字符根据当前字符和状态，查找SLR分析表判断action结束规约(生成四元式)移进将处理过程放入处理数组，字符串指针，各栈顶指针变化，各栈栈内内容变化2.3.3主程序流程图调用词法分析函数并输出二元式输入源程序文件名打印四元式调用SLR(1)分析程序打印标识符表和常量表第三章 程序代码设计3.1数据结构设计分隔符： char arr1 = ',', '', '', '', '(', ')', '"' ; 运算符： char arr = '+', '-', '*', '/', '=', '<', '>' ;关键字： String Key = "int", "float", "char", "while", "if" ; 存储二元式： ErYuan er = new ErYuan();数字位置： int NUM = 0;标识符位置： int ID_;String VN0 = "D", "S" ;String VT0 = "", "int", "float", ",", "id", "#" ;非终结符： String VN = "E", "T", "F", "A" ; 终结符： String VT = "id", "=", "+", "*", "(", ")", "", "#" ; 非终结符个数： int lengthVn = 3; 终结符个数： int lengthVt = 8; 状态数： int lengthZt = 15; 规约数组： int guiyue0;算数表达式和赋值语句文法的goto子表： int goto1;算数表达式和赋值语句文法的action子表： int action;标识符： String ident = new String100;标识符数： int countId = 0;存储四元式： SiYuan si = new SiYuan50; 存储临时变量Tn ：String ident_t = new String100;Tn的个数：int lengthIdt = 0;输入的字符串： String input0;3.2设计分析表变量说明语句的文法及相应的语义子程序：.att表示数据类型属性，fill函数表示将单词id及其类别属性填写符号表。（0）SD； acc（1）Dint id fill（id，int）；D.att=int; （2）Dfloat id fill(id,float); D.att=float; （3）DD（1），id fill(id,D(1).att);D.att=D(1).att; I0：S D;D int idD float idD D , idDI1:S D ;D D , idintI2:D int ididI6:D int id floatI3:D float idI7:D float id ,I5:D D , ididI8:D D , id I4:S D ; id;FOLLOW(S) = #FOLLOW(D) = , ;状态ACTIONGOTO;intfloat,id#D0S2S311S4S52S63S74acc5S86r1r17r2r28r3r33.3词法分析设计boolean IsFenGeFu(String str) 判断i当前所指的字符是否为一个分界符，是的话返回真，反之返回假void IsNum(String str) 此函数判断传递的参数是否为数字，是的话返回真，反之返回假void IsID(String str) 此函数判断传递的参数是否为标识符，是的话返回真，反之返回假boolean IsOperation(String str) 判断i当前所指的字符是否为一个运算符，是的话返回真，反之返回假void result(String a) 将字符串分类，得到数字、关键字、标识符等 a=a.trim();if (a.equals(null) | a.equals("n") | a.length() = 0|a.equals(" ")return;try if (a.length() = 1) if (a.equals(",") | a.equals("") | a.equals("")| a.equals("") | a.equals("(") | a.equals(")")| a.equals("")IsFenGeFu(a);else if (a.equals("+") | a.equals("-") | a.equals("*")| a.equals("/") | a.equals("=") | a.equals("<")| a.equals(">")IsOperation(a);else if (a.charAt(0) <= '9' && a.charAt(0) >= '0')IsNum(a);elseIsID(a); else if (a.charAt(0) <= '9' && a.charAt(0) >= '0') for (int k = 1; k <= a.length(); k+)if (a.charAt(k) <= '9' && a.charAt(k) >= '0')| a.charAt(k) = '.')continue;IsNum(a); else if (IsKey(a);elseIsID(a); catch (Exception ee) System.out.println(ee);boolean IsKey(String str) 此函数判断传递的参数是否为关键字，是的话，返回真，反之返回假void IsNum(String strclass ErYuan) 存储二元式void show() 输出二元式3.4语法和语义分析设计boolean isDelim(char c) 返回是否是终结符中字符void yufa( ) 语法分析，中间嵌套语义分析（主要代码分析） x = stack.getHead();/ 得到栈顶状态值value = actionxa;/ value为下一状态值while (true) System.out.println();stack.show();/ 输出各个栈顶值if (value >= 0 && value < 100)/ 移进temp.zhuangtai = value;temp.fuhao = new String(VTa);if (a = 0) temp.yuyi = node.num; elsetemp.yuyi = -1;temp.next = null;stack.push(temp);System.out.print("移进操作");if (value >= 100)/ 归约 int size, vn_temp, ID_temp;value = value - 100;vn_temp = guiyuevalue0;size = guiyuevalue1;int ID = new intsize;for (i = 1; i <= size; i+) temp = stack.pop();IDi - 1 = temp.yuyi;/ 获得语义栈的值if (temp = null) System.out.println("出栈错误!");return;String getID(int x) 返回标识符或者临时标识符void emit()存储四元式class Stack 堆栈void show() 输出四元式int tempID() 产生临时标识符void error(int i)/ 错误处理b = false;System.out.print("n出错:");switch (i) case 1:System.out.println("非法字符!");break;case 2:System.out.println("有语义错误!");break;case 3:System.out.println("无结尾符号!");break;算数表达式和赋值语句的文法及相应的语义子程序。（0）Aid=E； p=lookup(id.name);emit（E.PALCE, , p）; （1）EE(1)+T E.PALCE=newtemp(); emit(+，E(1).PALCE，T.PALCE，E.PALCE)（2）ET E.PALCE=T.PALCE;（3）TT(1)*F T.PALCE=newtemp(); emit(+，T(1).PALCE，F.PALCE，T.PALCE)（4）TF T.PALCE=F.PALCE;（5）F(E) F.PALCE=E.PALCE;（6）Fid P=LOOKUP(id.name)F.PALCE=P;I1:A id = E;=EI2:A id = E;E E + TE TT T * FT FF ( E )F id+I3:A id = E ;E E + TTI12:E E + T T T * FI5:T F F(I6:F ( E )E E + TE TT T * FT FF ( E )F id*id（I13:T T * F I4:E T T T * FTFI10:T T * FF ( E )F idI7:F id idid(Fid*I14:F ( E ) I11:F ( E )E E + TE）I0:A id = E;id+FI9:E E + TT T * FT FF ( E )F idT(I8:A id = E ; ;FOLLOW(A) = #;FOLLOW(E) = ;, +, );FOLLOW(T) = *, ;, +, );FOLLOW(F) = *, ;, +, );状态ACTIONGOTOid=+*();#ETF0S11S22S7S63453S9S84r210r2r25r4r4r4r46S7S611457r6r6r6r68acc9S7S612510S7S61311S9S1412r1S10r1r113r3r3r3r314r5r5r5r5第四章 程序测试和结果4.1程序测试源程序: hou.txt4.2 运行结果1.词法分析结果:如图 2.SLR(1) 运行结果:如图3.语义运行结果:如图第五章 总结本次课程设计涉及词法分析、自下而上语法分析程序的实现，SLR（1）分析器的实现以及生成中间代码。要求根据LR分析算法构造SLR（1）分析程序，并完成语法分析动作，同时完成语义分析生成四元式输出。通过两个星期的实验，已经顺利完成了任务。在这次课设当中，感觉到编译原理强大的理论性和抽象性，有了平时做实验的基础不会觉得无从下手，但是对于实现各个功能的函数的连接觉得很困惑。后来经过上网查阅资料，请教老师和同学，我学到了不少东西，对声明文法的分析中用到了词法分析中产生的符号表，利用参数传递此符号表，产生说明语句的编译过程。此程序还有一些不足的地方。其一，就是不能全面的容错，当输入错误的语句时不能够分析出来，而且对于不同属性的各标识符进行运算时没有相应的容错判断，如果有时间还有待于提高，这也是一个巨大的工作。其二，不是图形用户界面，只在运行结果中显示，作为软件使用不够方面。我们都该努力地追求实用性。编译原理是计算机专业的重要专业课之一。而实验又是学好编译原理课程的重要环节，设计一个与理论内容相适宜的实验是整体上提高编译原理能力决定性因素。在此次课程设计中我学到了很多，遇到的困难也带给我感受很多。通过这个全面的编译原理的实验我很大的提高了自己认真思考和自学的能力。同时感谢老师和同学的教导与帮助。我会在今后的学习中更加努力。参考文献1胡元义。 编译原理教程。 西安: 西安电子科技大学出版社， 2006.4。2陈火旺，刘春林等，程序设计语言编译原理（第三版）。北京:国防工业出版社，2000。3蒋立源，康幕宁主编，编译原理。 西安：西北工业大学出版社，2000.34周霭如，林伟健. C+程序设计基础。北京：电子工业出版社， 2006.4。 5 侯文泳，张冬沫编著，编译原理教程。北京：电子工业出版社. 2004。附录源程序代码CiFa.javapackage com.yang.ks;class CiFa char arr1 = ',', '', '', '', '(', ')', '"' ;/ 分隔符char arr = '+', '-', '*', '/', '=', '<', '>' ;/ 运算符String Key = "int", "float", "char", "while", "if" ;/ 关键字ErYuan er = new ErYuan();/ 存储二元式int NUM = 0;/ 数字位置int ID_;/ 标识符位置Node1 node1 = new Node150;void cifa(String s) int begin = 0, end = 0;try do try for (; begin+)if (s.charAt(begin) != ' ' && s.charAt(begin) != 'n')break; catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();String nowString = null;String nowString1 = ""try int r;for (r = begin; r < s.length(); r+) if (s.charAt(r) = ',' | s.charAt(r) = ''| s.charAt(r) = ' ' | s.charAt(r) = 'n'| s.charAt(r) = '+' | s.charAt(r) = '='| s.charAt(r) = '*' | s.charAt(r) = '-'| s.charAt(r) = '/')break;if (s.charAt(r) = ',' | s.charAt(r) = ''| s.charAt(r) = '+' | s.charAt(r) = '='| s.charAt(r) = '*' | s.charAt(r) = '-'| s.charAt(r) = '/') nowString1 = s.substring(r, r + 1);end = r; catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();if (end >= s.length()break;nowString = s.substring(begin, end);/ 返回定长字符串result(nowString);result(nowString1);begin = end + 1; while (true); catch (Exception ee) System.out.println(ee);boolean IsFenGeFu(String str)/ 判断i当前所指的字符是否为一个分界符，是的话返回真，反之假Node1 node = new Node1();for (int t = 0; t < 7; t+)try if (str.charAt(0) = arr1t) node.num = -1;node.str = str;er.add(node);return true; catch (Exception e) e.printStackTrace();return false;void IsNum(String str)/ 此函数判断传递的参数是否为数字，是的话，返回真，反之返回假Node1 node = new Node1();node.num = NUM;node.str = str;er.add(node);NUM+;void IsID(String str)/ 此函数判断传递的参数是否为标识符，是的话，返回真，反之返回假if (str = "n")return;Node1 node = new Node1();int flag = 0;for (int r = 0; r < node1.length; r+) try if (node1r.str.equals("")break;if (str.equals(node1r.str) node.num = node1r.num;node.str = node1r.str;er.add(node);flag = 1;break; catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();if (flag = 0) node.num = ID_;node.str = str;er.add(node);ID_+;boolean IsOperation(String str)/ 判断i当前所指的字符是否为一个运算符，是的话返回真，反之假Node1 node = new Node1();for (int t = 0; t < 7; t+)try if (str.charAt(0) = arrt) node.num = -1;node.str = str;er.add(node); catch (Exception e) e.printStackTrace();return false;void result(String a)/ 将字符串分类，得到数字、关键字、标识符等 a=a.trim();if (a.equals(null) | a.equals("n") | a.length() = 0|a.equals(" ")return;try if (a.length() = 1) if (a.equals(",") | a.equals("") | a.equals("")| a.equals("") | a.equals("(") | a.equals(")")| a.equals("")IsFenGeFu(a);else if (a.equals("+") | a.equals("-") | a.equals("*")| a.equals("/") | a.equals("=") | a.equals("<")| a.equals(">")IsOperation(a);else if (a.charAt(0) <= '9' && a.charAt(0) >= '0')IsNum(a);elseIsID(a); else if (a.charAt(0) <= '9' && a.charAt(0) >= '0') for (int k = 1; k <= a.length(); k+)if (a.charAt(k) <= '9' && a.charAt(k) >= '0')| a.charAt(k) = '.')continue;IsNum(a); else if (IsKey(a);elseIsID(a); catch (Exception ee) System.out.println(ee);boolean IsKey(String str)/ 此函数判断传递的参数是否为关键字，是的话，返回真，反之返回假for (int i = 0; i < 5; i+) if (str.equals(Keyi) Node1 node = new Node1();node.num = -1;node.str = str;er.add(node);return true;return false;class ErYuan/ 存储二元式int i = -1;void add(Node1 x) try i+;node1i = new Node1();node1i.str = x.str;node1i.num = x.num; catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();void show()/ 输出二元式System.out.println("二元式为：");for (int j = 0; j <= i; j+) System.out.println("(" + node1j.str + "," + node1j.num+ ")");class Node1 String str = ""int num = -1;Ks.javapackage com.yang.ks;import java.util.*;import java.io.*;class KeShe String VN0 = "D", "S" ;String VT0 = "", "int", "float", ",