digui.zip_编译原理_非预测递归分析

package 非递归预测分析; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class predict { private List<List<List<String>>> listPredict;//预测分析表 private String[]finalC; //终结符 private String[]nfinalC; //非终结符 private List<String> listStack; //模拟栈 private String input; //输入序列 public predict(){ super(); } public predict(String str){ /* * 初始化相应的参数 * (1)输入序列 * (2)预测分析表 * (3)终结集 * (4)非终结集 * (5)初始化栈 */ this.setInput(str); this.setlistPredict(this.creatPredict()); this.setFinalC(this.createFinal()); this.setnfinalC(this.createNFinal()); this.setlistStack(this.createStack()); } public predict(List<List<List<String>>> listPredict){ this.listPredict=listPredict; } public List<List<List<String>>> getlistPredict() { return listPredict; } public void setlistPredict(List<List<List<String>>> listPredict) { this.listPredict = listPredict; } public List<String> getlistStack() { return listStack; } public void setlistStack(List<String> listStack) { this.listStack = listStack; } public String getInput() { return input; } public void setInput(String input) { this.input = input; } public String[] getFinalC() { return finalC; } public void setFinalC(String[] finalC) { this.finalC = finalC; } public String[] getnfinalC() { return nfinalC; } public void setnfinalC(String[] nfinalC) { this.nfinalC = nfinalC; } /* * 构建一个预测分析表 */ public List<List<List<String>>> creatPredict(){ //预测分析表 String[][][]strPredict={ {{"E",";","L"},{"E",";","L"},{},{},{},{},{},{"E",";","L"},{},{},{"ε"}}, {{"T","E'"},{"T","E'"},{},{},{},{},{},{"T","E'"},{},{},{}}, {{},{},{"+","T","E'"},{"+","T","E'"},{},{},{},{},{"ε"},{"ε"},{}}, {{"F","T'"},{"F","T'"},{},{},{},{},{},{"F","T'"},{},{},{}}, {{},{},{"ε"},{"ε"},{"*","F","T'"},{"/","F","T'"},{"mod","F","T'"},{},{"ε"},{"ε"},{}}, {{"id"},{"num"},{},{},{},{},{},{"(","E",")"},{},{},{}} }; System.out.println(strPredict.length); System.out.println(strPredict[0].length); System.out.println(strPredict[1].length); List<List<List<String>>> list=new ArrayList<>(); for(int i=0;i<strPredict.length;i++){ List<List<String>>listA=new ArrayList<>(); for(int j=0;j<strPredict[i].length;j++){ List<String> listB=new ArrayList<>(); for(int k=0;k<strPredict[i][j].length;k++){ listB.add(strPredict[i][j][k]); } listA.add(listB); } list.add(listA); } return list; } public String[] createFinal(){ //终结符构建 String[]F={"id","num","+","-","*","/","mod","(",")",";","#"}; return F; } public String[] createNFinal(){ //非终结符构建 String[]nF={"L","E","E'","T","T'","F"}; return nF; } public List<String> createStack(){//构建初始栈 List<String> listStack=new ArrayList<>(); listStack.add("#"); listStack.add("L"); return listStack; } /* * 非递归的预测分析 * listPredict是预测分析表 * input是输入序列 */ public boolean match(List<String> listStack,String input){ String[]inputC=toChar(input); int ip=0; while(ip<inputC.length){ String a=listStack.get(listStack.size()-1); String b=inputC[ip]; if(isFinalC(a)){//若栈顶元素是一个终结符 (a)删除栈顶元素 (b)获取下一个输入序列字符 listStack.remove(listStack.size()-1); ip++; } else{//x不是终结, 则将使用栈顶元素的展开式对栈顶元素实现替换，且展开式不为空即("ε") System.out.print(listStack+" "); List<String>str=listPredict.get(findIndex(a,nfinalC)).get(findIndex(b,finalC)); String[]strPredict=tostrPredictrray(str); System.out.print("展开式:"+str); listStack.remove(listStack.size()-1); if(!str.get(0).equals("ε")){ listStack.addAll(toReverseList(strPredict)); } System.out.println(); } if(listStack.get(listStack.size()-1)=="#"){//匹配到了最后一个字符若是#则正确结束。 return true; } } return false; } /* * 将一个字符串转换成一个字符数组 */ public String[] toChar(String str){ return str.split(" "); } /* * 判断一个字符串是否属于终结符集 */ public boolean isFinalC(String str){ for(int i=0;i<finalC.length;i++){ if(finalC[i].equals(str)){ return true; } } return false; } /* * 根据一个字符串，查找出其在字符数组中的索引 */ public int findIndex(String str,String[]strPredict){ for(int i=0;i<strPredict.length;i++){ if(str.equals(strPredict[i])){ return i; } } return -1; } public String[] tostrPredictrray(List<String> list){ int length=list.size(); String[]strPredict=new String[length]; for(int i=0;i<length;i++){ strPredict[i]=list.get(i); } return strPredict; } /*将一个字符串数组给反序*/ public String[] toReverse(String[] str){ int length=str.length; for(int i=0;i<length/2;i++){ String s=str[i]; str[i]=str[length-1-i]; str[length-1-i]=s; } return str; } /* * 将一个字符串数组转换成List队列 */ public List<String> toReverseList(String[]str){ List<String> list=new ArrayList<>(); for(int i=str.length-1;i>=0;i--){ list.add(str[i]); } return list; } public static void main(String[]args){ String str="id + id * id ; #"; predict a=new predict(str); //开始匹配 boolean flag=a.match(a.getlistStack(), a.getInput()); if(flag==true){ System.out.println("正确结束！"); } else{ System.out.println("错误结束！"); } } }