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

1、福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：陈锦灿系：计算机专 业：计算机科学与技术年 级：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 小结

2、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,

3、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 < len)ch =

4、 str1.charAt(index);if(ch = 'a') j = 0;if(ch = 'b') j = 1;if(ch != 'a' && ch != 'b') t = 0; break;index+;i = sij;flag = i;if(flag>=3 && t=1)/flag>2时可终结System.out.println("n您所要验证的句子正确！nn");elseSystem.out.println("n您所要验证的句子错误！nn"

5、;);1.4 程序运行截图1.5 小结：通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解。2 LL(1)分析2.1 LL(1)文法 ETE' E'+TE'| TFT' T'*FT'| F(E)|i2.2 LL(1)预测分析表i+*()#EETE'ETE'E'E'+TE'E'E'TTFT'TFT'T'T'T'*FT

6、9;T'T'FFiF(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<String> list = new ArrayList<String>(); System.out.println("请输入一个语句:"); Scanner in =

7、new Scanner(System.in); String ins=in.nextLine().trim(); if(ins.indexOf("#")<0)/假如最后完了输入#号也没事 ins+="#" else ins=ins.substring(0,ins.indexOf("#")+1);/截取#号在内的前部 inString = new StringBuffer(ins); int kong=inString.indexOf(" "); while(kong>=0)/去掉输入串表达式中的空格 i

8、nString.delete(kong,kong+1); kong=inString.indexOf(" "); StringBuffer stack=new StringBuffer("#E");/分析栈，初始放入E String ll="","i","+","*","(",")","#", "E","ET/P","","","

9、;ET/P","","", "E","","ET/N","","","/P","/P", "T","TF/P","","","TF/P","","", "T","","/P","TF/N",

10、"","/P","/P", "F","/N","","",")E/N","","", ")","","","","","/N","", "#","","","","&qu

11、ot;,"","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().endsWi

12、th("'")|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="&q

13、uot; for(int i=1;i<ll.length;i+)/计算对应分析表的哪一行 if(topStack.equals(lli0) x=i; break; for(int i=1;i<ll0.length;i+)/计算对应分析表的列数 if(topIn.equals(ll0i) y=i; break; operation=llxy;/动作命令 if(operation.length()>=3) String first=operation.substring(0,operation.length()-2);/替换部分 String last=operation.sub

14、string(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

15、+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("不能完整匹配！"); el

16、se 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+"->&quo

17、t;); 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,inde

18、x1+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.len

19、gth()-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&&a

20、mp;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;i

21、<list.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) buf.append(buffer.reverse(); else

22、 while(buffer.length()>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; pub

23、lic static String getBlank(int n)/得到n个连续空格String blank=""for(int i=0;i<n;i+)blank+=" "return blank;2.4 程序运行截图2.5 小结通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。3 算符优先分析3.1 算符优先文法E -> E+T|TT -> T*F|F F -> P%F|P P -> (E)|i3.2 算符优先关系表+*%i()#+*%i(=)#3.

24、3 分析程序代码public class Test2 static HashMap<String, String> m = new HashMap<String, String>();static Stack<Character> sk;public static void table() m.put("+", ">");m.put("+*", "<");m.put("+%", "<");m.put("+i&qu

25、ot;, "<");m.put("+(", "<");m.put("+)", ">");m.put("+#", ">");m.put("*+", ">");m.put("*", ">");m.put("*%", "<");m.put("*i", "<"

26、);m.put("*(", "<");m.put("*)", ">");m.put("*#", ">");m.put("%+", ">");m.put("%*", ">");m.put("%", "<");m.put("%i", "<");m.put("%("

27、;, "<");m.put("%)", ">");m.put("%#", ">");m.put("i+", ">");m.put("i*", ">");m.put("i%", ">");m.put("ii", "");m.put("i(", "");m.put(&

28、quot;i)", ">");m.put("i#", ">");m.put("(+", "<");m.put("(*", "<");m.put("(%", "<");m.put("(i", "<");m.put("(", "<");m.put("()", "

29、=");m.put("(#", "");m.put(")+", ">");m.put(")*", ">");m.put(")%", ">");m.put(")i", "");m.put(")(", "");m.put(")", ">");m.put(")#", &q

30、uot;>");m.put("#+", "<");m.put("#*", "<");m.put("#%", "<");m.put("#i", "<");m.put("#(", "<");m.put("#)", "");m.put("#", "=");public stati

31、c void main(String args) int k = 1, i = 0, xiabiao = 0, f;sk = new Stack<Character>();table();System.out.println("请输入符号串:");Scanner sc = new Scanner(System.in);String s = sc.next() + "#"char c = s.toCharArray();sk.push('#');System.out.println("分析过程.");whil

32、e (i < c.length) f = k - 1;while (f >= 0 && (Character) sk.get(f) = 'A') f-;if (m.get(Character) sk.get(f) + "" + ci) = "<")| (m.get(Character) sk.get(f) + "" + ci) = "=") k+;sk.push(ci);i+; else xiabiao = f - 1;while (xiabiao >= 0)

33、&& (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 < sk.size(); a+) if(s

34、k.get(a)!='A') System.out.print(sk.get(a);System.out.print("n");if (Character) sk.peek() = '#') System.out.println(s.substring(0, s.length()-1) + " success!"); else System.out.println(s + " error！");3.4 程序运行截图3.5 小结在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件系统的内部功能

35、及内部实现，培养实践动手能力和程序开发能力的目的。4 LR分析4.1 LR文法（0）E'->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 =

36、new String/文法，是内定了"E","E+T",/E->E+T"E","T",/E->T"T","T*F",/T->T*F"T","F",/T->F"F","(E)",/F->(E)"F","i"/F->i;String table = new String/为了简单，LR分析表就手工输入了""

37、,"i","+","*","(",")","#","E","T","F","S0","S5","","","S4","","","1","2","3","S1","","

38、S6","","","","acc","","","","S2","","r2","S7","","r2","r2","","","","S3","","r4","r4"

39、,"","r4","r4","","","","S4","S5","","","S4","","","8","2","3","S5","","r6","r6","","r

40、6","r6","","","","S6","S5","","","S4","","r1","","9","3","S7","S5","","","S4","","",&

41、quot;","","10","S8","","S6","","","S11","","","","","S9","","r1","S7","","r1","r1","","&qu

42、ot;,"","S10","","r3","r3","","r3","r3","","","","S11","","r5","r5","","r5","r5","","",""St

43、ring 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 analysisTrac

44、k = new StringBuffer("#");/分析栈，初始放#ArrayList<String> list = new ArrayList<String>();String operator = ""/记录分析表中对应的值String staTrack=""int x,y;/记录在分析表中的位置boolean isOver=false;System.out.println("n语句分析过程如下：");System.out.println("状态栈"+getBlan

45、k(26)+"符号栈"+getBlank(20)+"输入串tACTIONtGOTO");while(!isOver)x=0;y=0;String inS = in.charAt(index)+""/输入串如今读到的位置for(int i= 1;i<table0.length;i+)/查表得到Y坐标if(table0i.equals(inS)y = i;break;staTrack = stateTrack.substring(stateTrack.lastIndexOf("S"),stateTrack.len

46、gth();/读取状态栈最上面一个状态for(int i=1;i<table.length;i+)/得到X坐标if(staTrack.equals(tablei0)x = i;break;operator = tablexy;/分析表中对应位置的动作if(operator.length()>0)System.out.print(stateTrack+getBlank(16-stateTrack.length()+analysisTrack+getBlank(18-analysisTrack.length()-in.length()+index)+in.substring(index

47、,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 = s

48、entencem1;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;i<liutemp.length();i+)/为了程序不节外生枝，就简单化了，这个地方的求liutemp的长度才确定有效字符个数还是不准确的，假如产生式中字母后