文法去除空产生式_文法化简 (CFG Simplification) 翻译

文法去除空产生式，也称为文法化简，是上下文无关文法（CFG）的一种常见化简形式。该化简形式的目的是消除文法中的空产生式，即可以直接推导出空串的产生式。

具体来说，文法去除空产生式的步骤如下：

1. 找出所有可以直接推导出空串的产生式，将它们从产生式集合中删除。
2. 对于剩下的产生式集合中的每个非终结符，找出所有可以通过一系列推导过程得到空串的产生式，将这些产生式中该非终结符的出现位置全部替换成空串。
3. 重复步骤2，直到没有新的产生式可以替换。

经过文法去除空产生式的化简后，产生式集合中不再存在可以直接推导出空串的产生式，这样可以使得我们在进行语法分析时更加简洁和高效。

需要注意的是，文法去除空产生式可能会导致某些非终结符无法推导出任何符号串，这些非终结符称为无用符号，可以通过进一步的文法化简来消除。

相关问题

用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 规则，请做相应的修改。