语法导论

从文学意义上讲，文法指的是自然语言会话的句法规则。自从英语、梵语、汉语等自然语言诞生以来，语言学家就一直在试图定义文法。

形式语言理论在计算机科学领域得到了广泛的应用。**诺姆·乔姆斯基**在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 → ε