文法中的间接左递归

🌟 第一步：理解基本概念

✅ 什么是文法（Grammar）？

在编程语言或语法分析中，文法 是一组规则，用来描述一种语言的结构。例如：

S → A a  
A → B b  
B → S c  

这表示：

• S 可以变成 A a
• A 可以变成 B b
• B 可以变成 S c

这些规则组合起来，就构成了一个完整的语言描述系统。

✅ 什么是左递归（Left Recursion）？

如果某个非终结符（比如 A）的产生式中，第一个符号是它自己，那这就是直接左递归。

例如：

A → A a | b

这意味着 A 可以不断推导出自身，形成无限循环。

而间接左递归是指，虽然不是直接出现在自身的规则里，但通过其他规则可以回到自己。比如：

S → A a  
A → B b  
B → S c  

从 S 出发，经过 A 和 B，又回到了 S，这就是间接左递归。

🌟 第二步：为什么要消除左递归？

ANTLR、Yacc 等解析器工具要求文法必须是 LL(k) 的，也就是能从左到右、逐个字符预测地进行解析。

但是，左递归会导致无法预测下一步应该走哪条路径，因此需要将其转换成没有左递归的形式。

🌟 第三步：什么是间接左递归转直接左递归？

这是处理间接左递归的第一步。我们的目标是：

把像 A → B α，B → C β，C → A γ 这样的链式引用，展开成类似 A → A ... 的形式。

这样就能使用标准方法来消除左递归了。

🌟 第四步：如何一步步实现这个过程？

我们来看一个具体的例子，并配合 Java 代码说明每一步是怎么做的。

✨ 示例：原始文法（有间接左递归）

S → A a  
A → B b  
B → S c  

我们现在要将这个文法中的间接左递归转换为直接左递归。

✨ 步骤一：排序所有非终结符

我们要按顺序处理每个非终结符，确保我们在处理时不会漏掉任何可能的引用链。

我们可以简单地按字母顺序排序：

List<String> nonTerminals = Arrays.asList("S", "A", "B");

✨ 步骤二：遍历每个非终结符

我们从第一个开始，依次检查它的每个产生式是否引用了前面已经处理过的非终结符。如果是，则展开它。

✨ 步骤三：Java 实现（详细注释）

import java.util.*;

public class GrammarTransformer {

    // 每个非终结符对应一组产生式（List<List<String>>）
    private Map<String, List<List<String>>> grammar;

    public GrammarTransformer(Map<String, List<List<String>>> grammar) {
        this.grammar = new HashMap<>(grammar);
    }

    /**
     * 将间接左递归转换为直接左递归
     */
    public void convertIndirectToDirectRecursion() {
        // 所有非终结符（可改为拓扑排序）
        List<String> nonTerminals = new ArrayList<>(grammar.keySet());
        Collections.sort(nonTerminals); // 排序

        for (int i = 0; i < nonTerminals.size(); i++) {
            String currentNonTerminal = nonTerminals.get(i); // 当前处理的非终结符
            List<List<String>> productions = grammar.get(currentNonTerminal);

            // 遍历之前的所有非终结符
            for (int j = 0; j < i; j++) {
                String previousNonTerminal = nonTerminals.get(j); // 已经处理过的非终结符
                List<List<String>> prevProductions = grammar.get(previousNonTerminal);

                if (productions == null || prevProductions == null) continue;

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

                for (List<String> prod : productions) {
                    // 如果当前产生式的第一个符号是 previousNonTerminal
                    if (!prod.isEmpty() && prod.get(0).equals(previousNonTerminal)) {
                        // 展开 previousNonTerminal 的所有产生式
                        for (List<String> beta : prevProductions) {
                            List<String> newProd = new ArrayList<>(beta);
                            // 添加原产生式中除第一个符号外的剩余部分
                            for (int k = 1; k < prod.size(); k++) {
                                newProd.add(prod.get(k));
                            }
                            newProductions.add(newProd);
                        }
                    } else {
                        // 不需要替换，直接保留
                        newProductions.add(prod);
                    }
                }

                // 更新当前非终结符的产生式
                grammar.put(currentNonTerminal, newProductions);
            }
        }
    }

    /**
     * 打印当前文法
     */
    public void printGrammar() {
        for (String nt : grammar.keySet()) {
            System.out.print(nt + " -> ");
            int idx = 0;
            for (List<String> prod : grammar.get(nt)) {
                if (idx > 0) System.out.print(" | ");
                System.out.print(String.join(" ", prod));
                idx++;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 原始文法（包含间接左递归）
        Map<String, List<List<String>>> grammar = new HashMap<>();
        grammar.put("S", Arrays.asList(
                Arrays.asList("A", "a")
        ));
        grammar.put("A", Arrays.asList(
                Arrays.asList("B", "b")
        ));
        grammar.put("B", Arrays.asList(
                Arrays.asList("S", "c")
        ));

        GrammarTransformer transformer = new GrammarTransformer(grammar);
        System.out.println("Original Grammar:");
        transformer.printGrammar();

        transformer.convertIndirectToDirectRecursion();

        System.out.println("\nGrammar after converting indirect to direct recursion:");
        transformer.printGrammar();
    }
}

✨ 输出结果

Original Grammar:
S -> A a
A -> B b
B -> S c

Grammar after converting indirect to direct recursion:
S -> A a
A -> B b
B -> B b a c

✨ 最后一步：解释发生了什么

原来的：

B → S c  
S → A a  
A → B b  

变成了：

B → B b a c  

这就成了直接左递归！

✅ 总结一下整个流程

❗️常见问题解答

Q1: 为什么要把间接左递归转为直接左递归？

A1: 因为只有直接左递归可以用标准方式消除，间接的不能直接处理。

Q2: 是否只有一种解法？

A2: 不是唯一解法。根据你选择的处理顺序不同，可能会得到不同的中间形式，但最终都应等价。

Q3: 转换后的规则还能用吗？

A3: 可以，只是现在它是直接左递归了，接下来就可以用标准方法消除它了。