文法：它描述語(yǔ)言語(yǔ)法結(jié)構(gòu)的一組形式規(guī)則。
?上下文無(wú)關(guān)文法：它定義的語(yǔ)法范疇（或語(yǔ)法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境。例如，在程序設(shè)計(jì)語(yǔ)言中，當(dāng)碰到一個(gè)算術(shù)表達(dá)式時(shí)，我們完全可以“就事論事”處理，而不必考慮它所處的上下文。然而，在自然語(yǔ)言中，隨便一個(gè)詞，甚至一個(gè)字的意思在不同的上下文中都有可能有不同的意思。幸運(yùn)的是，當(dāng)今的程序設(shè)計(jì)語(yǔ)言都是上下文無(wú)關(guān)的
。
好像有點(diǎn)抽象，來(lái)個(gè)例子
"→"表示箭頭左邊的由箭頭右邊的定義
把He gave me a book與上述規(guī)則進(jìn)行對(duì)照，看其中的語(yǔ)法范疇是否處于適當(dāng)?shù)奈恢?，如果你了解英語(yǔ)的話，你應(yīng)該可以確認(rèn)這是一個(gè)正確的句子。做科學(xué)研究都有一個(gè)過(guò)程從現(xiàn)象得出一般結(jié)論，再用實(shí)驗(yàn)驗(yàn)證這個(gè)一般性結(jié)論。有了這個(gè)語(yǔ)法規(guī)則我們可以造出很多這種英文句子（簡(jiǎn)單假設(shè)，英文語(yǔ)法遠(yuǎn)比這復(fù)雜）。如果我們要造一個(gè)句子表達(dá)我們自己的意思，利用這個(gè)規(guī)則，很容易。
根據(jù)上述規(guī)則，句子無(wú)需考慮上下文，就可以判斷正確性（符合<主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>的規(guī)則）。
其中，He，me等為終結(jié)符號(hào)，<主語(yǔ)>、<謂語(yǔ)>、<間接賓語(yǔ)>等為非終結(jié)符號(hào)。
這個(gè)文法最終要定義<句子>語(yǔ)法結(jié)構(gòu)，所以<句子>在這里稱(chēng)為開(kāi)始符號(hào)；<謂語(yǔ)>→<動(dòng)詞>這種書(shū)寫(xiě)形式稱(chēng)之為產(chǎn)生式。
歸納一下：上下文無(wú)關(guān)語(yǔ)法G包括四個(gè)部分：一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組產(chǎn)生式。
說(shuō)明一下：終結(jié)符號(hào)是組成語(yǔ)言不可再分的基本符號(hào)，在程序語(yǔ)言中就是保留字、標(biāo)識(shí)符、常數(shù)等；非終結(jié)符號(hào)是一個(gè)給定的語(yǔ)法概念，是一個(gè)類(lèi)（或集合）記號(hào)，而是不是某個(gè)個(gè)體記號(hào)；開(kāi)始符號(hào)是一個(gè)特殊的非終結(jié)符號(hào)，是語(yǔ)言中我們最終想得到的字符串（在程序語(yǔ)言中，我們最終感興趣的是“程序”這個(gè)語(yǔ)法范疇，其他的語(yǔ)法都是構(gòu)造“程序”的基石）;產(chǎn)生式（也稱(chēng)產(chǎn)生規(guī)則或者簡(jiǎn)稱(chēng)規(guī)則）是語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。
你想嘛，gave這個(gè)單詞，拆分為一個(gè)個(gè)字母，就不再是gave了，沒(méi)有什么特別的含義；而非終結(jié)符號(hào)就是諸如gave的動(dòng)詞的集合。
? 額，有個(gè)細(xì)節(jié)好像忽略了，產(chǎn)生式的形式：
A→α
箭頭左邊是一個(gè)非終結(jié)符，稱(chēng)之為產(chǎn)生式的左部，箭頭右邊稱(chēng)之為右部。
A是一個(gè)非終結(jié)符，α是由 非終結(jié)符號(hào)和終結(jié)符號(hào)的并集 的閉包 中的元素 組成的符號(hào)串
? 形式化的上下文無(wú)關(guān)文法定義：
一個(gè)四元數(shù)組G=(VN,VT,S,P)
VN:非空有限的非終結(jié)符集合
VT:非空有限的終結(jié)符集
S：開(kāi)始符號(hào)
P：產(chǎn)生式集合
其中，VN∩VT=?，S∈VN
P中產(chǎn)生式一般形式為A→α|β，其中A∈VN，α，β∈(VN∪VT)*
通常用大寫(xiě)字母表示非終結(jié)符，小寫(xiě)字母表示終結(jié)符，α、β、γ等代表由 終結(jié)符和非終結(jié)符號(hào)的并集的閉包?中的元素 組成的符號(hào)串。
例如:E→i|EAE A→+|*
是上下文無(wú)關(guān)語(yǔ)法，E、A是非終結(jié)符，E是開(kāi)始符，而i，+和*是終結(jié)符
2.用上下文無(wú)關(guān)語(yǔ)法定義一個(gè)語(yǔ)言
一個(gè)上下文無(wú)關(guān)語(yǔ)法如何定義一個(gè)語(yǔ)言呢，主要思想是從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對(duì)非終結(jié)符進(jìn)行替換和展開(kāi)。
例如：
算術(shù)表達(dá)式的定義可以寫(xiě)為：
E→i
E→E+E
E→E*E
E→(E)
E代表算術(shù)表達(dá)式，i代表變量。這四個(gè)產(chǎn)生式的后三個(gè)是遞歸的。
? 我們可以定義如下文法G
E→E+E|E*E|(E)|i
開(kāi)始符號(hào)為E，從E出發(fā)E=>（E）=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)
符號(hào)"=>"表示僅推導(dǎo)一步
我們定義αAβ=>αγβ為αAβ直接推導(dǎo)出αγβ，僅當(dāng)A→γ是一個(gè)產(chǎn)生式，且α，β∈(VN∪VT)*?。
如果a1=>a2=>a3=>...=>an，我們稱(chēng)這個(gè)序列是從a1到an的一個(gè)推導(dǎo)。若存在一個(gè)從a1到an的推導(dǎo)，則稱(chēng)之為a1可推導(dǎo)出an。用a1=>an表示從a1出發(fā)經(jīng)過(guò)零步或若干步，可推導(dǎo)出an。
?假設(shè)G是一個(gè)文法，S是它的開(kāi)始符號(hào)，如果S=>α則稱(chēng)α是一個(gè)句型。僅含終結(jié)符號(hào)的句型是句子。文法G所產(chǎn)生的句子全體是一個(gè)語(yǔ)言記為L(zhǎng)(G)。
L(G)={α|S+=>α&α∈VT*}
例如：文法G1：
S→bA
A→aA|a
從符號(hào)S出發(fā)我們可以推出，S=>bA=>ba
S=>bA=>baA=>baa
.
? ?.
.
S=>bA=>baA=>...=>ba...a
歸納得出所有以b開(kāi)頭后頭跟一個(gè)或者多個(gè)a的字符串L(G1)={ban|n>=1}
