【程序语言与编译】文法的分类（0-3型，乔姆斯基体系）-编程阁

适合读者：软考中级备考同学
阅读时间：3分钟
内容：0-3型文法的定义、产生式形式、对应自动机、对比表、例题

1. 为什么需要文法分类？

形式语言理论中，乔姆斯基（Chomsky）根据产生式的限制条件将文法分为四个层次：0型、1型、2型、3型。不同类型的文法描述不同复杂程度的语言，对应不同的自动机识别能力。软考中常考查各类文法的定义、产生式形式及其对应的自动机。

2. 乔姆斯基文法体系

所有文法用四元组G=(VT,VN,P,S)G = (V_T, V_N, P, S)G=(VT,VN,P,S)表示，其中VTV_TVT为终结符集，VNV_NVN为非终结符集，PPP为产生式集，SSS为开始符号。不同类型文法的区别在于对产生式α→β\alpha \rightarrow \betaα→β的形式限制不同。

2.1 0型文法（短语结构文法，PSG）

产生式形式：α→β\alpha \rightarrow \betaα→β，其中α\alphaα至少包含一个非终结符，α,β∈(VT∪VN)∗\alpha, \beta \in (V_T \cup V_N)^*α,β∈(VT∪VN)∗，无其他限制。
特点：最强大的文法，可以生成任何可枚举语言。
对应自动机：图灵机（Turing Machine）。
软考提示：0型文法理论意义大于实用，几乎不直接考查。

2.2 1型文法（上下文有关文法，CSG）

产生式形式：αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβ，其中A∈VNA \in V_NA∈VN，α,β,γ∈(VT∪VN)∗\alpha, \beta, \gamma \in (V_T \cup V_N)^*α,β,γ∈(VT∪VN)∗，γ≠ε\gamma \neq \varepsilonγ=ε（非空）。即AAA必须在特定上下文（α\alphaα和β\betaβ）中才能替换为γ\gammaγ。
特点：产生式左部长度 ≤ 右部长度（非收缩）。
对应自动机：线性有界自动机（Linear Bounded Automaton）。
软考考点：知道“上下文有关”意味着替换受周围符号限制，通常不要求深入。

2.3 2型文法（上下文无关文法，CFG）

产生式形式：A→γA \rightarrow \gammaA→γ，其中A∈VNA \in V_NA∈VN（单个非终结符），γ∈(VT∪VN)∗\gamma \in (V_T \cup V_N)^*γ∈(VT∪VN)∗（可为空串ε\varepsilonε）。
特点：左部只有一个非终结符，与上下文无关。这是程序设计语言语法描述的核心工具。
对应自动机：下推自动机（Pushdown Automaton, PDA）。
软考重点：大部分语法分析（如算术表达式、语句结构）用上下文无关文法描述。

2.4 3型文法（正则文法，RG）

产生式形式（右线性）：A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a，其中A,B∈VNA, B \in V_NA,B∈VN，a∈VTa \in V_Ta∈VT（也可有ε\varepsilonε产生式）。
特点：产生式右部最多一个非终结符且必须在最右端（右线性）；左线性形式为A→BaA \rightarrow BaA→Ba或A→aA \rightarrow aA→a。两种形式等价。
对应自动机：有限自动机（Finite Automaton, FA）。
软考重点：正则文法与正则表达式、有限自动机等价，常用于词法分析。

3. 四种文法的对比表

类型	名称	产生式形式	对应自动机	能力	典型应用
0型	短语结构文法	α→β\alpha \rightarrow \betaα→β（无限制）	图灵机	最强	理论计算机
1型	上下文有关文法	αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβ（γ≠ε\gamma \neq \varepsilonγ=ε）	线性有界自动机	强	自然语言处理
2型	上下文无关文法	A→γA \rightarrow \gammaA→γ	下推自动机	中等	程序设计语言语法
3型	正则文法	A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a	有限自动机	最弱	词法规则、模式匹配

包含关系：3型⊂\subset⊂2型⊂\subset⊂1型⊂\subset⊂0型（越往上描述能力越强）。

