**寫在開始**:
上篇我們介紹了編譯“工廠”的流程,本篇介紹,工廠里的“工具”。
**開始教程**:
語言和文法?語言我們知道,計算機語言,人類的語言,動物的語言,不同國家的語言,不同種族的語言等等。那神馬是文法呢?所謂文法,文,文字,法,規則,法則,法律。組合起來就是,文字的規則。每種語言都有自己的文法,不同的語言有不同的文法。例如我們的中文的文法,用一種規則來定義句子的組成,還拿“我是中國人”為例。
我們的個中文句子構造規則:<主語><謂語><賓語><補語><狀語>。?而英語的句子構造:S十V主謂結構 S十V十F主系表結構 S十V十O主謂賓結構 S十V十O1十O2主謂雙賓結構 S十V十O十C主謂賓補結構說明:S=主語;V=謂語;P=表語;O=賓語;O1=間接賓語;O2=直接賓語;C=賓語補足語。我們可以看出漢語和英語有不同的編排,不同的規則,這就是文法。?
**我們這里要說的是編譯程序的文法**。
**書中的文法定義**:使用文法作為工具,不僅為了嚴格地定義句子的結構,也是為了適當條數的規則把語言的全部句子描述出來,可以說文法是以有窮集合刻畫無窮集合的工具。
接下來了解一些關于表示文法的一些基本定義:
**一些基本定義**
**符號和符號串**:
正如我們學習的English是由單詞和標點符號構成的,單詞又是有字母構成的,計算機語言也是如此,也是由字母和數字等一些基本符號構成的,一個源程序就是一個“基本符號串”,所以我們開始了解符號和符號串相關的定義。
**字母表**:
元素的非空有窮集合。不同的語言有他自己不同的字母表,我們的計算機語言字母表就是數字,字母,標點等若干符號了。中文的字母表就是漢字了。
**符號串**:
字母表的符號組成任何又窮序列的符號串。例如字母表A={a,b,c}則由這個字母表組成的符號串包括: {ab,ac,bc,abc,a,b,c}。
有了這些就相當于有了123456,接下來就是一些運算了,符號串的一些運算了。
**連接運算**:
eg:x=bay=nanaxy=banana(很簡單,連接在一起)
**方冪運算**:x^0= e? ; x^1 = x;.....;(和小學數學的方冪一致)
**兩個字母表乘積**:∑1={0,1},∑2={a,b},∑1∑2 ={0a,0b,1a,1b};(小學數學結合運算)
**∑的正閉包**:
∑+=∑∪∑2∪∑3∪∑4∪……
**∑的克林閉包(kleene Closure**)**:
∑*=∑0∪∑+(與正閉包區別哦,這算是新概念)
例如:{0,1}+ = {0,1,00,01,11,000,001,010,011,100,……}
{0,1}* = {ε,0,1,00,01,11,000,001,010,011,100,…}
?
**我們用這些規則將我們的語言形式化**:
“我是中國人”:名詞:: =中國人;代詞::=我;動詞::=是;
編譯程序的文法把計算機語言形式化的定義:A->b ;讀作:A定義為b;或把他說成是一條關于A的規則(產生式);
**更加規范的定義**:
文法G的定義:四元組(Vn,Vt,P,S)?
Vn:是非終結符集;
Vt:終結符集;
P:表示一種規則(a->b)ab表示終結符和非終結符的集合,但a中至少包括一個非終結符。Vn,Vt,P是非空有窮集合。
S:表示開始符,他是一個非終結符,至少要有一條規則在左側。
?
**那什么是終結符和非終結符呢?規則又是怎樣?開始符?**
下面來看一個英文句子,以英文句子為例,說說這個過程,幻燈片上的這個例子很適合初學者。
分析句子:The grey wolf will eat? the? goat .

句子的組成規則:

我們如何用文法符號來描述這個歸納的過程呢?這個英文句子怎么形式化的表現出來呢?
這就是為什么我們上述的文法G要用那四個符號來表示了:
?
因為前人發現重復的地方,想用有窮的地方表達無窮的東西,用這四個方式來表示恰好能將所有的句子歸納。
這是對一個句子的分析,當然如果有一個句子,我們也可以根據這種規則判斷是個句子是否符合英文的文法。
**文法描述的語言是該文法一切句子的集合。**
給出幾個詞,我們能根據文法組成一個句子,可以根據規則產生語言。
給出一個句子,我們把句子的詞進行歸類,可以判斷這個句子是否可被識別。
例如:the grey will eat the goat
the grey wolf will eat wolf
the grey goat will eat the wolf
the grey goat will eat the grey
符合語法語義的句子僅是:
the grey wolf will eat goat
所以文法G的形式定義如上所述
Vt:終結符,我們一般用除了大寫字母表示。
Vn:非終結符,我們一般用大寫字母表示。
S:一般是開始符號。?
P:就表示一種規則啦。?
a->b被稱為產生式(定義式)
**仙人(前人)給定義的一些說法**:
文法G、、上述定義,cd是Vn和Vt中任意字符,符號串V和W V=caW=db (規則 a->b)則V能直接產生W,則說W是V的直接推導。或說W直接規約到V。
1如果V->W0->W1->W2...->Wn=W? (n>0)則稱**W規約到V**記作:V ---+- >W?(箭頭上帶一個加號,寫的時候不方便。。)
若? 1 或V=W則記作V ---*->W??????? (箭頭上帶一個星號)
**句子句型**:
設G[S]是以文法,如果符號x是從識別符號推到出來的,即有S---*--->x ,則稱x是文法G[S]的句型。
若x僅由終結符號組成,則稱x為該文法G[S]的句子。
?
本篇就到這里,講述了文法的概念--語言的規則,文法的組成,文法的一些基本定義解釋。
寫在最后:
?
小菜祝開心閱讀,共同提高。(僅是入門教程,更深入的學習遨游到書籍中,能盡快的理解)