Chomsky文法分类体系

0型文法(Type-0 Grammar)

$$\alpha \to \beta$$
无限制文法/短语结构文法

$\forall \alpha \to \beta \in P$，$\alpha$中至少包含1个非终结符。

由0型文法生成的语言称为0型语言。

1型文法(Type-1 Grammar)

$$\alpha \to \beta$$

上下文有关文法(Context-Sensitive Grammar)：
7

• $\forall \alpha \to \beta \in P,|\alpha |\le |\beta |$
• 产生式的一般形式：${\alpha }_{1}A{\alpha }_2\to {\alpha }_1\beta {\alpha }_2(\beta ̸=ϵ)$
• 由上下文有关文法（1型文法）G产生的语言L(G)，称为1型语言（上下文有关语言）。

2型文法(Type-2 Grammar)

$$\alpha \to \beta$$

上下文无关文法（Context-Free Grammar）：

• $\forall \alpha \to \beta \in P,a\in V_N$(产生式的左部一定要是非终结符)
• 产生式的一般形式：$A\to \beta$

例如：

1. $S\to L|LT$
2. $T\to L|D|TL|TD$
3. $L\to a|b|c|...|z$
4. $D\to 0|1|2|..|9$

由上下文无关文法生成的语言称为上下文无关语言（2型语言）

3型文法(Type-3 Grammar)

3型文法又称正则文法(Regular Grammar):

• 右线性文法：$A\to \omega B$或$A\to \omega$
• 左线性文法：$A\to B\omega$或$A\to \omega$

左线性文法和右线性文法都称为正则文法。

由于左部一定是非终结符，所以3型文法满足2型文法。

正则文法能描述程序设计语言的多数单词。

四种文法之间的关系

• 逐级限制
  • 0型文法：$\alpha$中至少包含1个非终结符
  • 1型文法：$|\alpha |\le |\beta |$
  • 2型文法：$\alpha \in V_N$
  • 3型文法：$A\to \omega B$或$A\to \omega$(右线性)。$A\to B\omega$或$A\to \omega$（左线性）