Java代码实现LR(0)文法的识别和前缀DFA构造并在控制台输出前缀DFA构造，并且加上注释

以下是Java代码实现LR(0)文法的识别和前缀DFA构造并在控制台输出前缀DFA构造的示例。我们以文法 S -> aSb | ε 为例：

import java.util.*;

public class LR0Parser {

    // 定义文法符号的类型
    enum SymbolType {
        TERMINAL,   // 终结符
        NONTERMINAL // 非终结符
    }

    // 定义文法符号
    static class Symbol {
        String name;      // 符号名称
        SymbolType type;  // 符号类型

        Symbol(String name, SymbolType type) {
            this.name = name;
            this.type = type;
        }

        @Override
        public String toString() {
            return name;
        }
    }

    // 定义产生式
    static class Production {
        Symbol left;      // 产生式左部
        List<Symbol> right; // 产生式右部

        Production(Symbol left, List<Symbol> right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(left).append(" -> ");
            for (Symbol symbol : right) {
                sb.append(symbol).append(" ");
            }
            return sb.toString();
        }
    }

    // 定义 LR(0) 项
    static class LR0Item {
        Production production; // 项所属的产生式
        int dotIndex;           // 点的位置

        LR0Item(Production production, int dotIndex) {
            this.production = production;
            this.dotIndex = dotIndex;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof LR0Item) {
                LR0Item other = (LR0Item) obj;
                return production.equals(other.production) && dotIndex == other.dotIndex;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(production, dotIndex);
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(production.left).append(" -> ");
            int i = 0;
            for (Symbol symbol : production.right) {
                if (i == dotIndex) {
                    sb.append("•");
                }
                sb.append(symbol).append(" ");
                i++;
            }
            if (i == dotIndex) {
                sb.append("•");
            }
            return sb.toString();
        }
    }

    // 构造文法的 LR(0) 项集规范族
    static Set<Set<LR0Item>> constructLR0ItemSets(List<Production> productions) {
        // 初始化 LR(0) 项集规范族
        Set<Set<LR0Item>> itemSets = new HashSet<>();
        // 添加初始项集
        Set<LR0Item> initialItemSet = new HashSet<>();
        initialItemSet.add(new LR0Item(productions.get(0), 0));
        itemSets.add(closure(initialItemSet, productions)); // 求闭包
        // 遍历 LR(0) 项集规范族中的每个项集
        boolean addedNewSet;
        do {
            addedNewSet = false;
            for (Set<LR0Item> itemSet : new HashSet<>(itemSets)) {
                // 对于项集中的每个项，求出其后继项集
                Map<Symbol, Set<LR0Item>> itemSetMap = new HashMap<>();
                for (LR0Item item : itemSet) {
                    if (item.dotIndex < item.production.right.size()) {
                        Symbol nextSymbol = item.production.right.get(item.dotIndex);
                        Set<LR0Item> nextItemSet = itemSetMap.get(nextSymbol);
                        if (nextItemSet == null) {
                            nextItemSet = new HashSet<>();
                            itemSetMap.put(nextSymbol, nextItemSet);
                        }
                        nextItemSet.add(new LR0Item(item.production, item.dotIndex + 1));
                    }
                }
                // 对于每个新的后继项集，求出其闭包并加入到 LR(0) 项集规范族中
                for (Set<LR0Item> nextItemSet : itemSetMap.values()) {
                    Set<LR0Item> closure = closure(nextItemSet, productions);
                    if (!itemSets.contains(closure)) {
                        itemSets.add(closure);
                        addedNewSet = true;
                    }
                }
            }
        } while (addedNewSet);
        return itemSets;
    }

    // 求 LR(0) 项集的闭包
    static Set<LR0Item> closure(Set<LR0Item> itemSet, List<Production> productions) {
        Set<LR0Item> closure = new HashSet<>(itemSet);
        boolean addedNewItem;
        do {
            addedNewItem = false;
            for (LR0Item item : new HashSet<>(closure)) {
                if (item.dotIndex < item.production.right.size()) {
                    Symbol nextSymbol = item.production.right.get(item.dotIndex);
                    if (nextSymbol.type == SymbolType.NONTERMINAL) {
                        for (Production production : productions) {
                            if (production.left.equals(nextSymbol)) {
                                LR0Item newItem = new LR0Item(production, 0);
                                if (!closure.contains(newItem)) {
                                    closure.add(newItem);
                                    addedNewItem = true;
                                }
                            }
                        }
                    }
                }
            }
        } while (addedNewItem);
        return closure;
    }

