跳至主要內容

文法

2026/9/14大约 8 分钟软考程序设计语言

文法

1. 考点：基础概念

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

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

  • 正则闭包与闭包：

    • 正则闭包 ( A+A^+ ) ：A+=A1∪A2∪A3∪⋯∪An∪…A^+ = A^1 \cup A^2 \cup A^3 \cup \dots \cup A^n \cup \dots（也就是所有正幂的组合，表示 1∼n1 \sim n 个）。
    • 闭包 ( A∗A^* ) ：A∗=A0∪A+A^* = A^0 \cup A^+（在正则闭包的基础上，加上 A0={ε}A^0 = \{\varepsilon\}，表示 0∼n0 \sim n 个）。

  • 常见示例：

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

  • 重点与口诀：

    • ε\varepsilon 表示 00 个，∗* 表示 0∼n0 \sim n 个，++ 表示 1∼n1 \sim n 个。
    • 口诀：加 (++) 11（至少 11 个），乘 (∗*) 00（可有 00 个）。

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 题目一

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

文法产生式 PP：

E→T∣E+TT→F∣T∗FF→−F∣NN→0∣1∣2∣3∣4∣5∣6∣7∣8∣9\begin{aligned} E &\rightarrow T \mid E + T \\ T &\rightarrow F \mid T * F \\ F &\rightarrow -F \mid N \\ N &\rightarrow 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \end{aligned}

  • A、2−3∗42 - 3 * 4
  • B、2+−3∗42 + -3 * 4
  • C、(2+3)∗4(2 + 3) * 4
  • D、2∗4−32 * 4 - 3

【解析】

  • 正确答案：B

  • 解析说明：

    • 选项 A：2−3∗42 - 3 * 4：式子中的 −- 是二元减号，而文法中 −- 只出现在 F→−FF \rightarrow -F 里，是一元负号（如 −3-3 的负号），文法不存在二元减法规则，无法推导，排除。

    • 选项 B：2+−3∗42 + -3 * 4：各部分都能由文法生成——E→E+TE \rightarrow E + T 提供加法，T→T∗FT \rightarrow T * F 提供乘法，F→−FF \rightarrow -F 提供一元负号，NN 提供数字，推导过程见下。

    • 选项 C：(2+3)∗4(2 + 3) * 4：文法的产生式中没有定义括号 ()()，无法推导，排除。

    • 选项 D：2∗4−32 * 4 - 3：与选项 A 同理，−- 是二元减号，文法不支持，排除。

    • 选项 B 的推导过程：

      E⇒E+T（应用 E→E+T）⇒2+T（E→T→F→N→2）⇒2+T∗F（应用 T→T∗F）⇒2+−F∗F（T→F→−F）⇒2+−3∗F（F→N→3）⇒2+−3∗4（F→N→4）\begin{aligned} E &\Rightarrow E + T &&\text{（应用 } E \rightarrow E + T \text{）} \\ &\Rightarrow 2 + T &&\text{（} E \rightarrow T \rightarrow F \rightarrow N \rightarrow 2 \text{）} \\ &\Rightarrow 2 + T * F &&\text{（应用 } T \rightarrow T * F \text{）} \\ &\Rightarrow 2 + -F * F &&\text{（} T \rightarrow F \rightarrow -F \text{）} \\ &\Rightarrow 2 + -3 * F &&\text{（} F \rightarrow N \rightarrow 3 \text{）} \\ &\Rightarrow 2 + -3 * 4 &&\text{（} F \rightarrow N \rightarrow 4 \text{）} \end{aligned}

      因此 2+−3∗42 + -3 * 4 可以由该文法推导出来，是正确的。

正确答案：B（2+−3∗42 + -3 * 4）。

3.2 题目二

题目： 大多数程序设计语言的语法规则用（ ）描述即可。

  • A、正规文法
  • B、上下文无关文法
  • C、上下文有关文法
  • D、短语结构文法

