编译原理习题4-2
编译原理习题4-2
📘 问题（Problem）
4.2.1 考虑如下上下文无关文法（Context-Free Grammar）：
1 | S → S S + | S S * | a |
以及字符串 aa+a*。
- 给出该字符串的最左推导（leftmost derivation）；
- 给出最右推导（rightmost derivation）；
- 给出该字符串的语法树（parse tree）；
- 判断该文法是否二义性（ambiguous）或非二义性（unambiguous），并说明理由；
- 描述该文法生成的语言（Describe the language generated by the grammar）。
✅ 答案（Answer）
1. Leftmost Derivation（最左推导）
1 | S => SS* |
2. Rightmost Derivation（最右推导）
1 | S => SS* |
3. Parse Tree（语法树）
4. Ambiguity（文法的二义性）
该文法是非二义性的（Unambiguous）。
理由是：对于任意一个字符串（如 aa+a*），我们只能构造出唯一的一棵语法树和唯一的推导过程（左推导和右推导都唯一对应）。没有多种方式生成相同字符串的不同语法树。
5. Language Description（语言描述）
该文法生成的是：
所有由 a 组成的合法后缀表达式（postfix expressions），其操作符为加号（+）和乘号（\*）。
例如，以下字符串都是合法表达式：
aa+（即中缀表达式a + a）aa+a*（即中缀表达式(a + a) * a）aaa++（即a + (a + a)）
💡 总结（Summary）
| 项目 | 内容 |
|---|---|
| 文法 | `S → S S + |
| 输入串 | aa+a* |
| 左推导 | S => SS* => SS+S* => aS+S* => aa+S* => aa+a* |
| 右推导 | S => SS* => Sa* => SS+a* => Sa+a* => aa+a* |
| 是否二义性 | 否，唯一语法树 |
| 描述的语言 | 所有只包含 a 和 +, * 的后缀表达式 |
📘 问题（Problem 4.2.2）
对每组给定的文法（Grammar）和字符串（String），执行以下任务：
- 给出最左推导（Leftmost Derivation）；
- 给出最右推导（Rightmost Derivation）；
- （可选）画出语法树；
- 判断文法是否二义性（Ambiguous），说明理由；
- 简要描述该文法所生成的语言（Language Description）。
✅ 解答（Answers and Explanation）
1. Grammar:
1 | S → 0 S 1 | 0 1 |
推导过程：
- 最左推导：
S => 0S1 => 00S11 => 000111 - 最右推导：
S => 0S1 => 00S11 => 000111
二义性：无（Unambiguous）
语言描述：
生成数量相等的 0 和 1 且 0 全部在前，1 全部在后的字符串。
即：
The set of strings with n 0s followed by n 1s (0ⁿ1ⁿ)。
2. Grammar:
1 | S → + S S | * S S | a |
推导过程：
- 最左推导：
S => +SS => +*SSS => +*aSS => +*aaS => +*aaa - 最右推导：
S => +SS => +Sa => +*SSa => +*Saa => +*aaa
二义性：无（Unambiguous）
语言描述：
所有的前缀表达式（prefix expressions），运算符为 + 与 *，操作数为 a。
如：+ * a a a 表示 a * a + a
3. Grammar:
1 | S → S (S) S | ε |
推导过程（略）
多个推导树可能生成相同字符串，因此：
二义性：有（Ambiguous）
语言描述：
所有平衡括号字符串（balanced parentheses）
例如：(()())、((())) 等。
由于可以用不同方式嵌套括号生成同一串，所以存在二义性。
4. Grammar:
1 | S → S + S | S S | (S) | S * | a |
推导过程：
- 最左推导：
S => SS => S*S => (S)*S => (S+S)*S => (a+S)*S => (a+a)*S => (a+a)*a - 最右推导：
S => SS => Sa => S*a => (S)*a => (S+S)*a => (S+a)*a => (a+a)*a
二义性：有（Ambiguous）
原因：可使用不同组合方式推导表达式，如 S+S vs SS vs (S)
语言描述：
混合使用括号、加法、乘法的算术表达式（带操作符优先级和结合性问题）。
5. Grammar:
1 | S → (L) | a |
推导过程（简略）：
- 左推导：
通过多次使用L → L, S展开出多个参数，最终组合为((a,a),a,(a)) - 右推导：
从最内层a向外逐步展开L和S
二义性：无（Unambiguous）
语言描述：
像 Python 中的元组（tuple）结构一样的表达式。例如：(a)、(a,a)、((a,a),a,(a))
6. Grammar:
1 | S → a S b S | b S a S | ε |
推导过程：
- 最左推导：
S => aSbS => aaSbSbS => aabSbS => aabbS => aabbaSbS => aabbabS => aabbab - 最右推导：
S => aSbS => aSbaSbS => aSbaSb => aSbab => aaSbSbab => aaSbbab => aabbab
二义性：有（Ambiguous）
原因：不同路径推导出同一个字符串，语法树结构不同。
语言描述：
所有 a 和 b 的数量相等的字符串（number of a’s equals number of b’s），但顺序可变。
7. Grammar:
1 | bexpr → bexpr or bterm | bterm |
特点：
- 这是布尔表达式的标准文法（标准递归下降结构）
- 操作符优先级：not > and > or
二义性：无（Unambiguous）
语言描述：
所有由 true、false、and、or、not 组成的布尔表达式。
✅ 总结表（Summary Table）
| 题号 | 是否二义性 | 语言描述 |
|---|---|---|
| 1 | 否 | 0ⁿ1ⁿ 形式的串 |
| 2 | 否 | 前缀表达式（prefix） |
| 3 | 是 | 平衡括号表达式 |
| 4 | 是 | 混合括号、加法、乘法的算术表达式 |
| 5 | 否 | Python风格的元组结构 |
| 6 | 是 | a、b 数量相等的字符串 |
| 7 | 否 | 布尔表达式（Boolean expressions） |
📘 4.2.3 问题（Problems）
为以下语言设计上下文无关文法（CFG）：
- 所有 0 都必须紧跟至少一个 1 的 0 和 1 串。
- 所有是回文串（palindrome）的 0 和 1 串，即正着和反着读一样。
- 所有 0 和 1 的个数相等的串。
- 所有 0 和 1 的个数不相等的串。
- 所有不包含子串 “011” 的 0 和 1 串。
- 所有形如
xy且x ≠ y且|x| = |y|的 0 和 1 串。
✅ 解答与解释（Answers and Explanation）
1. Every 0 is immediately followed by at least one 1
Language: 所有 0 必须紧跟至少一个 1 的 01 串。
CFG:
1 | S → 1S | 01S | ε |
解释：
- 每个
0后必须紧跟一个1，所以01是一个组合单元； - 其余部分可以是
1或继续01； - 递归串联，用
ε结尾。
示例串：
1、01、1101、0111是合法的；00、10不合法。
2. Palindromes（回文串）
CFG:
1 | S → 0S0 | 1S1 | 0 | 1 | ε |
解释：
- 回文串中，最外层的两个字符相同，中间递归是一个更短的回文串；
- 终止条件为单字符或空串。
示例：
0,1,010,0110,1001,ε
3. Equal number of 0s and 1s
CFG:
1 | S → 0S1S | 1S0S | ε |
解释：
- 每加入一个
0，就需要匹配一个1（但不一定顺序匹配）； - 可以嵌套，使得数量保持相等。
示例：
01,10,0011,1100,0101,1001
4. Unequal number of 0s and 1s
这个语言是 非上下文无关语言的补集，所以无法用一个 CFG 完整表示所有情况。但可以构造两个 CFG：
CFG（非正规，但近似）：
1 | S → A | B |
或用补集思想处理：
CFG for all 0-1 strings - CFG of equal number of 0s and 1s = unequal 0s and 1s
但这个语言是非上下文无关的（not CFL），所以无法被一个 CFG 准确描述。
5. Strings without “011”
思路：不能出现 “011”，用状态控制避免。
CFG:
1 | S → 0A | 1S | ε |
解释：
S处理任意前缀；0A代表刚出现了一个0，进入检查状态；A不能让011出现；- 如果看到
01，进入B，避免紧接下来的1。
6. xy, where x ≠ y, and |x| = |y|
语言描述： 所有可以分为左右两半的串
xy，其中长度相同但内容不一致。
特点：
- 这不是上下文无关语言（not context-free），不能用 CFG 完全表示。
- 因为 CFG 无法比较两个长度相等的子串是否不同。
解释：
- 类似语言
{ x y | x ≠ y, |x| = |y| }是非 CFL（not context-free），可用泵引理证明； - 所以只能用更强的模型如 Turing Machine 或带计数器自动机处理。
✅ 总结表（Summary Table）
| 子题 | 语言描述 | 是否可用 CFG 表示 | 示例 CFG |
|---|---|---|---|
| 1 | 每个 0 后面至少一个 1 | ✅ 是 | `S → 1S |
| 2 | 回文串（palindromes） | ✅ 是 | `S → 0S0 |
| 3 | 0 和 1 的个数相等 | ✅ 是 | `S → 0S1S |
| 4 | 0 和 1 的个数不相等 | ❌ 否（非 CFL） | 无完整 CFG，需更强模型或多 CFG 合并近似 |
| 5 | 不包含 “011” 的字符串 | ✅ 是 | `S → 0A |
| 6 | xy，x ≠ y，且 | x | = |
📘 题目（Problem）
扩展文法记号（Extended Grammar Notation）：
在某些文法中，为了简洁和表达方便，引入了方括号[]和花括号{}的元符号（metasymbols）：
[α]表示 α 是可选的（可以有，也可以没有）；{α}表示 α 可以重复任意多次（包括 0 次）。
❓问题：
证明：这些扩展记号不会增加文法的表达能力，即任何使用这些扩展的文法都能转换为不使用扩展记号的普通文法（CFG）。
✅ 解答（Answer）
我们给出每一种扩展记号的转换规则，并说明为什么是等价的。
🔹情况 1：[α] — 可选部分
扩展写法（Extended Notation）：
1 | A → X [Y] Z |
表示 Y 是可选的。
转换为普通文法（Standard CFG）：
1 | A → X Y Z | X Z |
中文解释：
- 有
Y的情况生成XYZ； - 没有
Y的情况生成XZ； - 所以使用
|分支处理可选项即可。
🔹情况 2：{α} — 任意重复部分
扩展写法：
1 | A → X {Y Z} |
表示 YZ 可以重复 0 次或多次。
转换为普通 CFG：
1 | A → X B |
中文解释：
- 我们引入一个新非终结符
B来表示“零次或多次的 YZ”； B → YZB表示重复；B → ε表示终止重复。
📌 总结转换对照表（Conversion Summary）
| 扩展文法写法（Extended） | 普通文法（Standard CFG） | 说明 | |
|---|---|---|---|
| A → X [Y] Z | A → XYZ \ | XZ | 可选的用 ` |
| A → X {Y Z} | A → X B, B → YZB \ | ε | 重复的用新非终结符建递归规则 |
📚 理论证明简要（Why extensions don’t add power）
- 方括号
[]和花括号{}都可以通过 有限个普通 CFG 规则来模拟； - CFG 的定义允许使用 ε 和递归形式
A → αA | ε来表达任意次数的结构； - 所以这些扩展只是语法糖（syntactic sugar），用于书写简洁；
- 并不改变文法能生成的语言类别，即语言仍是上下文无关语言（CFL）。
✅ 结论（Conclusion）
所以，使用
[ ]和{ }的扩展文法不会增加生成语言的表达能力。它们只是简化文法编写的工具，任何包含这些扩展的文法都可以转换为不包含扩展的普通上下文无关文法。
📘 原题（Problem）
文法如下：
1 | stmt → if expr then stmt else stmt |
✅ 答案（Answer）
使用扩展文法的简化结果如下：
1 | stmt → if expr then stmt [else stmt] |
🧠 解释（Explanation）
我们根据前一题 4.2.4 的扩展规则对原文法进行简化：
🔹 对 stmt 的简化
原始有两条规则：
if expr then stmt else stmtif expr then stmt
→ 显然 else stmt 是可选的部分，我们用方括号 [] 表示：
1 | stmt → if expr then stmt [else stmt] |
再加上原有的第三条规则不需要改动：
1 | stmt → begin stmtList end |
🔹 对 stmtList 的简化
原始规则：
stmt ; stmtListstmt
→ 可改写为：
1 | stmtList → stmt [; stmtList] |
表示 一条语句后面可选地跟着;和更多语句。
📌 总结（Summary）
| 原始文法 | 使用扩展文法简化后 |
|---|---|
if expr then stmt |
if expr then stmt [else stmt] |
stmtList → stmt ; stmtList |
stmtList → stmt [; stmtList] |
✅ 结论（Conclusion）
通过使用扩展文法的 []（可选）和 {}（重复）符号，能简化原始 CFG 的书写，让语法更清晰紧凑，同时不改变其生成的语言集合。
🔷 4.2.6
🧾 题目（Problem）
扩展 4.2.4 的思想：允许任何正则表达式形式的符号出现在产生式右侧（如 A -> (ab)*c+ 等），证明这种扩展不会带来更强的表达能力（即不会生成新的语言）。
✅ 答案（Answer）
任何使用正则表达式扩展形式的文法，都可以转换成标准 CFG（上下文无关文法）形式。
🧠 解释（Explanation）
- 正则表达式的构造规则包含：
- 连接（ab）
- 或（a|b）
- 重复（a*、a+）
这些都可以通过标准 CFG 表达：
举例：
A -> (ab)*
相当于：1
A -> ε | abA
A -> a+
相当于：1
A -> a | aA
A -> a|b
相当于：1
A -> a | b
因此，这些正则结构都可以通过有限产生式转换为普通 CFG。
📌 结论（Conclusion）
✅ 所以：允许正则表达式作为产生式右侧的扩展文法并不增加 CFG 的表达能力。
所有扩展文法产生的语言仍然是上下文无关语言。
🔷 4.2.7
🧾 题目（Problem）
一个符号 X 是无用的（useless），如果它永远不会出现在某个句子的推导中。
你需要：
- 给出一个删除所有无用符号的算法。
- 将算法应用于文法：
1 | S -> 0 | A |
✅ 答案（Answer）
🔧 算法：去除无用符号（两步）
Step 1：找出能导出终结符串的非终结符（称为 “有意义”）
- 初始化集合
G = {}。 - 如果
X -> w，其中w全是终结符或G中的符号，则将X加入G。 - 重复直到
G不再增长。
Step 2：找出能从 S 推导到的符号（称为 “可达”）
- 初始化集合
R = {S}。 - 如果某个产生式
A -> α，且A ∈ R，则把α中出现的非终结符加入R。 - 重复直到
R不再增长。
最终保留 G ∩ R 中的符号，删除其他所有产生式。
🧪 应用算法：原文法
1 | S -> 0 | A |
Step 1：找出能导出终结符串的符号：
S -> 0✅ S 可生成终结符串 ⇒S ∈ GB -> 1✅ B 可生成终结符串 ⇒B ∈ GA -> AB❌ A 依赖 B 和 A 本身 ⇒ A 不属于 G
所以：G = {S, B}
Step 2：找出可达的符号：
S是开始符号 ⇒S ∈ RS -> A⇒ A 是可达的 ⇒A ∈ RA -> AB⇒ B 是可达的 ⇒B ∈ R
所以：R = {S, A, B}
最终交集：G ∩ R = {S, B}
保留与 S 和 B 有关的产生式：
1 | S -> 0 |
（S -> A 被删除，因为 A 无用）
📌 最终文法：
1 | S -> 0 |
🧠 解释总结：
A 和 B 互相依赖，但 A 本身无法产生终结符串；B 虽然能，但如果没人能用上它，就被删掉了。
