Formal Grammar

#CS/FormalLanguageTheory

形式语法（formal grammar） 描述了如何从语言的字词（alphabet）构造符合语法（syntax）的有效句子，是形式语言的一部份。形式语法 不描述字符串的含义，也不描述在任何上下文中可以用它们做什么，只描述它们的形式（语义部分由形式语义定义）。^[1]

形式语法定义

现在常用的形式语法经典理论，文法 $G$ 由以下部分组成：

有限的非终结符集 $N$ ，与 $G$ 生成的字符串无交集
有限的终结符集 $Σ$ ，与 $N$ 无交集
有限的产生式规则集 $P$ ，每个规则都为如下形式
$(Σ \cup N)^{*} N (Σ \cup N)^{*} \to (Σ \cup N)^{*}$
每个产生式规则从一个符号串映射到另一个符号串，并且产生式左侧的字符串中必须至少包括一个非终结符号。
开始符号 $S \in N$ ，也叫句子符号

例子

有文法 $G$ ，其中 $N = {S, B}$ ， $Σ = {a, b, c}$ ， $S$ 是开始符号， $P$ 由一下产生式规则组成：

\begin{aligned} 1. S \to a B S c \\ 2. S \to a b c \\ 3. B a \to a B \\ 4. B b \to b b \end{aligned}

这个文法的形式语言是 $L (G) = {a^{n} b^{n} c^{n} | n >= 1}$ 。

分类

形式语法 被划分为四类，成为乔姆斯基谱系。

Wikipedia

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of production rules for such strings in a formal language.^[2]