通过语法推导树快速求短语，简单短语和句柄

第一步：写出规范推导（最右）序列

规范推导就是最右推导。我们的目标是从起始符号 E 出发，通过每步替换最右边的非终结符，最终得到句型 R(P+i)。

文法 G[E]:

• E ::= RP | P
• P ::= (E) | i
• R ::= RP+ | RP* | P+ | P*

推导过程：

1. E => RP

   • 我们选择 E → RP 开始，因为目标句型以 R 开头。现在句型是 RP，最右非终结符是 P。

2. => R(E)

   • 目标句型 R(P+i) 包含括号 ()。唯一能产生括号的规则是 P → (E)。我们用它替换最右的 P。现在句型是 R(E)，最右（也是唯一）的非终结符是 E。

3. => R(RP)

   • 现在需要推导括号里的内容 P+i。它由两部分组成。我们先用 E → RP 展开。现在句型是 R(RP)，最右非终结符是 P。

4. => R(Ri)

   • 为了得到 P+i 的 i 部分，我们用规则 P → i 替换最右的 P。现在句型是 R(Ri)，最右非终-结符是 R。

5. => R(P+i)

   • 最后，为了得到 P+ 部分，我们用规则 R → P+ 替换最右的 R。推导完成。

规范推导序列为：
E => RP => R(E) => R(RP) => R(Ri) => R(P+i)

第二步：快速查找短语、简单短语和句柄 (核心技巧)

方法：利用语法树结构。
根据上面的推导过程，我们可以画出这个句型对应的语法树：

      E
     / \
    R   P
       /|\
      ( E )
       / \
      R   P
     / \  |
    P   + i

现在，我们可以用这棵树来快速找出所有答案：

1. 找出所有短语

规则：语法树中，任何一个以非终结符为根的子树，其所有叶子节点从左到右组成的字符串，都是一个短语。

我们从下往上、从小到大找所有子树：

• 以最下面的 P 为根的子树，叶子是 i。 短语是 i。
• 以 R 为根的子树，叶子是 P 和 +。 短语是 P+。
• 以括号内的 E 为根的子树，叶子是 P, +, i。 短语是 P+i。
• 以最右边的 P 为根的子树，叶子是 (, P, +, i, )。 短语是 (P+i)。
• 以最顶层的 E 为根的子树（整棵树），叶子是 R, (, P, +, i, )。 短语是 R(P+i)。

所有短语列表： i, P+, P+i, (P+i), R(P+i)

2. 找出所有简单短语

规则：简单短语是一个直接由某条产生式一步推导而来的短语。在语法树上，任何一个以非终结符为根的子树，并且叶子节点和当前非终结符为父子关系（一步得来的），其所有叶子节点从左到右组成的字符串，都是一个短语。

我们检查刚才找出的短语：

• i： 是由 P → i 一步得来的吗？是的。所以 i 是简单短语。
• P+： 是由 R → P+ 一步得来的吗？是的。所以 P+ 是简单短语。
• P+i： 是由 E → P+i 一步得来的吗？不是，E 先变成 RP，经过多步才得到。所以它不是简单短语。
• (P+i)： 是由 P → (P+i) 一步得来的吗？不是，P 是先变成 (E)。所以它不是简单短-语。
• R(P+i)： 不是一步得来的。

所有简单短语列表： i, P+

3. 找出句柄

规则：句柄是该句型的最左边的简单短语。

1. 看我们的句型 R(P+i)。
2. 看我们的简单短语列表 i, P+。
3. 从左到右扫描句型 R(P+i)，看哪个简单短语先出现。
4. 我们先遇到的是 P+。

句柄是： P+

最终答案总结

• 规范推导序列: E => RP => R(E) => R(RP) => R(Ri) => R(P+i)
• 所有短语: i, P+, P+i, (P+i), R(P+i)
• 所有简单短语: i, P+
• 句柄: P+