對(duì)語(yǔ)言進(jìn)行形式化描述的規(guī)則叫文法砾莱。
詞法規(guī)則瑞筐、語(yǔ)法規(guī)則都以形式化的方法對(duì)語(yǔ)言進(jìn)行描述，這樣的規(guī)則就叫文法腊瑟。在使用 lex 的時(shí)候聚假，我們就可以使用文法來(lái)簡(jiǎn)單地定義和修改語(yǔ)言。
前幾篇筆記中我們比較細(xì)致地研究了正規(guī)式闰非，當(dāng)時(shí)我們用正規(guī)式來(lái)描述詞法規(guī)則膘格，然后根據(jù)正規(guī)式構(gòu)造可以識(shí)別由該正規(guī)式表示的語(yǔ)言的自動(dòng)機(jī)。
但其實(shí)财松，CFG 也是可以描述詞法的瘪贱。（但為什么不這么做呢？）
正規(guī)式辆毡，和 CFG
正規(guī)式所描述的語(yǔ)言結(jié)構(gòu)都可以用 CFG 描述菜秦，反之不一定。
正規(guī)式和 CFG 是有關(guān)系的舶掖！NFA 是可以轉(zhuǎn)化成 CFG 的Ｇ蜃颉！一個(gè) NFA 的狀態(tài)和狀態(tài)轉(zhuǎn)移關(guān)系就對(duì)應(yīng)一個(gè)產(chǎn)生式ＵＨ痢主慰！驚不驚喜？意不意外期犬？河哑？避诽？至于為啥可以咱們暫且不論龟虎，先從這里往下看，后面時(shí)機(jī)成熟沙庐，自會(huì)解釋鲤妥。
正規(guī)式到 CFG 的轉(zhuǎn)換：
構(gòu)造正規(guī)式的 NFA；
若 0 為初態(tài)拱雏，則 A0 為開始符號(hào)棉安；
-
對(duì)于 move(i, a) = j，引入產(chǎn)生式 Ai → aAj铸抑；
【從 i 狀態(tài)經(jīng)過(guò)標(biāo)記為 a 的邊轉(zhuǎn)移到 j 狀態(tài)贡耽。對(duì)于這樣的狀態(tài)轉(zhuǎn)移關(guān)系，我們可以為其生成對(duì)應(yīng)的產(chǎn)生式 Ai → aAj 】
NFA 中的每個(gè)邊，即每個(gè)狀態(tài)轉(zhuǎn)移都會(huì)生成一個(gè)對(duì)應(yīng)的產(chǎn)生式蒲赂。我們?cè)谶@里引入 Ai → aAj（這里的 a 是指經(jīng)過(guò)的邊）阱冶，這樣一來(lái)，我們就用這種方法將 NFA 中的狀態(tài)以及狀態(tài)轉(zhuǎn)移關(guān)系變成了 CFG 中的產(chǎn)生式滥嘴。
-
對(duì)于 move(i, ε) = j木蹬，引入產(chǎn)生式 Ai → Aj；
為空轉(zhuǎn)移生成與之對(duì)應(yīng)的產(chǎn)生式若皱。
若 i 是終態(tài)镊叁，則引入產(chǎn)生式 Ai → ε（終態(tài)，對(duì)應(yīng)的是空產(chǎn)生式）走触。
NFA 中有狀態(tài)和狀態(tài)間的轉(zhuǎn)移晦譬，我們就可以把這些變成一個(gè) CFG
【例】以正規(guī)式 r = ( a|b )*abb 的 NFA 構(gòu)造 CFG。
如果沒(méi)有最后的 ε互广，那么無(wú)論怎么推導(dǎo)蛔添，在推導(dǎo)的下一步總會(huì)引入一個(gè)新的非終結(jié)符，永遠(yuǎn)得不到一個(gè)我們想要的句子兜辞。
通過(guò)這種方式轉(zhuǎn)化出來(lái)的 CFG 也是一種“正規(guī)文法”（后續(xù)會(huì)講到）
另外迎瞧，我們也可以使用經(jīng)驗(yàn)（腦補(bǔ)）的方法來(lái)將正規(guī)式轉(zhuǎn)化成 CFG。對(duì)于上面的正規(guī)式 r逸吵，我們不難（凶硅？）寫出：
A → HT
H → ε | Ha | Hb
T → abb
過(guò)程：
- 通過(guò)觀察，我們發(fā)現(xiàn)正規(guī)式 (a|b)*abb 是可以分為明顯的兩部分的扫皱，即a或b的星閉包連接上abb足绅。第一部分就是星閉包，第二部分就是abb韩脑。因此氢妈，我們?cè)跇?gòu)造 CFG 的時(shí)候，也就可以一上來(lái)就把開始符號(hào)拆成兩部分段多，即上面第一行的 H 和 T
- 我們用前面的非終結(jié)符 H 來(lái)生成正規(guī)式中前半部分的星閉包首量。a或b的星閉包，就是由a或b構(gòu)成的長(zhǎng)度>=0的一個(gè)ab串进苍，于是我們就可以通過(guò) H 本身不限次引入 a加缘、b 來(lái)構(gòu)造星閉包，具體就是第二行的產(chǎn)生式觉啊。產(chǎn)生式 H->ε 的作用有二拣宏，一是為了滿足只有空串的情況，因?yàn)樾情]包可以為空杠人；二是用來(lái)結(jié)束 H 的產(chǎn)生式勋乾，只有有了 ε宋下，我們才能夠結(jié)束對(duì) H 的構(gòu)造，否則這個(gè)推導(dǎo)會(huì)一路無(wú)限遞歸下去辑莫。杨凑。。
- T 就是給 abb 準(zhǔn)備的
萬(wàn)一摆昧，如果 H 是正閉包而不是星閉包撩满，那么就可以改成：H→a|b|Ha|Hb
正規(guī)式和 CFG 的關(guān)系
我們都知道：如果 NFA 能夠接受一個(gè)串，那就說(shuō)明在這個(gè) NFA 內(nèi)部一定存在一條從初態(tài)到終態(tài)的路徑绅你，路徑上的鏈接就是這個(gè)串本身伺帘。
而，從上面的轉(zhuǎn)化規(guī)則和例子忌锯，我們可以確定：這樣的一個(gè)串一定對(duì)應(yīng)CFG里面的一個(gè)推導(dǎo)伪嫁。
也就是說(shuō)，NFA 中的一個(gè)路徑一定對(duì)應(yīng)著 CFG 中的一個(gè)推導(dǎo)偶垮。反過(guò)來(lái)講张咳，CFG 中任意一個(gè)推導(dǎo)也都對(duì)應(yīng)著 NFA 中的一個(gè)路徑。
因此似舵，正規(guī)式與 CFG 之間是等價(jià)的＝呕！
任意一個(gè)正規(guī)式所描述的語(yǔ)言砚哗，都可用 CFG 來(lái)描述龙助。也就是說(shuō)對(duì)任意一個(gè)正規(guī)式，我們都可以為他構(gòu)造出來(lái)其相應(yīng)的蛛芥、和它描述的語(yǔ)言相同的集合的 CFG提鸟。
但反過(guò)來(lái)，就不一定了——并不是所有用 CFG 描述的語(yǔ)言都可以用正規(guī)式來(lái)描述
好的仅淑，我已經(jīng)很震撼了：既然凡是正規(guī)式能描述的称勋，都能用CFG描述，反之則不行涯竟。這就說(shuō)明 CFG 的語(yǔ)言描述能力更強(qiáng)汰聋。
可对蒲，為什么還用正規(guī)式被因，而非 CFG 來(lái)描述詞法呢择卦？蝇庭？醉鳖？
為毛不用 CFG 描述詞法規(guī)則
原因很簡(jiǎn)潔：對(duì)人好，對(duì)機(jī)器也好哮内。
對(duì)人好：正規(guī)式更直觀簡(jiǎn)單盗棵，人容易理解壮韭。而正規(guī)式描述詞法恰巧已經(jīng)夠用了（詞法無(wú)非標(biāo)識(shí)符、關(guān)鍵字纹因、字面量之類喷屋，這些都是線性結(jié)構(gòu)，使用正規(guī)式就能充分描述）瞭恰；
對(duì)機(jī)器好：DFA 構(gòu)造起來(lái)比用于 CFG 分析的下推自動(dòng)機(jī)簡(jiǎn)單屯曹，效率更高。且使用兩種不同方式來(lái)表示詞法和語(yǔ)法惊畏，便于對(duì)兩者進(jìn)行區(qū)分恶耽，便于編譯器前端的模塊劃分。
貫穿詞法颜启、語(yǔ)法分析始終的思想
- 語(yǔ)言的描述和識(shí)別偷俭，是表示一個(gè)語(yǔ)言的兩個(gè)側(cè)面，二者缺一不可缰盏；
- 一般而言涌萤，正規(guī)式適用于描述線性結(jié)構(gòu)（標(biāo)識(shí)符、關(guān)鍵字口猜、注釋等）负溪；
- CFG 適用于描述具有嵌套（層次）性質(zhì)的非線性結(jié)構(gòu)，比如不同結(jié)構(gòu)的句子 if-then-else济炎、while-do 等笙以；
- 用正規(guī)式和 CFG 描述的語(yǔ)言，對(duì)應(yīng)的識(shí)別方法（自動(dòng)機(jī)）不同冻辩。
上下文有關(guān)文法 CSG
CFG 很棒猖腕，但 CFG 文法本身，無(wú)法描述上下文有關(guān)的結(jié)構(gòu)恨闪。
不能用 CFG 描述的語(yǔ)言：
上述的 L1倘感、L2、L3 均是上下文有關(guān)的咙咽。
與上述 CSL 類似的 CFL
文法老玛、語(yǔ)言與自動(dòng)機(jī)
0型文法：
若文法 G=(N, T, P, S) 的每個(gè)產(chǎn)生式 α→β 中，均有 α∈(N∪T)钧敞，且至少有一個(gè)非終結(jié)符蜡豹，β∈(N∪T) , 則稱 0 型文法。
產(chǎn)生式兩側(cè)的表達(dá)式需要含終結(jié)符溉苛，且是 N镜廉、T 元素組成的串。
1型文法：
在 0 型文法的基礎(chǔ)上愚战，要求：對(duì) G 的任何產(chǎn)生式 α→β（S → ε 除外）娇唯，滿足|α|≤|β|齐遵。
其實(shí)就是在 0 型的要求之上，要求產(chǎn)生式左側(cè)表達(dá)式必須比右側(cè)的短塔插，也就是說(shuō)這種語(yǔ)言不會(huì)越推越短梗摇，一定是越推越長(zhǎng)的（畢竟總是要把產(chǎn)生式往產(chǎn)生式里面代入，如果被代入的東西變長(zhǎng)了想许，那么一定就會(huì)隨著推導(dǎo)的進(jìn)行整個(gè)串都越來(lái)越長(zhǎng)）伶授，而且可以一次性換掉帶有終結(jié)符的非終結(jié)符序列。
2型文法：
在 0 型文法的基礎(chǔ)上流纹，要求：G 的任何產(chǎn)生式都要形如 A→β谎砾，有 A∈N，β∈(N∪T)* 捧颅。
這其實(shí)就是在說(shuō)景图，產(chǎn)生式左側(cè)必須是一個(gè)單獨(dú)的非終結(jié)符，右側(cè)還是和原來(lái)一樣隨便即可碉哑。
3型文法：
在 0 型文法的基礎(chǔ)上挚币，要求：G 的任何產(chǎn)生式都要形如【 A→ a 或 A → aB （或 A→Ba）】，其中A扣典、B∈N妆毕，a∈T
注意啊，這里的【 A→ a 或 A → aB （或 A→Ba）】是指在 “A → a” 或 “ A → aB （或 A→Ba）”這倆里面二選一贮尖，而不是“A→ a”笛粘、“A → aB”、“A→Ba”之間三選一湿硝。意思是說(shuō)薪前，一個(gè)串如果想要填字母就只能往一邊續(xù)。如果用 A → aB关斜，那就是向右側(cè)延伸示括，越續(xù)越長(zhǎng)。選 A→Ba 那就是向左側(cè)延伸痢畜，越續(xù)越長(zhǎng)垛膝。
任何一個(gè)1型文法，都是一個(gè)0型文法
任何一個(gè)2型文法丁稀，都是一個(gè)1型文法吼拥，都是一個(gè)0型文法
任何一個(gè)3型文法，都是一個(gè)2型文法线衫，都是一個(gè)1型文法凿可，都是一個(gè)0型文法。
所有3型文法的集合桶雀，是2型文法集合的子集
2型文法的集合矿酵，是1型文法集合的子集
1型文法的集合唬复，是0型文法集合的子集
為什么矗积， CSG 叫 CSG全肮？
CFG，左邊只有一個(gè)非終結(jié)符棘捣。
CSG 因?yàn)樽筮吙梢杂薪K結(jié)符（即辜腺，可以是一個(gè)文法符號(hào)序列），所以在對(duì)非終結(jié)符進(jìn)行展開時(shí)乍恐，我們需要考慮這個(gè)非終結(jié)符的左邊是什么评疗、右邊是什么，也就是說(shuō)我們要考慮這個(gè)非終結(jié)符的（已經(jīng)存在了的）上下文了茵烈，因此百匆，叫做上下文有關(guān)。
而 CFG 的非終結(jié)符完全可以在任何地方隨便展開呜投，只需要考慮他自己?jiǎn)为?dú)一個(gè)非終結(jié)符就行了加匈，所以叫上下文無(wú)關(guān)！
