DCG 和左递归 [英] DCG and left recursion
问题描述
我正在尝试实现一个 dcg，它采用一组 {a,b,c,d}* 形式的字符串.我遇到的问题是，如果我有一个 s([a,c,b],[]),它返回true这是正确的答案但是当我有一个s([a,c,f],[])形式的查询时，它不返回一个答案并且它用完了本地堆栈.
s -->[].s -->s，数量.数量 -->[一种].数量-->[乙].数量-->[C].数量-->[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 来完成此操作.因此，只有在找到第一个或多个答案后，查询才可能开始循环.随着时间的推移，这变得非常令人困惑:您是否应该始终记住该谓词可能会产生答案?另一个谓词产生两个，然后才循环?
最简单的方法是建立通用终止的概念，这是这里最可靠的概念.Goal 终止当 Goal, false 终止.这个 false 目标对应于无限期地击中 SPACE ；直到整个查询失败的那一刻.
现在试试:
<预>?- 短语(s,[a,c,f]), 假.** 循环 **还有:
<预>?- 短语(s,[a,b,c]), 假.** 循环 **从通用终止的角度来看，两个查询都不会终止.在最常用的词中，终止等同于通用终止.找到答案或解决方案就是这样，但不是终止.因此，有些查询看起来无害，只要您对答案感到满意，但实际上不会终止.但是很高兴您这么快就发现了这一点:如果您仅在正在运行的应用程序中发现这一点，情况会更糟.
找出原因
作为下一步，让我们确定不终止的原因.您可能会尝试使用调试器或跟踪器，但很可能它根本不会给您一个很好的解释.但是有一个更简单的方法:使用 failure-切片.只需将非终结符 {false} 添加到您的语法中；并将目标 false 转化为谓词.我们可以在这里利用一个非常漂亮的属性:
如果失败切片没有终止那么原始程序不会终止.
因此，如果我们很幸运并且找到了这样的切片，那么我们肯定知道只有在剩余的可见部分发生变化以某种方式时才会发生终止.最有用的切片是:
<预>?- 短语(s,[a,b,c]), false你的程序所剩无几！num//0不见了！没有人关心 num//0.这意味着:num//0 可以描述任何事情，不管是什么—程序仍然会循环.
为了解决这个问题，我们必须改变可见部分的一些东西.剩下的不多了！正如您已经观察到的，我们这里有一个左递归.修复它的经典方法是:
重新表述语法
您可以轻松地将语法重新表述为正确的递归:
<预>s --> [].s --> 数，s.现在两个查询都终止了.这是编译器构造中也已知的经典方法.
但是在某些情况下，语法的重新表述是不合适的.这个简单的例子不是这样的，但它经常出现在有一些有意的歧义的语法中.在这种情况下，您仍然可以:
添加终止诱导参数
<预>?- Xs = [a,b,c], 短语(s(Xs,[]), Xs).s(Xs,Xs) --> [].s([_|Xs0],Xs) --> s(Xs0,Xs1), num, {Xs1=Xs}.固有的非终止查询
无论您做什么，请记住并非每个查询都可以终止.如果你问:»告诉我所有存在的自然数 -ndash;真的所有这些，一个接一个！« 那么回答这个问题的唯一方法就是从 0 开始，然后把它们数起来.所以有疑问，那里有无数的答案/解决方案，我们不能责怪可怜的 Prolog 试图实现我们的愿望.但是，在这种情况下，我们最喜欢的是公平地枚举所有解决方案.我们可以使用具有良好终止特性的文法来做到这一点；也就是说，一个以固定长度列表结尾的文法.像这样:
<预>?- 长度(Xs，M)，短语(s，Xs).有关如何应用故障切片的其他示例，请参阅标签 故障切片.
I am trying to implement a dcg that takes a set of strings of the form {a,b,c,d}*.The problem i have is if I have a query of the form s([a,c,b],[]),It returns true which is the right answer but when i have a query of the form s([a,c,f],[]),It does not return an answer and it runs out of local stack.
s --> [].
s --> s,num.
num --> [a].
num--> [b].
num--> [c].
num--> [d].
Use phrase/2
Let's try phrase(s,[a,b,c]) in place of s([a,b,c],[]). The reason is very simple: In this manner we are making clear that we are using a DCG (dcg) and not an ordinary predicate. phrase/2 is the "official" interface to grammars.
So your first question is why does phrase(s,[a,c,f]) not terminate while phrase(s,[a,b,c]) "gives the right answer" — as you say. Now, that is quick to answer: both do not terminate! But phrase(s,[a,b,c]) finds a solution/answer.
Universal termination
These are two things to distinguish: If you enter a query and you get an answer like true or X = a; you might be interested to get more. Usually you do this by entering SPACE or ;ENTER at the toplevel. A query thus might start looping only after the first or several answers are found. This gets pretty confusing over time: Should you always remember that this predicate might produce an answer ; another predicate produces two and only later will loop?
The easiest way out is to establish the notion of universal termination which is the most robust notion here. A Goal terminates iff Goal, false terminates. This false goal corresponds to hitting SPACE indefinitely ; up to the moment when the entire query fails.
So now try:
?- phrase(s,[a,c,f]), false. ** LOOPS **
But also:
?- phrase(s,[a,b,c]), false. ** LOOPS **
From the viewpoint of universal termination both queries do not terminate. In the most frequent usage of the words, termination is tantamount to universal termination. And finding an answer or a solution is just that, but no kind of termination. So there are queries which look harmless as long as you are happy with an answer but which essentially do not terminate. But be happy that you found out about this so quickly: It would be much worse if you found this out only in a running application.
Identify the reason
As a next step let's identify the reason for non-termination. You might try a debugger or a tracer but most probably it will not give you a good explanation at all. But there is an easier way out: use a failure-slice. Simply add non-terminals {false} into your grammar ; and goals false into predicates. We can exploit here a very beautiful property:
If the failure-slice does not terminate then the original program does not terminate.
So, if we are lucky and we find such a slice, then we know for sure that termination will only happen if the remaining visible part is changed somehow. The slice which is most helpful is:
?- phrase(s,[a,b,c]), falses --> [], {false}. s --> s, {false},num.
There is not much left of your program! Gone is num//0! Nobody cares about num//0. That means: num//0 could describe anything, no matter what — the program would still loop.
To fix the problem we have to change something in the visible part. There is not much left! As you have already observed, we have here a left recursion. The classical way to fix it is:
Reformulate the grammar
You can easily reformulate your grammar into right recursion:
s --> []. s --> num, s.
Now both queries terminate. This is the classical way also known in compiler construction.
But there are situations where a reformulation of the grammar is not appropriate. This simple example is not of this kind, but it frequently happens in grammars with some intended ambiguity. In that case you still can:
Add termination inducing arguments
?- Xs = [a,b,c], phrase(s(Xs,[]), Xs).
s(Xs,Xs) --> [].
s([_|Xs0],Xs) --> s(Xs0,Xs1), num, {Xs1=Xs}.
Inherently non-terminating queries
Whatever you do, keep in mind that not every query can terminate. If you ask: »Tell me all the natural numbers that exist – really all of them, one by one!« Then the only way to answer this is by starting with, say, 0 and count them up. So there are queries, where there is an infinity of answers/solutions and we cannot blame poor Prolog to attempt to fulfill our wish. However, what we most like in such a situation is to enumerate all solutions in a fair manner. We can do this best with a grammar with good termination properties; that is, a grammar that terminates for a list of fixed length. Like so:
?- length(Xs, M), phrase(s, Xs).
For about other examples how to apply failure-slices, see tag failure-slice.
这篇关于DCG 和左递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
