三、上下文无关语言
1. 上下文无关文法（Context Free Grammar, CFG）
上下文无关文法G是一个四元组(V, ∑, R, S)，其中，
- V是一个字母表
- ∑是终结符集合，它是V的子集
- R是规则集合，它是(V-∑) ×V★的有穷子集
- S∈V -∑是起始符号
- V -∑的成员是非终结符
G生成的语言L(G)为{ω∈∑★:S=>ω}，也说G生成L(G)中的每一个字符串。如果L=L(G)，其中G是一个CFG，则称L是一个上下文无关语言(Context Free Language, CFL)。
假设存在一个上下文无关文法G=(V, ∑, R, S)。如果其中的R≤(V -∑)×∑★((V -∑)∪{ε})，即每个规则的右边都是一个终结符串至多再跟一个非终结符，则称G是右线性的。类似的，如果其中的R≤(V -∑)× ((V -∑)∪{ε})∑★，即每个规则的右边都是至多一个非终结符再跟一个终结符串，则称G是左线性的。可以证明，右线性文法、左线性文法和正则文法的表达能力是等价的。这说明了一个结论，上下文无关文法的表达能力比正则文法的表达能力强。
2. 语法分析树（Syntax Parser Tree, SPT）
从起始符号开始，根据CFG的规则生成字符串的过程，称为推导过程。该推导过程可以用语法分析树来表示。不同顺序的推导过程可以对应同一棵语法分析树，只要它在生成字符串的每个部分时使用相同的规则——尽管可能使用的顺序不同。语法分析树表示推导的等价类，因为它隐蔽了由于按不同的顺序使用规则而造成的推导过程的差异。在这个推导的等价类中，必然有最左推导和最右推导。
如果一个CFG生成的字符串有两棵以上不一样的语法分析树，或等价地，有两个不同的最左（右）推导，就称该CFG是有歧义的。把一棵语法分析树赋给某语言的一个给定的字符串，即对该字符串做语法分析，是理解它的结构、理解它属于这个语言的原因，以及最终理解它的语义的基础。因此，在程序设计语言中，是不允许使用有歧义的文法的。幸运的是，对于很多有歧义的CFG，可以通过进行修改，得到等价（即生成相同语言）的非歧义的文法。但是，还是存在这样的CFL：生成它的所有CFG一定是歧义的。这样的CFL称为固有歧义的。幸运的是，程序设计语言不会是固有歧义的。
3. 下推自动机(Push Down Automata, PDA)
对于超出右（左）线性文法表达能力的上下文无关语言，有穷自动机是无法实现的。给有穷自动机增加一些额外的特性，就能够满足这一要求。新的自动机叫做下推自动机。下推自动机是一个六元组M= (K, ∑, Γ, △, s, F)，其中，
- K是有穷的状态集合
- ∑是字母表（所有输入符号）
- Γ是字母表（所有栈符号）
- s∈K是初始状态
- F≤K是终结状态的集合
- △是类型为(K×(∑∪{ε})×Γ★)×(K×Γ★)的关系，称为转移关系
可以看出，与有穷自动机相比，下推自动机的字母表中增加了栈符号，转移关系中也需要考虑栈符号。与有穷自动机一样，在计算中已读过的输入部分对以后的运行不再起作用，因此，下推自动机的格局定义为K×∑★×Γ★的成员。如果M可以从格局(s,ω,ε)经过有限步到达格局(q,ε,ε)，其中q∈F，那么，称字符串ω被M接受。M接受的语言是M接受的所有字符串的集合，记作L(M)。
4. 定理
(1) 下推自动机接受的语言正好是上下文无关语言类，即，上下文无关文法生成的语言和下推自动机接受的语言是等价的。
(2) 上下文无关语言在并、连接和Kleene星号下是封闭的。
(3) 一个上下文无关语言与一个正则语言的交是一个上下文无关语言。
(4) （CFL泵引理）对于任意的CFL L，存在仅仅依赖于L的正整数N，对于任意的z∈L，当|z|≥N时，存在u，v，w，x，y，使得z=uvwxy，同时满足：
a) |vwx|≤N；
b) |vx|≥1；
c) 对于任意的非负整数i ，uviwxiy∈L。
(5) 有一个多项式算法，任给一个CFG，可以构造一台等价的PDA。
(6) 有一个多项式算法，任给一个PDA，可以构造一个等价的CFG。
(7) 有一个多项式算法，任给一个CFG和一个字符串x，可以判断x∈L(G)是否成立。
(8) 没有检验任给两个CFG（或PDA）等价的算法，也没有最小化PDA的状态数的算法。
5. 确定性和语法分析
与RL不一样，并不是所有的CFL都能被确定型下推自动机识别（Definite Push Down Automata, DPDA）。就PDA而言，非确定性比确定型更强大。DPDA识别的语言称为确定型上下文无关语言，它是CFL的真子集。确定型上下文无关语言类在补运算下是封闭的。
当面临实际的程序设计语言时，我们考虑的都是能够用DPDA识别的CFL。对程序设计语言进行语法分析时，一般有两种思路：自顶向下和自底向上。在自顶向下的语法分析中，经常使用以下两种启发式规则：左因子分解和消除左递归。在自底向上的语法分析中，面对优先关系的问题时，经常使用以下两种启发式规则：用优先关系来决定是移进还是归约；最长匹配优先归约。