Chomsky（乔姆斯基）将文法分为四类
Chomsky（乔姆斯基）将文法分为四类，具体如下：
1. 0型文法（短语文法/无限制文法）
- 产生式形式：对于任一产生式(\alpha \to \beta)，要求(\alpha \in (V_N \cup V_T)^+)（即(\alpha)是由非终结符(V_N)和终结符(V_T)组成的非空符号串）且至少包含一个非终结符，(\beta \in (V_N \cup V_T)^*)（(\beta)是由非终结符和终结符组成的任意符号串，包括空串）。
- 特点：对产生式的限制最少，几乎可以描述任何语言，但计算能力强，对应的语言称为0型语言（递归可枚举语言）。
2. 1型文法（上下文有关文法）
- 产生式形式：对于任一产生式(\alpha \to \beta)，要求(|\alpha| \leq |\beta|)（(\alpha)的长度小于等于(\beta)的长度），但(S \to \varepsilon)（(S)为开始符号，(\varepsilon)为空串）除外；也可表述为产生式形式为(\alpha A \beta \to \alpha \mu \beta)，其中(A \in V_N)，(\alpha, \beta \in (V_N \cup V_T)^*)，(\mu \in (V_N \cup V_T)^+)，即非终结符(A)只有在(\alpha)和(\beta)的上下文环境中才能替换为(\mu) 。
- 特点：比0型文法限制更严格，体现了“上下文有关”的特性（非终结符的替换依赖于其周围的符号），对应的语言称为1型语言（上下文有关语言）。
3. 2型文法（上下文无关文法）
- 产生式形式：对于任一产生式(\alpha \to \beta)，要求(\alpha \in V_N)（(\alpha)是单个非终结符），(\beta \in (V_N \cup V_T)^*)（(\beta)是由非终结符和终结符组成的任意符号串，包括空串）。
- 特点：非终结符的替换不依赖于其上下文（即单个非终结符可独立替换为任意符号串），是编译原理中研究的主要文法类型之一，对应的语言称为2型语言（上下文无关语言）。
4. 3型文法（正规文法/正则文法）
- 产生式形式：分为两种情况：
- 右线性文法：产生式形式为(A \to aB)或(A \to a)，其中(A, B \in V_N)，(a \in V_T)（非终结符(A)替换为一个终结符(a)后可接一个非终结符(B)，或直接替换为一个终结符(a)）；
- 左线性文法：产生式形式为(A \to Ba)或(A \to a)，其中(A, B \in V_N)，(a \in V_T)（非终结符(A)替换为一个非终结符(B)后接一个终结符(a)，或直接替换为一个终结符(a)）。
- 特点：对产生式的形式限制最严格，可描述正则语言（如程序设计语言中的词法规则），对应的语言称为3型语言（正规语言/正则语言）。
总结
这四类文法的限制条件逐渐增强（0型→1型→2型→3型），语言的表达能力逐渐减弱（0型语言包含1型语言，1型语言包含2型语言，2型语言包含3型语言）。它们的核心区别在于产生式的形式要求，尤其是对产生式左部（(\alpha)）和右部（(\beta)）的结构限制不同。
Chomsky文法的四类文法在实际场景中都有各自的应用实例，以下结合不同文法类型进行说明：
1. 3型文法（正规文法/正则文法）
- 应用场景：程序设计语言的词法分析。例如，在C语言中，标识符的定义规则（由字母或下划线开头，后接字母、数字或下划线）可以用正规文法描述。
- 产生式示例（右线性文法）：
定义非终结符(A)表示标识符的构造过程，终结符(a)、(b)、(\cdots)、(z)、(A)、(B)、(\cdots)、(Z)、(0)、(1)、(\cdots)、(9)、(_)表示字母、数字和下划线。
产生式可以写成：
(A \to aA)
(A \to bA)
(\cdots)
(A \to zA)
(A \to AA)
(\cdots)
(A \to ZA)
(A \to 0A)
(\cdots)
(A \to 9A)
(A \to _A)
(A \to a)
(A \to b)
(\cdots)
(A \to z)
(A \to A)
(\cdots)
(A \to Z)
(A \to 0)
(\cdots)
(A \to 9)
(A \to _)
通过这些产生式，可以推导出如abc、_123、Hello等合法的C语言标识符，也能识别不合法的标识符（如123abc，因为无法通过以非数字或下划线开头的产生式推导得到）。
2. 2型文法（上下文无关文法）
- 应用场景：程序设计语言的语法分析（描述语法规则）。以算术表达式的语法规则为例，比如算术表达式可以由表达式、运算符和因子组成。
- 产生式示例：
定义非终结符(E)（表达式）、(T)（项）、(F)（因子），终结符(+)、(-)、(\times)、(/)、(()、())、(i)（表示变量或常量）。
产生式为：
(E \to E + T)
(E \to E - T)
(E \to T)
(T \to T \times F)
(T \to T / F)
(T \to F)
(F \to (E))
(F \to i)
以推导算术表达式(i \times (i + i - i))为例（对应知识背景中对合法算术表达式的推导过程）： - 从(E)开始，(E \Rightarrow T)（根据(E \to T)）；
- (T \Rightarrow T \times F)（根据(T \to T \times F)）；
- (T \Rightarrow T)（保持(T)暂不进一步推导，先处理(F)），(F \Rightarrow (E))（根据(F \to (E))）；
- 此时(E)需要推导为(i + i - i)，先(E \Rightarrow E + T)（根据(E \to E + T)）；
- (E \Rightarrow E - T)（根据(E \to E - T)）；
- 然后将(E)和(T)逐步推导为(i)：(E \Rightarrow T \Rightarrow F \Rightarrow i)，(T \Rightarrow F \Rightarrow i)，(T \Rightarrow F \Rightarrow i)；
- 最终得到(i \times (i + i - i))，这展示了上下文无关文法在描述算术表达式语法结构上的应用，能判断一个表达式是否符合语法规则（如(i + (i)这种缺少右括号的表达式无法通过该文法的推导得到，因此是不合法的）。
3. 1型文法（上下文有关文法）
- 应用场景：描述自然语言中的一些复杂语法现象（如特定语境下词汇的搭配规则），或者某些具有上下文依赖的程序结构（如特定作用域内变量的定义和使用规则，不过实际中较少直接用1型文法描述程序结构，更多用于理论研究）。
- 示例：
定义一个简单的语言，描述“在‘book’的上下文中，‘read’才能被替换为‘reads’（表示第三人称单数的语法变化）”，非终结符(S)、(A)，终结符(read)、(reads)、(book)、(the)。
产生式为：
(S \to the A book)
(A \to read)
(the A book \to the reads book)（这里(A)在“the”和“book”的上下文（即(the) _ (book)）中才能由(read)变为(reads)，符合1型文法(\alpha A \beta \to \alpha \mu \beta)的形式，其中(\alpha = the)，(\beta = book)，(A = A)，(\mu = reads)）
通过这些产生式，只能推导出如“the read book”（普通形式）或“the reads book”（第三人称单数形式）这样的句子，而无法推导出“reads the book”（因为(A)的替换依赖于“the”和“book”的上下文，不符合上下文要求时不能进行(read)到(reads)的替换），体现了上下文有关文法对上下文依赖的描述能力。
4. 0型文法（短语文法/无限制文法）
- 应用场景：主要用于理论研究，因为其产生式几乎没有限制，能描述非常广泛的语言，但实际中很少直接应用（因为难以控制和分析）。不过可以构造一个简单的示例来理解其形式。
- 示例：
定义非终结符(A)、(B)，终结符(a)、(b)。
产生式为：
(AaB \to aaBb)
(A \to \varepsilon)（空串）
(B \to \varepsilon)
从(AaB)开始推导： - (AaB \Rightarrow aaBb)（根据(AaB \to aaBb)）；
- 然后可以选择应用(A \to \varepsilon)，得到(aBb)；
- 再应用(B \to \varepsilon)，得到(ab)；
或者也可以有其他推导路径，比如多次应用(AaB \to aaBb)后再消除(A)和(B)，能产生如(a^n b^n)（(n\geq1)）这样的语言（不过更复杂的0型语言可能包含无法用更受限文法描述的结构）。
总结
不同类型的Chomsky文法在实际中有着不同的应用：3型文法常用于词法分析（如编程语言的词法规则）；2型文法是语法分析的核心（如描述算术表达式、程序语句的语法结构）；1型文法可用于描述有上下文依赖的语言现象（如自然语言的部分语法规则）；0型文法更多在理论层面研究语言的边界和能力。这些实例体现了不同文法在描述语言结构上的特点和适用场景。