LR(0)分析法： 运用java语言 构造识别活前缀的DFA （即LR(0)项目集规范族的构造） （1）LR（0） 项目集的闭包ＣLOSURE, GO 函数，

LR(0)分析法是一种语法分析方法，它通过构建DFA来识别输入符号串是否符合给定的文法规则。下面是使用Java语言构造识别活前缀的DFA的步骤：

1. 定义LR(0)项目的结构体，包含产生式左部、产生式右部、点的位置和向前看符号等信息。

class LR0Item {
    String left; // 产生式左部
    String[] right; // 产生式右部
    int dot; // 点的位置
    Set<String> lookahead; // 向前看符号

    // 构造函数
    public LR0Item(String left, String[] right, int dot, Set<String> lookahead) {
        this.left = left;
        this.right = right;
        this.dot = dot;
        this.lookahead = lookahead;
    }

    // 判断是否为归约项
    public boolean isReduceItem() {
        return dot == right.length;
    }

    // 获取下一个符号
    public String getNextSymbol() {
        return right[dot];
    }

    // 获取产生式
    public String getProduction() {
        return left + " -> " + String.join(" ", right);
    }

    // 获取项目集
    public String getItemSet() {
        return getProduction() + ", " + lookahead.toString();
    }

    // 判断两个项目是否相等
    public boolean equals(LR0Item item) {
        return left.equals(item.left) && Arrays.equals(right, item.right) && dot == item.dot && lookahead.equals(item.lookahead);
    }
}

2. 定义DFA节点的结构体，包含项目集和转移函数等信息。

class DFANode {
    Set<LR0Item> items; // 项目集
    Map<String, DFANode> transition; // 转移函数

    // 构造函数
    public DFANode(Set<LR0Item> items) {
        this.items = items;
        this.transition = new HashMap<>();
    }

    // 判断是否为接受状态
    public boolean isAcceptState() {
        for (LR0Item item : items) {
            if (item.isReduceItem() && item.left.equals("S'")) {
                return true;
            }
        }
        return false;
    }

    // 根据符号进行转移
    public DFANode transition(String symbol) {
        return transition.get(symbol);
    }

    // 添加转移
    public void addTransition(String symbol, DFANode node) {
        transition.put(symbol, node);
    }

    // 获取项目集
    public String getItemSet() {
        StringBuilder builder = new StringBuilder();
        for (LR0Item item : items) {
            builder.append(item.getItemSet()).append("\n");
        }
        return builder.toString();
    }

    // 获取转移表
    public String getTransitionTable() {
        StringBuilder builder = new StringBuilder();
        for (String symbol : transition.keySet()) {
            builder.append(String.format("%-10s -> %s\n", symbol, transition.get(symbol).getItemSet()));
        }
        return builder.toString();
    }
}

3. 构造LR(0)项目集族，包括CLOSURE和GO函数。CLOSURE函数用于计算项目集的闭包，GO函数用于计算项目集的转移。

class LR0ItemSetFamily {
    List<Set<LR0Item>> itemSets; // 项目集族

    // 构造LR(0)项目集族
    public LR0ItemSetFamily(Grammar grammar) {
        itemSets = new ArrayList<>();
        Set<LR0Item> startSet = new HashSet<>();
        startSet.add(new LR0Item("S'", new String[]{"S"}, 0, grammar.getTerminals()));
        itemSets.add(closure(startSet, grammar));
        int i = 0;
        while (i < itemSets.size()) {
            Set<LR0Item> itemSet = itemSets.get(i);
            Map<String, Set<LR0Item>> go = go(itemSet, grammar);
            for (String symbol : go.keySet()) {
                Set<LR0Item> nextSet = closure(go.get(symbol), grammar);
                if (!itemSets.contains(nextSet)) {
                    itemSets.add(nextSet);
                }
                DFANode node = getNode(itemSet);
                node.addTransition(symbol, getNode(nextSet));
            }
            i++;
        }
    }

    // 计算项目集的闭包
    private Set<LR0Item> closure(Set<LR0Item> items, Grammar grammar) {
        Set<LR0Item> closure = new HashSet<>(items);
        while (true) {
            boolean changed = false;
            for (LR0Item item : closure) {
                if (!item.isReduceItem()) {
                    String nextSymbol = item.getNextSymbol();
                    Set<String> lookahead = lookahead(closure, item);
                    Set<LR0Item> productions = grammar.getProductions(nextSymbol);
                    for (LR0Item production : productions) {
                        LR0Item newItem = new LR0Item(production.left, production.right, 0, lookahead);
                        if (!closure.contains(newItem)) {
                            closure.add(newItem);
                            changed = true;
                        }
                    }
                }
            }
            if (!changed) {
                break;
            }
        }
        return closure;
    }

