语法分析算符优先-编译原理

package 语法分析器; // import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Scanner; import java.util.Set; import java.util.Stack; //测试数据 1 构建关系表好着 //8 //E->E+T //E->T //T->T*F //T->F //F->P^F //F->P //P->(E) //P->i //测试数据2（默认输入串为i+i#） //6 //S->#E# //P->i //F->P //T->F //E->T //E->E+T public class suanfuyouxianwenfa1 { static int step=0;//记录第几步从第一步开始 static int MAX=507; char[][] relation=new char[MAX][MAX];//关系表数组 static List<Character> VT= new ArrayList<Character> ();//终结符集 static List<WF> VN_set=new ArrayList<WF>();//非终结符 用来分离并存储产生式左部和右部 static Map<String,Integer> VN_dic=new HashMap<String,Integer>();//记录VN非终结符 static int[] used=new int[MAX];//用来记录终结符为第几个终结符 static String s1;//产生式左部的引用变量 static String s2;//产生式右部的引用变量 static boolean[][] F;//firstvt集 static boolean[][] Fl;//lastvt集 static char[][] table;//文法优先表 static char currentRelation;//优先关系 static int index=-1;//当前符号所在下标 static Stack stack=new Stack();// static Stack stackl=new Stack(); String stackString=null; static String str2="i+i#"; static char a;//当前符号 static Stack<Character> S=new Stack<Character>(); //查找某VN（非终结符）所在的VN_set list中所在的位置 public static int findindexFromVN_set(char P){ for(int i=0;i<VN_set.size();i++){ if(VN_set.get(i).left.charAt(0)==P){ return i; } } return -1; } //查找某VT（终结符）所在的VT list中的位置 public static int findindexFromVT(char a){ return VT.indexOf(a); } //构建firstvt用,把(P,a)推进栈//书上91页右下角程序思路 public static void insert(char P,char a){ // System.out.println("P->"+P+"|"+"findindexFromVN_set(P)->"+findindexFromVN_set(P)); // System.out.println("a->"+a+"|"+"VT.indexOf(a)->"+VT.indexOf(a)); if(!F[findindexFromVN_set(P)][VT.indexOf(a)]){ F[findindexFromVN_set(P)][VT.indexOf(a)]=true; stack.push(""+'('+P+','+a+')');//把(P,a)推进stack栈end } } //构建lastvt集用,把(P,a)推进栈//书上91页右下角程序思路 public static void insertl(char P,char a){ // System.out.println("P->"+P+"|"+"findindexFromVN_set(P)->"+findindexFromVN_set(P)); // System.out.println("a->"+a+"|"+"VT.indexOf(a)->"+VT.indexOf(a)); if(!Fl[findindexFromVN_set(P)][VT.indexOf(a)]){ Fl[findindexFromVN_set(P)][VT.indexOf(a)]=true; stackl.push(""+'('+P+','+a+')');//把(P,a)推进stack栈end } } //构造(非终极符)的firstvt函数//书上91页右下角程序思路 public static void makefirst(){ F=new boolean[VN_set.size()][VT.size()]; //先初始化F集 for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VT.size();j++){ F[i][j]=false; } } for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VN_set.get(i).right.size();j++){ if(Character.isUpperCase(VN_set.get(i).left.charAt(0))&&!Character.isUpperCase(VN_set.get(i).right.get(j).charAt(0))) { insert(VN_set.get(i).left.charAt(0),VN_set.get(i).right.get(j).charAt(0) ); } if((VN_set.get(i).right.get(j).length()>2)&&Character.isUpperCase(VN_set.get(i).left.charAt(0))&&Character.isUpperCase(VN_set.get(i).right.get(j).charAt(0))&&!Character.isUpperCase(VN_set.get(i).right.get(j).charAt(1))){ insert(VN_set.get(i).left.charAt(0),VN_set.get(i).right.get(j).charAt(1) ); } } } while(!stack.isEmpty()){ String str=(String) stack.pop();//str=(P,a); char Q=str.charAt(1);char a=str.charAt(3); for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VN_set.get(i).right.size();j++){ if(Character.isUpperCase(VN_set.get(i).left.charAt(0))&&VN_set.get(i).right.get(j).charAt(0)==Q){ insert(VN_set.get(i).left.charAt(0), a); } } } } for(int i=0;i<F.length;i++){ System.out.printf("%c :",VN_set.get(i).left.charAt(0)); for(int j=0;j<F[i].length;j++){ if(F[i][j]==true){ System.out.printf(" %c",VT.get(j)); } } System.out.println(); } } //构造(非终极符)的lastvt函数//书上91页右下角程序思路 public static void makelast(){ Fl=new boolean[VN_set.size()][VT.size()]; for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VT.size();j++){ Fl[i][j]=false; } } for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VN_set.get(i).right.size();j++){ if(Character.isUpperCase(VN_set.get(i).left.charAt(0))&&!Character.isUpperCase(VN_set.get(i).right.get(j).charAt(VN_set.get(i).right.get(j).length()-1))) { insertl(VN_set.get(i).left.charAt(0),VN_set.get(i).right.get(j).charAt(VN_set.get(i).right.get(j).length()-1) ); } if((VN_set.get(i).right.get(j).length()>2)&&Character.isUpperCase(VN_set.get(i).left.charAt(0))&&Character.isUpperCase(VN_set.get(i).right.get(j).charAt(VN_set.get(i).right.get(j).length()-1))&&!Character.isUpperCase(VN_set.get(i).right.get(j).charAt(VN_set.get(i).right.get(j).length()-2))){ insertl(VN_set.get(i).left.charAt(0),VN_set.get(i).right.get(j).charAt(VN_set.get(i).right.get(j).length()-2) ); } } } while(!stackl.isEmpty()){ String str=(String)stackl.pop();//str=(P,a); char Q=str.charAt(1);char a=str.charAt(3); for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VN_set.get(i).right.size();j++){ if(Character.isUpperCase(VN_set.get(i).left.charAt(0))&&VN_set.get(i).right.get(j).charAt(VN_set.get(i).right.get(j).length()-1)==Q){ insertl(VN_set.get(i).left.charAt(0), a); } } } } for(int i=0;i<Fl.length;i++){ System.out.printf("%c :",VN_set.get(i).left.charAt(0)); for(int j=0;j<Fl[i].length;j++){ if(Fl[i][j]==true){ System.out.printf(" %c",VT.get(j)); } } System.out.println(); } } //构造文法优先表函数//书上92页左上角程序思路 public static void make_table(){ table=new char[VT.size()][VT.size()]; for(int i=0;i<VN_set.size();i++){ for(int j=0;j<VN_set.get(i).right.size();j++){ String right=VN_set.get(i).right.get(j); for(int t=0;t<VN_set.get(i).right.get(j).length()-1;t++){ char c1=right.charAt(t); char c2=right.charAt(t+1); if(!Character.isUpperCase(c1)&&!Character.isUpperCase(c2)){ table[findindexFromVT(c1)][findindexFromVT(c2)]='='; } if((t<(VN_set.get(i).right.get(j).length()-2)) &&!Character.isUpperCase(c1) &&Character.isUpperCase(c2) &&!Character.isUpperCase(right.charAt(t+2))){ table[findindexFromVT(c1)][findindexFromVT(right.charAt(t+2))]='='; } if(!Character.isUpperCase(c1)&&Character.isUpperCase(c2)){ for(int i1=0;i1<F[findindexFromVN_set(c2)].length;i1++){ if(F[findindexFromVN_set(c2)][i1]==true){ table[findindexFromVT(c1)][i1]='<'; } } } if(Character.isUpperCase(c1)&&!Character.isUpperCase(c2)){ for(int i1=0;i1<Fl[findindexFromVN_set(c1)].length;i1++){ if(Fl[findindexFromVN_set(c1)][i1]==true){ table[i1][findindexFromVT(c2)]='>'; } } } } } } System.out.println("*********************算符优先关系表***************************"); System.out.println("\n--------------------------------------------------------"); for(int i=-1;i<VT.size();i++){ for(int j=-1;j<VT.size();j++){ if(i==-1&&j==-1){ System.out.printf("| |"); continue; } if(i==-1){ System.out.printf("%4c |",VT.get(j)); }else{ if(j==-1){ System.out.printf("|%4c |",VT.get(i)); continue; } System.out.printf("%4c |",table[i][j]); } } System.out.println("\n--------------------------------------------------------"); } } //移进规约函数//书上93页右上角程序思路 public static void move_reduction(String str){//str="i+i#" char Q;