在研究自然语言时，人们发现名词、动词、介词以及它们的短语之间存在着自然的递归关系，因此引入了 上下文无关文法(CFG) 来帮助整理和理解这种关系。同时，上下文无关文法在程序设计语言的规范化及编译中有重要应用。设计人员在编写程序设计语言的编译器和解释器时，通常需要先获取该语言的文法，因此在大多数的编译器和解释器中都包含了一个 语法分析器 。与上下文无关文法相关的语言集合称为 上下文无关语言(CFL)。
一、上下文无关语法概述
给出一个上下文无关语法的示例，称其为 $G_1$:
$$A \to 0A1 \\ A \to B \\ B \to \# $$
一个文法是由一组 替换规则 或称 产生式 组成；每条规则占一行，由一个符号和一个字符串构成，中间用箭头隔开；符号称为 变元，字符串则由变元和另一种称为 终结符 的符号构成，通常第一条规则的左边的变元被指定为 起始变元 ；则文法 $G_1$ 有3条规则，$A$和$B$是变元，其中$A$是起始变元，$0,1$和$\#$ 是终结符；
按照以下方法，能够根据文法生成其所描述的语言的每一个字符串：
- 写下起始变元
- 取一个已写下的变元，并找到该变元开始的规则，把这个变元替换成规则右边的字符串
- 重复步骤2，直到写下的字符串中没有变元为止
例如，文法 $G_1$ 生成的字符串 $000\#111$。获取一个字符串的替换序列称为 派生；文法 $G_1$ 生成字符串 $000\#111$ 的派生过程如下：
$$A \Rightarrow 0A1 \Rightarrow 000A111 \Rightarrow 000B111 \Rightarrow 000\#111$$
用上述方式生成的所有字符串构成该 文法的语言；用 $L(G_1)$表示文法$G_1$的语言，可以得出 $L(G_1) = ${$0^n\#1^n | n \geqslant 0$}，该语言称为 上下文无关语言 ；通常对于$A \to 0A1 $和$A \to B $可以合并为 $A \to 0A1 | B$
二、上下文无关文法形式化定义
$G = (V,\Sigma,R,S)$
- $V:$ 有穷 变元 集
- $\Sigma:$ 有穷 终结符 集
- $R:$ 有穷 规则 集 （形如 $A \to w,w \in (V \cup \Sigma)^*$）
- $S \in V:$ 初始变元
设 $u,v$和$w$是由变元及终结符构成的字符串，$A \to w$是文法的一条规则，称$uAv$ 生成 $uwv$，记作 $uAv \Rightarrow uwv$。如果 $u = v$，或者存在序列 $u_1,u_2…u_k$，使得
$$u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow … \Rightarrow u_k \Rightarrow v$$
其中 $k \geqslant 0$，则称$u$ 派生 $v$，记作 $u \overset{*}{\Rightarrow} v$。该语言的文法是 {$w \in \Sigma^* | S \overset{*}{\Rightarrow} w$}；