Intro
上下文无关语言（Context Free Language）是一类比正则语言更强的语言。描述上下文无关语言的文法叫上下文无关文法（CFG）。
CFG
上下文无关文法定义为四元组 \(G=(T,V,S,P)\)，其中
- \(T\) 是符号集，也叫Terminals
- \(V\) 是变量集
- \(S\) 是初始变量
- \(P\) 是产生式的集合（Set of Productions）
定义 \(T^*\) 是串，\((T\cup V)^*\) 是句子（sentential form）
上下文无关文法的大概想法是这样的：我们总是可以从初始变量开始，通过不断地把一个句子中的符号替换成另一个句子，最终得到一个串。这里“替换”指的就是关于产生式的应用，并且“上下文无关”的名字来源于“我们可以无脑替换”这一操作策略。
一个比较无聊的帮助理解的例子是这样的：可以把变量看成 STLC 里的变量，然后在最前面加上 quantifier，这样所谓的应用产生式就是 function application，串就是 value，产生式就是 function。
若 \(S\) 能经过若干步替换得到句子 \(\alpha\)，我们就写作 \(S\Rightarrow^* \alpha\)，称 \(S\) 推导出（derives）\(\alpha\)。通常不要求 \(S\) 一定是变量。
很显然 CFG \(G=(T,V,S,P)\) 定义的语言就是 \(\Set{s\mid S\Rightarrow^* s}\)
Derivation
这部分比较绕。
注意到在定义“推导”的时候我们并没有规定替换符号的顺序，因此给定语法 \(G\) 时，对于某个串 \(s\) 可能存在多个推导序列。一个平凡的例子是 \(S\rightarrow AA, A\rightarrow 0\)
- \(S\Rightarrow AA\Rightarrow 0A\Rightarrow 00\)
- \(S\Rightarrow AA\Rightarrow A0\Rightarrow 00\)
当然我们更关注的其实是推导作为树的结构，而不是线性序的形状，因此可以通过限定变量替换的顺序来得到推导树与推导序列的双射。常用的就是最左和最右推导。
关于双射的证明可以用简单的归纳得到...
Ambiguity
消除了线性序上的歧义还不够，对于给定的 \(G\) 和串 \(s\)，如果存在 \(s\) 的两个不同推导树，那么就称 \(G\) 是有歧义的（ambiguous）。由推导树与最左推导的双射可知，\(G\) 有歧义 iff 存在 \(s\) 有两个不同的最左推导。
注意到这里的歧义是语法的性质，如果是编译课就会讲怎么设计文法消除歧义。但实际上并非所有的上下文无关语言都能消除歧义，一个例子是 \(L=\Set{0^i1^j2^k\mid i=j\vee j=k}\)：
- 先推出 \(i=j\)，再推 \(j=k\)
- 先推出 \(j=k\)，再推 \(i=j\)
Normal Form
讲的是对于给定的语法 \(G\)，怎么化简得到等价的 \(G'\)。
这里需要特殊处理一下 \(\epsilon\)。若 \(\epsilon\in L(G)\)，那么我们实际上可以构造 \(G'\) 使得 \(L(G')=L(G)-\Set{\epsilon}\)，最后单独考虑 \(\epsilon\) （通过单独加产生式）。之所以特殊处理是为了形式更简单更好看（\(\epsilon\) 在连接操作下是幂等的，可以任意出现而不改变语言，神出鬼没）。
\(\epsilon\)-Production
若 \(V\Rightarrow \epsilon\)，那么就称这个产生式是 \(\epsilon\)-Production，这一步的目的是去掉长成这样的产生式。
Identification
归纳地定义变量上的谓词 \(\text{Nullable}\) 如下：
- 若 \(V\to \epsilon\)，则 \(\text{Nullable}(V)\)
- 若 \(V\to \alpha\)，且对 \(\alpha\) 中的任意变量 \(X\) 都有 \(\text{Nullable}(X)\)，则 \(\text{Nullable}(V)\)
容易看出 \(\text{Nullable}(V)\) 的含义是 \(V\Rightarrow^* \epsilon\)。
Removal
对于一条产生式 \(V\to \alpha\)，我们可以根据 \(\text{Nullable}()\) 的结果将这条产生式变成若干产生式。
具体而言是这样的，假设 \(A\in\text{Nullable}\)，那么我们必然可以引入中间变量 \(A'\) 写成如下形式：
- \(A\to \epsilon\)
- \(A\to A'\)，且 \(A'\not\in \text{Nullable}\)
当 \(A\) 出现在产生式的右侧时，我们不能直接删去1，考虑这个例子：
\(S\to AB\)，\(A\to \epsilon\mid a\)，\(B\to b\)，这个语法规定的语言是 \(\Set{ab,b}\)。假设我们删掉了 \(A\to\epsilon\)，那么语言就会变成 \(\Set{ab}\)，这样引入了语义变化。
注意到表达“空”有两种办法：
- 变量推导出 \(\epsilon\)
- 从产生式里删掉这个变量
因此可以先构造 \(S\to A'B\mid B\) 来语法化表示 \(\epsilon\)，此处的 \(A'\) 定义为 \(A'\to a\)，这样就维持了语义等价。
推广到产生式右侧有 \(k\) 个 \(\text{Nullable}\) 变量，那么就是新构造 \(2^k\) 个产生式，然后分别递归消消乐就好了。
Unit Production
Unit Production 说的是形如 \(A\to B, B\to C\) 这样的产生式。
如果 \(A\Rightarrow ^* B\)，且 \(B\to \alpha\)，\(\alpha\) 中不止一个变量，那么就引入新产生式 \(A\to \alpha\)。
反复添加直至收敛，然后就可以删去那些 Unit Production 了。
这个有点 copy propagation 的感觉，或者可以认为是图的 contraction。
Divergent
如果一个符号 \(A\) 满足 \(L(A)=\varnothing\)，那么以 \(A\) 为起点的推导将永不终止。这样的符号也可以直接删掉。
Identification
构造谓词 \(\text{Stoppable}\) 如下：
- 若 \(V\to s\)，那么 \(\text{Stoppable}(V)\)
- 若 \(V\to\alpha\)，且 \(\alpha\) 中的一切变量 \(X\) 都有 \(\text{Stoppable}(X)\)，那么 \(\text{Stoppable}(V)\)
Removal
对于 \(V\not\in \text{Stoppable}\)，删去 \(V\) 所处的产生式（左侧和右侧都算出现）
Unreachable
若 \(S\not\Rightarrow^* V\)，那么 \(V\) 就是 unreachable symbol，它和它的产生式都可以直接删掉。
这个就是 deadcode 了。
CNF
大名鼎鼎的 Chomsky Normal Form
大概意思是在做完上面那些 clean up 之后，我们的语法中的产生式右侧长度至少为 \(2\)（没有 Unit Production 和 \(\epsilon\)-Production）
那么可以人为地引入变量把语法树变成二叉的，并且叶子全是 \(V\to c\)，\(c\in\Sigma\) 这样的形式。
之所以这么做是为了证明上的方便，比如 CNF 的形式可以给树高估一个界。