### 编译原理答案解析——陈火旺第三版
#### 第二章
##### P-36-6
**题目解析**：
本题考察了上下文无关文法中的两种推导方式——最左推导和最右推导，并通过具体例子进行演示。
1. **背景介绍**：在编译原理中，文法是用来描述编程语言结构的一种形式化工具。一个上下文无关文法通常由非终结符、终结符、起始符号以及一系列产生式构成。对于一个特定的文法，可以通过不同的推导路径得到同一个句子，这些推导路径可以是最左推导或最右推导。
2. **最左推导**：在最左推导中，每次替换时总是选择当前剩余字符串中最左边的非终结符进行替换。例如，对于句子`0127`，其最左推导过程为：
- `N⇒ND⇒NDD⇒NDDD⇒DDDD⇒0DDD⇒01DD⇒012D⇒0127`
- 类似地，`34`和`568`的最左推导分别为：
- `N⇒ND⇒DD⇒3D⇒34`
- `N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒568`
3. **最右推导**：与最左推导相反，在最右推导中，每次替换时总是选择当前剩余字符串中最右边的非终结符进行替换。例如，对于同样的句子`0127`，其最右推导过程为：
- `N⇒ND⇒N7⇒ND7⇒N27⇒ND27⇒N127⇒D127⇒0127`
- 同样地，`34`和`568`的最右推导分别为：
- `N⇒ND⇒N4⇒D4⇒34`
- `N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒568`
##### P-36-7
**题目解析**：
本题要求构造能够生成奇数位数的数字串的文法。
1. **解题思路**：为了生成奇数位数的数字串，需要定义能够产生单个数字的规则（如`P→1|3|5|7|9`），同时还需要定义能够产生偶数位数的数字串的规则，并在此基础上添加一个额外的数字，以确保最终生成的数字串总共有奇数位。
2. **文法规则**：
- `S→P|AP`，其中`S`为起始符号，表示整个表达式；`P`代表单个奇数；`AP`代表偶数位数的数字串后跟一个奇数。
- `P→1|3|5|7|9`，表示奇数位数的数字。
- `A→AD|N`，`N`用于产生偶数位数的数字串，`AD`表示在前面数字的基础上添加一个新的数字。
- `N→2|4|6|8|P`，用于产生偶数位数的数字串。
- `D→0|N`，用于产生数字`0`或继续产生更多的数字。
3. **扩展方案**：如果考虑到正负符号的问题，可以在文法中增加对符号的处理，例如：
- `S→+P|-P|+AP|-AP`，这样就能够处理带正负号的情况了。
##### P-36-8
**题目解析**：
本题要求给出表达式文法并进行推导。
1. **文法规则**：
- `E→T|E+T|E-T`，表示表达式可以是项`T`，也可以是表达式加上或减去项。
- `T→F|T*F|T/F`，表示项可以是因子`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⇒T⇒T*F⇒F*F⇒i*F⇒i*(E)⇒i*(E+T)⇒i*(T+T)⇒i*(F+T)⇒i*(i+T)⇒i*(i+F)⇒i*(i+i)`
- 最右推导：
- `E⇒E+T⇒E+T*i⇒E+F*i⇒E+i*i⇒T+i*i⇒F+i*i⇒i+i*i`
- `E⇒T⇒T*F⇒T*(E)⇒T*(E+T)⇒T*(E+F)⇒T*(E+i)⇒T*(T+i)⇒T*(F+i)⇒T*(i+i)⇒F*(i+i)⇒i*(i+i)`
3. **语法树**：语法树是一种用来可视化推导过程的工具。它显示了从根节点到叶节点的推导路径，每个内部节点代表一个产生式，而叶节点代表终结符。例如，对于表达式`i+i+i`，其语法树如下所示：
```
E
/ \
+ i
/ \
i +
/ \
i i
```
##### P-36-9
**题目解析**：
本题探讨了文法的二义性问题。
1. **背景介绍**：一个文法如果存在一个句子具有多于一种推导路径，则称这个文法是二义性的。
2. **句子示例**：句子`iiiei`有以下两种推导方式：
- `S⇒iSeS⇒iSei⇒iiSei⇒iiiei`
- `S⇒iS⇒iiSeS⇒iiSei⇒iiiei`
3. **结论**：由于`iiiei`有两种不同的推导方式，故文法是二义性的。
通过对第二章几个典型例题的分析，我们不仅了解了上下文无关文法的基本概念，还深入学习了如何利用最左推导和最右推导来构造句子，以及如何识别文法的二义性。这些知识对于理解编程语言的语法结构和编译器的设计至关重要。