4. 软考常见考点

判断文法类型：给定一组产生式，判断属于0/1/2/3型。
- 若产生式全部形如A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a→ 3型（正则）。
- 若产生式全部左部为单个非终结符，但右部有多个非终结符嵌套（如E→E+TE \rightarrow E+TE→E+T） → 2型（上下文无关）。
- 若产生式左部包含多个符号（如aA→BcaA \rightarrow BcaA→Bc） → 1型或0型（通常考0型/1型区别）。
对应自动机：知道正则文法 ↔ 有限自动机，上下文无关文法 ↔ 下推自动机。
实际意义：词法分析用3型（正则表达式），语法分析用2型（上下文无关文法）。

5. 经典例题

题目1：给定文法GGG的产生式如下：

S → aB | bA A → aS | bAA | a B → bS | aBB | b

该文法属于乔姆斯基体系中的哪一型？

解析：所有产生式左部都是单个非终结符（S,A,BS, A, BS,A,B），右部由终结符和非终结符组成，没有上下文限制。符合2型（上下文无关文法）的定义。
答案：2型（上下文无关文法）

题目2：下列文法中，属于正则文法的是（）。
A.S→aSb ∣ εS \rightarrow aSb \,|\, \varepsilonS→aSb∣ε
B.S→Aa,A→Bb,B→cS \rightarrow Aa, A \rightarrow Bb, B \rightarrow cS→Aa,A→Bb,B→c
C.S→aA,A→Sb,S→εS \rightarrow aA, A \rightarrow Sb, S \rightarrow \varepsilonS→aA,A→Sb,S→ε
D.S→aA,A→bS \rightarrow aA, A \rightarrow bS→aA,A→b

解析：

A 产生anbna^n b^nanbn，不是正则文法（需记忆计数） → 2型。
B 产生式有S→AaS \rightarrow AaS→Aa（左线性），但A→BbA \rightarrow BbA→Bb也是左线性，整体可转为右线性吗？不是标准右线性，但左线性等价于正则，可接受。需要判断：若所有产生式形如A→aA \rightarrow aA→a或A→aBA \rightarrow aBA→aB或A→BaA \rightarrow BaA→Ba（左线性），仍属3型。但B中S→AaS \rightarrow AaS→Aa（左线性），A→BbA \rightarrow BbA→Bb（左线性），B→cB \rightarrow cB→c（终结），是左线性正则文法。
C 有A→SbA \rightarrow SbA→Sb（左线性），但S→aAS \rightarrow aAS→aA（右线性），混合形式仍然等价正则，不过通常要求统一方向，但理论上正则文法允许左线性和右线性混合？严格说混合可能产生非正则语言？软考中一般要求统一。C有S→εS \rightarrow \varepsilonS→ε也是允许的。但C中A→SbA \rightarrow SbA→Sb和S→aAS \rightarrow aAS→aA导致S⇒aA⇒aSbS \Rightarrow aA \Rightarrow aSbS⇒aA⇒aSb，产生类似anSbna^n S b^nanSbn，不是正则。
D 所有产生式S→aAS \rightarrow aAS→aA（右线性），A→bA \rightarrow bA→b（右线性），符合3型。
答案：D

题目3：与上下文无关文法对应的自动机是（）。
A. 有限自动机
B. 下推自动机
C. 图灵机
D. 线性有界自动机

答案：B

6. 记忆口诀

0型无限制，图灵机最强；
1型上下文，线性有界忙；
2型无关文，下推自动掌；
3型正则规，有限自动行。

7. 给备考同学的一句话

软考中文法的分类主要考查2型和3型：

看到产生式只有A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a形式 → 3型（正则）。
看到产生式左部是单个非终结符，但右部有像A→BCA \rightarrow BCA→BC或A→aBcA \rightarrow aBcA→aBc等嵌套形式 → 2型（上下文无关）。
如果产生式左部有多个符号（如aA→BbaA \rightarrow BbaA→Bb），通常属于1型或0型（软考一般不会考这么深）。