用 java语言实现LL(1)分析法：（词法分析器） 消除左递归

以下是使用Java语言实现消除左递归的示例代码：

import java.util.*;

public class LeftRecursionElimination {

    // 消除左递归
    public static Map<String, List<String>> eliminate(Map<String, List<String>> grammar) {
        Map<String, List<String>> newGrammar = new LinkedHashMap<>();
        List<String> nonTerminals = new ArrayList<>(grammar.keySet());

        for (int i = 0; i < nonTerminals.size(); i++) {
            String A = nonTerminals.get(i);
            List<String> productions = grammar.get(A);
            List<String> newProductions = new ArrayList<>();

            for (int j = 0; j < i; j++) {
                String B = nonTerminals.get(j);
                List<String> BProductions = grammar.get(B);

                for (String production : productions) {
                    if (production.startsWith(B)) {
                        for (String BProduction : BProductions) {
                            newProductions.add(BProduction + production.substring(1));
                        }
                    } else {
                        newProductions.add(production);
                    }
                }
            }

            productions = newProductions;
            newProductions = new ArrayList<>();
            boolean leftRecursive = false;

            for (String production : productions) {
                if (production.startsWith(A)) {
                    leftRecursive = true;
                    String alpha = production.substring(1);
                    for (String betaProduction : productions) {
                        if (!betaProduction.startsWith(A)) {
                            newProductions.add(betaProduction + A + "'");
                        }
                    }
                    newProductions.add(alpha + A + "'");
                } else {
                    newProductions.add(production + A + "'");
                }
            }

            if (leftRecursive) {
                newProductions.add("ε");
                newGrammar.put(A + "'", newProductions);
            } else {
                newGrammar.put(A, productions);
            }
        }

        return newGrammar;
    }

    public static void main(String[] args) {
        // 示例文法
        Map<String, List<String>> grammar = new LinkedHashMap<>();
        grammar.put("S", Arrays.asList("Aa", "b"));
        grammar.put("A", Arrays.asList("Ac", "Ad", "ε"));

        // 消除左递归
        Map<String, List<String>> newGrammar = eliminate(grammar);

        // 输出结果
        for (String nonTerminal : newGrammar.keySet()) {
            System.out.print(nonTerminal + " -> ");
            List<String> productions = newGrammar.get(nonTerminal);
            for (int i = 0; i < productions.size(); i++) {
                System.out.print(productions.get(i));
                if (i < productions.size() - 1) {
                    System.out.print(" | ");
                }
            }
            System.out.println();
        }
    }
}

在这个示例中，我们使用了一个`Map<String, List<String>>`结构来表示文法。其中，键为非终结符，值为该非终结符对应的产生式列表。我们首先遍历文法中的每个非终结符，并按照左递归和非左递归两类进行处理。对于左递归的产生式，我们将其转化为等价的非左递归形式。然后，在原有的产生式中添加新的产生式，使得每个非终结符的产生式都不含有左递归。

最后，我们输出消除左递归后的文法。