乔姆斯基把方法分成四种类型，即0型、1型、2型和3型，源于《编译原理》，但《软件设计师》教程对于该分类的介绍很简略，也很抽象，根据网上各类博客对其的解释和教程的说法，大致总结如下：
首先要阐明的是，
一般的文法至少都是0型文法，也就是说0型文法限制最少，二1,2,3型文法都是在0型文法基础上加以限制形成。
若将0型文法比作基类的话，1,2,3,4就是不断继承并加以限制得到的子类。
①0型文法
设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。0型文法也称短语文法。
0型文法的能力相当于图灵机(Turing)。
我们发现0型文法是限制最少的一种文法，平时见到的文法几乎都属于0型文法。
②1型文法
1型文法也叫上下文有关文法
，此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。
如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。
③2型文法
2型文法也叫上下文无关文法
，它对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。
如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。
④3型文法
3型文法也叫正规文法
，
它对应于有限状态自动机
。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。
如有：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结符＋一个终结符”的形式（即为aB）就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。
那么这四类文法如何判断呢？
其实四种文法就是规定产生式的左和右边的字符的组成规则不同而已，于是我们便可以严格根据左边和右边规则的不同来加以判断。
首先，应该明确，四种文法，从0型到3型，其规则和约定越来越多，限制条件也越来越多，
所以我们应该按照3->2->1->0的顺序去判断，一旦满足前面的规则，就不用去判断后面的了。
1.先来看看3型文法的判断规则
①：左边必须只有一个字符，且必须是非终结符；
②：其右边最多只能有两个字符，要么是一个非终结符+终结符（终结符+非终结符），要么是一个终结符。
③：对于3型文法中的所有产生式，若其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须满足终结符+非终结符。反之亦然。
2.再看看2型文法判断规则
①：与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。
②：2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。
3.最后再看看1型文法判断规则
①：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
②：与2型文法第二点相同，但需要满足|α|≤|β|.
0型文法不需要判断了，一般的文法都是0型文法。 O(∩_∩)O
乔姆斯基把方法分成四种类型，即0型、1型、2型和3型，源于《编译原理》，但《软件设计师》教程对于该分类的介绍很简略，也很抽象，根据网上各类博客对其的解释和教程的说法，大致总结如下：首先要阐明的是，一般的文法至少都是0型文法，也就是说0型文法限制最少，二1,2,3型文法都是在0型文法基础上加以限制形成。若将0型文法比作基类的话，1,2,3,4就是不断继承并加以限制得到的子类。①0型文法
1.处理
文法
的语法分析器大体上可以分为三种类
型
：通用的，自顶向下的和自顶向上的。
2.
文法
：一种用于描述程序设计语言语法的表示方法——“上下文无关
文法
”，简称“
文法
”。
3.一个上下文无关
文法
（
文法
）有四个元素组成：
文法
G可以抽象成四元组的形式：G=(VN,VT,P,S)
其中VN表示非终结符集，VT表示终结符集，P表示产生式集，S表示开始符号。
（1）一个终结符号集...
一、正则
文法
（3
型
）
定义：如果
文法
G=(N, Σ, P, S) 的 P 中的规则满足如下形式：A → B x（这里注意B只是一个形式，代表非终结符），或 A → x，其中 A, B ∈ N，x ∈ Σ， 则称该
文法
为正则
文法
（简写为 FSG）或称3
型
文 法。（左线性正则
文法
）（如果 A → x B，则该
文法
称为右线性正则
文法
。）
例如有如下规则：A→ Ax，A → x。那么可以推出AA...
文 法 和 语 言 的 分 类
著名的语言学家
乔姆斯基
(Chomsky )将
文法
和语言分为 4 大类,即 0
型
、1
型
、 2
型
和 3
型
。划分的依据是对
文法
中的规则施加不同的限制。
1.0
型文法
(无限制
文法
)
若
文法
G = (V N , V T , P , S )中的每条规则 α → β 是这样一种结构:
α ∈ ( V N ∪ V T )**且至少含一个非终结符,而 β ∈ (V N ∪ VT )*,则称 G是 0
型文法
。0
型文法
描述的语言是 0
型
语言。
由定义可见,α 和 β 均是
文法
的.
在
文法
的
乔姆斯基
体系中，
文法
被分为4类，分别是0
型文法
、1
型文法
、2
型文法
、3
型文法
。具体释义和特点如下：
一、0
型文法
:也叫短语结构
文法
或无限制
文法
，其描述能力相当于图灵机，可使用任何的语法描述形式;
二、1
型文法
:也叫上下文有关
文法
，其描述能...
0
型文法
也叫短语结构
文法
，PSG。0
型
语言PSL也叫短语结构语言或递归可枚举集。
1
型文法
也叫上下文有关
文法
，CSG。1
型
语言CSL也叫上下文有关语言。
2
型文法
也叫上下文无关
文法
，CFG。2
型
语言CFL也叫上下文无关语言。
3
型文法
也叫正则
文法
或正规
文法
，RG。3
型
语言RL也叫正则语言或正规语言。分左线性
文法
和右线性
文法
。
四者之间为包含关系。
Chomsky
文法
分类
体系
文章目录Chomsky
文法
分类
体系0
型文法
(Type-0 Grammar)1
型文法
(Type-1 Grammar)2
型文法
(Type-2 Grammar)3
型文法
(Type-3 Grammar)四种
文法
之间的关系
0
型文法
(Type-0 Grammar)
\alpha \rightarrow{\beta}
无限制
文法
/短语结构
文法
∀α→β∈P\fora...
乔姆斯基
（Chomsky)把
文法
分成四种类
型
0
型
、1
型
、2
型
和3
型
。
0
型文法
也称为短语
文法
，其能力相当于图灵机，任何0
型
语言都是递归可枚举的；反之，递归可枚举集也必定是一个0
型
语言。
1
型文法
也称为上下文有关
文法
，这种
文法
意味着对非终结符的替换必须考虑上下文。
2
型文法
就是上下文无关
文法
，非终结符的替换无需考虑上下文。
3
型文法
等价于正规式，因此也被称为正规
文法
或线性
文法
。通用程序设
有
文法
中的一个产生式 α -> β。
0
型文法
：α中至少包含一个非终结符
1
型文法
：也就是上下文有关
文法
(CSG) 满足 |α| <= |β| ，|x|表示x的符号个数。也就是α1Aα2 -> α1Bα2(且B不为空)
2
型文法
：也就是上下文无关
文法
(CFG)，即α只能为V
形式化方法
形式化方法，也称形式方法、正规方法。在计算机科学和软件工程领域，形式化方法是基于数学的特种技术，适合于软件和硬件系统的描述、开发和验证。将形式化方法用于软件和硬件设计，是期望能够像其它工程学科一样，使用适当的数学分析以提高设计的可靠性和强健性。但是，由于采用形式化方法的成本高意味着它们通常只用于开发注重安全性的高度整合的系统。
形式验证：在计算机硬件（特别是集成电路）和软件系统的设计过程中，形式验证的含义是根据某个或某些形式规范或属性，使用数学的方法证明其正确性或非正确性。
在计算机硬件（特别是
这四个
文法
都是采用的四元式，有区别的地方在于产生式α→β\alpha\rightarrow\betaα→β
对于0
型文法
α→β\alpha\rightarrow\betaα→β
α∈(VT∪VN)∗\alpha\in(V_T \cup V_N)^*α∈(VT∪VN)∗且α\alphaα必含有至少一个非终结符
