上下文無關文法與推導

最右推導(rightmost derivation)

最左紀律的鏡像:當好幾個變數等著被展開時,最右推導總是先重寫「最右邊」的那個。如果最左是嚴格地由左填空,那麼最右就是總是伸手去填最後一個空格。這是同一個施加順序的想法,只是從另一端做起。

形式上,若每一步都把產生式套用到當前句型中最右邊出現的變數,則該推導是最右推導,有時標記為 =>rm。以 E → E + E | a,a + a 的一個最右推導是 E =>rm E + E =>rm E + a =>rm a + a,其中右邊的 E 在左邊的 E 之前被展開。正如最左的情形,固定「最右」去除了重新排序要攻擊哪個變數的自由,只留下要套用哪條規則的選擇。

最右推導也與剖析樹一一對應(對給定的一棵樹恰有一個最右推導),所以它是同樣有效的讀出結構的方式。它的特殊重要性在於由下而上的剖析:LR 剖析器實際上是「逆向」構造一個最右推導,當它把輸入歸約回起始符號時,逐一辨識規則的右側(即句柄)。最右推導逆讀,正是由下而上剖析常被稱為「正則(canonical)」的原因。別假設某字串的最右推導作為序列會等於它的最左推導——作為序列它們通常不同,卻描述相同的樹。

文法 S → A B、A → a、B → b B | b。「abb」的最右推導:S =>rm A B =>rm A b B =>rm A b b =>rm a b b。每一步都展開最右邊的變數(B 全部展開後才輪到 A)。

每一步都重寫最右邊的變數;由下而上(LR)剖析逆向建造一個最右推導。

最左與最右是「同一個」推導概念的兩種紀律;兩者都與剖析樹一一對應。即使描述相同的樹,它們的步驟序列通常仍不同。

又稱
RM derivationcanonical derivation最右推演正則推導