### 陈火旺《编译原理》第三版课后习题答案解析
#### 第二章
##### P-36-6
本题考察了上下文无关文法中的**最左推导**与**最右推导**的概念。
1. **题目背景**：
- 文法 `G` 产生的语言 `L(G)` 是由0到9的数字串构成的集合。
- 需要给出一系列最左推导和最右推导的例子。
2. **文法规则**：
- `N ⇒ ND | D`
- `D ⇒ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9`
3. **最左推导示例**：
- `N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0127`
- `N ⇒ ND ⇒ DD ⇒ 3D ⇒ 34`
- `N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 5DD ⇒ 56D ⇒ 568`
4. **最右推导示例**：
- `N ⇒ ND ⇒ N7 ⇒ ND7 ⇒ N27 ⇒ ND27 ⇒ N127 ⇒ D127 ⇒ 0127`
- `N ⇒ ND ⇒ N4 ⇒ D4 ⇒ 34`
- `N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 568`
**解析**：
- 在最左推导中，我们始终选择当前字符串中最左边的非终结符进行替换。
- 在最右推导中，则始终选择当前字符串中最右边的非终结符进行替换。
- 通过这些例子，可以直观地理解如何根据给定的文法规则生成具体的句子。
##### P-36-7
本题涉及到了两个不同的文法，并要求分析其结构。
1. **文法 G1**：
- `S → P | AP`
- `P → 1 | 3 | 5 | 7 | 9`
- `A → AD | N`
- `N → 2 | 4 | 6 | 8 | P`
- `D → 0 | N`
2. **文法 G2**：
- `S → A B C | C`
- `A → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9`
- `B → BA | B0 | ε`
- `C → 1 | 3 | 5 | 7 | 9`
3. **解析**：
- 这两个文法都是用于生成特定形式的字符串。
- G1 更加复杂，包含了多个层次的非终结符，可以通过不同的方式组合来生成字符串。
- G2 相对简单，但是也展示了如何通过非终结符的递归定义来扩展生成能力。
##### P-36-8
本题考察了表达式的上下文无关文法及其推导过程。
1. **文法 G(E)**：
- `E → T | E + T | E - T`
- `T → F | T * F | T / F`
- `F → (E) | i`
2. **推导示例**：
- 最左推导：`E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ i + T ⇒ i + T * F ⇒ i + F * F ⇒ i + i * F ⇒ i + i * i`
- 最右推导：`E ⇒ E + T ⇒ E + T * F ⇒ E + T * i ⇒ E + F * i ⇒ E + i * i ⇒ T + i * i ⇒ F + i * i ⇒ i + i * i`
3. **语法树**：
- 通过语法树可以更直观地表示出表达式的结构。
**解析**：
- 通过不同的推导过程，可以看到同一个表达式可能有不同的语法树，这有助于理解表达式的结构以及如何通过文法生成。
- 这样的练习有助于加深对文法规则的理解，同时也能更好地掌握如何根据文法构造句子。
##### P-36-9
本题探讨了二义性文法的概念。
1. **句子**：
- `iiiei` 有两种不同的语法树。
2. **文法**：
- `S → iSeS | iSei`
- `S → iS | iiSei`
3. **解析**：
- 由于一个句子有两棵不同的语法树，这意味着文法是二义性的。
- 二义性文法可能会导致编译器或解释器在解析时出现歧义，因此通常需要避免。
---
以上是对陈火旺《编译原理》第三版部分章节课后习题的答案解析。这些题目不仅涵盖了基本的文法概念，还涉及到了复杂的推导过程和语法树的构建，有助于读者深入理解编译原理的基础知识。
