用java写一个上下文无关文法化简的算法程序，先消无用符号，再消空产生式，再消单生成式

好的，以下是一个先消无用符号，再消空产生式，再消单生成式的上下文无关文法化简算法的 Java 程序示例：

import java.util.*;

public class CNF_Simplifier {
    // 定义产生式规则
    private static final Map<String, List<String>> CFG_RULES = new HashMap<>();

    static {
        CFG_RULES.put("S", Arrays.asList("A", "B"));
        CFG_RULES.put("A", Arrays.asList("a", "S", "b"));
        CFG_RULES.put("B", Arrays.asList("c", "S", "d"));
        CFG_RULES.put("B", Arrays.asList("e"));
        CFG_RULES.put("C", Arrays.asList("f", "F"));
        CFG_RULES.put("D", Arrays.asList("g", "G"));
        CFG_RULES.put("E", Arrays.asList("h", "i"));
        CFG_RULES.put("F", Arrays.asList("j", "k"));
        CFG_RULES.put("G", Arrays.asList("l", "m"));
        CFG_RULES.put("H", Arrays.asList("n", "o"));
    }

    public static void main(String[] args) {
        // 将 CFG 规则转换为 CNF 规则
        List<String> cnfRules = convertToCNF(CFG_RULES);

        // 输出化简后的 CNF 规则
        for (String rule : cnfRules) {
            System.out.println(rule);
        }
    }

    private static List<String> convertToCNF(Map<String, List<String>> cfgRules) {
        // 消除无用符号
        Map<String, List<String>> usefulRules = eliminateUselessSymbols(cfgRules);

        // 消除空产生式
        Map<String, List<String>> epsilonFreeRules = eliminateEpsilonProductions(usefulRules);

        // 消除单生成式
        Map<String, List<String>> unitFreeRules = eliminateUnitProductions(epsilonFreeRules);

        // 将 CNF 规则转换为字符串列表
        List<String> cnfRules = new ArrayList<>();
        for (Map.Entry<String, List<String>> entry : unitFreeRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();

            for (String production : productions) {
                cnfRules.add(nonTerminal + " -> " + production);
            }
        }

        return cnfRules;
    }

    // 消除无用符号
    private static Map<String, List<String>> eliminateUselessSymbols(Map<String, List<String>> cfgRules) {
        Set<String> usefulNonTerminals = new HashSet<>();
        Set<String> usefulTerminals = new HashSet<>();

        // 将所有能够推导出终结符号的非终结符号加入到有用的非终结符号集合中
        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();

            for (String production : productions) {
                boolean canDeriveTerminals = true;

                for (int i = 0; i < production.length(); i++) {
                    char symbol = production.charAt(i);

                    if (Character.isLowerCase(symbol) || usefulTerminals.contains(Character.toString(symbol))) {
                        continue;
                    }

                    if (!usefulNonTerminals.contains(Character.toString(symbol))) {
                        canDeriveTerminals = false;
                        break;
                    }
                }

                if (canDeriveTerminals) {
                    usefulNonTerminals.add(nonTerminal);
                    break;
                }
            }
        }

        // 将所有出现在有用产生式中的终结符号加入到有用的终结符号集合中
        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();

