语法简介

从文学意义上讲，语法表示自然语言对话的句法规则。自从英语、梵语、普通话等自然语言诞生以来，语言学就一直试图定义语法。

形式语言理论在计算机科学领域有着广泛的应用。 Noam Chomsky 于 1956 年提出了一种语法数学模型，该模型对于编写计算机语言非常有效。

语法

语法 G 可以正式写成 4 元组 (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 → ε