用Java代码写一个lr分析程序

下面是一个简单的 Java 代码实现 LR 分析的示例：

import java.util.*;

public class LRParser {

    // 定义文法规则
    private static final String[][] grammar = {
        {"E'", "E"},
        {"E", "E+T"},
        {"E", "T"},
        {"T", "T*F"},
        {"T", "F"},
        {"F", "(E)"},
        {"F", "id"}
    };

    // 定义符号集合
    private static final Set<String> nonTerminals = new HashSet<>();
    private static final Set<String> terminals = new HashSet<>();
    private static final Map<String, Set<String>> followSets = new HashMap<>();

    static {
        for (String[] rule : grammar) {
            nonTerminals.add(rule[0]);
            for (int i = 1; i < rule.length; i++) {
                if (!nonTerminals.contains(rule[i])) {
                    terminals.add(rule[i]);
                }
            }
        }
    }

    // 构建 LR 分析表
    private static final String[][] actionTable = {
        {"S5", "", "", "S4", "", "", ""},
        {"", "S6", "", "", "", "", "acc"},
        {"", "R2", "S7", "", "R2", "R2", ""},
        {"", "R4", "R4", "", "R4", "R4", ""},
        {"S5", "", "", "S4", "", "", ""},
        {"", "R6", "R6", "", "R6", "R6", ""},
        {"S5", "", "", "S4", "", "", ""},
        {"S5", "", "", "S4", "", "", ""},
        {"", "S6", "", "", "S11", "", ""},
        {"", "R1", "S7", "", "R1", "R1", ""},
        {"", "R3", "R3", "", "R3", "R3", ""},
        {"", "R5", "R5", "", "R5", "R5", ""}
    };

    private static final int[][] gotoTable = {
        {1, 2, 3},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0},
        {8, 2, 3},
        {0, 0, 0},
        {0, 9, 3},
        {0, 0, 10},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0}
    };

    // 定义栈
    private static Stack<Integer> stateStack = new Stack<>();
    private static Stack<String> symbolStack = new Stack<>();

    // LR 分析函数
    public static void parse(String input) {
        stateStack.push(0);
        int i = 0;
        while (i < input.length()) {
            int state = stateStack.peek();
            String lookahead = input.substring(i, i + 1);
            String action = actionTable[state][terminals.indexOf(lookahead)];
            if (action.isEmpty()) {
                throw new RuntimeException("Invalid input at position " + i);
            }
            if (action.startsWith("S")) {
                // 移进
                int nextState = Integer.parseInt(action.substring(1));
                stateStack.push(nextState);
                symbolStack.push(lookahead);
                i++;
            } else if (action.startsWith("R")) {
                // 规约
                int rule = Integer.parseInt(action.substring(1));
                String[] rhs = grammar[rule][1].split("\\s+");
                for (int j = 0; j < rhs.length; j++) {
                    stateStack.pop();
                    symbolStack.pop();
                }
                int prevState = stateStack.peek();
                String lhs = grammar[rule][0];
                stateStack.push(gotoTable[prevState][nonTerminals.indexOf(lhs)]);
                symbolStack.push(lhs);
            } else {
                // 接受
                return;
            }
        }
    }

    public static void main(String[] args) {
        String input = "id+id*id";
        parse(input);
        System.out.println("Input string is valid");
    }
}

在上面的代码中，我们定义了一个简单的 LR 分析器，用于解析输入字符串是否符合文法规则。首先，我们定义了文法规则和符号集合。然后，我们根据文法规则构建 LR 分析表，并定义了栈。最后，我们实现了 LR 分析函数 `parse`，用于解析输入字符串。其中，我们使用了两个栈来记录当前状态和符号，根据 LR 分析表中的状态转移和规约动作，我们不断地移进和规约符号，直到接受输入字符串或发现不合法字符。最终，我们在 `main` 函数中测试了 LR 分析器的功能。