剖析與文法的應用

LR 剖析(LR parsing)

LR 這個名字與 LL 相對:L 表示輸入由左到右(Left to right)讀,R 表示剖析器重建一個最右推導(Rightmost derivation),但是反向地,從葉子往上建。LR 剖析是由下而上移位-歸約剖析的強大、表驅動形式,是自動工具產生的那種,也是能處理人們自然想寫的文法的那種。

LR 剖析器由一台從文法建出的有限自動機驅動,其狀態概括了「此刻我們可能正在辨認到一半的一切」。剖析器把這些狀態連同符號一起保存在堆疊上。每一步它查一張以目前狀態與下一個前瞻詞符為索引的表,表告訴它恰好其中之一:移位該詞符(並轉到新狀態)、以某條特定規則歸約(堆疊頂端是句柄)、接受,或回報錯誤。各變體在同一構想上形成一道逐級增強的階梯。LR(0) 不用前瞻、最弱;SLR(simple LR)加入 FOLLOW 集前瞻以化解某些歸約;LALR(look-ahead LR),yacc 與 bison 採用的甜蜜點,合併狀態以保持表小、同時涵蓋多數真實文法;完整的 LR(1) 追蹤每個狀態精確的前瞻,最強但產生最大的表。

LR 剖析之所以重要,是因為它既強大又自動。它接受每一個確定型上下文無關語言,一個嚴格大於 LL 所能處理的類別,包括直接處理左遞迴文法,而產生器能把文法直接變成快速的線性時間剖析器。誠實的代價是:產生出的表人類讀不懂,且當文法對所選變體而言不是 LR 時,工具會發出移位-歸約或歸約-歸約衝突,作者必須理解並化解。

yacc 與 bison 產生 LALR(1) 剖析器。餵入自然的左遞迴文法 E -> E + E | E * E | num(加上化解衝突的優先序宣告),它們產出一張狀態表,能以線性時間剖析 1 + 2 * 3,因 * 結合得較緊而先把 2 * 3 歸約,再做加法。

LR 變體依能力排序:LR(0) < SLR < LALR < LR(1);LALR 是產生器實務上的預設。

LR 嚴格強於 LL,但並非無所不能:它恰好剖析確定型上下文無關語言。真正歧義的文法無法被任何 LR 變體變成無衝突;歧義必須被消除或以優先序規則化解。

又称
LR(0)SLRLALRLR(1)LR 剖析