语法简介

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

形式语言理论在计算机科学领域有着广泛的应用。诺姆·乔姆斯基 (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 ⇒Gx β y

例子

让我们考虑语法 -

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

一些可以导出的字符串是 -

S ⇒ aA b使用产生式 S → aAb

⇒ a aA bb使用产生式 aA → aAb

⇒ aaa A bbb使用产生式 aA → aaAb

⇒ aaabbb使用产生式 A → ε