個人認為編譯原理對于一個程序員來說很重要，可能你認為編程的時候用的都是C++、C#、Java等高級語言，至于編譯原理懂與不懂并無大礙。其實不然，所謂萬變不離其宗，所有高級語言的誕生都是基于最根本的編譯原理的。搞懂了編譯原理，對于一個程序員的能力提升有著很大的幫助。因為它會讓你對編程有更加深刻的理解，有助于你寫出質量更高的代碼。好廢話不多說，切入正題！ 本文主要說一下編譯原理里的文法、正規式、有窮自動機和語法推導樹。 **文法** 文法就是計算機語言的一個嚴格的規范，有點類似人類語言的語法。就像形容詞修飾名詞，副詞修飾形容詞跟動詞類似，只不過計算機的文法的標準和規范更加的嚴格而已。 文法的表達式：G=(Vn,Vt,P,S) ?Vn是非終結符的集合，Vt是終結符的集合，P是推導式的一個集合，S是開始符。 文法中有三種符號和四種文法類型： 三種符號為：開始符——S；非終結符——A、B、C、AB等；終結符——a、b、c等。其實說白了開始符就是Start的縮寫，非終結符就是大寫字母或大寫字母的組合（開始符S也是非終結符），終結符就是小寫字母或小寫字母的組合。 文法共分為四種，即0型文法——短語文法；1型文法——上下文有關文法；2型文法——上下文無關文法；3型文法——正規文法。 四個文法類的定義是逐漸增加限制的，即每一種正規文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是短語文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。 **注意：除0型文法以外，每一種文法都必須符合上一種文法。** **0型文法：** 書中的定義：設G=(VN，VT，P，S)，如果它的每個產生式α→β是這樣一種結構：α∈( VN∪VT )*且至少含有一個非終結符，而β∈( VN∪VT )*，則G是一個0型文法。 通俗的解釋：即產生式左邊至少有一個大寫字母，右邊隨意。 **1型文法：** 書中的定義：設G=(VN，VT，P，S)，若P中的每一個產生式α→β均滿足|β|≥|α| ，僅僅S→ε除外，則文法G是1型文法。 通俗的解釋：即產生式右邊的字母個數必須大于等于左邊的字母個數。 **2型文法：** 書中的定義：設G=(VN，VT，P，S)，若P中的每一個產生式α→β滿足：α是一非終結符，β∈( VN∪VT )*則此文法稱為2型文法。 通俗的解釋：即產生式左邊必須完全都是大寫字母。 **3型文法：** 書中的定義：設G=(VN，VT，P，S)，若P中的每一個產生式的形式都是A→aB或A→a，其中A和B都是非終結符，a是終結符，則G是3型文法。 通俗的解釋：即所有產生式右邊要么沒有大寫字母，如果有必須全部在小寫字母右邊或者全部在小寫字母左邊也就是要保持線性一致。 **正規式** 正規式是由正規文法轉換而來，它們之間的轉換規則共有三條： 規則1：正規文法（A—>xB,B->y ），正規式（A=xy）。這點很簡單，用小學的數學知識就可以解決！如：A=xB，B=y，那么A=xy。 規則2：正規文法（A—>xA|y），正規式（A=x*y）。這是一個遞歸，它其實是——正規文法（A—>xA，A—>y），因為A—>xA，而右邊的A又可以有A—>xA，所以就可以無限循環下去，最終還是要有結尾的，要不就沒法表示了，所以有A=x*y，表明有無窮個x并以y結尾。 規則3：A—>x,A->y。那么A=x|y。這個就很簡單了，不過多解釋了。 其實上面說的那些話完全可以用下面一個表來代替，簡單而又明了，哈哈！  有窮自動機跟語法推導樹留到下一篇博客再為大家講解吧！敬請期待！