3 句柄

一般来说，一个句型的句柄是句型中一个和产生式右部匹配的子串，称之为句柄就意味着其可以规约，但不总是这样，上一页的例子中提到 $aAb$ 不能规约成 $aAA$，虽然 $b$ 是 $A→b$ 右部的子串，但是在这里因为不能规约，所以这里 $b$ 不是句柄。

严谨定义：一个右句型 $\gamma$ 的句柄 $\delta$ 是某个产生式（例如 $A→\beta$）右部 $\beta$ 和 $\gamma$ 中的一个位置 $N$（从1开始计数）。

• 在 $\gamma[N]$ 处，可以找到串 $\beta$
• 用 $A$ 替代 $\delta$，得到的是最右推导的前一个右句型

即：如果 $S\Rightarrow^*_{rm}\alpha Aw\Rightarrow_{rm}\alpha\beta w$，那么在 $\alpha$ 之后的 $\beta$ 是串 $\alpha\beta w$ 的一个句柄。

由于是最右推导，所以句柄右侧（上面的例子中是 $w$）只有终结符，实际上就是尚未处理的输入串。

之所以强调“一个”，是因为文法二义会导致句柄不唯一。

文法二义导致句柄不唯一

例如文法：$E→E+E|E*E|(E)|\textbf{id}$

因为二义文法可能存在两个最右推导！

本文阅读量