上下文无关文法是描述程序语言语法的强有力的数学工具
3型文法：正则文法：词法结构
2型文法：上下文无关文法：语法结构
1型文法：上下文有关文法
0型文法：任意文法
每一个外部文法（大圈）都比内部文法（小圈）表达能力强
举个自然语言处理的例子 自然语言中的句子的典型结构 主语 谓语 宾语名词 动词 名词 例子： 名词：{羊， 老虎， 草， 水}动词：{吃， 喝} 句子： 羊 吃 草羊 喝 水老虎 吃 老虎草 吃 老虎…对这个例子，我们进行形式化分析：
（S表示句子，->表示推出，N表示名词，V表示动词）
S -> N V N N -> s(sheep) | t(tiger) | g(grass) | w(water)V -> e(eat) | d(drink)我们将其中的大写符号叫做非终结符：{S, N, V}
将小写的符号（名词+谓词）叫做终结符：{s, t, g, w, e, d}
开始符号是：S
上下文无关文法上下文无关文法 G 是一个四元组：
G = ( V T , V N , P , S ) G = (V_T,V_N,P,S) G=(VT,VN,P,S)
其中 V T V_T VT是终结符集合 V N V_N VN是非终结符集合P是一组产生式规则 每条规则的形式： X − > β 1 β 2 . . . β n , n > = 0 ， X ∈ V N , β i ∈ ( V T ⋃ V N ) X -> beta_1 beta_2 ... beta_n, n >= 0，X in V_N,beta_i in (V_T bigcup V_N) X−>β1β2...βn,n>=0，X∈VN,βi∈(VT⋃VN) S是唯一的开始符号（非终结符） S ∈ V N S in V_N S∈VN对于之前给出的上下文无关文法的例子
S -> N V N N -> s | t | g | wV -> e | d非终结符号： V N = S , N , V V_N = {S, N, V} VN=S,N,V
终结符号： V T = s , t , g , w , e , d V_T = {s, t, g, w, e, d} VT=s,t,g,w,e,d
开始符号： S S S
最左推导和最右推导 最左推导：每次总是选择最左侧的符号进行替换 即对于上例中的 N V N ，首先替换最左边的 N， 再替换之后最左侧的非终结符 V， 最后替换最有一个非终结符 N 最右推导：每次总是选择最右侧的符号进行替换 语法分析给定文法 G 和句子 S， 语法分析要回答的问题：是否存在对句子 S 的推导？
若仍然选择上面的文法 G，当 S = t d g 时，我们能够实现 S 通过若干步的推导得到 t d g。所以回答 是。
若 S = t d d， 则不能实现该推导，回答 否。