给定文法 $ P = { E \to E + T \mid T, \quad T \to T * F \mid F, \quad F \to (E) \mid \text{id} } $，我们以句子 $ \text{id}_1 + \text{id}_2 * \text{id}_3 $ 为例，进行最右推导、语法树构建和短语分析。
1. 最右推导过程
最右推导（规范推导）是指在每一步推导中，总是替换最右侧的非终结符。从开始符号 $ E $ 出发：
E⇒E+T(使用 E→E+T)⇒E+T∗F(使用 T→T∗F)⇒E+T∗id3(使用 F→id)⇒E+F∗id3(使用 T→F)⇒E+id2∗id3(使用 F→id)⇒T+id2∗id3(使用 E→T)⇒F+id2∗id3(使用 T→F)⇒id1+id2∗id3(使用 F→id) \begin{align*} E & \Rightarrow E + T \quad \text{(使用 } E \to E + T\text{)} \\ & \Rightarrow E + T * F \quad \text{(使用 } T \to T * F\text{)} \\ & \Rightarrow E + T * \text{id}_3 \quad \text{(使用 } F \to \text{id}\text{)} \\ & \Rightarrow E + F * \text{id}_3 \quad \text{(使用 } T \to F\text{)} \\ & \Rightarrow E + \text{id}_2 * \text{id}_3 \quad \text{(使用 } F \to \text{id}\text{)} \\ & \Rightarrow T + \text{id}_2 * \text{id}_3 \quad \text{(使用 } E \to T\text{)} \\ & \Rightarrow F + \text{id}_2 * \text{id}_3 \quad \text{(使用 } T \to F\text{)} \\ & \Rightarrow \text{id}_1 + \text{id}_2 * \text{id}_3 \quad \text{(使用 } F \to \text{id}\text{)} \end{align*}E⇒E+T(使用E→E+T)⇒E+T∗F(使用T→T∗F)⇒E+T∗id3(使用F→id)⇒E+F∗id3(使用T→F)⇒E+id2∗id3(使用F→id)⇒T+id2∗id3(使用E→T)⇒F+id2∗id3(使用T→F)⇒id1+id2∗id3(使用F→id)
✅ 最终得到句子：$ \text{id}_1 + \text{id}_2 * \text{id}_3 $
注意：这是最右推导，因此每次都优先展开最右边的非终结符（如先处理 $ T $ 中的 $ F $，再往左处理 $ E $）。
2. 推导的树结构（语法树）
E / | \ E + T /| \ / | \ T F T * F /|\ \ /|\ \ F id2 id3 | id1更清晰地表示为：
E / | \ E + T | / \ T T * | | | F F id3 | | id1 id2但实际上，根据推导顺序，应为：
E / | \ E + T | / \ T T * | | | F F F | | | id1 id2 id3但注意：由于 $ T \to T * F $，所以中间的 $ T $ 应该是递归生成的。正确语法树如下：
E / | \ E + T /|\ /|\ T T * F | | | F F id3 | | id1 id2而最底层的 $ T \to F \to \text{id}_2 $，所以完整结构是左递归展开。
最终语法树反映了左结合的+和*，且*优先级高于+。
3. 短语分析
基于上述最右推导过程，识别短语与直接短语：
- 短语：在一个句型中，能被某个非终结符逐步推导出的子串称为该非终结符的短语。
- 直接短语（素短语）：仅通过一步推导就能得到的短语（即使用一次产生式替换）。
分析句型 $ \text{id}_1 + \text{id}_2 * \text{id}_3 $ 的各部分：
| 子串 | 对应非终结符 | 是否为短语 | 是否为直接短语 | 理由 |
|---|---|---|---|---|
| $ \text{id}_1 $ | $ F $ | 是 | 是 | $ F \Rightarrow \text{id}_1 $ |
| $ \text{id}_2 $ | $ F $ | 是 | 是 | $ F \Rightarrow \text{id}_2 $ |
| $ \text{id}_3 $ | $ F $ | 是 | 是 | $ F \Rightarrow \text{id}_3 $ |
| $ \text{id}_2 * \text{id}_3 $ | $ T $ | 是 | 否 | $ T \Rightarrow T * F \Rightarrow^* \text{id}_2 * \text{id}_3 $ |
| $ \text{id}_1 + \text{id}_2 * \text{id}_3 $ | $ E $ | 是 | 否 | 整个句子由 $ E $ 推导而来 |
此外：
- $ \text{id}_1 $ 是相对于 $ T $ 的短语吗？→ 是，因为 $ T \Rightarrow F \Rightarrow \text{id}_1 $
- 直接短语只有那些一步推出的：$ \text{id}_1, \text{id}_2, \text{id}_3 $
- 句柄（handle）是最左直接短语，在最右推导中用于规约的关键部分，此处为 $ \text{id}_3 $（首次规约对象）
总结
- 文法定义了一个典型的表达式文法，支持加法和乘法，具有左递归以实现左结合。
- 最右推导展示了如何从 $ E $ 一步步生成目标句子，强调了运算符优先级（
*高于+）。 - 语法树直观体现结构：
+的右操作数是一个T（即id2 * id3），说明*先结合。 - 短语分析有助于理解语义计算和语法分析器设计（如 LR 分析器中的规约动作）。
