上下文無關語言:化簡與正規形式

左遞迴移除(left-recursion removal)

若一個習慣總是以「先做這件事,然後做更多」開頭,你可以把它翻成「先做一次,然後視情況重複」——結果相同,但現在有了明確的第一步,而不是無限卡住。左遞迴移除就是這樣翻轉文法:把在左側遞迴的規則改寫成在右側遞迴,使由上而下的剖析器總能取得進展。

對於直接左遞迴,把 A 的規則分成左遞迴的那些 A -> A alpha1 | A alpha2 | ... 與其他的 A -> beta1 | beta2 | ...。引入一個全新的輔助變數 A'。把它們換成 A -> beta1 A' | beta2 A' | ... 與 A' -> alpha1 A' | alpha2 A' | ... | epsilon。其概念是:A 現在以某個非遞迴的 beta 片段開頭,然後 A' 在右側接上任意多個 alpha 尾巴。間接左遞迴的處理方式是:先把變數排序,把較早變數的規則代入較晚的,直到所有間接情形都變成直接的,再套用直接修法。

這個變換完全保持語言不變,但關鍵是它會改變剖析樹:向左傾的樹(適合左結合運算子)變成向右傾。這表示任何依賴原形狀的語意動作或結合性都必須重新接上,通常是在剖析器中顯式計算結合性,而不是從樹上直接讀出。左遞迴移除連同左因子分解,正是讓文法適合由上而下的 LL 或遞迴下降剖析的關鍵,它也是 Greibach 正規形式轉換的一個子步驟。

從 E -> E + T | T 移除直接左遞迴。這裡 alpha = +T,beta = T。引入 E':E -> T E', E' -> + T E' | epsilon。現在 E 以 T 開頭(真正的進展),而 E' 在右側重複「+T」。語言完全相同,但樹現在向右傾。

左遞迴透過輔助變數 A' 變成右遞迴;語言保持不變,樹被重新塑形。

移除左遞迴保持語言不變,但把剖析樹形狀從向左傾翻成向右傾,這可能破壞左結合性。你必須在剖析器的動作中重建結合性,而不能假設樹仍編碼了它。

又称
eliminating left recursionleft-recursion elimination左遞迴消除去左遞迴