            if (usefulNonTerminals.contains(nonTerminal)) {
                for (String production : productions) {
                    for (int i = 0; i < production.length(); i++) {
                        char symbol = production.charAt(i);

                        if (Character.isLowerCase(symbol)) {
                            usefulTerminals.add(Character.toString(symbol));
                        }
                    }
                }
            }
        }

        // 构建新的产生式规则
        Map<String, List<String>> usefulRules = new HashMap<>();

        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();

            if (usefulNonTerminals.contains(nonTerminal)) {
                List<String> usefulProductions = new ArrayList<>();

                for (String production : productions) {
                    boolean canDeriveTerminals = true;

                    for (int i = 0; i < production.length(); i++) {
                        char symbol = production.charAt(i);

                        if (Character.isLowerCase(symbol) || usefulTerminals.contains(Character.toString(symbol))) {
                            continue;
                        }

                        if (!usefulNonTerminals.contains(Character.toString(symbol))) {
                            canDeriveTerminals = false;
                            break;
                        }
                    }

                    if (canDeriveTerminals) {
                        usefulProductions.add(production);
                    }
                }

                usefulRules.put(nonTerminal, usefulProductions);
            }
        }

        return usefulRules;
    }

    // 消除空产生式
    private static Map<String, List<String>> eliminateEpsilonProductions(Map<String, List<String>> cfgRules) {
        Map<String, List<String>> epsilonFreeRules = new HashMap<>();

        // 将所有可以推导出空串的非终结符号加入到 epsilon 集合中
        Set<String> epsilon = new HashSet<>();
        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();

            if (productions.contains("")) {
                epsilon.add(nonTerminal);
            }
        }

        // 递归地将所有可以推导出空串的非终结符号从产生式中删除
        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();

            List<String> epsilonFreeProductions = new ArrayList<>();

            for (String production : productions) {
                if (production.equals("")) {
                    continue;
                }

                boolean containsEpsilon = false;

                for (int i = 0; i < production.length(); i++) {
                    String symbol = Character.toString(production.charAt(i));

                    if (epsilon.contains(symbol)) {
                        containsEpsilon = true;
                        break;
                    }
                }

                if (!containsEpsilon) {
                    epsilonFreeProductions.add(production);
                } else {
                    List<String> newProductions = new ArrayList<>();
                    newProductions.add("");

                    for (int i = 0; i < production.length(); i++) {
                        String symbol = Character.toString(production.charAt(i));

                        if (epsilon.contains(symbol)) {
                            List<String> tempProductions = new ArrayList<>();

                            for (String newProduction : newProductions) {
                                tempProductions.add(newProduction + symbol);
                            }

                            newProductions.addAll(tempProductions);
                        } else {
                            for (int j = 0; j < newProductions.size(); j++) {
                                String newProduction = newProductions.get(j);
                                newProductions.set(j, newProduction + symbol);
                            }
                        }
                    }

                    epsilonFreeProductions.addAll(newProductions);
                }
            }

            epsilonFreeRules.put(nonTerminal, epsilonFreeProductions);
        }

        return epsilonFreeRules;
    }

    // 消除单生成式
    private static Map<String, List<String>> eliminateUnitProductions(Map<String, List<String>> cfgRules) {
        Map<String, List<String>> unitFreeRules = new HashMap<>();

        // 构建映射关系
        Map<String, Set<String>> unitMap = new HashMap<>();

        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();
            Set<String> unitSet = new HashSet<>();

            for (String production : productions) {
                if (production.length() == 1 && Character.isUpperCase(production.charAt(0))) {
                    unitSet.add(production);
                }
            }

            unitMap.put(nonTerminal, unitSet);
        }

        // 消除单生成式
        for (Map.Entry<String, List<String>> entry : cfgRules.entrySet()) {
            String nonTerminal = entry.getKey();
            List<String> productions = entry.getValue();
            Set<String> unitSet = unitMap.get(nonTerminal);
            List<String> unitFreeProductions = new ArrayList<>(productions);

            for (String unit : unitSet) {
                List<String> tempProductions = new ArrayList<>(unitFreeProductions);

                for (String production : tempProductions) {
                    if (unitFreeProductions.contains(production)) {
                        unitFreeProductions.addAll(cfgRules.get(unit));
                        unitFreeProductions.remove(production);
                    }
                }
            }

            unitFreeRules.put(nonTerminal, unitFreeProductions);
        }

        return unitFreeRules;
    }
}

该程序中，我们首先定义了一个上下文无关文法的产生式规则`CFG_RULES`，并实现了一个`convertToCNF`方法，将该 CFG 规则转换为 CNF 规则。接着，我们分别实现了消除无用符号、消除空产生式和消除单生成式的方法，最后将 CNF 规则转换为字符串列表并返回。

在消除无用符号的方法`eliminateUselessSymbols`中，我们首先将所有能够推导出终结符号的非终结符号加入到有用的非终结符号集合中，然后将所有出现在有用产生式中的终结符号加入到有用的终结符号集合中，最后构建新的产生式规则并返回。

在消除空产生式的方法`eliminateEpsilonProductions`中，我们首先将所有可以推导出空串的非终结符号加入到 epsilon 集合中，然后递归地将所有可以推导出空串的非终结符号从产生式中删除，并生成新的产生式规则。

在消除单生成式的方法`eliminateUnitProductions`中，我们首先构建了一个映射关系，将所有单生成式的右部符号放入一个集合中，然后逐一消除单生成式，并生成新的产生式规则。

请注意，本示例程序仅适用于特定的 CFG 规则，如果您需要处理其他类型的 CFG 规则，请做相应的修改。