判别是否是LL（1）文法的java代码

以下是一个简单的 Java 代码，可用于判定一个文法是否为 LL(1) 文法：

import java.util.*;

public class LL1GrammarChecker {

    // 判断是否为 LL(1) 文法的方法
    public static boolean isLL1Grammar(Map<String, List<String>> grammar) {
        // 对于每个非终结符号 A
        for (String A : grammar.keySet()) {
            // 构建 A -> α1 | α2 | ... | αn 的形式
            List<String> productions = grammar.get(A);
            // 计算 FIRST(A)
            Set<String> first = calculateFirst(A, productions, grammar);
            // 对于每个产生式 A -> αi
            for (String alpha : productions) {
                // 计算 FIRST(αi)
                Set<String> alphaFirst = calculateFirst(alpha, grammar);
                // 如果 FIRST(αi) 包含 ε，则将 FOLLOW(A) 加入 FOLLOW(αi)
                if (alphaFirst.contains("ε")) {
                    Set<String> follow = calculateFollow(A, grammar);
                    for (String symbol : follow) {
                        if (symbol.equals("$")) {
                            continue;
                        }
                        if (!calculateFirst(symbol, grammar).contains("ε")) {
                            return false;
                        }
                    }
                }
                // 如果 FIRST(αi) 交 FOLLOW(A) 不为空，则不是 LL(1) 文法
                Set<String> intersect = new HashSet<>(alphaFirst);
                intersect.retainAll(calculateFollow(A, grammar));
                if (!intersect.isEmpty()) {
                    return false;
                }
            }
        }
        return true;
    }

    // 计算一个符号串的 FIRST 集合
    private static Set<String> calculateFirst(String symbolString, Map<String, List<String>> grammar) {
        Set<String> first = new HashSet<>();
        // 如果符号串是 ε，则 FIRST(ε)={ε}
        if (symbolString.equals("ε")) {
            first.add("ε");
            return first;
        }
        // 如果符号串的第一个符号是终结符号，则 FIRST(符号串)={符号串的第一个符号}
        String firstSymbol = symbolString.substring(0, 1);
        if (grammar.containsKey(firstSymbol)) {
            first.addAll(calculateFirst(firstSymbol, grammar));
        } else {
            first.add(firstSymbol);
        }
        // 如果符号串的第一个符号可以推出 ε，则将下一个符号加入 FIRST(符号串)
        if (first.contains("ε")) {
            first.addAll(calculateFirst(symbolString.substring(1), grammar));
        }
        return first;
    }

    // 计算一个非终结符号的 FOLLOW 集合
    private static Set<String> calculateFollow(String nonterminal, Map<String, List<String>> grammar) {
        Set<String> follow = new HashSet<>();
        // 对于文法开始符号 S，将 $ 加入 FOLLOW(S)
        if (nonterminal.equals(grammar.keySet().iterator().next())) {
            follow.add("$");
        }
        // 对于每个产生式 A -> αBβ，将 FIRST(β) 中不包含 ε 的符号加入 FOLLOW(B)
        for (String A : grammar.keySet()) {
            for (String alpha : grammar.get(A)) {
                int BIndex = alpha.indexOf(nonterminal);
                while (BIndex != -1) {
                    if (BIndex < alpha.length() - 1) {
                        Set<String> betaFirst = calculateFirst(alpha.substring(BIndex + 1), grammar);
                        follow.addAll(betaFirst);
                        if (betaFirst.contains("ε")) {
                            follow.addAll(calculateFollow(A, grammar));
                        }
                    } else {
                        follow.addAll(calculateFollow(A, grammar));
                    }
                    BIndex = alpha.indexOf(nonterminal, BIndex + 1);
                }
            }
        }
        return follow;
    }

    // 测试代码
    public static void main(String[] args) {
        // 示例文法：S -> aA | bB, A -> c | ε, B -> c | d
        Map<String, List<String>> grammar = new HashMap<>();
        grammar.put("S", Arrays.asList("aA", "bB"));
        grammar.put("A", Arrays.asList("c", "ε"));
        grammar.put("B", Arrays.asList("c", "d"));

        boolean isLL1 = isLL1Grammar(grammar);
        System.out.println("该文法是否为 LL(1) 文法：" + isLL1);
    }

}

该代码实现了一个 LL1GrammarChecker 类，其中 isLL1Grammar 方法接受一个文法的产生式集合作为参数，返回一个布尔值，表示该文法是否为 LL(1) 文法。

该方法的实现分为以下几个步骤：

1. 对于每个非终结符号 A，计算 FIRST(A)。
2. 对于每个产生式 A -> αi，计算 FIRST(αi)。
3. 如果 FIRST(αi) 包含 ε，则将 FOLLOW(A) 加入 FOLLOW(αi)。
4. 如果 FIRST(αi) 交 FOLLOW(A) 不为空，则该文法不是 LL(1) 文法。

其中，calculateFirst 方法和 calculateFollow 方法用于计算 FIRST 和 FOLLOW 集合，分别采用了迭代和递归的方式实现。