我們可以利用文法的構造規則，構造出自己的語言。

　　而chomsky的文法定義則是很好的工具。

　　從形式上文法是一個四元式（VN,VT,P,S）

　　VN為非終結符的集合 　　 如：動詞

　　VT為終結符的集合　　　　如：動詞->eat（eat不可分解，則為終結符）

　　P文法規則的集合　　　　　　

　　S開始符號

　 閉包的概念：

　　如果VN為{主語，謂語}

　　則VN的星閉包（就是普通閉包）為{空串，主語謂語謂語主語，主語謂語，謂語主語....}

　　VN里面各種各樣的組合

　　正閉包則是除開空串的閉包。

　　chomsky將文法分成4類：

　　0型文法（短語文法或無限制文法），識別0語言的機器叫做圖靈機

　　定義：P中產生式a-->b，其中a屬于V正閉包且至少含有一個非終結符,b屬于V星閉包

　　注：任何0型文法都是可遞歸可枚舉的

　　　　對0型文法作某些限制，可以得到其他文法的定義

　　1型文法（上下文有關文法），線性界限自動機

　　增加的限制：除了S產生空串之外，產生式的右部長度要大于等于左部，S不能出現在右部，

　　　　　　　　非終結符不能產生空串。

　　例如：aAb-->ayb(在某種條件下A轉換為y，所以稱為上下文有關)

　　2型文法（上下文無關文法），下推自動機

　　增加的限制：P中只有A->b，而不是a->b，產生式左邊只能有一個非終結符。

　　3型文法（正規文法），有限狀態自動機

　　增加的限制：產生式的右邊非終結符的位置要么在最左邊要么在最右邊而且最多只能有一個

　　在左端則稱左線性文法，在右端則稱右線性文法

　　

　　對比：

　　四種文法之間的關系是隨著型號的增加，對語言的限制條件就越來越大

　　條件如下：

　　0型文法　: 產生式左右兩邊都可以出現任意符號串

　　1型文法　: 產生式的左邊可以有終結符的出現，產生式右邊是任意符號串

　　2型文法　：產生式的左邊是非終結符，產生式的右邊是任意符號串

　　3型文法　：產生式的左邊是非終結符，產生式的右邊非終結符的位置要么在最左邊要么在最右邊而且最多只能有一個

　　　　　　　　如：A-->aB | d

　　　　　　　　　　A-->Ba | d

　　文法的簡化：

　　文法當中有時會存在一些沒有的規則，刪掉對P沒有影響而且使得構造的文法更加簡練

　　1、查找有無形如P->P的產生式，刪除

　 2、若存在推導過程中永遠不會用到，刪除

　　3、若某個產生式在推導過程中不能從中導出終結符，刪除

　　4、整理

　

總結

以上是生活随笔為你收集整理的chomsky文法（编译原理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。