文法

1. 考点：基础概念

• 形式文法定义：一个形式文法是一个有序四元组 $G = (V, T, S, P)$，其中：

  1. $V$：​非终结符。不是语言组成部分，不是最终结果，可理解为占位符。
  2. $T$：​终结符。是语言的组成部分，是最终结果。且 $V \cap T = \emptyset$。
  3. $S$：​起始符。是语言的开始符号。
  4. $P$：​产生式。用终结符替代非终结符的规则，形如 $\alpha \to \beta$。

• 正则闭包与闭包：

  • **正则闭包 (​$A^+$**​ ) ：$A^+ = A^1 \cup A^2 \cup A^3 \cup \dots \cup A^n \cup \dots$（也就是所有正幂的组合，表示 $1 \sim n$ 个）。
  • **闭包 (​$A^*$**​ ) ：$A^* = A^0 \cup A^+$（在正则闭包的基础上，加上 $A^0 = \{\varepsilon\}$，表示 $0 \sim n$ 个）。

• 常见示例：

  • 若 $a^* = \{a, aa, aaa, \dots, \varepsilon\}$
  • 若 $(ab)^* = \{ab, abab, ababab, \dots, \varepsilon\}$

• 重点与口诀：

  • $\varepsilon$ 表示 $0$ 个，$*$ 表示 $0 \sim n$ 个，$+$ 表示 $1 \sim n$ 个。
  • 口诀：加 ($+$) $1$（至少 $1$ 个），乘 ($*$) $0$（可有 $0$ 个）。

2. 考点 ：文法与推导树例题详解

2.1 题目描述

已知文法 G=({a,b},{S,A},S,P)G=({a,b},{S,A},S,P)，其中产生式 PP 如下：

S→aASS→aAS

S→aS→a

A→SbAA→SbA

A→SSA→SS

A→baA→ba

问题​：请构造句型 ​​aabAa​ 的推导树。

---

2.2 文法基础概念回顾

在开始推导前，先明确符号的含义（结合图片右侧提示）：

V（非终结符） ​：​{S, A}。代表还没展开的“占位符”，可以被替换。

T（终结符） ​：​{a, b}。代表最终结果，不能再被替换。

S（起始符） ​：​S。所有推导的起点。

P（产生式） ​：形如 α→βα→β 的替换规则。

---

2.3 详细推导过程（自顶向下，从左到右）

我们的目标是生成字符串 ​aabAa​。推导的核心思路是：​每次替换最左边的非终结符，不断匹配目标串的前缀，直到生成完整的句子。

2.3.1 展开起始符 S

当前状态​：起始符 SS。

目标分析​：目标串 ​aabAa​ 以 ​a 开头。

选择规则：

规则 S→aS→a 虽然也能生成 ​a​，但生成后只有一个字符，推导就会结束，无法得到长度为 5 的 ​aabAa。

所以必须选择规则 S→aASS→aAS，保留后续继续推导的能力。

执行替换​：将 SS 替换为 ​aAS。

当前句型​：​a A S

树结构（对应图中第 1 棵树） ：

根节点 SS 生出三个子节点：​a​、​A​、​S。

2.3.2 展开第一个非终结符 A

当前状态​：​a A S​。目标串是 ​aabAa。

目标分析​：我们已经有了首字符 ​a​，现在需要生成第二个字符 ​a​（目标串的 ​aa...​）。当前最左侧的非终结符是 ​A。

选择规则​：观察 AA 的产生式：

A→baA→ba：以 ​b​ 开头，不符合目标串第二个字符 ​a，排除。

A→SSA→SS：会导致 ​a SSS，不好控制。

A→SbAA→SbA：可以配合 S→aS→a 生成 ​abA​，正好匹配目标串的 ​ab... 前缀。

所以选择 A→SbAA→SbA。

执行替换​：将 ​A​ 替换为 ​SbA。

当前句型​：​a S b A S​ （注意：​a​ + ​SbA​ + ​S）。

树结构（对应图中第 2 棵树） ：

在第一步的树基础上，节点 ​A​ 生出三个子节点：​S​、​b​、​A。

2.3.3 展开最左侧的 S

当前状态​：​a S b A S​。目标串 ​aabAa。

目标分析​：我们现在需要让句型变成 ​a a b ...​。当前句型是 ​a S b ...​，中间的 ​S​ 必须变成 ​a 才能匹配。

选择规则​：应用规则 S→aS→a。

执行替换​：将第二个位置的 ​S​ 替换为 ​a。

当前句型​：​a a b A S

树结构（对应图中第 3 棵树） ：

在第二步的树基础上，节点 ​A​ 下面的第一个子节点 ​S​ 生出子节点 ​a。

2.3.4 完成推导（图中未画出，但必不可少）

当前状态​：​a a b A S​。目标串 ​aabAa。

目标分析​：句型当前是 ​aabAS​，目标串是 ​aabAa​。最后一个字符需要是 ​a。

选择规则​：应用规则 S→aS→a。

