Jac*_*lch 2 prolog left-recursion dcg failure-slice
我正在尝试实现一个带有一组形式为{a,b,c,d}*的字符串的dcg.我遇到的问题是如果我有一个形式s的查询([a,c,b], []),它返回true,这是正确的答案但是当我有一个形式s([a,c,f],[])的查询时,它不返回一个答案,它用完了本地堆栈.
s --> [].
s --> s,num.
num --> [a].
num--> [b].
num--> [c].
num--> [d].
phrase/2让我们试着phrase(s,[a,b,c])代替s([a,b,c],[]).原因很简单:通过这种方式,我们明确表示我们使用的是DCG(dcg),而不是普通的谓词.phrase/2是语法的"官方"接口.
所以你的第一个问题是为什么phrase(s,[a,c,f])不在phrase(s,[a,b,c])"给出正确的答案"时终止- 正如你所说.现在,这很快回答:两者都没有终止!但phrase(s,[a,b,c])找到解决方案/答案.
这些是要区分的两件事:如果您输入查询并得到像true或的答案X = a; 你可能有兴趣获得更多.通常你通过输入SPACE或;ENTER在顶层来做到这一点.因此,查询可能仅在找到第一个或多个答案后才开始循环.随着时间的推移,这变得非常混乱:你是否应该永远记住这个谓词可能会产生答案; 另一个谓词产生两个,后来才会循环？
最简单的方法是建立通用终止的概念,这是这里最强大的概念.A Goal终止iff Goal, false终止.这个false目标对应于SPACE无限期击球; 直到整个查询失败的那一刻.
所以现在尝试:
?- phrase(s,[a,c,f]), false. ** LOOPS **
但是也:
?- phrase(s,[a,b,c]), false. ** LOOPS **
从通用终止的角度来看,两个查询都不会终止.在最常用的词中,终止等于通用终止.找到答案或解决方案就是这样,但没有任何终止.因此,只要您对答案感到满意但基本上不会终止,那么查询看起来就是无害的.但是很高兴您能够如此快速地发现这一点:如果您只是在正在运行的应用程序中发现这一点会更糟糕.
下一步让我们确定不终止的原因.您可能会尝试调试器或跟踪器,但很可能它根本不会给您一个很好的解释.但是有一个更简单的方法:使用故障切片.只需{false}在您的语法中添加非终端; 和目标false进入谓词.我们可以利用这里非常漂亮的房产:
如果失败片未终止,则原始程序不会终止.
所以,如果我们很幸运并且我们找到了这样的切片,那么我们肯定知道仅当剩余的可见部分以某种方式改变时才会发生终止.最有用的切片是:
?- phrase(s,[a,b,c]), falses --> [], {false}. s --> s, {false},num.
你的程序还剩下多少!走了num//0!没有人关心num//0.这意味着:num//0可以描述任何东西,无论如何 - 程序仍然会循环.
要解决这个问题,我们必须改变可见部分的内容.剩下的不多了!正如您已经观察到的,我们在这里有一个左递归.解决它的经典方法是:
您可以轻松地将语法重新表达为正确的递归:
s --> []. s --> num, s.
现在两个查询终止.这是编译器构造中也称为的经典方法.
但有些情况下,语法的重新制定是不合适的.这个简单的例子不属于这种情况,但它常常出现在语法中,并且有些模糊不清.在这种情况下,你仍然可以:
?- Xs = [a,b,c], phrase(s(Xs,[]), Xs).
s(Xs,Xs) --> [].
s([_|Xs0],Xs) --> s(Xs0,Xs1), num, {Xs1=Xs}.
无论你做什么,请记住并非每个查询都可以终止.如果你问:»告诉我所有存在的自然数 - 真的全部,一个一个!«然后回答这个的唯一方法是从0开始并计算它们.所以有一些问题,其中有无穷无尽的答案/解决方案,我们不能责怪可怜的Prolog实现我们的愿望.但是,在这种情况下我们最喜欢的是以公平的方式列举所有解决方案.我们可以通过具有良好终止特性的语法来做到这一点; 也就是说,一个语法终止于固定长度列表.像这样:
?- length(Xs, M), phrase(s, Xs).
有关如何应用故障片的其他示例,请参阅标签故障片.