编译原理 LL1语法分析器(JAVA写的)

package re.sa; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class LL1SA { /* * 原始文法： * * E→E+T|E/T|T * T→T-F|T*F|F * F→(E)|i */ /* * 消除左递归 * * E→TM * M→+TM|/TM|ε * T→FN * N→-FN|*FN|ε * F→(E)|i */ /* * 求First集和Follow集 * * First(E)={(,i} Follow(E)={),#} * First(T)={(,i} Follow(T)={+,/,#} * First(F)={(,i} Follow(F)={-,*,#} * First(M)={+,/,ε} Follow(M)={),#} * First(N)={-,*,ε} Follow(N)={+,/,#} */ // 构造预测分析表 private String[] Vt = {"+", "/", "-", "*", "(", ")", "i"}; private String[] Vn = {"E", "T", "F", "M", "N"}; private String[][] M = { //+=0 /=1 -=2 *=3 (=4 )=5 i=6 #=7 { "", "", "", "", "TM", "", "TM", ""}, //E=0 { "", "", "", "", "FN", "", "FN", ""}, //T=1 { "", "", "", "", "(E)", "", "i", ""}, //F=2 { "+TM", "/TM", "", "", "ε", "", "", "ε"}, //M=3 { "ε", "ε", "-FN", "*FN", "", "", "", "ε"} //N=4 }; //开始分析 private String[] stack = new String[256]; private String stack_top; private int stack_ptr = -1; private int ptr = 0; private char c_temp; private int Vt_code; private int Vn_code; private void get_char(String sentence){ c_temp = sentence.charAt(ptr); ptr++; if(c_temp == '+'){ Vt_code = 0; }else if(c_temp == '/'){ Vt_code = 1; }else if(c_temp == '-'){ Vt_code = 2; }else if(c_temp == '*'){ Vt_code = 3; }else if(c_temp == '('){ Vt_code = 4; }else if(c_temp == ')'){ Vt_code = 5; }else if(c_temp == 'i'){ Vt_code = 6; }else if(c_temp == '#'){ Vt_code = 7; } } private void push(String str){ stack_ptr++; stack[stack_ptr] = str; } private void pull(){ stack_top = stack[stack_ptr]; stack[stack_ptr] = null; stack_ptr--; if(stack_top.equals("E")){ Vn_code = 0; }else if(stack_top.equals("T")){ Vn_code = 1; }else if(stack_top.equals("F")){ Vn_code = 2; }else if(stack_top.equals("M")){ Vn_code = 3; }else if(stack_top.equals("N")){ Vn_code = 4; } } private boolean isVt(String str){ for(int i = 0; i < Vt.length; i++){ if(str.equals(Vt[i])){ return true; } } return false; } private boolean isVn(String str){ for(int i = 0; i < Vn.length; i++){ if(str.equals(Vn[i])){ return true; } } return false; } public boolean SyntaxAnalyse(String sentence){ push("#"); push("E"); get_char(sentence); boolean flag = true; while(flag){ pull(); if(isVt(stack_top)){ if(stack_top.equals(String.valueOf(c_temp))){ get_char(sentence); }else{ return false; } }else if(stack_top.equals("#")){ if(stack_top.equals(String.valueOf(c_temp))){ flag = false; }else{ return false; } }else if(M[Vn_code][Vt_code] != null){ if(!M[Vn_code][Vt_code].equals("ε")){ for(int i = M[Vn_code][Vt_code].length() - 1; i >= 0 ; i--){ push(String.valueOf(M[Vn_code][Vt_code].charAt(i))); } } }else{ return false; } } return true; } public static void main(String[] args) throws IOException{ while(true){ LL1SA sa = new LL1SA(); System.out.print("请输入语句："); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String str = in.readLine(); String sentence = str + "#"; boolean result = sa.SyntaxAnalyse(sentence); if(result == true){ System.out.println(str + " 是正确表达式！"); }else if(result == false){ System.out.println(str + " 是错误表达式！"); }else{ System.out.println("分析程序出现错误！"); } } } }