编译原理课程设计-福建农林大学java.doc

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：陈锦灿系：计算机专 业：计算机科学与技术年 级：2012级学 号：3126010067指导教师：林清波20152016学年第一学期福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目 录1 正则表达式11.1 正则表达式11.2 确定化(化简)后的状态转换图11.3 分析程序代码11.4 程序运行截图11.5 小结：12 LL(1)分析22.1 LL(1)文法22.2 LL(1)预测分析表22.3 分析程序代码22.4 程序运行截图22.5 小结23 算符优先分析33.1 算符优先文法33.2 算符优先关系表33.3 分析程序代码33.4 程序运行截图33.5 小结34 LR分析44.1 LR文法44.2 LR分析表44.3 分析程序代码(代码原创)44.4 程序运行截图44.5 小结4参考文献：41 正则表达式1.1 正则表达式 (a|b)*(aa|bb)(a|b)* 1.2 确定化(化简)后的状态转换图 1.3 分析程序代码import java.util.Scanner;public class Test4 public static void main(String args) int s=1,2,3,2,1,4,3,5,6,4,6,4,3,5;System.out.println(文法规则：n(a|b)*(aa|bb)*(a|b)*);System.out.println(请输入您所要验证的句子：n);Scanner sc = new Scanner(System.in);String str1 = sc.next();int len = str1.length();char ch;int i,j = 0,t,flag,index;i=0;index = 0;t=1;/判断输入是否正确flag=0;/判断句子是否正确while(index =3 & t=1)/flag2时可终结System.out.println(n您所要验证的句子正确！nn);elseSystem.out.println(n您所要验证的句子错误！nn);1.4 程序运行截图1.5 小结：通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解。2 LL(1)分析2.1 LL(1)文法 ETE E+TE| TFT T*FT| F(E)|i2.2 LL(1)预测分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)2.3 分析程序代码public class Test public static void main(String a) int id=1; int index1=1;/记录栈最后一个非终结符的位置 String topStack,topIn,operation; StringBuffer inString=null; ArrayList list = new ArrayList(); System.out.println(请输入一个语句:); Scanner in = new Scanner(System.in); String ins=in.nextLine().trim(); if(ins.indexOf(#)=0)/去掉输入串表达式中的空格 inString.delete(kong,kong+1); kong=inString.indexOf( ); StringBuffer stack=new StringBuffer(#E);/分析栈，初始放入E String ll=,i,+,*,(,),#, E,ET/P,ET/P, E,ET/N,/P,/P, T,TF/P,TF/P, T,/P,TF/N,/P,/P, F,/N,)E/N, ),/N, #,acc ;/ll(1)分析矩阵 System.out.println(LL(1)分析过程如下：); System.out.println(n序号t分析栈+getBlank(20)+ 输入数据+getBlank(20)+动作); StringBuffer liutemp = null; while(stack.length()0) int x=0,y=0;/记录在分析表中的的横纵坐标 if(stack.toString().endsWith()|stack.toString().endsWith()/证明是带了一撇的非终结符 index1 = stack.length()-2;/ else index1=stack.length()-1; topStack=String.valueOf(stack.substring(index1,stack.length();/栈顶元素 if(inString.length()0) topIn=String.valueOf(inString.charAt(0);/剩余输入串的第一个元素 else topIn=; for(int i=1;ill.length;i+)/计算对应分析表的哪一行 if(topStack.equals(lli0) x=i; break; for(int i=1;i=3) String first=operation.substring(0,operation.length()-2);/替换部分 String last=operation.substring(operation.length()-2,operation.length();/是否换行部分 if(first.equals()/如果是空字符，有不要加入栈 first=; if(operation.equals(acc) if(stack.length()=1&inString.length()=1) System.out.println(id+t+stack+getBlank(21-stack.length()-inString.length()+inString+getBlank(11-operation.length()+operation); stack.delete(0,1); inString.delete(0,1); System.out.println(匹配成功！); else System.out.println(id+t+stack+getBlank(21-stack.length()-inString.length()+inString+getBlank(6)+error); System.out.println(不能完整匹配！); else if(last.equals(/P) System.out.println(id+t+stack+getBlank(21-stack.length()-inString.length()+inString+getBlank(11-operation.length()+operation); stack.replace(index1,index1+topStack.length(),first);/把栈顶元素替换为分析表中值 if(first.equals() list.add(llx0+-); else liutemp = new StringBuffer(first); list.add(llx0+-+reverse(liutemp); id+; else if(last.equals(/N) System.out.println(id+t+stack+getBlank(21-stack.length()-inString.length()+inString+getBlank(11-operation.length()+operation); stack.replace(index1,index1+topStack.length(),first); inString.delete(0,1);/相当于读下一个元素 liutemp = new StringBuffer(first); list.add(llx0+-+topIn+reverse(liutemp); if(stack.toString().endsWith()|stack.toString().endsWith() index1 = stack.length()-2;/重新设置index1值 else index1=stack.length()-1; id+; else System.out.println(分析表构造出错！); System.exit(0); else if(y=0) System.out.println(id+t+stack+getBlank(21-stack.length()-inString.length()+inString+getBlank(6)+error); System.out.println(输入的符号不符合规定文法！); System.exit(0); else if(x!=0&y!=0&operation.length()=0) System.out.println(id+t+stack+getBlank(21-stack.length()-inString.length()+inString+inString+getBlank(6)+error); System.out.println(输入符号串不完整！); System.exit(0); System.out.println(n该语句自顶向下构建语法树过程：); for(int i = 0;ilist.size();i+) System.out.println(list.get(i); public static StringBuffer reverse(StringBuffer buffer)/字母、运算符倒置 StringBuffer buf = new StringBuffer(); int ix=-1; int length=0; if(buffer.indexOf()0&buffer.indexOf()0) length = buffer.length(); if(buffer.charAt(length-1)=|buffer.charAt(length-1)=) buf.append(buffer.substring(length-2,length); buffer.delete(length-2,length); else buf.append(buffer.charAt(length-1); buffer.delete(length-1,length); return buf; public static String getBlank(int n)/得到n个连续空格String blank=;for(int i=0;i E+T|TT - T*F|F F - P%F|P P - (E)|i3.2 算符优先关系表+*%i()#+*%i(=)#3.3 分析程序代码public class Test2 static HashMap m = new HashMap();static Stack sk;public static void table() m.put(+, );m.put(+*, );m.put(+%, );m.put(+i, );m.put(+(, );m.put(+#, );m.put(*+, );m.put(*, );m.put(*%, );m.put(*i, );m.put(*(, );m.put(*#, );m.put(%+, );m.put(%*, );m.put(%, );m.put(%i, );m.put(%(, );m.put(%#, );m.put(i+, );m.put(i*, );m.put(i%, );m.put(ii, );m.put(i(, );m.put(i), );m.put(i#, );m.put(+, );m.put(*, );m.put(%, );m.put(i, );m.put(, );m.put()*, );m.put()%, );m.put()i, );m.put()(, );m.put(), );m.put()#, );m.put(#+, );m.put(#*, );m.put(#%, );m.put(#i, );m.put(#(, );m.put(#), );m.put(#, =);public static void main(String args) int k = 1, i = 0, xiabiao = 0, f;sk = new Stack();table();System.out.println(请输入符号串:);Scanner sc = new Scanner(System.in);String s = sc.next() + #;char c = s.toCharArray();sk.push(#);System.out.println(分析过程.);while (i = 0 & (Character) sk.get(f) = A) f-;if (m.get(Character) sk.get(f) + + ci) = = 0)& (m.get(Character) sk.get(xiabiao) + + ci) = ) | (Character) sk.get(xiabiao) = A) xiabiao-;for (int t = f; (t = xiabiao & t 0); t-) sk.pop();sk.push(A);sk.push(ci);k = sk.size();i+;for (int a = 0; a E（1）E-E+T（2）E-T（3）T-T*F（4）T-F（5）F-(E)（6）F-i4.2 LR分析表ACTIONGOTOi+*()#ETF0S5S41221S6acc2r2S7r2r23r4r4r4r474S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r54.3 分析程序代码(代码原创)public class Test3 String sentence = new String/文法，是内定了E,E+T,/E-E+TE,T,/E-TT,T*F,/T-T*FT,F,/T-FF,(E),/F-(E)F,i/F-i;String table = new String/为了简单，LR分析表就手工输入了,i,+,*,(,),#,E,T,F,S0,S5,S4,1,2,3,S1,S6,acc,S2,r2,S7,r2,r2,S3,r4,r4,r4,r4,S4,S5,S4,8,2,3,S5,r6,r6,r6,r6,S6,S5,S4,r1,9,3,S7,S5,S4,10,S8,S6,S11,S9,r1,S7,r1,r1,S10,r3,r3,r3,r3,S11,r5,r5,r5,r5,;String in=null;public Test3()this.printSentence();/打印文法Scanner sc = new Scanner(System.in);System.out.println(n请输入一个句子：);in = sc.nextLine().toString();in = removeBlank(in);int index=0;/记录输入串的索引位置StringBuffer stateTrack = new StringBuffer(S0);/状态栈，初始时如S0StringBuffer analysisTrack = new StringBuffer(#);/分析栈，初始放#ArrayList list = new ArrayList();String operator = ;/记录分析表中对应的值String staTrack=;int x,y;/记录在分析表中的位置boolean isOver=false;System.out.println(n语句分析过程如下：);System.out.println(状态栈+getBlank(26)+符号栈+getBlank(20)+输入串tACTIONtGOTO);while(!isOver)x=0;y=0;String inS = in.charAt(index)+;/输入串如今读到的位置for(int i= 1;itable0.length;i+)/查表得到Y坐标if(table0i.equals(inS)y = i;break;staTrack = stateTrack.substring(stateTrack.lastIndexOf(S),stateTrack.length();/读取状态栈最上面一个状态for(int i=1;i0)System.out.print(stateTrack+getBlank(16-stateTrack.length()+analysisTrack+getBlank(18-analysisTrack.length()-in.length()+index)+in.substring(index,in.length()+t+operator);if(operator.startsWith(S)/移进stateTrack.append(operator);analysisTrack.append(inS);index+;/输入串指针下移一位else if(operator.startsWith(r)/规约int m = Integer.parseInt(operator.substring(1,operator.length()-1;/截取后面的数字，用于查产生式，这是从1开始的String liutemp = sentencem1;list.add(sentencem1+=+sentencem0);/规约步骤if(analysisTrack.toString().endsWith(liutemp)analysisTrack.delete(analysisTrack.length()-liutemp.length(),analysisTrack.length();/在分析栈除去产生式右部的字符串elseSystem.out.println(n规约时出错！);System.exit(0);analysisTrack.append(sentencem0);/加上产生式左部，就相当于规约了int stindex=stateTrack.lastIndexOf(S);for(int i=0;iT+FstateTrack.delete(stindex,stateTrack.length();/一次去掉去掉一个状态stindex=stateTrack.lastIndexOf(S);x = 0;y = 0;staTrack = stateTrack.substring(stateTrack.lastIndexOf(S),stateTrack.length();for(int i=1;itable.length;i+)/得到待规约X坐标if(staTrack.equals(tablei0