上下文無關(guān)文法

一個(gè) 上下文無關(guān)文法 由一定數(shù)量的 產(chǎn)生式 (productions) 組成。每個(gè)產(chǎn)生式的 左邊 (left-hand side) 是一個(gè)被稱為非終結(jié)符 (nonterminal) 的抽象符號(hào)， 右邊 (right-hand side) 是零或多個(gè)非終結(jié)符和 終結(jié)符 (terminal symbols) 的有序排列。任何文法，它的終結(jié)符都來自指定的字母集。

當(dāng)從一個(gè)叫做 目標(biāo)符 (goal symbol) 的特殊非終端符組成的句子起始，那么給出的上下文無關(guān)文法就表示 語言 (language)，即，將產(chǎn)生式右邊序列的非終結(jié)符當(dāng)作左邊，進(jìn)行反復(fù)替換的結(jié)果就成為可能的終結(jié)符序列集合（可能無限）。