文法

定義

一個文法G是下述元素構成的一個四元組（N, Σ,P,S）：

● “非終結符號”集合N。

● “終結符號”集合Σ，Σ與N無交。

● 取如下形式的一組“產生式規則”P，

● (Σ ∪N)*中的字元串→ (Σ ∪N)* 中的字元串，並且產生式左側的字元串中必須至少包括一個非終結符號。

● “起始符號”S，S屬於N。

一個由形式文法G= (N, Σ,P,S)產生的語言是所有如下形式的字元串集合，這些字元串全部由“終結符號”集Σ中符號構成，並且可以從“初始符號”S出發，不斷應用P中的“產生式規則”而得到。

例子

考慮以下的文法G，其中N= {S, D}, Σ = {-, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},P包含如下規則：

● 1. S -> -D

● 2. S -> D

● 3. D -> 0D

● 4. D -> 1D

● 5. D -> 2D

● ...

● 12. D -> 9D

● 13. D -> 0

● 14. D -> 1

● 15. D -> 2

● ...

● 22. D -> 9

S為初始符號。以此文法可以產生所有整數。

文法形式

在計算機科學中，文法是編譯原理的基礎，是描述一門程序設計語言和實現其編譯器的方法。文法的描述多用BNF(巴克斯範式)，而另一個重要的概念：正則表達式，也是文法的另一種形式。

文法分類

自從喬姆斯基(Chomsky)於1956年建立形式語言的描述以來，形式語言的理論發展很快。這種理論對計算機科學有著深刻的影響，特別是對程序設計語言的設計、編譯方法和計算複雜性等方面更有重大的作用。

喬姆斯基把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在於對產生式施加不同的限制。

多數程序設計語言的單詞的語法都能用正規文法或3型文法來描述。

3型文法G=(VN，VT，P，S)的P中的規則有兩種形式：一種是前面定義的形式，即：A→aB或A→a其中A，B∈VN ，a∈VT*，另一種形式是：A→Ba或A→a，前者稱為右線性文法，後者稱為左線性文法。正規文法所描述的是VT*上的正規集。

四個文法類的定義是逐漸增加限制的，因此每一種正規文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。

類型說明

文法G定義為四元組(VN，VT，P，S )其中

VN:非終結符號(或語法實體，或變數)集；

VT:終結符號集；

P: 規則的集合；

VN，VT和P是 非空有窮集。

S:稱作識別符號或開始符號的一個非終結符，它至少要在一條產生式中作為左部出現。

VN和VT不含公共的元素，即VN ∩ VT = φ

用V表示VN ∪ VT ，稱為文法G的字母表或字彙表

規則，也稱重寫規則、產生式或生成式，是形如→或 ∷=的( ，)有序對，其中是字母表V的正閉包V+中的一個符號，是V*中的一個符號。  稱為規則的左部，  稱作規則的右部。

設G=(VN，VT，P，S)，如果它的每個產生式α→β是這樣一種結構：α∈( VN∪VT )*且至少含有一個非終結符，而β∈( VN∪VT )*，則G是一個0型文法。

0型文法也稱短語文法。一個非常重要的理論結果是，0型文法的能力相當於圖靈機(Turing)。或者說，任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個0型語言。

對0型文法產生式的形式作某些限制，以給出1，2和3型文法的定義。

設G=(VN，VT，P，S)為一文法，若P中的每一個產生式α→β均滿足|β|≥|α| ，僅僅S→ε除外，則文法G是1型或上下文有關的。

在有些文獻給的定義中，將上下文有關文法的產生式的形式描述為α1Aα2→α1βα2，其中α1、α2和β都在( VN∪VT

)*中(即在V*中)，β≠ε，A在VN中。這種定義與前邊的定義等價。但它更能體現"上下文有關"這一術語，因為只有A出現在α1和α2的上下文中，才允許用β取代A。

設G=(VN，VT，P，S)，若P中的每一個產生式α→β滿足：α是一非終結符，β∈( VN∪VT )*則此文法稱為2型的或上下文無關的。有時將2型文法的產生式表示為形如：A→β其中A∈VN，也就是說用β取代非終結符A時，與A所在的上下文無關，因此取名為上下文無關文法。

例4.1和例4.2中的文法都是上下文無關的，下面我們再給出一個例子(例4.4)，例中的文法G是上下文無關文法，G的語言是由相同個數的a和b所組成的{a，b}*上的串。

設G=(VN，VT，P，S)，若P中的每一個產生式的形式都是A→aB或A→a，其中A和B都是非終結符，a是終結符，則G是3型文法或正規文法。

