一. 文法公式
文法定義公式如下:
G = (VT , VN , P , S)
-
VT: 終結(jié)符集合
終結(jié)符就是不可以再推導(dǎo)的字符。
也就是說對(duì)于一個(gè)字符a,它屬于終結(jié)符集合VT(a∈VT) ,a不可以再推導(dǎo)的字符欺殿，即不能用其他字符表示a苍糠。表現(xiàn)形式就是a不能單獨(dú)出現(xiàn)在產(chǎn)生式左邊钠龙。
-
VN: 非終結(jié)符集合
非終結(jié)符即可以繼續(xù)推導(dǎo)的字符威创。
-
P: 產(chǎn)生式集合
產(chǎn)生式就是推導(dǎo)公式榕订，表示這個(gè)文法的定義規(guī)則。
產(chǎn)生式形式α→β，其中α和β都是屬于文法符合串 (VN∪VT)* 姨伤。α稱為產(chǎn)生式的左部或者頭部哨坪；β稱為產(chǎn)生式的右部或者體。
文法符合串乍楚，即終結(jié)符集合和非終結(jié)符集合任一排列組合成的字符串当编。例如aAbbB, 其中 (a,b∈VT , A,B∈VN) 就是一個(gè)文法符合串。
-
S: 開始符號(hào)
即文法從這個(gè)符號(hào)
S利用產(chǎn)生集合P開始推導(dǎo)徒溪。S是一個(gè)非終結(jié)符忿偷，即 S∈VN。
一般情況下臊泌，第一個(gè)產(chǎn)生式左部符號(hào)就是開始符號(hào)鲤桥。
二. 文法分類
Chomsky 文法分類將文法分為四種，0型文法(PSG)缺虐、1型文法(CSG)芜壁、2型文法(CFG)和3型文法(RG)。
其實(shí)不同的文法就是對(duì)產(chǎn)生式進(jìn)行逐層限制形成的高氮。
2.1 0型文法(PSG)
又被稱為無限制文法(Unrestricted Grammar), 或者短語結(jié)構(gòu)文法（Phrase Structure Grammar）
定義: 對(duì)于產(chǎn)生式 α→β ，α 至少包含一個(gè)非終結(jié)符顷牌。
即 α,β∈(VN∪VT)* ,
α和β都是文法符合串剪芍，并且α文法符合串中必須包含一個(gè)非終結(jié)符。
例如: aA→0bB; A0→11bB; 其中 (a,0,b∈VT),(A,B∈VN)窟蓝。
為什么要叫無限制文法罪裹，明明它要求產(chǎn)生式的左部必須包含一個(gè)非終結(jié)符。
因?yàn)槲覀冎澜K結(jié)符是不能再推導(dǎo)出其他字符的运挫，所以產(chǎn)生式的左部不能全是終結(jié)符組成的文法符合串(VT*)状共，這個(gè)是不允許的，所以產(chǎn)生式的左部必須包含一個(gè)非終結(jié)符谁帕。
2.2 1型文法(CSG)
又被稱為上下文有關(guān)文法(Context-Sensitive Grammar)
定義：對(duì)于產(chǎn)生式 α→β , |α| <= |β|, 僅僅 S→ε 除外
|α|表示α這個(gè)文法符合串中字符個(gè)數(shù)峡继。例如aAb這個(gè)字符個(gè)數(shù)就是3個(gè)。
也就是說1型文法要求產(chǎn)生式右部文法符合串
β的字符個(gè)數(shù)要不小于產(chǎn)生式左部文法符合串α的字符個(gè)數(shù)匈挖；但是空產(chǎn)生式(S→ε) 除外碾牌。
ε表示空串，即文法符號(hào)串中沒有任何字符元素(|ε|=0)
為什么叫做上下文有關(guān)文法儡循？
因?yàn)閷?duì)于任何一個(gè)非終結(jié)符
A(即 A∈VN)舶吗，想要將它替換成其他文法符號(hào)串，必須要有對(duì)應(yīng)形式的產(chǎn)生式择膝。
一般情況下誓琼，這種產(chǎn)生式的形式為 α1Aα2→α1βα2
其中 α1,α2,β∈(VN∪VT)*, β≠ε，A∈VN。
所以對(duì)于非終結(jié)符A, 出現(xiàn)在α1和α2上下文中腹侣，就可以替換成文法符號(hào)串β呵扛。
例如: 對(duì)于這個(gè)產(chǎn)生式
1A2→112342，可以將非終結(jié)符A替換成文法符號(hào)串1234筐带。
2.3 2型文法(CFG)
又被稱為上下文無關(guān)文法(Context-Free Grammar)
定義：對(duì)任一產(chǎn)生式 α→β今穿，都有 α∈VN，β∈(VN∪VT)*
對(duì)產(chǎn)生式左部進(jìn)行了限制伦籍，
α就是非終結(jié)符集合VN中一個(gè)字符元素蓝晒。
當(dāng)然一個(gè)非終結(jié)符也是一個(gè)特殊的文法符號(hào)串，串中只有一個(gè)字符帖鸦，且是一個(gè)非終結(jié)符芝薇。
β∈(VN∪VT)*,β表示一個(gè)文法符號(hào)串，其中空串 ε 也是一個(gè)特殊文法符號(hào)串作儿。
所以對(duì)于2型文法也有空產(chǎn)生式 (S→ε)
為什么叫上下文無關(guān)文法洛二？
因?yàn)閷?duì)于任何一個(gè)非終結(jié)符
A(即 A∈VN)，可以直接根據(jù)產(chǎn)生式替換成一個(gè)文法符號(hào)串攻锰，而不需要特殊的上下文環(huán)境晾嘶。
2.4 3型文法(RG)
又被稱為正則文法（Regular Grammar，RG）娶吞，分為右線性（Right Linear）文法和左線性（Left Linear）文法垒迂。
定義: 對(duì)任一產(chǎn)生式 α→β，都有 α∈VN妒蛇，β最多兩個(gè)字符元素机断，如果有二個(gè)字符必須是（終結(jié)符+非終結(jié)符）的格式，如果是一個(gè)字符绣夺，那么必須是終結(jié)符吏奸。
產(chǎn)生的左部只能是一個(gè)非終結(jié)符元素。
產(chǎn)生的右部最多兩個(gè)字符元素 (即bB,Bb其中 b∈VT, B∈VN)陶耍，或者只有一個(gè)元素,且必須是終結(jié)符(即b, b∈VT)奋蔚。
根據(jù)產(chǎn)生式右部非終結(jié)符位置不同，分為右線性文法和左線性文法物臂。
- 右線性文法:
A→bB或者A→b - 左線性文法:
A→Bb或者A→b
注: 正則文法產(chǎn)生式集合中每個(gè)產(chǎn)生式有相同的線性旺拉，即所有產(chǎn)生式要么都是右線性文法，要么都是左線性文法棵磷。
2.5 小結(jié)
可以看出蛾狗，不同文法就是對(duì)產(chǎn)生式進(jìn)行逐層的限制，所以各個(gè)文法是包含關(guān)系仪媒，即0型文法包含1型文法沉桌；1型文法又包含2型文法谢鹊；2型文法最后包含3型文法。
