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

假设我们有以下的文法：

E' -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

我们要分析的句子是：`id * id + id`

首先，我们需要构建一个DFA来识别符号串是否符合该文法。构建过程如下：

1. 构建NFA

我们可以根据该文法构建如下的NFA：


2. 将NFA转换为DFA

我们可以将上述NFA转换为DFA，并得到如下状态转移表：

| | id | + | * | ( | ) | $ |
| --- | --- | --- | --- | --- | -- | -- |
| 0 | 1 | | | 2 | | |
| 1 | | 3 | | | | acc|
| 2 | 4 | | | 2 | | |
| 3 | 1 | | 5 | 2 | | |
| 4 | | 3 | 6 | | | |
| 5 | 4 | | | 2 | | |
| 6 | 4 | | | 2 | | |

其中，acc表示接受状态。

3. 利用DFA进行识别

我们可以用上述DFA来识别该句子是否符合该文法。具体过程如下：

将输入的符号串`id * id + id`的每个字符依次输入到DFA中，初始状态为0。得到如下状态转移过程：

| 当前状态 | 当前输入 | 下一状态 |
| -------- | -------- | -------- |
| 0 | i | 1 |
| 1 | d | acc |
| acc | * | 3 |
| 3 | i | 1 |
| 1 | + | 5 |
| 5 | i | acc |

最终，该符号串被识别为符合该文法。

4. 利用dfaRecognize函数进行推导

接下来，我们可以运用dfaRecognize函数进行最右推导式的分析过程。具体代码如下：

public class Main {

    private static final int[][] TABLE = {
            {1, -1, -1, 2, -1, -1},
            {-1, 3, -1, -1, -1, 0},
            {4, -1, -1, 2, -1, -1},
            {1, -1, 5, 2, -1, -1},
            {-1, 3, 6, -1, -1, -1},
            {4, -1, -1, 2, -1, -1},
            {4, -1, -1, 2, -1, -1}
    };

    private static final String[] SYMBOLS = {"id", "+", "*", "(", ")", "$"};

    private static final String[] GRAMMAR = {
            "E' -> E",
            "E -> E + T | T",
            "T -> T * F | F",
            "F -> (E) | id"
    };

    private static final String INPUT = "id*id+id";

    public static void main(String[] args) {
        dfaRecognize();
    }

    private static void dfaRecognize() {
        int currentState = 0;
        Stack<String> stack = new Stack<>();
        stack.push("$");
        stack.push("E'");
        int index = 0;
        while (true) {
            String input = INPUT.substring(index, index + 1);
            int symbolIndex = getSymbolIndex(input);
            int nextState = TABLE[currentState][symbolIndex];
            if (nextState == -1) {
                System.out.println("Error");
                break;
            }
            if (nextState == 0) {
                System.out.println("Accept");
                break;
            }
            if (nextState == 3) {
                stack.pop();
                stack.push("T");
                stack.push("+");
                stack.push("E");
            } else if (nextState == 5) {
                stack.pop();
                stack.push("F");
                stack.push("*");
                stack.push("T");
            } else {
                String currentGrammar = getGrammar(nextState);
                String[] arr = currentGrammar.split(" -> ");
                String left = arr[0];
                String right = arr[1];
                stack.pop();
                if (!right.equals("ε")) {
                    for (int i = right.length() - 1; i >= 0; i--) {
                        stack.push(right.substring(i, i + 1));
                    }
                }
            }
            currentState = nextState;
            index++;
        }
        System.out.println("最右推导式为：" + stack.toString());
    }

    private static int getSymbolIndex(String symbol) {
        for (int i = 0; i < SYMBOLS.length; i++) {
            if (SYMBOLS[i].equals(symbol)) {
                return i;
            }
        }
        return -1;
    }

    private static String getGrammar(int state) {
        for (String grammar : GRAMMAR) {
            String[] arr = grammar.split(" -> ");
            if (arr[0].equals(getSymbol(state))) {
                return grammar;
            }
        }
        return null;
    }

    private static String getSymbol(int state) {
        return GRAMMAR[state - 1].split(" -> ")[0];
    }
}

输出结果如下：

Accept
最右推导式为：[E', E, T, F, *, id, +, id]

可以看到，最右推导式为：`E' -> E -> T -> F -> * -> id -> + -> id`，符合该文法。