上下文无关文法

上下文无关文法 G 是 4-元组：

${\displaystyle G=(V,\Sigma ,R,S)}$

这里的

1. ${\displaystyle V}$ 是“非终结”符号或变量的有限集合。它们表示在句子中不同类型的短语或子句。
2. ${\displaystyle \Sigma }$ 是“终结符”的有限集合，无交集于 ${\displaystyle V}$，它们构成了句子的实际内容。
3. ${\displaystyle S}$ 是开始变量，用来表示整个句子（或程序）。它必须是 ${\displaystyle V}$ 的元素。
4. ${\displaystyle R}$ 是从 ${\displaystyle V}$ 到 ${\displaystyle (V\cup \Sigma )^{*}}$ 的关系，使得 ${\displaystyle \exists w\in (V\cup \Sigma )^{*}:(S,w)\in R}$。

此外，${\displaystyle R}$ 是有限集合。${\displaystyle R}$ 的成员叫做文法的“规则”或“产生式”。星号表示Kleene星号运算。

补充定义 1

对于任何字符串 ${\displaystyle u,v\in (V\cup \Sigma )^{*}}$，我们称 ${\displaystyle u}$ 生成 ${\displaystyle v}$，写为 ${\displaystyle u\Rightarrow v}$，如果 ${\displaystyle \exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}}$ 使得 ${\displaystyle u=u_{1}\alpha u_{2}}$ 且 ${\displaystyle v=u_{1}\beta u_{2}}$。因此 ${\displaystyle v}$ 是应用规则 ${\displaystyle (\alpha ,\beta )}$ 于 ${\displaystyle u}$ 的结果。

补充定义 2

对于任何 ${\displaystyle u,v\in (V\cup \Sigma )^{*},u{\stackrel {*}{\Rightarrow }}v}$（或 ${\displaystyle u\Rightarrow \Rightarrow v}$ 在某些教科书中），如果 ${\displaystyle \exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0}$ 使得 ${\displaystyle u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v}$。

补充定义 3

文法 ${\displaystyle G=(V,\Sigma ,R,S)}$ 的语言是集合

${\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}$

补充定义 4

语言 ${\displaystyle L}$ 被称为是上下文无关语言（CFL），如果存在一个 CFG ${\displaystyle G}$ 使得 ${\displaystyle L=L(G)}$。

每一个不生成空串的上下文无关文法都可以转化为等价的Chomsky 范式或Greibach 范式。这里两个文法等价的含义指它们生成相同的语言。

由于Chomsky范式在形式上非常简单，所以它在理论和实践上都有应用。比如，对每一个上下文无关语言，我们可以利用Chomsky范式构造一个多项式算法，用它来判断一个给定字串是否属于这个语言（CYK算法）。

• 上下文有关文法
• 形式文法
• 分析表达式文法
• 随机上下文无关文法
• 巴科斯范式
• 乔姆斯基范式
• Greibach范式