    // 计算项目集的转移
    private Map<String, Set<LR0Item>> go(Set<LR0Item> items, Grammar grammar) {
        Map<String, Set<LR0Item>> go = new HashMap<>();
        for (LR0Item item : items) {
            if (!item.isReduceItem()) {
                String nextSymbol = item.getNextSymbol();
                Set<LR0Item> productions = grammar.getProductions(nextSymbol);
                for (LR0Item production : productions) {
                    LR0Item newItem = new LR0Item(production.left, production.right, 0, item.lookahead);
                    if (!go.containsKey(nextSymbol)) {
                        go.put(nextSymbol, new HashSet<>());
                    }
                    go.get(nextSymbol).add(newItem);
                }
            }
        }
        return go;
    }

    // 计算LR(0)项目的向前看符号
    private Set<String> lookahead(Set<LR0Item> items, LR0Item item) {
        Set<String> lookahead = new HashSet<>();
        if (item.isReduceItem()) {
            lookahead.addAll(item.lookahead);
        } else {
            String nextSymbol = item.getNextSymbol();
            for (LR0Item i : items) {
                if (!i.equals(item) && !i.isReduceItem() && i.getNextSymbol().equals(nextSymbol)) {
                    lookahead.addAll(i.lookahead);
                }
            }
        }
        return lookahead;
    }

    // 获取DFA节点
    private DFANode getNode(Set<LR0Item> items) {
        for (DFANode node : nodes) {
            if (node.items.equals(items)) {
                return node;
            }
        }
        DFANode node = new DFANode(items);
        nodes.add(node);
        return node;
    }

    // 获取DFA节点集合
    public List<DFANode> getNodes() {
        return nodes;
    }

    // 获取DFA表
    public String getDFATable() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < nodes.size(); i++) {
            builder.append(String.format("State %d:\n%s%s\n", i, nodes.get(i).getItemSet(), nodes.get(i).getTransitionTable()));
        }
        return builder.toString();
    }
}

4. 根据输入符号串进行LR(0)分析。分析过程中，使用栈来保存状态和符号。

class LR0Parser {
    private List<DFANode> nodes; // DFA节点集合
    private Map<String, Integer> actionTable; // ACTION表
    private Map<String, Integer> gotoTable; // GOTO表

    // 构造函数
    public LR0Parser(Grammar grammar) {
        LR0ItemSetFamily itemSetFamily = new LR0ItemSetFamily(grammar);
        nodes = itemSetFamily.getNodes();
        actionTable = new HashMap<>();
        gotoTable = new HashMap<>();
        for (int i = 0; i < nodes.size(); i++) {
            DFANode node = nodes.get(i);
            for (String symbol : node.transition.keySet()) {
                if (grammar.isTerminal(symbol)) {
                    actionTable.put(String.format("%d %s", i, symbol), nodes.indexOf(node.transition(symbol)));
                } else {
                    gotoTable.put(String.format("%d %s", i, symbol), nodes.indexOf(node.transition(symbol)));
                }
            }
            for (LR0Item item : node.items) {
                if (item.isReduceItem()) {
                    for (String lookahead : item.lookahead) {
                        actionTable.put(String.format("%d %s", i, lookahead), -grammar.getProductionIndex(item.left, item.right));
                    }
                }
            }
        }
    }

    // 分析输入符号串
    public boolean parse(List<String> input) {
        Stack<Integer> stateStack = new Stack<>();
        Stack<String> symbolStack = new Stack<>();
        stateStack.push(0);
        int index = 0;
        while (true) {
            int state = stateStack.peek();
            String symbol = index < input.size() ? input.get(index) : "$";
            if (actionTable.containsKey(String.format("%d %s", state, symbol))) {
                int next = actionTable.get(String.format("%d %s", state, symbol));
                if (next >= 0) { // shift
                    stateStack.push(next);
                    symbolStack.push(symbol);
                    index++;
                } else { // reduce
                    int productionIndex = -next;
                    Production production = grammar.getProduction(productionIndex);
                    for (int i = 0; i < production.right.length; i++) {
                        stateStack.pop();
                        symbolStack.pop();
                    }
                    state = stateStack.peek();
                    symbolStack.push(production.left);
                    stateStack.push(gotoTable.get(String.format("%d %s", state, production.left)));
                }
            } else {
                return false;
            }
            if (stateStack.size() == 1 && symbolStack.peek().equals("S'")) {
                return true;
            }
        }
    }
}

LR(0)分析法是一种强大的语法分析方法，可以处理大部分上下文无关文法。使用Java语言实现LR(0)分析法需要注意代码的结构和数据结构的选择，以便更好地组织和管理LR(0)项目集族、DFA和分析表等信息。