A. 四种文法的类型(编译原理)
乔姆斯基（Chomsky）按产生式的类型把文法分为四种类型：0、1、2、3型文法。
*在下文中的产生式中，箭头左边的大写字母为严格的非终结符，而其左边的小写字母不严格要求为非终结符，如[0型文法]中的第2条产生式。
【0型文法】
产生式形式：α→β
要求：箭头左边的α 至少 含有 一个非终结符 ， 其余 不加任何限制
例如，G：C→AaB
aA→a
B→b|Bb
【1型文法】
产生式形式：α→β
要求： |α|≤|β| (产生式左端的长度<=右端的长度)，S→ε除外。
例如G： C→aAB
aA→aBa
B→b|Bb
【2型文法】(上下文无关文法)
产生式形式：A→β，A∈VN(终结符) ，β∈V *(VN∪VT，即可为终结符也可为非终结符)
说明：当以β替换A时，与A的上下文环境无关；
大部分程序设计语言近似于2型文法。
【3型文法】(正规文法 / 右线性文法)
产生式形式：A→a，A→aB，
说明：a∈VT(终结符) ， A，B∈VN(非终结符)，即产生式右端的第一个符号必须为 终结符
例如 G：A→aB
B→b|bB
【其他说明】对于这四种类型的文法：
*包含关系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'译为A包含B)
*严格程度：3 > 2 > 1 > 0
*判断文法所属类型的顺序：3 → 2 → 1 → 0