文法（grammar）

想像你有一台小機器，它不檢查句子，而是「建造」句子。你從一個佔位符開始，依照一份固定的規則清單，不斷把佔位符替換成其他片段，直到剩下的全是真正的字詞為止。文法正是如此：它是一組有限的重寫規則，用來「生成」字串，而不是像 DFA 那樣「讀取」字串並判斷接受與否。這是描述語言的第二種偉大方式，它把問題從「辨識」翻轉成「生成」。

具體來說，文法包含幾項材料：一些特殊的佔位符號（稱為變數或非終端符號），代表「仍在施工中的片段」；finished 字串中真正出現的字母表字母（終端符號）；一個選定的起始佔位符；以及一份形如「這個佔位符可以被重寫成那串序列」的產生式清單。你從起始符號開始，反覆套用規則來生成字串，每次把一個佔位符替換成它某個允許的右側，直到只剩終端符號為止。用這種方式能產生的「所有」字串所成的集合，就是這個文法所生成的語言。

文法之所以重要，是因為它能捕捉有限自動機不易呈現的「結構」。像 S → ( S ) 這樣的規則是遞迴的：S 內部又含有另一個 S，這種巢狀正是描述配對括號、巢狀程式區塊與算術表達式的關鍵。不同家族的文法位於喬姆斯基階層（Chomsky hierarchy）的不同層級；對程式語言最重要的一層是上下文無關文法，也就是本領域的焦點。請小心別把文法（負責生成）與剖析器（給定字串、設法找出文法如何能生成它）混為一談。