|
轉(zhuǎn)載請(qǐng)注明來源http://www.cnblogs.com/qjkobe/p/5332612.html，謝謝。 編譯原理學(xué)文法類型的時(shí)候，會(huì)出現(xiàn)喬姆斯基給出的四種文法類型，然而，這些概念太過于抽象了，對(duì)于初學(xué)者實(shí)在很難理解，所以，在這里，我給出一些我自己的理解，希望能對(duì)大家有所幫助。 在這之前，你必須對(duì)終結(jié)符和非終結(jié)符有所了解，簡單來說，非終結(jié)符就是這個(gè)東西還能→別的東西（→的標(biāo)準(zhǔn)叫法是定義為），但是終結(jié)符就不能了，比如說，分子→原子，原子→夸克?？淇司筒荒茉俜至耍圆荒苡善渌Ｗ佣x。（隨便舉個(gè)例子，基于2016年，免得以后萬一夸克不是最小的了呢，機(jī)智如我） ps：終結(jié)符里包含ε，也就是空。 然后，必須明確是概念是文法類型之間的包含關(guān)系。 先有0型，然后后面的文法都是對(duì)前者添加更多的限制，來縮小它的范圍。 那么，什么是0型文法，其實(shí)就是，→的左邊，是非終結(jié)符和終結(jié)符的組合，由于終結(jié)符是有ε這個(gè)空存在的，所以，這就相當(dāng)于只要有一個(gè)非終結(jié)符，其他怎么樣都行。向右的右邊，沒有任何限制。舉個(gè)例子： 終結(jié)符：A，B，C，S（注：S作為開始符，是非終結(jié)符，至少在一條規(guī)則中作為左部出現(xiàn)，規(guī)則就是什么→什么） 非終結(jié)符：a，b，c（注：ε也在里面，不過一般不會(huì)寫出來，因?yàn)樵谝?guī)則里加上S→ε沒有意義。） →左邊可以是：S，SA，A，aA，aAb，aAa，AB，aAB.....等等 →右邊可以是：a，ab，b，abc，ε，A，AB....等等，反正，什么都可以，只要在終結(jié)符和非終結(jié)符的集合里。 那好，0型的限制這么少，1型又是怎樣的呢，其實(shí)，1型加的限制就是，對(duì)任一產(chǎn)生式α→β，都有|β|>=|α|， 僅僅 S→ε除外，這個(gè)說法有點(diǎn)讓人摸不著頭腦，讓我們換一種說法 表達(dá)式的形式應(yīng)該為：α1Aα2→α1βα2，A在終結(jié)符集合中，剩下的符號(hào)都是任意的（終結(jié)符和非終結(jié)符的集合），這意味著什么，我舉個(gè)例子來說明： A→aB S→abc bB→bc aB→bB 我們在上述例子的第一個(gè)規(guī)則中A→aB中，想把B給替換掉，但是我們發(fā)現(xiàn)，沒有B→這樣的規(guī)則，然而，聰明的我們又發(fā)現(xiàn)，有aB→這樣的式子，所以我們就把a(bǔ)B替換成了bB，然后bB又可以替換成bc。 這其實(shí)就表達(dá)了這樣一個(gè)意思，我要換這個(gè)B啊，必須得和他周圍的東西一起換掉，就好像超市，B單獨(dú)一個(gè)東西賣不出去，只有打包才行，所以，1型文法又稱為上下文有關(guān)文法。 注：這里有人會(huì)覺得，1型不就是0型嗎？這個(gè)答案是肯定的，因?yàn)槭前P(guān)系嘛。但是0型就不一定是1型了。舉個(gè)例子，比如以下規(guī)則； S→ab bB→c aB→cB 上面的規(guī)則中，最后二條違背了1型的定義，所以，上述例子是0型不是1型。 搞懂了1型，那么，2型文法又加了什么限制呢，其實(shí)就是，→的左邊，都只能存在一個(gè)非終結(jié)符，那種AA，aB，aBc之類的就不能存在了，左邊必須單身狗，向右的右邊依舊很自由，什么都可以（終結(jié)符和非終結(jié)符的集合）。 比如： A→aB S→bAA B→a C→abA 大家會(huì)發(fā)現(xiàn)，當(dāng)我要在A→aB中，把B替換掉的時(shí)候，由于存在B→a，所以直接就可以替換掉B，而不用在乎A→aB這個(gè)式子的B的旁邊有沒有別的東西，所以，2型文法又叫做上下文無關(guān)文法。 最后一種，3型文法，又稱為正規(guī)文法，它的限制可就十分之死板了，它只允許兩種形式的產(chǎn)生式存在，一個(gè)是A→aB，一個(gè)是A向右a，A和B都是非終結(jié)符，a則是終結(jié)符。舉個(gè)例子： S→aA S→a A→bB A→b 反正就是只有兩種格式的式子允許存在，所以正規(guī)文法其實(shí)是很少的。 PS：終結(jié)符和非終結(jié)符的集合可以是，ab，AB，aBc這樣的組合，但是上述文字中我如果沒說集合，那就只能有一個(gè)，比如，A，b，C，d |
|
|
