运用Java语言和dfaRecognize函数实现24.最右推导式 E' → E → E + T → E + F → E + id → id * id + id的分析过程

假设我们有一个字符串：id * id + id。

首先，我们定义文法产生式：

E' → E
E → E + T | T
T → T * F | F
F → (E) | id

然后，我们构建DFA状态转移表：

| | id | * | + | ( | ) | $ |
|---|-------|-------|-------|-------|-------|-------|
| 0 | s4 | - | - | s5 | - | - |
| 1 | - | s6 | - | - | - | acc |
| 2 | - | r3 | r3 | - | r3 | r3 |
| 3 | - | r6 | r6 | - | r6 | r6 |
| 4 | - | r7 | r7 | - | r7 | r7 |
| 5 | s4 | - | - | s5 | - | - |
| 6 | s4 | - | - | s5 | - | - |

其中，s表示移进，r表示归约，acc表示接受。

接下来，我们使用dfaRecognize函数进行分析：

public static boolean dfaRecognize(String input) {
    Stack<Integer> stateStack = new Stack<>(); //状态栈
    Stack<Character> symbolStack = new Stack<>(); //符号栈
    stateStack.push(0);
    symbolStack.push('$'); //将结束符号入栈

    int ptr = 0; //指向输入串的指针
    while (true) {
        int curState = stateStack.peek();
        char curInput = ptr >= input.length() ? '$' : input.charAt(ptr);
        char action = actionTable[curState][getCol(curInput)];
        if (action == '-') { //出错
            System.out.println("Error!");
            return false;
        } else if (action == 's') { //移进
            int nextState = goToTable[curState][getCol(curInput)];
            stateStack.push(nextState);
            symbolStack.push(curInput);
            ptr++;
        } else if (action == 'r') { //归约
            int reduceRuleIndex = actionTable[curState][getCol(symbolStack.get(symbolStack.size() - 2))];
            String reduceRule = reduceRules[reduceRuleIndex];
            int reduceLength = reduceRule.substring(3).length();
            for (int i = 0; i < reduceLength; i++) {
                stateStack.pop();
                symbolStack.pop();
            }
            int newState = goToTable[stateStack.peek()][getCol(reduceRule.charAt(0))];
            stateStack.push(newState);
            symbolStack.push(reduceRule.charAt(0));
        } else if (action == 'acc') { //接受
            System.out.println("Accept!");
            return true;
        }
    }
}

private static int getCol(char c) {
    switch (c) {
        case 'id':
            return 0;
        case '*':
            return 1;
        case '+':
            return 2;
        case '(':
            return 3;
        case ')':
            return 4;
        case '$':
            return 5;
        default:
            return -1;
    }
}

最后，我们调用dfaRecognize函数进行分析：

public static void main(String[] args) {
    String input = "id*id+id";
    System.out.println(dfaRecognize(input));
}

输出如下：

Accept!
true

因此，该字符串符合文法产生式，是合法的。