编译原理 - 算符优先分析方法（JAVA）

╰半夏微凉° 2023-02-16 00:44 61阅读 0赞

# 1. 理论依据 #

1）判断输入文法是否算符文法  
根据定义：**产生式右部不包含两个相邻非终结符的文法称为算符文法。**  
我们们对输入的文法进行依次遍历，查看每个产生式的右部进行遍历查找，如果发现出现两个非终极符连续出现，则发出提示，文法不符，并要求重新输入文法。

2）采用由定义构造算符优先关系集合并构造矩阵

由以上公式，先得到对应的FIRSTVT与LASTVT集合，再依次遍历文法找到所需的…aV…或者…Vb…产生式，与FIRSTVT（V）或者LASTVT（V）卡氏积，得到>,<,=的算符优先关系，将这些关系存入算法关系集合，之后将得到的算法优先关系集合解析，构造出算符优先关系矩阵。打印出来。  
同时对于起始S和结束符\#,有\#<FIRST(S),LASTVT(S)>\#,且对\#S\#,有\#=\#。  
即在优先关系矩阵右边和下边构建添加\#符号，方便初始情况等一些特殊情况的处理。

3）算符优先分析算法分析句子

算符优先分析算法是自下而上的语法分析方法，是对当前句型不断查找最左素短语进行规约的过程。寻找最左短语时，先找到最左素短语的末尾终结符，然后再向前搜索最左素短语的首终结符。  
代码使用的流程为：使用符号栈的栈顶非终结字符a与输入流首字符b构成（a,b）到算符优先矩阵里查找优先关系，判断当前是否是=，或者<,如果是，则继续从输入流首字符输入到符号栈，如果是>,则进行规约动作；并将规约的终结符入栈。  
直到输入流为“\#”，此时再来判断符号栈栈顶符号是否为文法的输入符号。  
完成对该句子的文法合法性分析。

3.数据结构分析

（1）FIRSTVT集合与LASTVT集合  
由以上分析我们可以得出，FIRSTVT与LASTVT集合都是基于（终结符）->\{非终结符集合\}的key->value形式。  
故采用以下形式：  
private static Map<Character, Set> firstVt = new HashMap<>();  
private static Map<Character, Set> lastVt = new HashMap<>();  
其中，<Character，Set> 第一个Character为终结符，Set为该终结符求出的非终结符集合。  
（2）算符矩阵集合  
用Map<String,Character>存,String中存优先变的行值和列值,Character表示String中所存行列的大小关系如"ab"表示行为’a’,列为’b’的时候,关系为Character中的值。  
即（a，b）a与b拼接存入String，Character存入（a,b）对应的关系“<” ,“>”,或者“=”。例子：ab 对应 =。  
同时代码多增加了一列一行“\#”，以来处理初始情况和结束情况。

（3）句子分析  
句子分析采用了栈结构，将“\#”符号放入符号栈底。同时要求输入句子时以“\#”结尾；

伪代码如下：

k:=1; 
    S[k]:= ‘#’;
    REPEAT
         把下一个输入符号读进 a 中； 
         IF S[k] ∈ Vt THEN j:=k ELSE j:= k-1;
         WHILE S[j] > a DO 
               BEGIN
               REPEAT
                    Q:=S[j]; 
                    IF S[j-1]∈ VT THEN j:j-1 ELSE j:j-2
               UNTIL S[j] < Q;
               把 S[j+1]…S[k]归约为某个 N；
               k:=j+1;
               S[k]:=N;
               END OF WHILE;
          IF S[j] < a OR s[j] = a THEN
               BEGIN k:=k+1;S[k]:=N; END
          ELSE ERROR
    UNTIL  a = ‘#’

# 2. 结果截图 #

![在这里插入图片描述][20200606175907175.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]

# 3. 实现代码 #

