語法導論

從文學意義上講，文法指的是自然語言會話的句法規則。自從英語、梵語、漢語等自然語言誕生以來，語言學家就一直在試圖定義文法。

形式語言理論在計算機科學領域得到了廣泛的應用。**諾姆·喬姆斯基**在1956年給出了一個有效的計算機語言編寫文法數學模型。

文法

一個文法**G**可以形式化地寫成一個四元組 (N, T, S, P)，其中：

• **N** 或 **V_N** 是變數或非終結符的集合。

• **T** 或 **∑** 是終結符的集合。

• **S** 是一個特殊的變數，稱為起始符，S ∈ N

• **P** 是終結符和非終結符的產生式規則。產生式規則的形式為 α → β，其中 α 和 β 是 V_N ∪ ∑ 上的字串，並且 α 中至少有一個符號屬於 V_N。

示例

文法 G1：

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

這裡：

• **S、A** 和 **B** 是非終結符；

• **a** 和 **b** 是終結符

• **S** 是起始符，S ∈ N

• 產生式，**P : S → AB, A → a, B → b**

示例

文法 G2：

(({S, A}, {a, b}, S,{S → aAb, aA → aaAb, A → ε } )

這裡：

• **S** 和 **A** 是非終結符。

• **a** 和 **b** 是終結符。

• **ε** 是空串。

• **S** 是起始符，S ∈ N

• 產生式 **P : S → aAb, aA → aaAb, A → ε**

文法的推導

可以使用文法中的產生式從其他字串推匯出字串。如果文法**G**有一個產生式**α → β**，我們可以說**x α y** 在**G**中推匯出**x β y**。這個推導寫成：

x α y ⇒G x β y

示例

讓我們考慮一下文法：

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

可以推匯出的一些字串是：

S ⇒ aAb 使用產生式 S → aAb

⇒ aaAbb 使用產生式 aA → aAb

⇒ aaaAbbb 使用產生式 aA → aaAb

⇒ aaabbb 使用產生式 A → ε