JAVA语言编写的编译原理FIRST和FOLLOW集.doc

package cn.spy.action;import java.util.ArrayList;import java.util.Scanner;import java.util.StringTokenizer;*某一输入实例：* E-TE* E-+E|* T-FT* T-T|* F-PF* F-*F|* P-(E)|a|b|* end*/public class FirstFollow3 public ArrayList in=new ArrayList();/这数据结构真是逼人绝路才去想到绝处逢生，哈哈，关键实现了可变长度文法接收，在这存放的是拆分后最简单的文法，也是由用户输入public ArrayList first = new ArrayList();/包括左推导符和其First集public ArrayList follow = new ArrayList();public ArrayList track = new ArrayList();/track有一条一条的非终结符串组成的路径数组public FirstFollow3()Scanner sc = new Scanner(System.in);System.out.println(请分行输入一个完整文法:(end结束);String sline=;sline=sc.nextLine();while(!sline.startsWith(end)StringBuffer buffer=new StringBuffer(sline);int l=buffer.indexOf( );while(l=0)/去空格buffer.delete(l,l+1);l=buffer.indexOf( );sline=buffer.toString();String s=sline.split(-);/左推导符if(s.length=1)s=sline.split();/考虑到输入习惯和形式问题if(s.length=1)s=sline.split(=);if(s.length=1)System.out.println(文法有误);System.exit(0);StringTokenizer fx = new StringTokenizer(s1,|);/按英文隔符拆开产生式或按中文隔符拆开while(fx.hasMoreTokens()String one = new String2;/对于一个语句只需保存两个数据就可以了，语句左部和语句右部的一个简单导出式，假如有或符，就按多条存放one0=s0;/头不变,0位置放非终结符one1=fx.nextToken();/1位置放导出的产生式，就是产生式右部的一个最简单导出式in.add(one);sline=sc.nextLine();/求First集过程cess(First);/* 打印First集算法和First集*/System.out.println(nFirst集算法：);this.print(track);/打印First集算法System.out.println(nFirst集：);for(int i=0;ifirst.size();i+)String r=first.get(i);System.out.print(First(+r0+)=);for(int j=1;jr.length;j+)System.out.print(rj);if(jr.length-1)System.out.print(,);System.out.println();track.clear();/因为下面还要用，这里就先清空了/求Follow集过程cess(Follow);System.out.println(nFollow集算法：);for(int i=0;itrack.size();i+)String one = track.get(i);System.out.print(Follow(+follow.get(i)0+):t);for(int j=0;jone.length;j+)System.out.print(onej+t);System.out.println();System.out.println(nFollow集：);for(int i=0;ifollow.size();i+)String r=follow.get(i);System.out.print(Follow(+r0+)=);for(int j=1;jr.length;j+)System.out.print(rj);if(jr.length-1)System.out.print(,);System.out.println();public void process(String firstORfollow)for(int i=0;iin.size();i+)boolean bool=true;for(int j=0;ji;j+)if(in.get(j)0.equals(in.get(i)0)bool=false;if(bool)ArrayList a=null;if(firstORfollow.equals(First) a=this.getFirst(in.get(i)0,First(+in.get(i)0+)/);else if(firstORfollow.equals(Follow)a=this.getFollow(in.get(i)0,in.get(i)0,);String sf=new Stringa.size()/2+1;String st=new Stringa.size()/2;sf0=in.get(i)0;for(int j=0;ja.size();j+)if(j%2=0) sfj/2+1=a.get(j);elsestj/2=a.get(j);if(firstORfollow.equals(First) first.add(sf);/first集else if(firstORfollow.equals(Follow)follow.add(sf);track.add(st);/对应上面求得集的路径，在开始保存该非终结符了，因为已保存了该字符的First或Follow表示法public ArrayList getFirst(String s,String track1)/s表示左推导，track表示寻找路径，避免循环查找ArrayList result = new ArrayList();ArrayList result1 = new ArrayList();if(Character.isUpperCase(s.charAt(0)/如果是非终结符，大写for(int i=0;i=0)/假如在查找过程嵌套了这步，证明进入了无限循环，不需再找，此路径无结果;/有点要注意一下，本来一开始就把第一个开始推导符的First路径放进去了的，所以要避开这一次，不然已开始就结束了else if(one1.length()=1|one1.charAt(1)!=&one1.charAt(1)!=)result1=getFirst(one1.charAt(0)+,track1+First(+one1.charAt(0)+)/);else if(one1.length()1&one1.charAt(1)=|one1.charAt(1)=)/假如接下来一个要求First的非终结符带了一撇，那一撇包括英文表示和中文表示result1=this.getFirst(one1.substring(0,2),track1+First(+one1.substring(0,2)+)/);result=addArrayString(result,result1);result1.clear();else/如果产生式首字符是终结字符if(s.equals()/注意：表示空的字符只能是这种了，其他形式在这个编译器中不能通过，还请原谅result1.add(#);elseresult1.add(s);result1.add(track1);/为了方便，把路径也加入了结果集，不然可能路径不匹配，没办法，因为中间有删去重复项result=result1;return result;public ArrayList getFollow(String s,String element,String track1)/从右至左反推，不是求Follow的等价Follow，因为推到后面的反而范围大ArrayList result = new ArrayList();ArrayList result1 = new ArrayList();if(Character.isUpperCase(s.charAt(0) for(int i=0;i=0&track1.indexOf(char)(a+i)+)=0)/假如之前走过某一步，就不必再走了，那是死循环，之前在这语句前面加了个else,结果又部分内容显示不出来，总算发现了，就算反推到开始符号，也不一定就到结果了的，开始符号也可以反推，所以要继续;else if(one1.indexOf(s)=0&(olen-slen=one1.indexOf(s)|slen=2|one1.charAt(one1.indexOf(s)+1)!=&one1.charAt(one1.indexOf(s)+1)!=)/如果在右产生式中真正存在需要求反推的字符,后面的条件控制它是真正存在，因为里面包含这个字符也不一定是真，就像E中包含E，但这不是真正的包含int index=-1;index = one1.indexOf(s,0);while(index=0)/之前这没有用到循环，结果可能少点东西，仔细一想，必须要，就算是一个推导语句，也可能推出多个相同非终结符的组合，其实这也是一种特殊情况了，不考虑也可能正确了，也可能之前在其他地方把这样的结果求出来了，不求也没事，但就像假如要求T的Follow集，假如可以产生出T+a*T*b，这时还是有用的，万一吧if(olen-slen=index)/如果该非终结符在末尾，那么求导出该产生式的非终结符的倒推result1=getFollow(one0, element,track1+(char)(a+i);result=addArrayString(result,result1);result1.clear();else/如果后继非终结符在产生式中不是最后int t=index+slen;/指向在产生式非终结符s的后一个字符位置result1=returnFirstofFollow(s, element, track1, one0, one1, index, t);result=addArrayString(result,result1);/之前也没写这句话，结果把之前的内容覆盖了，就是之前的数据丢失result1.clear();index = one1.indexOf(s,index+1);/endwhileif(one1.endsWith(element)/如果最开始要求的Follow集非终结符在末尾result1.add(#);result1.add(in.get(0)0+one1+t);result=addArrayString(result,result1);/之前也没写这句话，结果把之前的内容覆盖了，就是之前的数据丢失result1.clear(); /endforreturn result;public ArrayList returnFirstofFollow(String s,String element,String track1,String one0,String one1,int index,int t)/返回求Follow集中要求的First集部分ArrayList result = new ArrayList();ArrayList result1 = new ArrayList();ArrayList beckFirst;String lsh;/记录下一个字符if(t+10)/这些都是为了算法输出容易理解点用的，其实要不输出这算法，要省下好多东西ls=in.get(int)(track1.charAt(track1.length()-1)-a);/得到上一步调用的语句if(Character.isUpperCase(ls1.charAt(ls1.length()-1)beflen=1;beckFirst=this.getFirst(lsh,First(+lsh+)/);/相当于得到后继字符的First集for(int j=0;jbeckFirst.size()/2;j+)/调用求First集，返回的不一定只一个结果String lh=;if(beckFirst.get(j*2).equals(#)result1.add(beckFirst.get(j*2);/这个加了是数据，下面一步就是把地址加上，就是一个结果，要两份数据if(ls=null)lh=in.get(0)0+one1+one1.substring(0,index)+element+one1.substring(t+lsh.length(),one1.length();elselh=in.get(0)0+one1+one1.substring(0,index)+ls1+one1.substring(index+s.length(),one1.length()+.+element+one1.substring(t+lsh.length(),one1.length();result1.add(lh);result=addArrayString(result,result1);result1.clear();if(1+index+lsh.length()one1.length()/证明后面还有字符,为什么要这一步，打个比方把，假如要求F的Follow集，而存在产生式FPQ,而P的有个First集为空，那么得还接着求Q的First，类推，假如最后一个字符Q还是返回空，那么求要求产生式左边的推导非终结符的Follow集了，必须把这些结果都算到F的Follow集中去result1=returnFirstofFollow(s, element, track1, one0,one1, index, t+lsh.length();else/到最后,那么求要求产生式左边的推导非终结符的Follow集了，其实这和上面一种情况都很特殊了，一般用不上了result1=getFollow(one0, element, track1);else/其实下面这一大坨都是为了易懂一点，Follow集算法清晰一点，好苦啊if(Character.isUpperCase(one1.charAt(t)/如果是有随后的一个非终结符的First集求出的结果if(ls=null)lh=in.get(0)0+one1+one1.substring(0,index)+element+beckFirst.get(j*2)+one1.substring(t+lsh.length(),one1.length();elselh=in.get(0)0+one1+one1.substring(0,index)+ls1+one1.substring(index+s.length(),one1.length()+.+element+beckFirst.get(j*2)+one1.substring(t+lsh.length(),one1.length(); else/如果不是大写，就是终结符了，那么用First集求出来的结果连接起来还是一样的，所以不要重复打印两次了if(ls=null)if(element=in.get(0)0|s.equals(element)lh=in.get(0)0+one1.substring(0,index)+element+one1.substring(t,one1.length()+t;elselh=in.get(0)0+one1+one1.substring(0,index)+element+one1.substring(t,one1.length()+t;elseif(ls1.length()=1|ls1.length()=2&!ls1.endsWith()&!ls1.endsWith()lh=in.get(0)0+one1+one1.substring(0,index)+element+one1.substring(t,one1.length();elselh=in.get(0)0+one1+one1.substring(0,index)+ls1+one1.substring(index+s.length(),one1.length()+.+element+one1.substring(t,one1.length()+!;result1.add(beckFirst.get(j*2);/这个加了是数据，下面一步就是把地址加上，就是一个结果，要两份数据result1.add(lh);result=addArrayString(result,result1);/之前也没写这句话，结果把之前的内容覆盖了，就是之前的数据丢失result1.clear();return result;public ArrayList addArrayString(ArrayList a,ArrayList b)/两个字符串数组相加ArrayList result = new ArrayList();for(int i=0;ia.get(i+1).length()/如果新来的路径比现有的短result.set(index, s);result.set(index+1,a.get(i+1);continue;result.add(s);result.add(a.get(i+1);/还是要把路径继续保存在新的结果集中for(int i=0;ib.get(i+1).length()/如果新来的路径比现有的短result.set(index, s);result.set(inde