DCG和左递归

问题描述 投票:3回答:2

我正在尝试实现一个采用一组{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].
prolog dcg left-recursion failure-slice
2个回答
9
投票

使用phrase/2

让我们尝试用phrase(s,[a,b,c])代替s([a,b,c],[])。原因很简单:通过这种方式,我们可以清楚地表明我们使用的是DCG(),而不是普通的谓词。 phrase/2是语法的“官方”接口。

所以您的第一个问题是,为什么phrase(s,[a,c,f])给出正确答案时phrase(s,[a,b,c])没有终止?现在,可以快速回答:both不要终止!但是phrase(s,[a,b,c])找到了解决方案/答案。

通用终止

这是两点区别:如果您输入查询并得到trueX = a之类的答案;您可能有兴趣获得more。通常,您可以通过在顶层输入SPACE; ENTER来执行此操作。因此,只有在找到第一个或几个答案后,查询才可能开始循环。随着时间的流逝,这变得非常令人困惑:您是否应该始终记得该谓词可能会产生答案;另一个谓词产生两个,只有稍后才会循环?

最简单的方法是建立通用终止”的概念,这是这里最可靠的概念。如果Goal终止,则Goal, false终止。这个false目标对应于无限期地击SPACE;直到整个查询失败为止。

现在尝试:

?-词组(s,[a,c,f]),错误。**圈**

而且:

?-词组(s,[a,b,c]),错误。**圈**

从通用终止的角度来看,两个查询都不会终止。在单词的最常用用法中,终止等同于通用终止。而找到答案或解决方案仅仅是解决问题,而不是终结。因此,只要您对答案感到满意,有些查询看起来就没有害处,但实际上不会终止。但是很高兴您这么快就发现了这一点:如果仅在正在运行的应用程序中发现这一点,那就更糟了。

确定原因

下一步,我们确定未终止的原因。您可以尝试调试器或跟踪器,但很可能根本无法给您一个很好的解释。但是有一个更简单的方法:使用。只需将非结尾{false}添加到您的语法中即可;并将目标false转化为谓词。我们可以在这里利用一个非常美丽的属性:

If失败切片未终止then原始程序未终止。

因此,如果我们很幸运并且找到了这样的切片,那么我们可以肯定地知道,只有在更改了其余可见部分的情况下,终止才会发生以某种方式。最有用的部分是:

?-词组(s,[a,b,c]),falses-> [],{false}。s-> s,{false}num

您的程序还剩下很多! num//0走了!没有人关心num//0。这意味着:num//0可以描述anything,无论如何-程序仍会循环。

要解决该问题,我们必须在可见部分中进行一些更改。剩下的不多了!正如您已经观察到的,我们这里有一个左递归。解决它的经典方法是:

重新构造语法

您可以轻松地将语法重构为正确的递归:

s-> []。s-> num,s。

现在两个查询都终止。这是在编译器构造中也已知的经典方法。

但是在某些情况下,重新制定语法是不合适的。这个简单的例子不是这种例子,但是它经常发生在语法中,并带有一定的歧义。在这种情况下,您仍然可以:

添加引发终止的参数

α-Xs= [a,b,c],短语(s(Xs,[]),Xs)。s(Xs,Xs)-> []。s([_ | Xs0],Xs)-> s(Xs0,Xs1),num,{Xs1 = Xs}。

固有非终止查询

无论您做什么,请记住,并非每个查询都可以终止。如果您问:»告诉我所有存在的自然数–实际上是所有自然数,一个接一个!«然后,回答这个问题的唯一方法是从0开始并计数。因此,存在疑问,答案/解决方案无穷无尽,我们不能责怪可怜的Prolog未能实现我们的愿望。但是,在这种情况下,我们最希望以公平的方式列举所有解决方案。我们可以使用具有良好终止特性的语法来做到最好;也就是说,语法以固定长度的列表终止。像这样:

α-长度(Xs,M),短语(s,Xs)。

有关如何应用失败切片的其他示例,请参见标签


0
投票

我不知道这是否有帮助,因为我正在使用的序言似乎具有非常不同的语法,但是我只是编写了以下程序来尝试与您的程序匹配,所以效果很好。

程序

s([]).
s([X|Xs]) :- num(X), s(Xs).

num(a).
num(b).
num(c).
num(d).

输出

?- [prologdcg].
% prologdcg compiled 0.00 sec, 2,480 bytes
true.

?- s([a,c,b]).
true.

?- s([a,c,f]).
false.

使用SWI-prolog运行。

© www.soinside.com 2019 - 2024. All rights reserved.