推導（derivation）

推導是文法如何建造出某個特定字串的逐步故事。想像一個句子在你眼前生長：你從一個佔位符開始，把它換成某規則的右側，再換掉新佔位符之一，如此繼續，每一步都加以敘述，直到抵達一個全是真正符號的字串。這段被記錄下來的重寫序列「就是」推導。

形式上，推導是一串字串（句型），其中每一個都由前一個套用單一產生式規則而來——寫成 w0 => w1 => w2 => ... => wn——從起始符號開始，以終端符號字串結束。我們寫 S =>* w（讀作「S 經零步或多步推導出 w」）表示存在這樣一個有限序列。例如以規則 S → S S | ( S ) | ε，「()」的一個推導是 S => (S) => ()（先用 S → (S) 再用 S → ε）。一個字串在文法的語言中，恰當且唯當存在一個從起始符號出發、推導出它的推導。

推導是把意義附加到語法上的方式：替一段原始碼找出一個推導，本質上正是剖析器在做的事；而重寫的順序可以標準化（最左、最右）以使推導唯一且可比較。一個關鍵的微妙之處：單一「字串」可能有許多不同的推導，它們只是把獨立的選擇重新排序，卻描述「相同」的結構——所以光憑推導順序並非「結構」的正確概念。結構是由剖析樹捕捉的，它把所有這些排序塌縮成一張圖；當一個字串有兩棵真正不同的剖析樹時，該文法就是歧義的。