本文關(guān)鍵詞：編譯原理，由筆耕文化傳播整理發(fā)布。

最近對數(shù)據(jù)結(jié)構(gòu)的研究又有了進展，挺好玩的，總結(jié)這些內(nèi)容的同時，希望也能幫助到大家，這樣的話，達到雙贏，這才是寫博客的目的，接下來我們來輕松學(xué)習(xí)編譯原理，不要被這些紙老虎嚇著了。我們一步步來看到底是怎么個情況，該怎么學(xué)習(xí)呢。。。

其實這部分內(nèi)容在我上課的時候，是特別頭疼的，不知道老師講的什么，但是經(jīng)過自己分析琢磨，感覺還好，能分析的差不多，所以就跟大家分享一下：

其實這個特別簡單，我們來看個例子就懂了：

S->Ap

S->Bq

A->a

A->cA

B->b

B->dB

這其中我們看到的，S為開始符，S,A,B為非終結(jié)符，在左邊，可以推導(dǎo)出一個式子來。而p,q,a,b,c,d為終結(jié)符。其實咱們一點都不用記，應(yīng)該太簡單了，你這樣想，S（start）也是一個非終結(jié)符，然后大寫的為非終結(jié)符，小寫的為終結(jié)符，那么這個概念就一點難度都沒有了。

文法的類型：

主要是要求咱們判斷這幾個文法的類型。

0型文法：

0型文法是這幾個文法中，限制最少的一個，所以見到的至少是0型文法。G=(Vn,Vt,P,S),其中我們得知道，Vn是非終結(jié)符的集合，Vt是終結(jié)符的集合，P是推導(dǎo)式的一個集合，S是開始符。我們從圖來慢慢分析：

我們從圖中來闡述一下這些概念，S,A,B為Vn，而p,q,a,b,c,d,為Vt,S為開始符。整個集合為P。

我們每個式子里邊的左邊必須要包含這些元素或者元素組合中的至少一個非終結(jié)符，右邊可以是這些元素的任意組合。我想這樣可能好理解一些，這樣我們什么公式都不需要記住了，左邊有非終結(jié)符，右邊有終結(jié)符，就OK。如：

A->ab。

1型文法：

也叫上下文有關(guān)文法；這個1型文法理解起來也沒有多大的難度；在0型文法的基礎(chǔ)上，我們再添加一點點的限制就行了，我們看添加了什么限制：

右邊的長度>=左邊的長度，這個長度咱們可以這么來理解，就是這些字符的數(shù)量，小的推出大的或者相等的。這樣就沒有難度了。比如：

A->B，A->Bba  都符合要求，那么反過來，Bba->A就不符合要求了，因為左邊是3，右邊是1�？磮D：

2型文法：

叫上下文無關(guān)文法。2型文法在1型文法的基礎(chǔ)上，我們規(guī)定2型文法中，左邊必須是非終結(jié)符，然而一個終結(jié)符一個非終結(jié)符的組合不是一個非終結(jié)符，如Ab不是一個非終結(jié)符，但是兩個非終結(jié)符的組合就是一個非終結(jié)符了，如AB就是行了。

那么應(yīng)該是這樣的：

aB->abc就不符合要求，但是AB->abc就符合要求了。

3型文法:

也叫正規(guī)文法，對應(yīng)有限狀態(tài)自動機。在2型文法的基礎(chǔ)上再加限制。要求更加高。

要么一個非終結(jié)符推出一個終結(jié)符，要么一個非終結(jié)符推出一個終結(jié)符并且?guī)б粋�非終結(jié)符。同時說這是一個文法當(dāng)中的。那么這種屬于3型文法，

這右線性與左線性是相互獨立的，，我們來看例子。

你不能一會寫一下右線性一會寫一下左線性，這樣拼湊在一起就構(gòu)成不了3型文法了。要寫就只寫右線性，或者只寫左線性，不能一塊來，分開來就對了。

那么這幾個文法的關(guān)系應(yīng)該是：

接下來我們來實戰(zhàn)一下，鍛煉一下我們的基礎(chǔ)。

我們來做一個題目:

實戰(zhàn)：

1、我們分開來寫，應(yīng)該是：A->e   A->aB   B->Ab  B->a

2、我們先來判斷是否符合0型文法：0型文法規(guī)定左邊必須有非終結(jié)符，那么這些都是符合的。

3、我們再來看是否符合1型文法：1型文法規(guī)定從小推到大。也符合。

4、我們再來看是否符合2型文法：2型文法規(guī)定左邊必須是非終結(jié)符，也滿足。

5、我們繼續(xù)看是否符合3型文法：規(guī)定只能符合右線性或者左線性，那么前面一個應(yīng)該是符合右線性的，后面一個是符合左線性的。所以綜合起來就不符合3型文法了。

得出結(jié)論：那么這個題目屬于2型文法。

正規(guī)式：

正規(guī)式與正規(guī)文法之間的轉(zhuǎn)換：

我們要掌握的三個規(guī)則，咱們看一張表就能明確了：

我們來分析一下這些規(guī)則；

規(guī)則1：文法產(chǎn)生式（A—>xB,B->y ），正規(guī)式（A=xy）。對于這個文法產(chǎn)生式轉(zhuǎn)換成正規(guī)式，我覺得就是一個代入的過程，把B=y代入A->xB即可得出正規(guī)式。反過來，正規(guī)式轉(zhuǎn)換成文法產(chǎn)生式，則添加一個變量就搞定了。

規(guī)則2：這個式子里邊有一個遞歸，A—>xA，這樣就產(chǎn)生遞歸了，應(yīng)該是這樣的：A->xA,A->xA……這樣的無窮下去，最終A還是要等于y的，所以x就有無窮多個，從0個到無窮多個，所以這個推導(dǎo)出來的正規(guī)式就是A=x*y，表明x有無窮多個。

規(guī)則3：A—>x,A->y。那么A=x|y。這個就很簡單了。A退出x或者y。

我們接下來來看看有限自動機：

NFA與DFA的定義：

DFA:確定的有限自動機

M=(S,E,f,So,Z)，我們來分析分析這個五元組：

S是一個有限狀態(tài)集合；

E就是一個輸入字符；

f是一個SxE至S的映射；

So：初態(tài)；

Z:終態(tài)。

我們來看看具體的例子，光是理論和概念的東西最不好理解，來看看例子吧：

DFA=({S,A,B,C,f},{1,0},F,S,{f}),

我們對照上面式子就能看的出來各個元素代表的意義，我們再來分析一遍：

{S,A,B,C,f}是一個狀態(tài)集合；{1,0}是輸入字符；F是一個映射，S是初態(tài)，{f}是一個終態(tài)。

那么我們接下來看這些映射：

K（S,0）=B,K(S,1)=A,K(A,0)=f,K(A,1)=C,K(B,0)=C,K(B,1)=f,k(C,1)=f;

我們根據(jù)這個流程，就有了這么一張圖：

然后再看看NFA的定義：

M=(S,E,f,So,Z) 這個五元組跟DFA的定義一樣。

編譯原理還有這兩個的轉(zhuǎn)換，我們在后面的博客中慢慢完善吧~

編譯原理這部分咱們先講這么多，如講的有不對的地方，還請您指出，將感激不盡~

  本文關(guān)鍵詞：編譯原理，由筆耕文化傳播整理發(fā)布。