深入淺出說(shuō)編譯原理(一)

昵稱(chēng)10504424 2013-03-13

展開(kāi)全文

個(gè)人認(rèn)為編譯原理對(duì)于一個(gè)程序員來(lái)說(shuō)很重要,，可能你認(rèn)為編程的時(shí)候用的都是C++、C#,、Java等高級(jí)語(yǔ)言,，至于編譯原理懂與不懂并無(wú)大礙。其實(shí)不然,，所謂萬(wàn)變不離其宗,，所有高級(jí)語(yǔ)言的誕生都是基于最根本的編譯原理的。搞懂了編譯原理,，對(duì)于一個(gè)程序員的能力提升有著很大的幫助,。因?yàn)樗鼤?huì)讓你對(duì)編程有更加深刻的理解，有助于你寫(xiě)出質(zhì)量更高的代碼,。好廢話(huà)不多說(shuō),，切入正題！

本文主要說(shuō)一下編譯原理里的文法,、正規(guī)式,、有窮自動(dòng)機(jī)和語(yǔ)法推導(dǎo)樹(shù)。

文法

文法就是計(jì)算機(jī)語(yǔ)言的一個(gè)嚴(yán)格的規(guī)范,，有點(diǎn)類(lèi)似人類(lèi)語(yǔ)言的語(yǔ)法,。就像形容詞修飾名詞，副詞修飾形容詞跟動(dòng)詞類(lèi)似,，只不過(guò)計(jì)算機(jī)的文法的標(biāo)準(zhǔn)和規(guī)范更加的嚴(yán)格而已,。

文法的表達(dá)式：G=(Vn,Vt,P,S) Vn是非終結(jié)符的集合，Vt是終結(jié)符的集合,，P是推導(dǎo)式的一個(gè)集合,，S是開(kāi)始符。

文法中有三種符號(hào)和四種文法類(lèi)型：

三種符號(hào)為：開(kāi)始符——S,；非終結(jié)符——A,、B、C,、AB等,；終結(jié)符——a,、b、c等,。其實(shí)說(shuō)白了開(kāi)始符就是Start的縮寫(xiě),，非終結(jié)符就是大寫(xiě)字母或大寫(xiě)字母的組合（開(kāi)始符S也是非終結(jié)符），終結(jié)符就是小寫(xiě)字母或小寫(xiě)字母的組合,。

文法共分為四種,，即0型文法——短語(yǔ)文法；1型文法——上下文有關(guān)文法,；2型文法——上下文無(wú)關(guān)文法,；3型文法——正規(guī)文法。

四個(gè)文法類(lèi)的定義是逐漸增加限制的,，即每一種正規(guī)文法都是上下文無(wú)關(guān)的,，每一種上下文無(wú)關(guān)文法都是上下文有關(guān)的,，而每一種上下文有關(guān)文法都是短語(yǔ)文法,。稱(chēng)0型文法產(chǎn)生的語(yǔ)言為0型語(yǔ)言。上下文有關(guān)文法,、上下文無(wú)關(guān)文法和正規(guī)文法產(chǎn)生的語(yǔ)言分別稱(chēng)為上下文有關(guān)語(yǔ)言,、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言。

注意：除0型文法以外,，每一種文法都必須符合上一種文法,。

0型文法：

書(shū)中的定義：設(shè)G=(VN，VT,，P,，S)，如果它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu)：α∈( VN∪VT )*且至少含有一個(gè)非終結(jié)符,，而β∈( VN∪VT )*,，則G是一個(gè)0型文法。

通俗的解釋?zhuān)杭串a(chǎn)生式左邊至少有一個(gè)大寫(xiě)字母,，右邊隨意,。

1型文法：

書(shū)中的定義：設(shè)G=(VN，VT,，P,，S)，若P中的每一個(gè)產(chǎn)生式α→β均滿(mǎn)足|β|≥|α| ,，僅僅S→ε除外,，則文法G是1型文法。

通俗的解釋?zhuān)杭串a(chǎn)生式右邊的字母?jìng)€(gè)數(shù)必須大于等于左邊的字母?jìng)€(gè)數(shù),。

2型文法：

書(shū)中的定義：設(shè)G=(VN,，VT,，P，S),，若P中的每一個(gè)產(chǎn)生式α→β滿(mǎn)足：α是一非終結(jié)符,，β∈( VN∪VT )*則此文法稱(chēng)為2型文法。

通俗的解釋?zhuān)杭串a(chǎn)生式左邊必須完全都是大寫(xiě)字母,。

3型文法：

書(shū)中的定義：設(shè)G=(VN,，VT，P,，S),，若P中的每一個(gè)產(chǎn)生式的形式都是A→aB或A→a，其中A和B都是非終結(jié)符,，a是終結(jié)符,，則G是3型文法。

通俗的解釋?zhuān)杭此挟a(chǎn)生式右邊要么沒(méi)有大寫(xiě)字母,，如果有必須全部在小寫(xiě)字母右邊或者全部在小寫(xiě)字母左邊也就是要保持線(xiàn)性一致,。

正規(guī)式

正規(guī)式是由正規(guī)文法轉(zhuǎn)換而來(lái)，它們之間的轉(zhuǎn)換規(guī)則共有三條：

規(guī)則1：正規(guī)文法（A—>xB,B->y ）,，正規(guī)式（A=xy）,。這點(diǎn)很簡(jiǎn)單，用小學(xué)的數(shù)學(xué)知識(shí)就可以解決,！如：A=xB,，B=y，那么A=xy,。

規(guī)則2：正規(guī)文法（A—>xA|y）,，正規(guī)式（A=x*y）。這是一個(gè)遞歸,，它其實(shí)是——正規(guī)文法（A—>xA,，A—>y），因?yàn)?span style="TEXT-ALIGN: left; LINE-HEIGHT: 26px; FONT-FAMILY: 'Microsoft YaHei'; FONT-SIZE: 16px">A—>xA,，而右邊的A又可以有A—>xA,，所以就可以無(wú)限循環(huán)下去，最終還是要有結(jié)尾的,，要不就沒(méi)法表示了,，所以有A=x*y，表明有無(wú)窮個(gè)x并以y結(jié)尾,。

規(guī)則3：A—>x,A->y,。那么A=x|y。這個(gè)就很簡(jiǎn)單了，不過(guò)多解釋了,。

其實(shí)上面說(shuō)的那些話(huà)完全可以用下面一個(gè)表來(lái)代替,，簡(jiǎn)單而又明了，哈哈,！

有窮自動(dòng)機(jī)跟語(yǔ)法推導(dǎo)樹(shù)留到下一篇博客再為大家講解吧,！敬請(qǐng)期待！

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,，所有內(nèi)容均由用戶(hù)發(fā)布,，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購(gòu)買(mǎi)等信息,，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請(qǐng)點(diǎn)擊一鍵舉報(bào),。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：昵稱(chēng)10504424 > 《軟件雜談》

舉報(bào)/認(rèn)領(lǐng)