文法：1.法制；法規。 2.文章的作法。 3.文法。語言的結構方式。包括詞的構成和變化﹐詞組和句子的組織。文法即文章的書寫法規，一般用來指以文字、詞語、短句、句子的編排而組成的完整語句和文章的合理性組織。這個是我們小時候接觸過的關于文法的概念，那個時候的文法總是會和主語，賓語，謂語等聯系在一起。
二十年過去了，今天她再次出現在我面前，還是一樣的眼神，藏在記憶深處的“文法”跟眼前的這個“她”有什麼不一樣呢？在計算機科學中，文法是編譯原理的基礎，是描述一門程式設計語言和實作其編譯器的方法。文法的描述多用BNF(巴克斯範式)，而另一個重要的概念:正規表達式，也是文法的另一種形式。今天小編主要給大家講解一下文法的相關知識。介紹文法的知識之前，先讓我們來看一張圖，小編會圍繞這張圖的内容展開，一一介紹。
好了，按照我們上面導圖的順序，小編一一來講解一下各個知識點，還請各位大神不吝賜教。
終結符和非終結符
聽着“終結”兩個字兒，頓時感覺高大上的感覺，有麼有，伴随着的是，這個是什麼nie，都沒有聽說過，這是什麼東東，其實這個并沒有我們想象中的那麼困難，首先，我們來看一個例子：
結合上面的例子，開講啦，S為開始符，S,A,B為非終結符，在左邊，可以推導出一個式子來。而p,q,a,b,c,d為終結符。講到這裡，小夥伴們是不是有點兒懵的感覺呢，什麼終結符非終結符的，這個知識點我們可以這樣來幫助我們來了解，我們可以這樣想，S（start）也是一個非終結符，然後大寫的為非終結符，小寫的為終結符，那麼這個概念就了解起來，也就沒有那麼困難了。
文法的類型
文法的類型，有四種，這類知識點，在軟考中通查都會這樣考察我們，讓我們判斷這幾種文法的類型。
0型文法
結合下面的例子，我們來看看什麼叫0型文法；
0型文法是這幾個文法中，限制最少的一個，是以我們平常見到的至少是0型文法。G=(Vn,Vt,P,S),其中Vn是非終結符的集合，Vt是終結符的集合，P是推導式的一個集合，S是開始符。結合上面的例子，小編的分析如下：我們從圖中來闡述一下這些概念，S,A,B為Vn，而p,q,a,b,c,d,為Vt,S為開始符。整個集合為P。我們每個式子裡邊的左邊必須要包含這些元素或者元素組合中的至少一個非終結符，右邊可以是這些元素的任意組合，左邊有非終結符，右邊有終結符，就歐了。如：A->ab。
1型文法
也叫上下文有關文法；這個1型文法了解起來也不是我們想象中的那麼困難；在0型文法的基礎上，我們再添加一點點的限制就行了，我們看添加了什麼限制：右邊的長度>=左邊的長度，這個長度我們可以這樣來了解，就是這些字元的數量，小的推出大的或者相等的。這樣可以幫助我們了解。比如：A->B，A->Bba 都符合要求，那麼反過來，Bba->A就不符合要求了，因為左邊是3，右邊是1。
2型文法
也叫上下文無關文法。2型文法在1型文法的基礎上，我們規定2型文法中，左邊必須是非終結符，然而一個終結符一個非終結符的組合不是一個非終結符，如Ab不是一個非終結符，但是兩個非終結符的組合就是一個非終結符了，如AB就是行了。那麼應該是這樣的：aB->abc就不符合要求，但是AB->abc就符合要求了。
3型文法
也叫正規文法，對應有限狀态自動機。在2型文法的基礎上再加限制。要求更加高。要麼一個非終結符推出一個終結符，要麼一個非終結符推出一個終結符并且帶一個非終結符。4個文法類的定義是逐漸增加限制的，是以每一種正規文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。說了這麼多的理論知識，接下來，我們來看一個問題：
結合上面的表格，我們來分析一下這些規則
規則1：文法産生式（A—>xB,B->y ），正規式（A=xy）。對于這個文法産生式轉換成正規式，我了解的就是一個代入的過程，把B=y代入A->xB即可得出正規式。反過來，正規式轉換成文法産生式，則添加一個變量就可以了了。 規則2：這個式子裡邊有一個遞歸，A—>xA，這樣就産生遞歸了，應該是這樣的：A->xA,A->xA……這樣的無窮下去，最終A還是要等于y的，是以x就有無窮多個，從0個到無窮多個，是以這個推導出來的正規式就是A=x*y，表明x有無窮多個。規則3：A—>x,A->y。那麼A=x|y，這個就明白了。A退出x或者y。
有窮自動機
NFA與DFA的定義：DFA:确定的有限自動機，M=(S,E,f,So,Z)，我們來分析分析這個五元組：S是一個有限狀态集合；E就是一個輸入字元；f是一個SxE至S的映射；So：初态；Z:終态。我們來看看具體的例子，光是理論和概念的東西最不好了解，來看看例子吧：DFA=({S,A,B,C,f},{1,0},F,S,{f}),我們對照上面式子就能看的出來各個元素代表的意義，我們再來分析一遍：{S,A,B,C,f}是一個狀态集合；{1,0}是輸入字元；F是一個映射，S是初态，{f}是一個終态。那麼我們接下來看這些映射：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;我們根據這個流程，就有了這麼一張圖：
然後再看看NFA的定義：M=(S,E,f,So,Z) 這個五元組跟DFA的定義一樣，在此不再贅述。
小編寄語：第一次接觸編譯原理的相關知識，小編了解的不是很深入，該博文主要介紹了文法，正規表達式有窮自動機，都是小編在現階段了解的一丢丢的皮毛，希賽視訊看下來，也是暈頭轉向，一篇漆黑的感覺，總結完編譯原理的相關知識後，對這塊的内容的了解仍然不深，不為别的，該博文，隻為記錄一個單純的過程，還有我走過的軟考之路，未完待續......