編譯原理課程設(shè)計福建農(nóng)林大學java

1、福建農(nóng)林大學計算機與信息學院計算機類課程設(shè)計報告課程名稱：編譯原理課程設(shè)計題目：語法分析器姓 名：陳錦燦系：計算機專 業(yè)：計算機科學與技術(shù)年 級：2012級學 號：3126010067指導教師：林清波20152016學年第一學期福建農(nóng)林大學計算機與信息學院計算機類課程設(shè)計結(jié)果評定評語：成績：指導教師簽字：任務(wù)下達日期：評定日期：目 錄1 正則表達式11.1 正則表達式11.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖11.3 分析程序代碼11.4 程序運行截圖11.5 小結(jié)：12 LL(1)分析22.1 LL(1)文法22.2 LL(1)預(yù)測分析表22.3 分析程序代碼22.4 程序運行截圖22.5 小結(jié)

2、23 算符優(yōu)先分析33.1 算符優(yōu)先文法33.2 算符優(yōu)先關(guān)系表33.3 分析程序代碼33.4 程序運行截圖33.5 小結(jié)34 LR分析44.1 LR文法44.2 LR分析表44.3 分析程序代碼(代碼原創(chuàng))44.4 程序運行截圖44.5 小結(jié)4參考文獻：41 正則表達式1.1 正則表達式 (a|b)*(aa|bb)(a|b)* 1.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖 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("文法規(guī)則：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時可終結(jié)System.out.println("n您所要驗證的句子正確！nn");elseSystem.out.println("n您所要驗證的句子錯誤！nn"

5、;);1.4 程序運行截圖1.5 小結(jié)：通過該課程設(shè)計，掌握了什么是編譯程序，編譯程序工作的基本過程及其各階段的基本任務(wù)，熟悉了編譯程序總流程框圖，了解了編譯程序的生成過程、構(gòu)造工具及其相關(guān)的技術(shù)對課本上的知識有了更深的理解。2 LL(1)分析2.1 LL(1)文法 ETE' E'+TE'| TFT' T'*FT'| F(E)|i2.2 LL(1)預(yù)測分析表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;/記錄棧最后一個非終結(jié)符的位置 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);/截取#號在內(nèi)的前部 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)+" 輸入數(shù)據(jù)"+getBlank(20)+"動作"); StringBuffer liutemp = null; while(stack.length()>0) int x=0,y=0;/記錄在分析表中的的橫縱坐標 if(stack.toString().endsWi

12、th("'")|stack.toString().endsWith("")/證明是帶了一撇的非終結(jié)符 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+)/計算對應(yīng)分析表的哪一行 if(topStack.equals(lli0) x=i; break; for(int i=1;i<ll0.length;i+)/計算對應(yīng)分析表的列數(shù) 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;/重新設(shè)置index1值 else index1=stack.len

19、gth()-1; id+; else System.out.println("分析表構(gòu)造出錯！"); 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("輸入的符號不符合規(guī)定文法！"); 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該語句自頂向下構(gòu)建語法樹過程："); 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個連續(xù)空格String blank=""for(int i=0;i<n;i+)blank+=" "return blank;2.4 程序運行截圖2.5 小結(jié)通過該課程設(shè)計，全面系統(tǒng)的理解了編譯原理程序構(gòu)造的一般原理和基本實現(xiàn)方法。把死板的課本知識變得生動有趣，激發(fā)了學習的積極性。3 算符優(yōu)先分析3.1 算符優(yōu)先文法E -> E+T|TT -> T*F|F F -> P%F|P P -> (E)|i3.2 算符優(yōu)先關(guān)系表+*%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 小結(jié)在這次課程設(shè)計中，我就是按照實驗指導的思想來完成。加深了理解文件系統(tǒng)的內(nèi)部功能

35、及內(nèi)部實現(xiàn)，培養(yǎng)實踐動手能力和程序開發(fā)能力的目的。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 分析程序代碼(代碼原創(chuàng))public class Test3 String sentence =

36、new String/文法，是內(nèi)定了"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");/狀態(tài)棧，初始時如S0StringBuffer analysisTrac

44、k = new StringBuffer("#");/分析棧，初始放#ArrayList<String> list = new ArrayList<String>();String operator = ""/記錄分析表中對應(yīng)的值String staTrack=""int x,y;/記錄在分析表中的位置boolean isOver=false;System.out.println("n語句分析過程如下：");System.out.println("狀態(tài)棧"+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(jié)坐標if(table0i.equals(inS)y = i;break;staTrack = stateTrack.substring(stateTrack.lastIndexOf("S"),stateTrack.len

46、gth();/讀取狀態(tài)棧最上面一個狀態(tài)for(int i=1;i<table.length;i+)/得到X坐標if(staTrack.equals(tablei0)x = i;break;operator = tablexy;/分析表中對應(yīng)位置的動作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")/規(guī)約int m = Integer.parseInt(operator.substring(1,operator.length()-1;/截取后面的數(shù)字，用于查產(chǎn)生式，這是從1開始的String liutemp = s

48、entencem1;list.add(sentencem1+"=>"+sentencem0);/規(guī)約步驟if(analysisTrack.toString().endsWith(liutemp)analysisTrack.delete(analysisTrack.length()-liutemp.length(),analysisTrack.length();/在分析棧除去產(chǎn)生式右部的字符串elseSystem.out.println("n規(guī)約時出錯！");System.exit(0);analysisTrack.append(sentencem0);/加上產(chǎn)生式左部，就相當于規(guī)約了int stindex=stateTrack.lastIndexOf("S");for(int i=0;i<liutemp.length();i+)/為了程序不節(jié)外生枝，就簡單化了，這個地方的求liutemp的長度才確定有效字符個數(shù)還是不準確的，假如產(chǎn)生式中字母