正規(guī)式到 CFG 的轉(zhuǎn)換：

1. 構(gòu)造正規(guī)式的 NFA；

2. 若 0 為初態(tài)，則 A0 為開始符號(hào)；

3. 對(duì)于 move(i, a) = j，引入產(chǎn)生式 Ai → aAj；

   【從 i 狀態(tài)經(jīng)過標(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)過的邊），這樣一來，我們就用這種方法將 NFA 中的狀態(tài)以及狀態(tài)轉(zhuǎn)移關(guān)系變成了 CFG 中的產(chǎn)生式。

4. 對(duì)于 move(i, ε) = j，引入產(chǎn)生式 Ai → Aj；

   為空轉(zhuǎn)移生成與之對(duì)應(yīng)的產(chǎn)生式。

5. 若 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。

如果沒有最后的 ε，那么無論怎么推導(dǎo)，在推導(dǎo)的下一步總會(huì)引入一個(gè)新的非終結(jié)符，永遠(yuǎn)得不到一個(gè)我們想要的句子。

通過這種方式轉(zhuǎn)化出來的 CFG 也是一種“正規(guī)文法”（后續(xù)會(huì)講到）

另外，我們也可以使用經(jīng)驗(yàn)（腦補(bǔ)）的方法來將正規(guī)式轉(zhuǎn)化成 CFG。對(duì)于上面的正規(guī)式 r，我們不難（？）寫出：

A → HT
H → ε | Ha | Hb
T → abb

過程：

1. 通過觀察，我們發(fā)現(xiàn)正規(guī)式 (a|b)*abb 是可以分為明顯的兩部分的，即a或b的星閉包連接上abb。第一部分就是星閉包，第二部分就是abb。因此，我們?cè)跇?gòu)造 CFG 的時(shí)候，也就可以一上來就把開始符號(hào)拆成兩部分，即上面第一行的 H 和 T
2. 我們用前面的非終結(jié)符 H 來生成正規(guī)式中前半部分的星閉包。a或b的星閉包，就是由a或b構(gòu)成的長度>=0的一個(gè)ab串，于是我們就可以通過 H 本身不限次引入 a、b 來構(gòu)造星閉包，具體就是第二行的產(chǎn)生式。產(chǎn)生式 H->ε 的作用有二，一是為了滿足只有空串的情況，因?yàn)樾情]包可以為空；二是用來結(jié)束 H 的產(chǎn)生式，只有有了 ε，我們才能夠結(jié)束對(duì) H 的構(gòu)造，否則這個(gè)推導(dǎo)會(huì)一路無限遞歸下去。。。
3. T 就是給 abb 準(zhǔn)備的

萬一，如果 H 是正閉包而不是星閉包，那么就可以改成：H→a|b|Ha|Hb

正規(guī)式和 CFG 的關(guān)系

我們都知道：如果 NFA 能夠接受一個(gè)串，那就說明在這個(gè) NFA 內(nèi)部一定存在一條從初態(tài)到終態(tài)的路徑，路徑上的鏈接就是這個(gè)串本身。

而，從上面的轉(zhuǎn)化規(guī)則和例子，我們可以確定：這樣的一個(gè)串一定對(duì)應(yīng)CFG里面的一個(gè)推導(dǎo)。

也就是說，NFA 中的一個(gè)路徑一定對(duì)應(yīng)著 CFG 中的一個(gè)推導(dǎo)。反過來講，CFG 中任意一個(gè)推導(dǎo)也都對(duì)應(yīng)著 NFA 中的一個(gè)路徑。

因此，正規(guī)式與 CFG 之間是等價(jià)的??！

任意一個(gè)正規(guī)式所描述的語言，都可用 CFG 來描述。也就是說對(duì)任意一個(gè)正規(guī)式，我們都可以為他構(gòu)造出來其相應(yīng)的、和它描述的語言相同的集合的 CFG。

但反過來，就不一定了——并不是所有用 CFG 描述的語言都可以用正規(guī)式來描述

好的，我已經(jīng)很震撼了：既然凡是正規(guī)式能描述的，都能用CFG描述，反之則不行。這就說明 CFG 的語言描述能力更強(qiáng)。

可，為什么還用正規(guī)式，而非 CFG 來描述詞法呢？？？

為毛不用 CFG 描述詞法規(guī)則

原因很簡潔：對(duì)人好，對(duì)機(jī)器也好。

對(duì)人好：正規(guī)式更直觀簡單，人容易理解。而正規(guī)式描述詞法恰巧已經(jīng)夠用了（詞法無非標(biāo)識(shí)符、關(guān)鍵字、字面量之類，這些都是線性結(jié)構(gòu)，使用正規(guī)式就能充分描述）；

對(duì)機(jī)器好：DFA 構(gòu)造起來比用于 CFG 分析的下推自動(dòng)機(jī)簡單，效率更高。且使用兩種不同方式來表示詞法和語法，便于對(duì)兩者進(jìn)行區(qū)分，便于編譯器前端的模塊劃分。

貫穿詞法、語法分析始終的思想

1. 語言的描述和識(shí)別，是表示一個(gè)語言的兩個(gè)側(cè)面，二者缺一不可；
2. 一般而言，正規(guī)式適用于描述線性結(jié)構(gòu)（標(biāo)識(shí)符、關(guān)鍵字、注釋等）；
3. CFG 適用于描述具有嵌套（層次）性質(zhì)的非線性結(jié)構(gòu)，比如不同結(jié)構(gòu)的句子 if-then-else、while-do 等；
4. 用正規(guī)式和 CFG 描述的語言，對(duì)應(yīng)的識(shí)別方法（自動(dòng)機(jī)）不同。

上下文有關(guān)文法 CSG

CFG 很棒，但 CFG 文法本身，無法描述上下文有關(guān)的結(jié)構(gòu)。

不能用 CFG 描述的語言：

上述的 L1、L2、L3 均是上下文有關(guān)的。

與上述 CSL 類似的 CFL

文法、語言與自動(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è)的短，也就是說這種語言不會(huì)越推越短，一定是越推越長的（畢竟總是要把產(chǎn)生式往產(chǎn)生式里面代入，如果被代入的東西變長了，那么一定就會(huì)隨著推導(dǎo)的進(jìn)行整個(gè)串都越來越長），而且可以一次性換掉帶有終結(jié)符的非終結(jié)符序列。

2型文法：

在 0 型文法的基礎(chǔ)上，要求：G 的任何產(chǎn)生式都要形如 A→β，有 A∈N，β∈(N∪T)* 。

這其實(shí)就是在說，產(chǎn)生式左側(cè)必須是一個(gè)單獨(dú)的非終結(jié)符，右側(cè)還是和原來一樣隨便即可。

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”之間三選一。意思是說，一個(gè)串如果想要填字母就只能往一邊續(xù)。如果用 A → aB，那就是向右側(cè)延伸，越續(xù)越長。選 A→Ba 那就是向左側(cè)延伸，越續(xù)越長。

image.png

• 任何一個(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é)符的左邊是什么、右邊是什么，也就是說我們要考慮這個(gè)非終結(jié)符的（已經(jīng)存在了的）上下文了，因此，叫做上下文有關(guān)。

而 CFG 的非終結(jié)符完全可以在任何地方隨便展開，只需要考慮他自己單獨(dú)一個(gè)非終結(jié)符就行了，所以叫上下文無關(guān)！