文法即文章的書寫法規，一般用來指以文字、詞語、短句、句子的編排而組成的完整語句和文章的合理性組織。

●最簡單的語句組合一：主詞及動詞：

“我”“哭了”

“天氣”“改變了”

“哭笑”“難分”

●最簡單的語句組合二：主詞、動詞及受詞：（括弧內為隱藏語）

我愛你

“道”“可”“道”，“(這個道字)”“〈並〉非”“常道”。《道德經》老子

“打羽毛球”“是”“最好的(運動)”

“駕駛”“〈使我〉”“樂趣無窮”

●比較複雜的語句組合一：主語〈短句〉、謂語及賓語：

例：“我這個從來沒有戀愛經驗的少年人”、“竟然不知為了什麼原因而喜歡了”及“一個黃毛小丫頭”

●複雜的語句組合二：主語及複式謂語：

例：“有些頭腦守舊而自以為是的讀書人”、“認為如廁的動作不雅，”“所以寫成出恭。”

在口語中，因為說話者或受話人都知道相方的關係和說話主題，所以大都隱去主詞或受詞。但在書寫文章時，必須要清楚表明主和賓雙方。

●動賓結構：一般口語，多是動賓結構的，即前面是動詞，後面是名片語成的。這是因為受話人明知語句的主語而不用說出來的關係。

〈你正在──主語不用說出來〉拍馬屁、

〈你真的是〉痴線（廣東慣用語）、〈你是在〉敲竹杠、〈你在〉潑冷水、〈你不要〉耍花招等。

●主謂結構，主謂（陳述）結構，即前面是主詞或主語，後面加上一個描述或動作的單字、詞語或片語組成的。這是因為說話語句中的受詞或賓語不用說出來的關係。

多為說話語句中的動詞部分，主語和賓語也不用說出了。例如：（這個）天曉得，、〈他的〉嘴巴軟〈了〉等。

●複詞結構

●偏正結構由兩組〈或以上〉字詞所組成的〈複合〉名詞──用作主語部分，或賓語部分。

●形容詞〈相當於英語的形容詞〉及名詞。

替罪羊、耳邊風、糊塗蟲、絆腳石等。

鬼畫〈形容詞〉符

由兩組〈或以上〉字詞所組成的短句，如謂語部分。

●動詞及副詞。

跳得很遠、大聲哭叫、清早起來

文字、詞語、句子、文章、詞、書本、編集

中文舊式體裁

楚辭、秦漢駢文、詩、詞、歌、賦、唐宋古文

民謠、元曲、明清八股、文言文、白話文

歷、記事或紀錄、經、史、子

中文體裁

抒情文、描寫文

散文、小說

記敘文

歷史、回憶錄

議論文

社論、評述、

報告

論文、會議記錄

說明文

通告、產品說明書、書序

應用文

合約、租約

文法詞性分類

程序設計語言中的幾類單詞可用下述規則描述：

〈標識符〉→l|l〈字母數字〉

〈字母數字〉→l|d|l〈字母數字〉|d〈字母數字〉

〈無符號整數〉→d|d〈無符號整數〉

〈運算符〉→+|-|*|/|=|〈〈等號〉|〉〈等號〉……

〈等號〉→=

〈界符〉→，|；|(|)|……

其中l表示a～z中的任何一英文字母，d表示0～9中的任一數字。

關鍵字（保留字）也是一種單詞，一般關鍵字（保留字）都是由字母構成，它的描述也極容易，實際上，關鍵字（保留字）集合是標識符集合的子集。

最複雜的一類單詞要屬無符號實數了，比如25.55e+5和2.1，它們可以由如下規則描述。

例4.6

〈無符號數〉→d〈余留無符號數〉|.〈十進小數〉|e〈指數部分〉

〈余留無符號數〉→d〈余留無符號數〉|.〈十進小數〉|e〈指數部分〉|ε

〈十進小數〉→d〈余留十進小數〉

〈余留十進小數〉→e〈指數部分〉|d〈余留十進小數〉|ε

〈指數部分〉→d〈余留整指數〉|s〈整指數〉

〈整指數〉→d〈余留整指數〉

〈余留整指數〉→d〈余留整指數〉|ε

其中s表示正或負號(+，-)，d表示0～9中的任一數字。

舉例

例：1型（上下文有關）文法

文法G[S]： S→CD　Ab→bA

C→aCA Ba→aB

C→bCB Bb→bB

AD→aD C→ε

BD→bD D→ε

Aa→aA

L(G)={ww|w∈{a,b}*}

例：2型（上下文無關）文法

文法G[S]： S→0A|1B|0

A→0A|1B|0S

B→1B|1|0