【解析】

  • 正确答案：B

  • 解析说明：

    • 关于选项 B（上下文无关文法） ：大多数程序设计语言的语法规则可以用上下文无关文法来描述。上下文无关文法足够描述程序语言的语法结构，如表达式、语句、程序块等。

    • 其他选项说明：

      • A、正规文法：用于描述词法规则（如标识符、常数），不足以描述语法规则。
      • C、上下文有关文法：比上下文无关文法更强大，但过于复杂，不常用于描述程序语言语法。
      • D、短语结构文法：最一般的文法，包括所有文法类型，但过于宽泛，不适用于实际程序设计语言的语法描述。

正确答案：B（上下文无关文法）。

3.3 题目三

题目： 程序设计语言的大多数语法现象可以用 CFG（上下文无关文法）表示。下面的 CFG 产生式集用于描述简单算术表达式，其中 ++、−-、∗* 表示加、减、乘运算，id\text{id} 表示单个字母表示的变量，那么符合该文法的表达式为（ \quad ）。

文法产生式 PP：

E→E+T∣E−T∣TT→T∗F∣FF→−F∣id\begin{aligned} E &\rightarrow E + T \mid E - T \mid T \\ T &\rightarrow T * F \mid F \\ F &\rightarrow -F \mid \text{id} \end{aligned}

  • A、a+−b−ca+-b-c
  • B、a∗(b+c)a*(b+c)
  • C、a∗−b+2a*-b+2
  • D、−a/b+c-a/b+c

【解析】

  • 正确答案：A

  • 解析说明：

    • 选项 A：a+−b−ca+-b-c 的推导过程：

      E⇒E−T⇒E+T−T⇒T+T−T⇒F+T−T⇒id+T−T⇒a+T−T⇒a+F−T⇒a+−F−T⇒a+−id−T⇒a+−b−T⇒a+−b−F⇒a+−b−id⇒a+−b−c\begin{aligned} E &\Rightarrow E - T \\ &\Rightarrow E + T - T \\ &\Rightarrow T + T - T \\ &\Rightarrow F + T - T \\ &\Rightarrow \text{id} + T - T \\ &\Rightarrow a + T - T \\ &\Rightarrow a + F - T \\ &\Rightarrow a + -F - T \\ &\Rightarrow a + -\text{id} - T \\ &\Rightarrow a + -b - T \\ &\Rightarrow a + -b - F \\ &\Rightarrow a + -b - \text{id} \\ &\Rightarrow a + -b - c \end{aligned}

      因此 a+−b−ca+-b-c 可以由该文法推导出来，是正确的。

    • 选项 C：a∗−b+2a*-b+2 的推导过程：

      E⇒E+T⇒T+T⇒T∗F+T⇒F∗F+T⇒id∗F+T⇒a∗F+T⇒a∗−F+T⇒a∗−id+T⇒a∗−b+T⇒a∗−b+F\begin{aligned} E &\Rightarrow E + T \\ &\Rightarrow T + T \\ &\Rightarrow T * F + T \\ &\Rightarrow F * F + T \\ &\Rightarrow \text{id} * F + T \\ &\Rightarrow a * F + T \\ &\Rightarrow a * -F + T \\ &\Rightarrow a * -\text{id} + T \\ &\Rightarrow a * -b + T \\ &\Rightarrow a * -b + F \end{aligned}

      到这里，最后一项需要匹配 22。但 FF 只能推导为：

      F→−F∣idF \rightarrow -F \mid \text{id}，而 id\text{id} 只表示单个字母变量，不能是数字 22。

      因此，22 无法由 FF 推导出来，推导过程在最后一步卡住，选项 C 不正确。

    • 选项 B：a∗(b+c)a*(b+c)：文法中没有定义括号 ()()，无法推导。

    • 选项 D：−a/b+c-a/b+c：文法中没有定义除法 //，无法推导。

正确答案：A（a+−b−ca+-b-c）。