package parser.simplepriority;
    
    import java.util.*;
    
    
    public class analyze { 
    
        /** * FIRSTVT集合 */
        private static Map<Character, Set<Character>> firstVt = new HashMap<>();
        /** * LASTVT集合 */
        private static Map<Character, Set<Character>> lastVt = new HashMap<>();
        /** * 输入的文法 */
        private static List<String> input = new ArrayList<>();
    
        /** * 终结符 */
        private static Set<Character> End = new LinkedHashSet<>();
    
        /** * 非终结符 */
        private static Set<Character> NoEnd = new LinkedHashSet<>();
    
        /** * 算符矩阵 */
        private static Map<String, Character> matrix = new HashMap<>();
    
        private static Scanner in = new Scanner(System.in);
    
        /** * 文法的左右分割一一对应 */
        private static Map<Character, List<String>> produce = new HashMap<>();
    
    
        /** * 获得firstVt集合 */
        private static void getFirstVT(Character s, Set<Character> fvt) { 
            String str = null;
            int i = 0;
            for (i = 0; i < input.size(); i++) { 
                if (input.get(i).charAt(0) == s) { 
                    str = input.get(i);
                }
            }
            for (i = 3; i < str.length(); i++) { 
                if (str.charAt(i) < 65 || str.charAt(i) > 90) { 
                    //P->a.....，即以终结符开头，该终结符入Firstvt
                    if ((str.charAt(i - 1) == '>' && str.charAt(i - 2) == '-') || str.charAt(i - 1) == '|') { 
                        fvt.add(str.charAt(i));
                    }
                    //P->Qa....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt
                    if ((str.charAt(i - 2) == '|' || (str.charAt(i - 2) == '>' && str.charAt(i - 3) == '-')) && str.charAt(i - 1) >= 65 && str.charAt(i - 1) <= 90) { 
                        fvt.add(str.charAt(i));
                    }
                }
                //若有P->Q.....，即以非终结符开头，该非终结符的Firstvt加入P的Firstvt
                if (str.charAt(i - 1) == '|' && str.charAt(i) >= 65 && str.charAt(i) <= 90) { 
                    if (str.charAt(i) == str.charAt(0)) { 
                        continue;
                    }
                    //递归
                    getFirstVT(str.charAt(i), fvt);
                }
            }
        }
    
        /** * 获得lastVt集合 */
        private static void getLastVT(Character s, Set<Character> lvt) { 
            String str = null;
            int i = 0;
            for (i = 0; i < input.size(); i++) { 
                if (input.get(i).charAt(0) == s) { 
                    str = input.get(i);
                }
            }
            for (i = 3; i < str.length(); i++) { 
                if (str.charAt(i) < 65 || str.charAt(i) > 90) { 
                    //P->....aQ，即先以非终结符结尾，前面是终结符，则终结符入Lastvt,Q处于产生式最后一位的情况
                    if (i == str.length() - 1 || (i == str.length() - 2 && str.charAt(i + 1) >= 65 && str.charAt(i + 1) <= 90 && str.charAt(i) != '|' && (str.charAt(i) != '>' && str.charAt(i) != '-'))) { 
                        lvt.add(str.charAt(i));
                    }
                    if (i < str.length() - 2) { 
                        //P->....aQ，即先以非终结符结尾，前面是终结符，则终结符入Lastvt
                        if (str.charAt(i + 1) == '|' || (str.charAt(i + 2) == '|' && str.charAt(i + 1) >= 65 && str.charAt(i + 1) <= 90)) { 
                            lvt.add(str.charAt(i));
                        }
                    }
                } else { 
                    //P->....Q，即以非终结符结尾，该非终结符的Lastvt入P的Lastvt
                    if (i == str.length() - 1) { 
                        if (str.charAt(i) == str.charAt(0)) { 
                            continue;
                        }
                        getLastVT(str.charAt(i), lvt);
                    } else if (str.charAt(i + 1) == '|') { 
                        if (str.charAt(i) == str.charAt(0)) { 
                            continue;
                        }
                        //P->....Q，即以非终结符结尾，该非终结符的Lastvt入P的Lastvt
                        getLastVT(str.charAt(i), lvt);
                    }
                }
            }
        }
    
        /** * 显示firstVt集合和lastVt集合 */
        private static void DisplayFirstVT_LastVT() { 
            for (int i = 0; i < input.size(); i++) { 
                Set<Character> fvt = new HashSet<>();
                getFirstVT(input.get(i).charAt(0), fvt);
                firstVt.put(input.get(i).charAt(0), fvt);
            }
            for (int i = 0; i < input.size(); i++) { 
                Set<Character> lvt = new HashSet<>();
                getLastVT(input.get(i).charAt(0), lvt);
                lastVt.put(input.get(i).charAt(0), lvt);
            }
            System.out.println("firstVt集合如下:");
            for (Map.Entry<Character, Set<Character>> entry : firstVt.entrySet()) { 
                System.out.print("firstVt(" + entry.getKey() + "): {");
                int flag = 0;
                for (Character value : entry.getValue()) { 
                    flag++;
                    System.out.print(value);
                    if (flag != entry.getValue().size()) { 
                        System.out.print(",");
                    }
                }
                System.out.println("}");
            }
            System.out.println("lastVt集合如下:");
            for (Map.Entry<Character, Set<Character>> entry : lastVt.entrySet()) { 
                System.out.print("lastVt(" + entry.getKey() + "): {");
                int flag = 0;
                for (Character value : entry.getValue()) { 
                    flag++;
                    System.out.print(value);
                    if (flag != entry.getValue().size()) { 
                        System.out.print(",");
                    }
                }
                System.out.println("}");
            }
        }
    
    
        /** * 获取所有终结符 */
        private static void getEnd() { 
            for (int i = 0; i < input.size(); i++) { 
                String temp = input.get(i);
                for (int j = 3; j < temp.length(); j++) { 
                    if (temp.charAt(j) < 65 || temp.charAt(j) > 90 && temp.charAt(j) != '|') { 
                        End.add(temp.charAt(j));
                    }
                }
            }
            End.add('#');
        }
    
        /** * 获取所有非终结符 */
        private static void getNoEnd() { 
            for (int i = 0; i < input.size(); i++) { 
                String temp = input.get(i);
                for (int j = 3; j < temp.length(); j++) { 
                    if (temp.charAt(j) >= 65 && temp.charAt(j) <= 90) { 
                        NoEnd.add(temp.charAt(j));
                    }
                }
            }
        }
    
        /** * 将每一行的文法分离,如E->E+T|T分离成E和E+T,T */
        private static void getProduce() { 
            for (int i = 0; i < input.size(); i++) { 
                List<String> list = new ArrayList<>();
                String str = input.get(i);
                StringBuffer a = new StringBuffer();
                for (int j = 3; j < str.length(); j++) { 
                    if (str.charAt(j) != '|') { 
                        a.append(str.charAt(j));
                    } else { 
                        list.add(a.toString());
                        //清空a
                        a.delete(0, a.length());
                    }
                }
                list.add(a.toString());
                produce.put(str.charAt(0), list);
            }
        }
    
        /** * 错误 */
        public static void partError() { 
            matrix.put(")(", 'b');
            matrix.put("((", 'b');
            matrix.put("(#", 'a');
        }
    
    
        /** * 构造算符优先矩阵并打印 * 用Map<String,Character>存,String中存优先变得行值和列值, * Character表示String中所存行列的大小关系如"++"表示行为'+',列为'+'的时候,关系为Character中的值 * * @return */
        private static void priorityMatrix() { 
            for (int i = 0; i < input.size(); i++) { 
                String str = input.get(i);
                for (int j = 3; j < input.get(i).length(); j++) { 
                    if ((str.charAt(j) < 65 || str.charAt(j) > 90) && (str.charAt(j) != '|')) { 
                        if (j < str.length() - 1 && (str.charAt(j + 1) < 65 || str.charAt(j + 1) > 90)) { 
                            String temp = str.charAt(j) + "" + str.charAt(j + 1);
                            matrix.put(temp, '=');
                        } else { 
                            if (j < str.length() - 2 && (str.charAt(j + 2) < 65 || str.charAt(j + 2) > 90) && (str.charAt(j + 2) != '|')) { 
                                matrix.put(str.charAt(j) + "" + str.charAt(j + 2), '=');
                            }
                        }
                        if (j < str.length() - 1 && str.charAt(j + 1) >= 65 && str.charAt(j + 1) <= 90) { 
                            Set<Character> coll = firstVt.get(str.charAt(j + 1));
                            for (Character value : coll) { 
                                matrix.put(str.charAt(j) + "" + value, '<');
                            }
                        }
                        if (j - 1 != 2 && str.charAt(j - 1) >= 65 && str.charAt(j - 1) <= 90) { 
                            Set<Character> coll = lastVt.get(str.charAt(j - 1));
                            for (Character value : coll) { 
                                matrix.put(value + "" + str.charAt(j), '>');
                            }
                        }
                    }
                }
            }
            Set<Character> coll = firstVt.get(input.get(0).charAt(0));
            for (Character value : coll) { 
                matrix.put('#' + "" + value, '<');
            }
            Set<Character> coll1 = lastVt.get(input.get(0).charAt(0));
            for (Character value : coll1) { 
                matrix.put(value + "" + '#', '>');
            }
            partError();
            for (Character value : End) { 
                for (Character value1 : End) { 
                    if (matrix.get(value + "" + value1) == null) { 
                        matrix.put(value + "" + value1, 'b');
                    }
                }
            }
            matrix.put("##", '=');
    
    /* for (Map.Entry<String, Character> entry : matrix.entrySet()) { System.out.println(entry.getKey()+" "+entry.getValue()); }*/
            getEnd();
            System.out.println("\n构造的算符优先关系表如下:");
            int kong = 0;
            for (Character value : End) { 
                if (kong == 0) { 
                    System.out.print(" ");
                }
                kong++;
                System.out.print(value);
                if (kong != End.size()) { 
                    System.out.print(" ");
                }
            }
            System.out.println();
            for (Character value : End) { 
                System.out.print(value);
                for (Character value1 : End) { 
                    Character ch = matrix.get(value + "" + value1);
                    if (ch != null) { 
                        System.out.print(" " + ch);
                    } else { 
                        System.out.print(" " + " ");
                    }
                }
                System.out.println();
            }
        }
    
        /** * 判断其是不是算符文法 * 如果没有连个连续非终结符号相连的就是算符优先文法 * @return */
        private static boolean isOperator() { 
            int i;
            for (i = 0; i < input.size(); i++) { 
                for (int j = 0; j < input.get(i).length() - 1; j++) { 
                    String str = input.get(i);
                    if (str.charAt(j) >= 65 && str.charAt(j) <= 90) { 
                        if ((str.charAt(j + 1) >= 65 && str.charAt(j + 1) <= 90)) { 
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    
        /** * 判断其是不是终结符 * @return */
        private static boolean isEnd(Character ch) { 
            for (Character value : End) { 
                if (value.equals(ch)) { 
                    return true;
                }
            }
            return false;
        }
    
        /** * 判断其是不是非终结符 * @return */
        private static boolean isNoEnd(Character ch) { 
            for (Character value : NoEnd) { 
                if (value.equals(ch)) { 
                    return true;
                }
            }
            return false;
        }
    
        /** * 根据产生式右部分返回左边 * @return */
        private static char retLeft(String str) { 
            char ch = 0;
            for (Map.Entry<Character, List<String>> map : produce.entrySet()) { 
                ch = map.getKey();
                for (String value : map.getValue()) { 
                    if (value.length() != str.length()) { 
                        continue;
                    }
                    int i;
                    for (i = 0; i < str.length(); i++) { 
    
                        if (str.charAt(i) >= 65 && str.charAt(i) <= 90) { 
                            if (value.charAt(i) >= 65 && value.charAt(i) <= 90) { 
                            } else { 
                                break;
                            }
                        } else { 
                            if (value.charAt(i) != str.charAt(i)) { 
                                break;
                            }
                        }
                    }
                    if (i == str.length()) { 
                        return ch;
                    }
                }
            }
            return 0;
        }
    
        /** * 将字符数组转换成字符串 * @param list * @return */
        public static String replaceToString(List<Character> list) { 
            StringBuffer a = new StringBuffer();
            for (Character value : list) { 
                if (value != ',' && value != '[' && value != ']') { 
                    a.append(value);
                }
            }
            return a.toString();
        }
    
        /** * 算符优先分析过程 * 使用一个符号栈，用它寄存终结符和非终结符,k代表符号栈的深度 * 在正常情况下，算法工作完毕时，符号栈S应呈现:#N */
        public static void analysisProcess() { 
            int status = 0;
            int count = 0;
            int k = 0;
            int j = 0;
            int step = 0;
            String gui = null;
            System.out.println("请输入要分析的句子(注意:记得以'#'结束)");
            String sentence = null;
            sentence = in.nextLine();
            if (sentence.charAt(sentence.length() - 1) != '#') { 
                sentence = sentence + "#";
            }
            List<Character> listStack = new ArrayList<>();
            System.out.printf("%-8s%-20s%-8s%-10s%-8s\n", "步骤", "栈", "a读入", "剩余串", "操作");
            listStack.add('#');
            char a = sentence.charAt(step++);
            do { 
                if (status == 0) { 
                    if (count != 0) { 
                        System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count, replaceToString(listStack), a, sentence.substring(step));
                    } else { 
                        System.out.printf("%-8d %-20s %-8c %-10s", count, replaceToString(listStack), a, sentence.substring(step));
                    }
                } else { 
                    System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count, replaceToString(listStack), a, sentence.substring(step));
                }
                char ch = listStack.get(k);
                if (isEnd(ch)) { 
                    j = k;
                } else if (j >= 1) { 
                    j = k - 1;
                }
                char temp = 0;
                if (matrix.get(listStack.get(j) + "" + a) != null) { 
                    //规约
                    while (matrix.get(listStack.get(j) + "" + a).equals('>')) { 
                        if (listStack.size() == 2 && a == '#') { 
                            break;
                        }
                        StringBuffer judge = new StringBuffer();
                        do { 
                            temp = listStack.get(j);
                            if (isEnd(listStack.get(j - 1))) { 
                                j = j - 1;
                            } else { 
                                j = j - 2;
                            }
                        } while (!matrix.get(listStack.get(j) + "" + temp).equals('<'));
                        for (int i = j + 1; i < listStack.size(); i++) { 
                            judge.append(listStack.get(i));
                        }
                        int te = listStack.size();
                        for (int t = j + 1; t < te; t++) { 
                            listStack.remove(j + 1);
                        }
                        char res = retLeft(judge.toString());
                        if (res != 0) { 
                            count++;
                            k = j + 1;
                            listStack.add(res);
                            status = 1;
                            gui = "用" + res + "->" + judge.toString() + "规约";
                            if (status == 0) { 
                                System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", "移进", count, replaceToString(listStack), a, sentence.substring(step));
                            } else { 
                                System.out.printf("%-8s\n%-8d %-20s %-8c %-10s", gui, count, replaceToString(listStack), a, sentence.substring(step));
                            }
                        }
                    }
                }
                //移进
                if (matrix.get(listStack.get(j) + "" + a).equals('<') || matrix.get(listStack.get(j) + "" + a).equals('=')) { 
                    count++;
                    k++;
                    status = 0;
                    listStack.add(a);
                } else { 
                    switch (matrix.get(listStack.get(j) + "" + a)) { 
                        case 'a':
                            System.out.print("非法左括号! ");
                            return;
                        case 'b':
                            System.out.print("缺少运算符! ");
                            return;
                        case 'c':
                            System.out.print("缺少表达式! ");
                            return;
                        default:
                            break;
                    }
                }
                if (listStack.size() == 2 && a == '#') { 
                    break;
                }
                if (step < sentence.length()) { 
                    a = sentence.charAt(step++);
                } else { 
                    break;
                }
            } while (listStack.size() != 2 || a != '#');
            System.out.printf("%-8s\n", "分析成功");
        }
    
    
        /** * 主函数 * * @param args */
        public static void main(String[] args) { 
            int flag = 1;
            String a;
            System.out.println("请输入文法:");
            while (flag != 0) { 
                while (!(a = in.nextLine()).equals("")) { 
                    input.add(a);
                }
                if (isOperator()) { 
                    System.out.println("此文法是算符文法!");
                    flag = 0;
                } else { 
                    System.out.println("此文法不是算符文法!请重新输入:");
                    input.clear();
                }
            }
            getEnd();
            getNoEnd();
            getProduce();
            DisplayFirstVT_LastVT();
            priorityMatrix();
            analysisProcess();
        }
    }

package parser.simplepriority;
    
    import java.io.File;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Scanner;
    
    public class OperatorPriorityAnalyst { 
    
        final String INPUT_PATH = "src/Test/input.txt";
        //final String OUTPUT_PATH = "src/Test/output.txt";
        final String VT = "i+-*/()#";
        final int EXPRESSION_ACCEPT = 0;
        final int EXPRESSION_WRONG = 1;
        final int SHIFT = -1;               //移进
        final int REDUCE = 1;               //规约
        final int EQUAL = 0;
        HashMap<String, Integer> table;
        HashMap<Character, Integer> operatorPriorityTable;
        HashMap<String, String> reduceTable;                //栈顶规约表
        String sequence;
        boolean meetZero = false;           //计算过程中是否出现0做除数
    
        public void analysis() throws Exception { 
            int turn = 1;
            init();
            Scanner scanner = new Scanner(new File(INPUT_PATH));
            //FileWriter writer = new FileWriter(new File((OUTPUT_PATH)));
    
            String oriExpression;//original expression
    
            while (scanner.hasNextLine()) { 
    
                StringBuffer outputBuffer = new StringBuffer();//output.txt information for each input.txt line
    
                oriExpression = scanner.nextLine();
                oriExpression = oriExpression.substring(0, oriExpression.length() - 1);
                //gets rid of the ;
    
                String[] words = getAbstractSeq(oriExpression);
                //sequence is now initialised.
    
                if (words.length == 1) { 
                    System.out.println((turn++) + " : 正确 值为" + words[0]);
                    continue;
                }
    
                char[] stack = new char[sequence.length()];
                int top = -1;
    
                char[] queue = sequence.toCharArray();
                int front = 1;
    
                stack[++top] = '#';
    
                int expression_state;
    
                while (true) { 
                    char curWord = queue[front];
                    char topWord = '.';
    
                    int near = top;
                    for (; near >= 0; --near) { 
                        if (VT.indexOf(stack[near]) >= 0) { 
                            topWord = stack[near];
                            break;
                        }
                    }
                    if (topWord == '.') { 
                        expression_state = EXPRESSION_WRONG;
                        outputBuffer.append("未找到离栈顶最近的VT");
                        break;
                    }
                    if (curWord == '#' && topWord == '#') { 
                        expression_state = EXPRESSION_ACCEPT;
                        break;
                    } else { 
                        String key = topWord + " " + curWord;
                        if (!table.containsKey(key)) { 
                            expression_state = EXPRESSION_WRONG;
                            outputBuffer.append("错误单词为:" + words[front - 1]);
                            break;
                        } else { 
                            if (table.get(key) <= 0) {           //移进或者相等
                                stack[++top] = curWord;
                                ++front;
                                continue;
                            } else { 
                                //栈顶规约
                                int start = near - 1;       //start是near之前的Vt的下标
                                while (true) { 
    
                                    if (start < 0) { 
                                        expression_state = EXPRESSION_WRONG;
                                        outputBuffer.append("规约过程失败");
                                        break;
                                    }
    
                                    if (VT.indexOf(stack[start]) < 0) { 
                                        --start;
                                    } else {                 //查表
                                        String key1 = stack[start] + " " + stack[near];
                                        if (table.get(key1) == SHIFT) { 
                                            String result = reduceTable.get(String.valueOf(stack, start + 1, top - start));
                                            if (result == null) { 
                                                expression_state = EXPRESSION_WRONG;
                                                outputBuffer.append("错误单词为:" + words[front - 1]);
                                                break;
                                            }
                                            //对要规约的单词进行检查
                                            int wrong = -1;
                                            for (int i = start + 1; i <= top; ++i) { 
                                                if (!checkWhenReduce(stack[i], stack, i, top, start + 1)) { 
                                                    wrong = i;
                                                    break;
                                                }
                                            }
                                            if (wrong != -1) { 
                                                expression_state = EXPRESSION_WRONG;
                                                outputBuffer.append("错误单词为 " + stack[wrong]);
                                                break;
                                            }
                                            top = start;
                                            for (int i = 0; i < result.length(); ++i)
                                                stack[++top] = result.charAt(i);
                                            break;
                                        } else { 
                                            near = start;
                                            --start;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
    
                if (expression_state == EXPRESSION_ACCEPT) { 
                    //writer.write("正确 逆波兰式为 " + getReversePolishExpression(words, value) + " 其值为" + value.value + '\n');
                    String expression = getReversePolishExpression(words);
                    System.out.println((turn++) + " : 正确 逆波兰式为 " + expression + " 其值为 " + getReversedPolishValue(expression));
                } else { 
                    //writer.write("错误 错误位置是" + outputBuffer.toString() + '\n');
                    System.out.println((turn++) + " : 错误 " + outputBuffer.toString());
                }
            }
    
            scanner.close();
            //writer.close();
        }
    
        private void init() { 
            table = new HashMap<>();
            table.put("# +", SHIFT);
            table.put("# -", SHIFT);
            table.put("# *", SHIFT);
            table.put("# /", SHIFT);
            table.put("# (", SHIFT);
            table.put("# i", SHIFT);
            table.put("+ *", SHIFT);
            table.put("+ /", SHIFT);
            table.put("+ (", SHIFT);
            table.put("+ i", SHIFT);
            table.put("- *", SHIFT);
            table.put("- /", SHIFT);
            table.put("- (", SHIFT);
            table.put("- i", SHIFT);
            table.put("* i", SHIFT);
            table.put("* (", SHIFT);
            table.put("/ (", SHIFT);
            table.put("/ i", SHIFT);
            table.put("( +", SHIFT);
            table.put("( -", SHIFT);
            table.put("( *", SHIFT);
            table.put("( /", SHIFT);
            table.put("( (", SHIFT);
            table.put("( i", SHIFT);
            table.put("+ #", REDUCE);
            table.put("+ +", REDUCE);
            table.put("+ -", REDUCE);
            table.put("+ )", REDUCE);
            table.put("- #", REDUCE);
            table.put("- +", REDUCE);
            table.put("- -", REDUCE);
            table.put("- )", REDUCE);
            table.put("* #", REDUCE);
            table.put("* +", REDUCE);
            table.put("* -", REDUCE);
            table.put("* *", REDUCE);
            table.put("* /", REDUCE);
            table.put("* )", REDUCE);
            table.put("/ #", REDUCE);
            table.put("/ +", REDUCE);
            table.put("/ -", REDUCE);
            table.put("/ *", REDUCE);
            table.put("/ /", REDUCE);
            table.put("/ )", REDUCE);
            table.put(") #", REDUCE);
            table.put(") +", REDUCE);
            table.put(") -", REDUCE);
            table.put(") *", REDUCE);
            table.put(") /", REDUCE);
            table.put(") )", REDUCE);
            table.put("i #", REDUCE);
            table.put("i +", REDUCE);
            table.put("i -", REDUCE);
            table.put("i *", REDUCE);
            table.put("i /", REDUCE);
            table.put("i )", REDUCE);
            table.put("# #", EQUAL);
            table.put("( )", EQUAL);
    
            operatorPriorityTable = new HashMap<>();
            operatorPriorityTable.put('+', 1);
            operatorPriorityTable.put('-', 1);
            operatorPriorityTable.put('/', 2);
            operatorPriorityTable.put('*', 2);
            operatorPriorityTable.put('(', 0);
            operatorPriorityTable.put(')', 4);
    
            reduceTable = new HashMap<>();
            reduceTable.put("#X#", "X");
            reduceTable.put("X+X", "X");
            reduceTable.put("X-X", "X");
            reduceTable.put("X", "X");
            reduceTable.put("X*X", "X");
            reduceTable.put("X/X", "X");
            reduceTable.put("(X)", "X");
            reduceTable.put("i", "X");
        }
    
        private boolean checkWhenReduce(char w, char[] stack, int pos, int upper, int bottom) { 
            if (w == 'i') { 
                if ((pos + 1 <= upper && stack[pos + 1] == 'X') && (pos - 1 >= upper && stack[pos - 1] == 'X')) { 
                    return false;
                }
            } else if (w == ')') {  //往前查找
                boolean flag = false;//是否遇到（
                for (int i = pos - 1; i >= bottom; --i) { 
                    if (!flag && stack[i] == 'X')
                        return false;
                    else if (stack[i] == ')') continue;
                    else return true;
                }
            } else if (w == '(') { 
                return true;
            } else { 
                if ((pos - 1 >= bottom && stack[pos - 1] != 'X') || (pos + 1 <= upper && stack[pos + 1] != 'X'))
                    return false;
            }
            return true;
        }
    
        //简单词法分析器
        private String[] getAbstractSeq(String originalExpression) { 
            StringBuffer buffer = new StringBuffer();//buffer for result sequence
            buffer.append('#');
    
            ArrayList<String> list = new ArrayList<>();
    
            char[] S = new char[100];
            int top = -1;
    
            for (int i = 0; i < originalExpression.length(); ++i) { 
                char ch = originalExpression.charAt(i);
                if (isBlank(ch)) { 
                    continue;
                } else { 
                    if (VT.indexOf(ch) >= 0) { 
                        if (top != -1) { 
                            //If it's an operator
                            buffer.append("i");
                            buffer.append(ch);
                            //clear the stack
                            String number = new String(S, 0, top + 1);
                            top = -1;
                            list.add(number);//add the number
                            list.add(String.valueOf(ch));//add the operator
                        } else { 
                            buffer.append(ch);
                            list.add(String.valueOf(ch));
                        }
                    } else { 
                        S[++top] = ch;
                    }
                }
            }
    
            if (top != -1) { 
                String number = new String(S, 0, top + 1);
                buffer.append("i");
                list.add(number);
            }
    
            buffer.append("#");
            sequence = buffer.toString();
            return list.toArray(new String[list.size()]);
        }
    
        private String getReversePolishExpression(String[] words) { 
            StringBuffer output = new StringBuffer();
            char[] operatorStack = new char[words.length];
            int top = -1;
    
            for (int i = 0; i < words.length; ++i) { 
                if (isWordOperator(words[i])) { 
                    /*char operator = words[i].charAt(0); while (operatorTop != -1 && getPriorityDifference(operator, operatorStack[operatorTop]) <= 0) { char poppedOperator = operatorStack[operatorTop--]; output.append(poppedOperator + ' '); }*/
                    char operator = words[i].charAt(0);
                    if (operator == '(') { 
                        operatorStack[++top] = operator;
                    } else if (operator == ')') { 
                        while (operatorStack[top] != '(') { 
                            output.append(operatorStack[top--] + " ");
                        }
                        top--;
                    } else { 
                        //当（栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作：将栈顶元素出栈输出
                        while (top != -1 && operatorStack[top] != '(' && getPriorityDifference(operatorStack[top], operator) >= 0) { 
                            output.append(operatorStack[top--] + " ");
                        }
                        operatorStack[++top] = operator;
                    }
                } else { 
                    output.append(words[i] + ' ');
                }
            }
            while (top != -1)
                output.append(operatorStack[top--] + " ");
            return output.toString();
        }
    
        private float getReversedPolishValue(String expression) { 
            float[] stack = new float[expression.length()];
            int top = -1;
            String[] words = expression.split(" ");
            for (String s : words) { 
                if (isWordOperator(s)) { 
                    float a = stack[top--];
                    float b = stack[top--];
                    switch (s) { 
                        case "+":
                            stack[++top] = a + b;
                            break;
                        case "-":
                            stack[++top] = b - a;
                            break;
                        case "*":
                            stack[++top] = a * b;
                            break;
                        case "/":
                            if (b == 0) { 
                                meetZero = true;
                                return Float.MIN_VALUE;
                            } else { 
                                stack[++top] = b / a;
                            }
                            break;
                    }
                } else { 
                    stack[++top] = Float.valueOf(s);
                }
            }
            return stack[0];
        }
    
        /*判断两个优先符优先级关系*/
        private int getPriorityDifference(char c1, char c2) { 
            return operatorPriorityTable.get(c1) - operatorPriorityTable.get(c2);
        }
    
        /*判断是否是空白*/
        private boolean isBlank(char ch) { 
            if (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r')
                return true;
            else return false;
        }
    
        private boolean isWordOperator(String word) { 
            char c = word.charAt(0);
            if (c >= '0' && c <= '9') return false;
            else return true;
        }
    }

[20200606175907175.png]: https://img-blog.csdnimg.cn/20200606175907175.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200606175914828.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200606175918898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200606175924183.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc=,size_16,color_FFFFFF,t_70