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

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

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

其實(shí)這個(gè)特別簡(jiǎn)單，我們來看個(gè)例子就懂了：

S->Ap

S->Bq

A->a

A->cA

B->b

B->dB

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

文法的類型：

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

0型文法：

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

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

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

A->ab。

1型文法：

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

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

A->B，A->Bba  都符合要求，那么反過來，Bba->A就不符合要求了，因?yàn)樽筮吺?，右邊是1�？磮D：

2型文法：

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

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

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

3型文法:

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

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

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

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

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

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

我們來做一個(gè)題目:

實(shí)戰(zhàn)：

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

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

3、我們?cè)賮砜词欠穹?型文法：1型文法規(guī)定從小推到大。也符合。

4、我們?cè)賮砜词欠穹?型文法：2型文法規(guī)定左邊必須是非終結(jié)符，也滿足。

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

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

正規(guī)式：

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

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

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

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

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

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

我們接下來來看看有限自動(dòng)機(jī)：

NFA與DFA的定義：

DFA:確定的有限自動(dòng)機(jī)

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

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

E就是一個(gè)輸入字符；

f是一個(gè)SxE至S的映射；

So：初態(tài)；

Z:終態(tài)。

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

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

我們對(duì)照上面式子就能看的出來各個(gè)元素代表的意義，我們?cè)賮矸治鲆槐椋?/span>

{S,A,B,C,f}是一個(gè)狀態(tài)集合；{1,0}是輸入字符；F是一個(gè)映射，S是初態(tài)，{f}是一個(gè)終態(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ù)這個(gè)流程，就有了這么一張圖：

然后再看看NFA的定義：

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

編譯原理還有這兩個(gè)的轉(zhuǎn)換，我們?cè)诤竺娴牟┛椭新晟瓢蓗

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

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