文法：它描述語(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ù)奈恢玫袷玻绻懔私庥⒄Z(yǔ)的話贷岸，你應(yīng)該可以確認(rèn)這是一個(gè)正確的句子磷雇。做科學(xué)研究都有一個(gè)過程從現(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)饼煞，所以<句子>在這里稱為開始符號(hào)砖瞧；<謂語(yǔ)>→<動(dòng)詞>這種書寫形式稱之為產(chǎn)生式。
歸納一下：上下文無(wú)關(guān)語(yǔ)法G包括四個(gè)部分：一組終結(jié)符號(hào)荣堰，一組非終結(jié)符號(hào)，一個(gè)開始符號(hào)振坚，以及一組產(chǎn)生式屡拨。
說(shuō)明一下：終結(jié)符號(hào)是組成語(yǔ)言不可再分的基本符號(hào)褥实，在程序語(yǔ)言中就是保留字、標(biāo)識(shí)符哥艇、常數(shù)等貌踏；非終結(jié)符號(hào)是一個(gè)給定的語(yǔ)法概念窟勃，是一個(gè)類（或集合）記號(hào)秉氧，而是不是某個(gè)個(gè)體記號(hào)；開始符號(hào)是一個(gè)特殊的非終結(jié)符號(hào)亚斋，是語(yǔ)言中我們最終想得到的字符串（在程序語(yǔ)言中，我們最終感興趣的是“程序”這個(gè)語(yǔ)法范疇纸泡，其他的語(yǔ)法都是構(gòu)造“程序”的基石）;產(chǎn)生式（也稱產(chǎn)生規(guī)則或者簡(jiǎn)稱規(guī)則）是語(yǔ)法范疇的一種書寫規(guī)則女揭。
你想嘛栏饮，gave這個(gè)單詞抡爹，拆分為一個(gè)個(gè)字母冬竟，就不再是gave了泵殴，沒有什么特別的含義拼苍；而非終結(jié)符號(hào)就是諸如gave的動(dòng)詞的集合疮鲫。
? 額，有個(gè)細(xì)節(jié)好像忽略了妇多，產(chǎn)生式的形式：
A→α
箭頭左邊是一個(gè)非終結(jié)符者祖，稱之為產(chǎn)生式的左部绢彤，箭頭右邊稱之為右部。
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：開始符號(hào)
P：產(chǎn)生式集合
其中坟比，VN∩VT=?葛账，S∈VN
P中產(chǎn)生式一般形式為A→α|β籍琳，其中A∈VN，α喝峦，β∈(VN∪VT)*
通常用大寫字母表示非終結(jié)符谣蠢，小寫字母表示終結(jié)符眉踱，α、β谈喳、γ等代表由 終結(jié)符和非終結(jié)符號(hào)的并集的閉包?中的元素 組成的符號(hào)串婿禽。
例如:E→i|EAE A→+|*
是上下文無(wú)關(guān)語(yǔ)法扭倾，E挽绩、A是非終結(jié)符，E是開始符恢筝，而i，+和*是終結(jié)符
2.用上下文無(wú)關(guān)語(yǔ)法定義一個(gè)語(yǔ)言
一個(gè)上下文無(wú)關(guān)語(yǔ)法如何定義一個(gè)語(yǔ)言呢巨坊，主要思想是從文法的開始符號(hào)出發(fā)撬槽，反復(fù)連續(xù)使用產(chǎn)生式，對(duì)非終結(jié)符進(jìn)行替換和展開趾撵。
例如：
算術(shù)表達(dá)式的定義可以寫為：
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
開始符號(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，我們稱這個(gè)序列是從a1到an的一個(gè)推導(dǎo)言津。若存在一個(gè)從a1到an的推導(dǎo)怀吻，則稱之為a1可推導(dǎo)出an。用a1=>an表示從a1出發(fā)經(jīng)過零步或若干步渣窜，可推導(dǎo)出an访雪。
?假設(shè)G是一個(gè)文法，S是它的開始符號(hào)精置，如果S=>α則稱α是一個(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開頭后頭跟一個(gè)或者多個(gè)a的字符串L(G1)={ban|n>=1}
