上下文无关文法

上下文无关文法 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)}$ 。

例子 1

一个简单的上下文无关文法的例子是：S -> aSb | ab 。这个文法产生了语言 {aⁿbⁿ : n ≥ 1} 。不难证明这个语言不是正则的。

例子 2

这个例子可以产生变量 x,y,z 的算术表达式：

S -> T + S | T - S | T

T -> T * T | T / T | ( S ) | x | y | z

例如字符串 "( x + y ) * x - z * y / ( x + x )" 就可以用这个文法来产生。

例子 3

字母表 {a,b} 上 a 和 b 数目不相等的所有字符串可以由下述文法产生：

S -> U | V

U -> TaU | TaT

V -> TbV | TbT

T -> aTbT | bTaT | ε

这里 T 可以产生 a 和 b 数目相等的所有字符串，U 可以产生 a 的数目多于 b 的数目的所有字符串， V 可以产生 a 的数目少于 b 的数目的所有字符串。

推导与语法树

最左推导

在推导的任何一步α=> β中，都是对α中的最左边非终结符进行替换。 如文法:

S -> AB

A -> a|t

B -> +CD

C -> a

D -> a

那么最左推导为:

S => AB => aB => a+CD => a+aD => a+aa

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

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

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