上下文無關文法（context-free grammar）

由有限自動機辨識的正規語言會撞到一道牆：記憶體有限的機器無法無界地計數，所以它無法保證左括號數量等於右括號數量，也無法描述任意深的巢狀。程式語言、算術與配對括號全都「需要」這種巢狀。上下文無關文法正是爬上階梯一層、用來精確捕捉這種遞迴、巢狀結構的工具。

形式上，上下文無關文法是一個四元組 (V, Σ, R, S)。V 是變數（非終端符號）的有限集合，也就是佔位符。Σ（Sigma）是終端符號的字母表，即所生成字串中真正出現的字母，且 V 與 Σ 互不相交。R 是產生式規則的有限集合，而 S ∈ V 是起始符號。它的決定性限制——也是「上下文無關」之名的由來——是每條規則都具有 A → α 的形狀，左側是「單一」變數 A，右側 α 是任意由變數與終端符號組成的字串。因為左側只是一個變數，你不管它周圍有什麼都可以重寫它；它的「上下文」無關緊要。這條「左側單一變數」的規則就是整個定義，也是上下文無關文法與階層中更強大的上下文相關文法之間的分野。

上下文無關文法是電腦語言語法的主力：幾乎每種程式語言中表達式、敘述與巢狀區塊的結構，都是用 CFG 來規定，通常以 BNF 書寫。它在能力上與下推自動機（有限狀態控制加上單一堆疊）等價，且恰好生成上下文無關語言。一個常見誤解是「上下文無關」代表忽略語意——並非如此；它純粹是對規則「形式」的語法限制（左側一個變數），而上下文無關文法仍可描述結構豐富的語言。