编译原理：上下文无关文法 CFG

Fuzzing 中的一篇重要文章 NAUTILUS 中提到了CFG，即上下文无关文法，特此回顾。
CFG（又称 2 型文法）的特点：它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。

文法是一组替换规则，类似于英文中的语法，He gave me a book，He 是主语，gave 是谓语，me 是间接宾语，a book 是直接宾语。
那么可以抽象为以下文法

<句子> -> <主语><谓语><间接宾语><直接宾语>
<主语> -> <代词>
<谓语> -> <动词>
<间接宾语> -> <代词>
<直接宾语> -> <冠词><名词>
<代词> -> He

箭头表示定义，如一个句子可以由 主语+谓语+间接宾语+直接宾语 构成。

一、语法描述的几个基本概念

（1）ε 是空字，它不包含任何字符。
（2）∑ 是字母表，表示有穷字符集。如∑={a, b}
（3）∑* 是 ∑ 上所有字的全体，字是由 ∑ 中字符构成的有穷序列。如 ∑* = {a, b, aa, bb, ab, ba, aaa, …}
（4）假设 V 是 ∑* 的子集，则有 V⁰ = {ε}，V* = V⁰ U V¹ U V² U …，V* 称为 V 的闭包。
（5）V⁺ 称为 V 的正规闭包，它和闭包的区别是它不包含 ε。

二、上下文无关文法 Context-Free Grammar

上下文无关文法 G 由一个四元组组成 (T, N, S, P)。

1. T 是终结符集合，它非空。终结符是不可再被分解和定义的单位，如前面英语语法中的He。
2. N 是非终结符集合，也非空，且 T 和 N 的交集为空集。非终结符是可以再分解和定义的，如<句子>、<主语>等。
3. S 是文法的开始符号，S 是一种非终结符，如前面的<句子>是一个开始符号。
4. P 是产生式的集合，如前面英语语法的定义规则。