编译原理冲刺 · 第 02 课 ⏱ 冲刺模式 · ≤1周

文法基础

看懂"文法"这门课的通用语言 —— 后面 LL(1)、算符优先全靠它。对应教材第 2 章 2.3。

🎯 本课唯一目标

拿到一个文法，能说出它的四元组、写推导、画语法树、判断二义性、判断它是 Chomsky 第几型。

为什么学它？　文法是全景图里"语法分析"那一格的语言。第 4、5 章所有大题（求 FIRST/FOLLOW、LL(1)、算符优先）都建立在"看得懂文法、会推导、会画语法树"之上。这一课是地基，今天搭稳，后面省一半力。

一、文法是什么：一个四元组

一个文法记作 G[S] = (V_N, V_T, P, S)^[1]，四样东西：

V_N　非终结符集合（大写字母，如 E、T，代表"还能往下展开的语法成分"）
V_T　终结符集合（具体符号，如 i、+、(，是最终出现在句子里的）。V_N 与 V_T 不相交。
P　产生式集合（规则，形如 α→β，读作"α 可以是 β"）
S　开始符号（∈V_N，一切从它推起）

二、推导、句型、句子

推导（⇒）：用某产生式的右部，替换符号串里的一个非终结符。例：有 E→E+E，则 E ⇒ E+E。

最左推导：每步都替换最左边的非终结符。最右推导（又叫规范推导）：每步替换最右边的。
句型：从 S 推出的任意符号串（可以含非终结符）。
句子：只含终结符、且能从 S 推出的串。
语言 L(G) = 所有句子的集合。

三、语法树与二义性

语法树（推导树）：根是 S，每用一条产生式 A→XYZ 就让 A 长出子结点 X、Y、Z；所有叶子从左到右连起来就是一个句型。

二义性（高频考点）：如果文法里存在某一个句子，能画出两棵不同的语法树（等价说法：有两个不同的最左推导，或两个不同的最右推导），这个文法就是二义的^[2]。

四、Chomsky 文法分类

型别	名称	产生式限制	识别工具/用途
0 型	短语文法	α→β，α 含至少一个非终结符	图灵机
1 型	上下文有关 CSG	\|α\| ≤ \|β\|（右部不短于左部）	线性界限自动机
2 型	上下文无关 CFG	左部是单个非终结符 A→β	下推自动机／描述语法
3 型	正规文法	右线性 A→aB 或 A→a	有限自动机／描述单词

型别

名称

产生式限制

识别工具/用途

0 型

短语文法

α→β，α 含至少一个非终结符

图灵机

1 型

上下文有关 CSG

|α| ≤ |β|（右部不短于左部）

线性界限自动机

2 型

上下文无关 CFG

左部是单个非终结符 A→β

下推自动机／描述语法

3 型

正规文法

右线性 A→aB 或 A→a

有限自动机／描述单词

包含关系：3 型 ⊂ 2 型 ⊂ 1 型 ⊂ 0 型（限制越多、级别数越大、能力越弱）。编译里：2 型描述语法、3 型描述单词。

⚑ 套路卡

判第几型：看左部——左部是单个非终结符才可能是 2/3 型；再看右部是不是 A→aB/A→a 这种"一个终结符带头"的形态 → 是则 3 型，否则 2 型。

证二义：挑一个句子，给它构造两棵不同的语法树（或两个不同最左推导）。能造出来 = 二义。

五、老师示范一题

例题　已知文法 G[E]：E → E+E | E*E | (E) | i。证明 G 是二义的。

思路：找一个句子，给出两个不同的最左推导。取句子 i+i*i。

最左推导①（先用 E→E+E）：
 E ⇒ E+E ⇒ i+E ⇒ i+E*E ⇒ i+i*E ⇒ i+i*i      （结合方式： i+(i*i) ）

最左推导②（先用 E→E*E）：
 E ⇒ E*E ⇒ E+E*E ⇒ i+E*E ⇒ i+i*E ⇒ i+i*i    （结合方式： (i+i)*i ）

两个推导都是最左推导、都得到同一个句子 i+i*i，但过程不同，对应两棵不同的语法树：

树① 根为 +            树② 根为 *
      E                    E
    / | \                / | \
   E  +  E              E  *  E
   |    /|\            /|\    |
   i   E * E          E + E   i
       |   |          |   |
       i   i          i   i
   = i+(i*i)          = (i+i)*i

一个句子有两棵不同的语法树，故 G 二义。　∎

💡 采分套路：写出两个不同的最左（或最右）推导是最稳的证法；再补一句"对应两棵不同语法树"即可。

六、你来做

点选项立即判分。错了会标出正确答案并解释。

1. 文法 G=(V_N, V_T, P, S) 不包含下面哪一项？

2. 只由终结符组成、且能从开始符号推出的符号串称为？

3. 产生式 A→aB（B 为非终结符）属于第几型文法？

4. 一个句子存在两棵不同的语法树，说明该文法是？

5. 最右推导又被称为？

得分：0 / 5

四元组：非终结、终结、产生式、开始符
含终结符全 = 句子；可含非终结 = 句型；两棵树 = 二义

📺 主源推荐　哈工大《编译原理》国家精品课 · 第 2 讲「程序设计语言及其文法」 — 中国大学MOOC^[2]。

🙋 文法的推导、句型/句子、二义性是后面所有语法分析的基础，有一点没吃透就来问我——比如"再给我一道判断第几型的题""二义性还能怎么证"。

[1] 文法四元组定义、推导、句型/句子/语言、Chomsky 分类：陈火旺《程序设计语言编译原理》第 2 章 2.3。
[2] 语法树与二义性：哈工大《编译原理》国家精品课（中国大学MOOC）第 2 讲。