执行替换​：将最后的 ​S​ 替换为 ​a。

最终句型​：​a a b A a​，即 ​​aabAa​。

推导完成 ✅

---

2.4 完整的最左推导序列

用符号 ⇒⇒ 表示一次推导（替换），完整过程如下：

S⇒aAS(使用 S→aAS)⇒aSbAS(使用 A→SbA)⇒aabAS(使用 S→a)⇒aabAa(使用 S→a)S​⇒aAS(使用 S→aAS)⇒aSbAS(使用 A→SbA)⇒aabAS(使用 S→a)⇒aabAa(使用 S→a)​---

2.5 推导树结构分析

结合图片中的三棵树，推导树从根到叶的生长过程如下：

树 1​：根节点 SS，生子节点 ​a​、​A​、​S。

树 2​：将树 1 中的 ​A​ 展开，生子节点 ​S​、​b​、​A。

树 3​：将树 2 中 ​A​ 下面的第一个 ​S​ 展开，生子节点 ​a。

最终树（隐含） ​：将树 3 中最右侧的 ​S​ 展开，生子节点 ​a。

最终推导树的叶子节点从左到右依次为​：​a​、​a​、​b​、​A​、​a​，即句型 ​aabAa。

3. 经典例题

3.1 题目一

题目： 简单算术表达式的结构可以用下面的上下文无关文法进行描述（E 为开始符号），请判断下列选项中，（）是符合该文法的句子。

给定文法 G​G​ ：

E→T∣E+TE→T∣E+T

T→F∣T∗FT→F∣T∗F

F→−F∣NF→−F∣N

N→0∣1∣2∣3∣4∣5∣6∣7∣8∣9N→0∣1∣2∣3∣4∣5∣6∣7∣8∣9

选项：

A. ​2 - 3 * 4

B. ​2 + -3 * 4

C. ​(2 + 3) * 4

D. ​2 * 4 - 3

解析：

选项 A： ​2 - 3 * 4​ ❌

为什么不合法？

题目给出的文法中，​只有加法 ​ ​+​ ​ 和乘法 ​ ​*​ ​ ，根本没有减法 ​ ​-​ ​ 作为二元运算符。

注意：文法里的 ​-​ 只出现在 F→−FF→−F 中，表示的是​一元负号​（比如 ​-3 中的负号），而不是二元减号。

所以 ​2 - 3 * 4​ 中的减号无法被文法生成，​排除。

选项 B： ​2 + -3 * 4​ ✅

为什么合法？

这个式子由三部分组成：

• 2：普通的数字
• +：加法
• -3：负数（一元负号 + 数字）
• *：乘法
• 4：普通的数字

文法中：

• +​ 由 E→E+TE→E+T 提供
• *​ 由 T→T∗FT→T∗F 提供
• 一元负号 ​-​ 由 F→−FF→−F 提供
• 数字由 NN 提供

全部都能匹配，​合法。稍后会给出完整推导树。

选项 C： ​(2 + 3) * 4​ ❌

为什么不合法？

题目描述里虽然提到了“​()​ 是符合该文法的句子”，但​文法的产生式里根本没有括号 ​ ​(​ ​ 和 ​ ​)​ ​ 的规则。

也就是说，这套文法​不支持括号，无法生成带括号的表达式。

所以 ​(2 + 3) * 4​ 中的括号无法被文法生成，​排除。

选项 D： ​2 * 4 - 3​ ❌

为什么不合法？

和选项 A 类似，这里有二元减号 ​-​，但文法只支持加法 ​+​ 和乘法 ​* 作为二元运算符，没有二元减号。

所以 ​2 * 4 - 3​ 不合法，​排除。

---

选项 B 的详细推导过程

目标：从开始符号 EE 出发，推导出 ​2 + -3 * 4。

核心策略：从最外层开始，先确定整体结构，再逐层展开。

第一步：确定整体是加法结构

因为式子 ​2 + -3 * 4​ 的最外层运算是加法 ​+，所以首先应用规则：

E→E+TE→E+T

此时句型变为：​E + T

• 左边的 ​E​ 负责生成 ​2
• 右边的 ​T​ 负责生成 ​-3 * 4

第二步：展开左边的 E 生成 2

应用规则链：E→T→F→N→2E→T→F→N→2

此时句型变为：​2 + T

第三步：展开右边的 T 生成 -3 * 4

因为 ​-3 * 4 的结构是“乘法”，所以应用规则：

T→T∗FT→T∗F

此时句型变为：​2 + T * F

第四步：展开左边的 T 生成 -3

-3​ 是一个带一元负号的数字，需要用 F→−FF→−F 来处理。

应用规则链：

• T→FT→F
• F→−FF→−F
• F→N→3F→N→3

此时句型变为：​2 + -3 * F

第五步：展开右边的 F 生成 4

应用规则链：F→N→4F→N→4

最终句型​：​2 + -3 * 4 ✅

---

正确答案：B。

‍