编译原理课程设计-WHILE循环语句的翻译程序设计（LR方法、输出四元式）.doc

学 号：0121210340318 课内实践题目WHILE循环语句的翻译程序设计（LR方法、输出四元式）学院计算机科学与技术学院专业计算机科学与技术班级计算机1203班姓名指导教师2014年月日课内实践任务书学生姓名： 专业班级： 计算机1201班 指导教师： 工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（LR方法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。（2）完成题目要求的中间代码四元式的描述。（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5）设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2014年 9月 1日系主任（或责任教师）签名： 2014年 月 日1、系统描述通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，实现词法分析程序对单词序列的词法检查和分析，加深对语法及语义分析原理的理解。用语法制导完成语义分析，并将形成的中间代码以四元式的形式输出。2、文法及属性文法的描述2 .1 while文法的描述文法 1 :S-S 2 :S-while(B)E 3 :E-AE 4 :E-A 5 :A-ipA 6 :A-i; 7 :B-iti 8 :B-i 其中while、(、)、p、t、；和i均为终结符， 而S、A、B、E这些大写字母均为非终结符 。t表示比较运算符，p表示算术运算符，i表示合法标识符。authorhanxu2.2 属性文法的翻译（制导）对该文法的属性文法描述如下：(1) S-while(B)Eprinf(ifBgotoEelsegotonext)(2) E-AEprint(E.val=A.valE.val)(3) E-Aprint(E.val=A.val)(4) A-ipA print(A=i.Val p A.Val) (5) A-i；A.Val=i；(6) B-itiprint(B=i1.Valti2.Val)(7) B-iB.Val=i3、语法语法分析表设计和分析方法描述3.1 while语法的DFA3.2 LR（1） 分析表4、中间代码设计本系统中所采用的中间代码形式是四元式，是一种比较普遍采用的形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a：=b*c+b*d的四元式表示如下：1）（*，b，c，t1）2）（*，b，d，t2）3）（+，t1，t2，t3）4）（：=，t3，-，a）四元式对中间结果的引用必须通过给定的名字，也就是说，四元式的联系是通过临时变量实现的。将while(Bt（比较符）C)gotoL写成（jt，B，C，L）本程序中所用到的四元式语句如下：1)形如（op，arg1，arg2，result）的赋值语句2)形如（jrop，B，C，L）的条件转移语句3)形如（=，arg1，-，result）的复写语句5、编译系统的概要设计5.1 词法分析设计词法分析程序的主要任务：对构成源程序的字符串从左到右进行扫描，逐个字符地读入并按照一定的规则切分成一个个具有独立意义的单词（同时滤掉注释和空白），并确定这些单词的属性，再把他们转化为统一长度的标准形式属性字。5.2 语法分析设计语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。5.3 语法制导设计在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。6、详细的算法描述6.1 词法分析主要算法/语句分解(uncompleted!)protectedstatic String Decomposition(char source)StringBuilder s = new StringBuilder();int count = 0;String result = new StringMax_Word_Num;for(int i = 0; i source.length; i+) /空格分割if(sourcei = ) if(s.length() != 0)resultcount = s.toString();count+;s.setLength(0);/字符串分割elseif(sourcei = )if(s.length() != 0)resultcount = s.toString();count+;s.setLength(0);s.append(sourcei);i+;while(sourcei != )s.append(sourcei);i+;s.append(sourcei);resultcount = s.toString();count+;s.setLength(0);/双位运算符分割elseif(sourcei = +& i + 1 source.length& sourcei + 1 = +) | (sourcei = -& i + 1 source.length& sourcei + 1 = -) | (sourcei = =& i + 1 source.length& sourcei + 1 = =)| (sourcei = !& i + 1 & i + 1 source.length& sourcei + 1 = =)| (sourcei = & i + 1 source.length& sourcei + 1 = =)| (sourcei = & i + 1 source.length& sourcei + 1 = &)| (sourcei = |& i + 1 S * 2 :S-while(B)E 3 :E-AE 4 :E-A 5 :A-ipA 6 :A-i; 7 :B-iti 8 :B-i其中while、(、)、p、t、；和i均为终结符，而S、A、B、E这些大写字母均为非终结符。t表示比较运算符，p表示算术运算符，i表示合法标识符。 * authorhanxu * */publicclass java_while finalstaticintMax_Word_Num = 100; static java_test j = new java_test();static String LR_1 = new String1814;/比较符T集合finalstatic String Tranop = =, , =, =, !=;/运算符P集合finalstatic String Operator = +, -, *, /, =, &, |, , &,|, +, -,;/判断是否在运算符集p中protectedstaticboolean CheckOperator(String source)for(int i = 0; i Operator.length; i+)if(source.equals(Operatori)returntrue;returnfalse;/判断是否在比较符集T中protectedstaticboolean CheckTranop(String source)for(int i = 0; i Tranop.length; i+)if(source.equals(Tranopi)returntrue;returnfalse;/构造LR（1）表publicstaticvoid CreateLR_1()for(int i = 0; i 18; i +)for(int j = 0; j 14; j +)LR_1ij = ;/从while, (, ), , , i, p, t, ;, #, S, E, B, A分别对应0 - 13LR_100 = s2;LR_1010 = 1;LR_119 = acc;LR_121 = s3;LR_135 = s5;LR_1312 = 4;LR_142 = s6;LR_152 = r8;LR_157 = s7;LR_163 = s9;LR_175 = s8;LR_182 = r7;LR_195 = s14;LR_1911 = 11;LR_1913 = 10;LR_1104 = r4;LR_1105 = s14;LR_11011 = 13;LR_11013 = 10;LR_1114 = s12;LR_1129 = r2;LR_1134 = r3;LR_1146 = s15;LR_1148 = s17;LR_1155 = s14;LR_11513 = 16;LR_1164 = r5;LR_1165 = r5;LR_1174 = r6;LR_1175 = r6;/从符号转为相应的序号protectedstaticint StringtoInt(String source)int i = 0;if(source.equals(while) i = 0;elseif(source.equals() i = 1;elseif(source.equals() i = 2;elseif(source.equals() i = 3;elseif(source.equals() i = 4;elseif(java_test.CheckTag(source) i = 5;elseif(CheckOperator(source) i = 6;elseif(CheckTranop(source) i = 7;elseif(source.equals(;) i = 8;elseif(source.equals(#) i = 9;elseif(source.equals(S) i = 10;elseif(source.equals(E) i = 11;elseif(source.equals(B) i = 12;elseif(source.equals(A) i = 13;return i;/state转为序号protectedstaticint StatetoInt(String source)int i = 0;char source_ = source.toCharArray();if(source_.length = 3)int j = (int)source_source_.length - 1 - (int)0;int k = (int)source_source_.length - 2 - (int)0; k = k * 10;i = k + j; elseif(source_0 != s& source_.length = 2)int j = (int)source_source_.length - 1 - (int)0;int k = (int)source_source_.length - 2 - (int)0; k = k * 10;i = k + j;elseif(source_0 != s& source_.length = 1)i = (int)source_source_.length - 1 - (int)0;elseif(source_0 = s& source_.length = 2)i = (int)source_source_.length - 1 - (int)0;return i;/比较字符，看是移进还是规约操作protectedstatic String compare(String source_1, String source_2)int i,j; i = StatetoInt(source_1); j = StringtoInt(source_2);returnLR_1ij; /查看操作是规约还是移入 1 = 移入 0 = 规约 -1 = gotoprotectedstaticint Check(String source)char source_ = source.toCharArray();if(source_0 = s)return 1;elseif(source_0 = r)return 0;elsereturn -1;/规约protectedstatic String recall(String source) String source_1;if(source.equals(r2) source_1 = S;elseif(source.equals(r3) | source.equals(r4) source_1 = E;elseif(source.equals(r7) | source.equals(r8) source_1 = B;elseif(source.equals(r5) | source.equals(r6) source_1 = A;else source_1 = Error;return source_1; /依次规约SuppressWarnings(null)protectedstaticvoid eliminate(String source) String s_ = new Stringsource.length;/状态组 String state = new StringMax_Word_Num; state0 = s0;int p = 0; s_p+ = #; File file = new File(D:result.txt); FileWriter writer = null;try writer = new FileWriter(file); catch (IOException e1) e1.printStackTrace(); StringBuilder s = new StringBuilder();try writer.write(state0 + + s_0 + ); catch (IOException e) e.printStackTrace(); for(int i = 0, j = 0; i source.length& sourcei != null; i+)s.append(sourcei);try writer.write(s.toString() + rn); catch (IOException e) e.printStackTrace(); /写入四元式 File file1 = new File(D:四元式.txt); FileWriter writer1 = null;try writer1 = new FileWriter(file1); catch (IOException e1) e1.printStackTrace(); int count = 1, count_ = 0, c;for(int i = 0, j = 0; i source.length& sourcei != null; i+) String state_ = compare(statej, sourcei);int state_op = Check(state_);/移进操作if(state_op = 1) j+;s_p+ = sourcei;statej = state_; /规约elseif(state_op = 0) String re_source = recall(state_);if(re_source.equals(Error) System.out.println(规约出错！);break; elseswitch(state_) caser8:try writer1.write( j, + s_p - 1 + , / , + count+ + ) + rn); catch (IOException e) e.printStackTrace(); s_p - 1 = re_source; statej = 4; break;caser7:try writer1.write(j + s_p - 2 + , + s_p - 3 + , + s_p - 1 + , + count+ + ) + rn); catch (IOException e) e.printStackTrace(); s_p - 1 = null; s_p - 2 = null; s_p - 3 = re_source; p = p - 2; statej = null; statej - 1 = null; statej - 2 = 4; j = j - 2;break;caser6:try writer1.write( + s_p - 3 + , + s_p - 4 + , + s_p - 2 + , t + count_+ + ) + rn); catch (IOException e) e.printStackTrace(); s_p - 1 = null; s_p - 2 = re_source; p = p - 1; statej = null;if(statej - 2.equals(s15) statej - 1 = 16;else statej - 1 = 10; j = j - 1;break;caser5:c = count_ - 1;try if(s_p - 4.equals(=)writer1.write( + s_p - 4 + , t + c + , + / + , + s_p - 5 + ) + rn);elseif(CheckOperator(s_p - 4)writer1.write( + s_p - 4 + , + s_p - 5 + , t + c + , t + count_+ + ) + rn); catch (IOException e) e.printStackTrace(); s_p - 1 = null; s_p - 2 = null; s_p - 3 = re_source; p = p - 2; statej = null; statej - 1 = null; if(statej - 3.equals(s9) | statej - 3.equals(10) statej - 2 = 10;else statej - 2 = 16; j = j - 2;break;caser4: s_p - 1 = re_source; if(statej - 1.equals(10) statej = 13;else statej = 11; break;caser3: s_p - 1 = null; s_p - 2 = re_source; p = p - 1; statej = null;if(statej - 2.equals(10) statej - 1 = 13;else statej - 1 = 11; j = j - 1;break;caser2: s_p - 1 = null; s_p - 2 = null; s_p - 3 = null; s_p - 4 = null; s_p - 5 = null; s_p - 6 = null; s_p - 7 = re_source; p = p - 6; statej = null; statej - 1 = null; statej - 2 = null; statej - 3 = null; statej - 4 = null; statej - 5 = null; statej - 6 = 1; j = j - 5; System.out.println();break; try StringBuilder State_S = new StringBuilder(); StringBuilder Stack_S = new StringBuilder(); StringBuilder Input_S = new StringBuilder(); for(int i_ = 0; i_ state.length& statei_ != null; i_+)State_S.append(statei_ + );State_S.append( );for(int i_ = 0; i_ s_.length& s_i_ != null; i_+) Stack_S.append(s_i_);Stack_S.append( );if(state_op = 0)for(int i_ = i ; i_ source.length& sourcei_ != null; i_+) Input_S.append(sourcei_);elsefor(int i_ = i + 1 ; i_ source.length& sourcei_ != null; i_+)Input_S.append(sourcei_); Input_S.append( continue ); writer.write(State_S.toString() + Stack_S.toString() + Input_S.toString() + rn ); catch (IOException e) e.printStackTrace();/成功识别则退出if(sourcei.equals(#) try writer.write(接受acc！ + rn); catch (IOException e) e.printStackTrace(); break; if(state_op = 0) i-;try writer.close(); catch (IOException e) e.printStackTrace();try writer1.close(); catch (IOException e) e.printStackTrace(); publicstaticvoid main(String a)CreateLR_1();for(int i = 0; i 18; i +)for(int j = 0; j 14; j +)if(LR_1ij.equals() System.out.print( 0 );elseSystem.out.print(LR_1ij + );System.out.println();StringBuilder ss = new StringBuilder(); String s;try BufferedReader input = new BufferedReader(new FileReader(D:while.txt);