前言
编译原理这种课一听就知道肯定特别晦涩难懂，上课没听懂，今天花了一天时间来学文法，看了一天也是是有些眉目，书上讲的并不是特别清楚，倒是从各大博客中汲取到不少知识。虽然感觉还只是停留在理论阶段，但也要记录一下吧，不然到时候理论都想不起来。
文法的定义
文法 G 定义为一个四元组（VN, VT, P, S)
- VN ：非终结符的非空有穷集
- VT ：终结符的非空有穷集，VN∩VT=Φ
- P ：产生式的非空有穷集
- S ：S∈VN，为文法 G 的开始符号
文法的分类
乔姆斯基(Chomsky)根据对产生式的要求不同，将文法分为四类，即：0型文法、1型文法、2型文法和3型文法，这四类文法通常称为 Chomsky 体系。
| 文法 G | 产生式结构 | 语言 L(G) |
|---|---|---|
| 0型文法(短语结构文法) | ∀α→β∈P，其中α、β∈(VT∪VN)* ，∣α∣≠0 | 0型语言(短语结构语言) |
| 1型文法(上下文有关文法) | ∀α→β∈P，其中α、β∈(VT∪VN)* ，∣α∣≤∣β∣ | 1型语言(上下文有关语言) |
| 2型文法(上下文无关文法) | ∀A→β∈P，其中A∈VN，β∈(VT∪VN)* | 2型语言(上下文无关语言) |
| 3型文法(正则文法) | ∀A→α∣αB∈P(右线性)或∀A→α∣Bα∈P(左线性)，其中，A，B∈VN，α∈VT∪{ε} | 3型语言(正则语言) |
下面的例子中，A、B∈VN, a、b∈VT, 即大写字母表示非终结符，小写字母表示终结符。
0型文法
例：A→a, Aa→aA, AA→a, AA→Aa
左边至少有一个非终结符，不然的话也就不用推导了
1型文法
例：A→a, Ab→Abc, AB→Bc
在0型文法的基础上限制右边长度不能短于左边，所以 AA→a 不是1型文法。(α→ε除外)
2型文法
例：A→a, A→aB, B→a, B→ab
在1型文法的基础上限制左边不能有终结符，所以 Ab→Abc 不是2型文法。
3型文法
例：A→a, A→aB, B→a, B→cB
在2型文法的基础上限制右边只能有一个终结符，而且左线性和右线性不能同时出现，所以 A→aa 或者 B→cB 和 B→Bc 同时出现的都不是3型文法。
