上下文無關文法與推導
最左推導(leftmost derivation)
當一個句型有好幾個變數等著被展開時,你下一步要重寫哪一個?最左推導對此立下嚴格規定:總是展開「最左邊」的變數。這就像嚴格地由左到右讀寫一個句子,絕不在填完較前面的空格之前跳去填較後面的。這條紀律馴服了任意重寫順序的混亂。
形式上,若每一步都把產生式套用到當前句型中最左邊出現的變數,則該推導是最左推導。我們有時用下標標記這些步驟,=>lm。例如以 E → E + E | a,字串 a + a + a 有最左推導 E =>lm E + E =>lm a + E =>lm a + E + E =>lm a + a + E =>lm a + a + a,其中每一步都重寫第一個剩下的變數。固定「最左」的用意,是去除重新排序獨立選擇的自由,於是唯一剩下的選擇就是要套用哪「條」規則。
關鍵事實:對給定的一棵剖析樹,恰好存在「一個」最左推導,而一個最左推導也恰好決定一棵剖析樹。所以最左推導與剖析樹一一對應——這使它成為精確定義歧義的正確工具(一個文法是歧義的,當且唯當某字串有兩個不同的最左推導,等價地有兩棵不同的剖析樹),也是由上而下剖析器的自然模型,後者在由左到右掃描輸入時建造一個最左推導。請特別注意:同一字串的最左推導與最右推導可能是不同的序列,卻仍對應到「相同」的剖析樹。
文法 S → A B、A → a A | a、B → b。「aab」的最左推導:S =>lm A B =>lm a A B =>lm a a B =>lm a a b。每一步都展開最左邊的變數(A 先於 B)。
每一步都重寫最左邊的變數;這讓推導與剖析樹一一對應。
每棵剖析樹恰有一個最左推導與一個最右推導;某字串的最左與最右序列可能不同,卻描述「相同」的樹。歧義 = 兩個不同的最左推導(= 兩棵不同的剖析樹)。
又稱
另見