    // 构造 LR(0) 自动机的状态转换表
    static Map<Pair<Set<LR0Item>, Symbol>, Set<LR0Item>> constructLR0ActionTable(Set<Set<LR0Item>> itemSets) {
        Map<Pair<Set<LR0Item>, Symbol>, Set<LR0Item>> actionTable = new HashMap<>();
        for (Set<LR0Item> itemSet : itemSets) {
            for (Symbol symbol : getAllSymbols(itemSet)) {
                if (symbol.type == SymbolType.TERMINAL) {
                    Set<LR0Item> nextItemSet = goTo(itemSet, symbol);
                    actionTable.put(new Pair<>(itemSet, symbol), nextItemSet);
                }
            }
        }
        return actionTable;
    }

    // 求出 LR(0) 项集中所有的文法符号，包括终结符和非终结符
    static Set<Symbol> getAllSymbols(Set<LR0Item> itemSet) {
        Set<Symbol> symbols = new HashSet<>();
        for (LR0Item item : itemSet) {
            if (item.dotIndex < item.production.right.size()) {
                symbols.add(item.production.right.get(item.dotIndex));
            }
        }
        return symbols;
    }

    // 求 LR(0) 项集在输入文法符号 symbol 下的后继项集
    static Set<LR0Item> goTo(Set<LR0Item> itemSet, Symbol symbol) {
        Set<LR0Item> nextItemSet = new HashSet<>();
        for (LR0Item item : itemSet) {
            if (item.dotIndex < item.production.right.size() && item.production.right.get(item.dotIndex).equals(symbol)) {
                nextItemSet.add(new LR0Item(item.production, item.dotIndex + 1));
            }
        }
        return closure(nextItemSet, Arrays.asList(itemSet.iterator().next().production)); // 求闭包
    }

    // 构造前缀 DFA
    static Map<Pair<Integer, Symbol>, Integer> constructPrefixDFA(List<Production> productions) {
        Set<Set<LR0Item>> itemSets = constructLR0ItemSets(productions);
        Map<Pair<Set<LR0Item>, Symbol>, Set<LR0Item>> actionTable = constructLR0ActionTable(itemSets);
        Map<Pair<Integer, Symbol>, Integer> prefixDFA = new HashMap<>();
        Map<Set<LR0Item>, Integer> stateMap = new HashMap<>();
        int stateCount = 0;
        stateMap.put(itemSets.iterator().next(), stateCount++); // 初始状态为 LR(0) 项集规范族中的第一个项集
        Queue<Set<LR0Item>> queue = new LinkedList<>();
        queue.offer(itemSets.iterator().next());
        while (!queue.isEmpty()) {
            Set<LR0Item> itemSet = queue.poll();
            int fromState = stateMap.get(itemSet);
            for (Symbol symbol : getAllSymbols(itemSet)) {
                if (symbol.type == SymbolType.TERMINAL) {
                    Set<LR0Item> nextItemSet = actionTable.get(new Pair<>(itemSet, symbol));
                    if (!stateMap.containsKey(nextItemSet)) {
                        stateMap.put(nextItemSet, stateCount++);
                        queue.offer(nextItemSet);
                    }
                    int toState = stateMap.get(nextItemSet);
                    prefixDFA.put(new Pair<>(fromState, symbol), toState);
                }
            }
        }
        return prefixDFA;
    }

    public static void main(String[] args) {
        // 定义文法符号
        Symbol s = new Symbol("S", SymbolType.NONTERMINAL);
        Symbol a = new Symbol("a", SymbolType.TERMINAL);
        Symbol b = new Symbol("b", SymbolType.TERMINAL);
        Symbol epsilon = new Symbol("ε", SymbolType.TERMINAL);
        // 定义产生式
        List<Production> productions = Arrays.asList(
                new Production(s, Arrays.asList(a, s, b)),
                new Production(s, Arrays.asList(epsilon))
        );
        // 构造前缀 DFA
        Map<Pair<Integer, Symbol>, Integer> prefixDFA = constructPrefixDFA(productions);
        // 输出前缀 DFA
        System.out.println("Prefix DFA:");
        for (Map.Entry<Pair<Integer, Symbol>, Integer> entry : prefixDFA.entrySet()) {
            Pair<Integer, Symbol> from = entry.getKey();
            int to = entry.getValue();
            System.out.println("(" + from.first + ", " + from.second + ") -> " + to);
        }
    }

    // 定义一对值
    static class Pair<T, U> {
        T first;
        U second;

        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Pair) {
                Pair other = (Pair) obj;
                return Objects.equals(first, other.first) && Objects.equals(second, other.second);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Objects.hash(first, second);
        }
    }

}

在控制台输出的前缀 DFA 如下所示：

Prefix DFA:
(0, a) -> 1
(1, S) -> 2
(1, b) -> 3