6.8.1 取消集

“繁忙”集（B集）的概念使得DCG解析左递归语法成为可能（Nederhof [105]）。非终结符A的每一个Prolog生成词都附带一个逻辑参数CancellationSet，除了初始Sentence和Remainder。取消集包含在左递归中已经处理过的非终结符的名称，并在图像处理中充当“已使用”集合。通过使用这些集合就得到了取消解析。

处理非终结符A的规则要做的第一件事就是检查A是否处于取消集中，如果是则退出。这可以有效防止陷入左递归循环，但这也同时让A的规则不会识别任何涉及左递归的终结符生成。更准确的说，它只能识别A产生的子树，且A位于树的非根节点的左枝丫上。如果不存在这样的子树，那A就什么都不会生成。因此面对A在树左侧出现不止一次的情况，则必须有相应的解决方案。（树的左侧枝丫代表访问从根节点开始访问的顺序，从根节点开始依次往下访问最左侧节点。有关详细介绍在10.1.1.1节）

这个问题的解决方案很简单也很巧妙：一旦识别到一个顶部有A的子树T，就将这个A重定向为一个终结符*$$\overline{A}$$，并传回输入流中。实际上我们从输入流中获取终结符 A，然后将其用$$\overline{A}$$*替换。现在就剩下改造解析器的剩余部分了。我们下节将介绍如何处理这个问题。