语法语义分析（预测分析）(JDK 1.8)

文法为：
E -> E+T | E-T | T
T -> T*F | T/F | F
F ->（E）| i
根据预测分析法，对表达式进行语法分析，判断一个表达式是否正确
对于正确的表达式，使用逆序波兰式求值

波兰式比较简单，使用栈就可以实现，具体参照代码

import java.io.File;
import java.util.*;

public class PredictiveAnalyst {

    String sequence;

    final int EXPRESSION_ACCEPT = 0;
    final int EXPRESSION_WRONG = 1;

    final String INPUT_PATH = "src/Test/input.txt";
    final String OUTPUT_PATH = "src/Test/output.txt";
    final String VT = "i+-*/()#";

    HashMap<Character, Integer> operatorPriorityTable;
    HashMap<String, String> predictTable;

    boolean meetZero = false;

    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);
            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] = '#';
            stack[++top] = 'E';

            int expression_state;

            //analysis starts with the expression
            while (true) {
                if (stack[top] != '#') {

                    char x = stack[top--];

                    if (VT.indexOf(x) < 0) {

                        //If x is not a terminal symbol
                        if (front >= queue.length) {
                            expression_state = EXPRESSION_WRONG;
                            outputBuffer.append("错误单词为:" + words[front-3]);
                            break;
                        }
                        String key = x + " " + queue[front];
                        String value = predictTable.get(key);

                        if (value != null) {
                            //倒序入栈
                            for (int i = value.length() - 1; i >= 0; --i)
                                stack[++top] = value.charAt(i);
                            continue;
                        } else {
                            //查找为空
                            expression_state = EXPRESSION_WRONG;
                            outputBuffer.append("错误单词为:" + words[front-1]);
                            break;
                        }
                    } else {
                        //not a terminal symbol
                        ++front;
                        if (x != '#') {
                            continue;
                        } else {
                            expression_state = EXPRESSION_WRONG;
                            outputBuffer.append("错误单词为:" + words[front-1]);
                            break;
                        }
                    }
                } else {
                    if (queue[front] == '#') {
                        expression_state = EXPRESSION_ACCEPT;
                        break;
                    } else {
                        expression_state = EXPRESSION_WRONG;
                        outputBuffer.append("错误单词为:" + words[front-1]);
                        break;
                    }
                }
            }

            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 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 void init() {
        //Initialise the hash table
        /*将原文法中的E'替换为A, T'替换为B*/
        predictTable = new HashMap<>();
        predictTable.put("E i", "TA");
        predictTable.put("E (", "TA");
        predictTable.put("A +", "+TA");
        predictTable.put("A -", "-TA");
        predictTable.put("A )", "");
        predictTable.put("A #", "");
        predictTable.put("T i", "FB");
        predictTable.put("T (", "FB");
        predictTable.put("B +", "");
        predictTable.put("B -", "");
        predictTable.put("B *", "*FB");
        predictTable.put("B /", "/FB");
        predictTable.put("B )", "");
        predictTable.put("B #", "");
        predictTable.put("F i", "i");
        predictTable.put("F (", "(E)");

        operatorPriorityTable = new HashMap<>();
        operatorPriorityTable.put('+', 1);
        operatorPriorityTable.put('-', 1);
        operatorPriorityTable.put('/', 2);
        operatorPriorityTable.put('*', 2);
        operatorPriorityTable.put('(', 0);
        operatorPriorityTable.put(')', 4);
    }

    /*判断两个优先符优先级关系*/
    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;
    }

}