🌟 第一步：理解基本概念
? 什么是文法（Grammar）？
在編程語言或語法分析中，文法 是一組規則，用來描述一種語言的結構。例如：
S → A a
A → B b
B → S c 這表示：
S可以變成A aA可以變成B bB可以變成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) {// 如果當前產生式的第一個符號是 previousNonTerminalif (!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 cGrammar 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 這就成了直接左遞歸！
? 總結一下整個流程
步驟 | 說明 |
1?? | 識別文法中的間接左遞歸（如 |
2?? | 對所有非終結符排序（這里用了字母順序） |
3?? | 逐步處理每個非終結符，把引用了前面非終結符的規則展開 |
4?? | 最終得到一些規則以自身開頭（即直接左遞歸） |
??常見問題解答
Q1: 為什么要把間接左遞歸轉為直接左遞歸？
A1: 因為只有直接左遞歸可以用標準方式消除，間接的不能直接處理。
Q2: 是否只有一種解法？
A2: 不是唯一解法。根據你選擇的處理順序不同，可能會得到不同的中間形式，但最終都應等價。
Q3: 轉換后的規則還能用嗎？
A3: 可以，只是現在它是直接左遞歸了，接下來就可以用標準方法消除它了。
