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型文法更多在理论层面研究语言的边界和能力。这些实例体现了不同文法在描述语言结构上的特点和适用场景。