为包含相同数量的特定数字的字符串编写 DCG - Prolog [英] Writing DCG for strings containing same number of specific digits - Prolog

问题描述

我正在编写一个 DCG，它将采用 u2v 形式的字符串，其中 u 和 v 不必是等长且u中0的个数必须与v<中1的个数相同/代码>.

I'm working on writing a DCG that would take strings in the form of u2v where u and v do not have to be of equal length and the number of 0's in u must be the same as the number of 1's in v.

到目前为止，我已经能够写出几个在纸上工作的语法，但是当我编码它们并尝试查询时，我通常会在某处结束循环.这是我能得到的最接近的:

So far I've been able to write several grammars that work on paper but when I code them and try a query I typically end up with a loop somewhere. This is the closest I've been able to get:

s-->[2].
s-->u,[0],n.
s-->u,s,v.
n-->s,[1],v.
u-->[1],u.
u-->[].
v-->[0],v.
v-->[].

我可以得到查询 s([0,1,1,2,0,0,1,0],N) 的正确答案. 就是:

I can get the correct answers for the query s([0,1,1,2,0,0,1,0],N). which would be:

N = [] ;
N = [0]

但它不会像它应该的那样以 false 终止.相反，它只是重复这些答案.我对 Prolog 的了解非常有限，而且我主要是从 LPN 自学，所以我猜这更多是我不了解 Prolog 如何评估这些东西的问题.如果有人能解释为什么它不会终止，那将是最有帮助的.

But it doesn't terminate with false after as it should. Instead it just repeats those answers. My knowledge of Prolog is pretty limited and I've been mostly self teaching from LPN, so I'm guessing this is more an issue of me not understanding how Prolog evaluates these kinds of things. If someone could explain why it won't terminate, that would be most helpful.

推荐答案

多有趣的问题！

我立刻想到的是你想利用你的语法结构.例如，要匹配括号，您必须按照以下方式进行操作:

What immediately comes to mind for me is that you want to utilize the structure of your grammar. For instance, to match parentheses you have to do something along the lines of this:

expr --> [].
expr --> ['('], expr, [')'].

那样的话，要么你有括号之间的任何东西，要么你每次都有一个左和右括号.

That way, either you have whatever goes between parens, or you have a left and a right paren, every time.

我看不出有什么明显的方法可以解决这个问题.可能有办法，但我不明白它是什么.然而，由于 Prolog 变量的工作方式，DCG 具有在解析中的不同位置之间传播信息的近乎超自然的能力，即通过为 DCG 规则创建参数，如下所示:

I don't see an obvious way to achieve this kind of breakdown with this problem. There might be a way, but I don't see what it is. However, DCGs have the almost-supernatural ability to propagate information around between different locations in the parse, thanks to the way Prolog's variables work, and that's by creating parameters to the DCG rules, like so:

rule(Stuff) --> ...

无论如何，下一个麻烦是您想要计数某些东西，这意味着可能涉及算术.然而！我们可以通过使用 Peano 数字来作弊，因为我们真正关心的是它们恰好在两边相等，所以我们真的不需要将结果传回给用户.

Anyway, the next snafu is that you're wanting to count something, which means arithmetic might be involved. However! We can cheat a little bit by using Peano numbers, since all we really care about is that they happen to equal each other on both sides, we don't really need to pass the result back to the user.

事不宜迟，这是我想出的解决方案:

Without further ado, here's the solution I came up with:

u2v    --> u2v(_).
u2v(N) --> u(N), [2], v(N).

u(0)    --> [].
u(s(N)) --> [0], u(N).
u(N)    --> [X], { member(X, [1,2,3,4,5,6,7,8,9]) }, u(N).

v(0)    --> [].
v(s(N)) --> [1], v(N).
v(N)    --> [X], { member(X, [0,2,3,4,5,6,7,8,9]) }, v(N).

我确信有更好的方法来编写此代码(甚至可能有完全更好的方法)，但在我有限的测试中，这个方法似乎确实有效.它甚至会生成，除了两边讨厌的无限递归.

I'm sure there are nicer ways to write this code (there may even be totally superior approaches) but this one does seem to work in my limited testing. It would even generate, except for the pesky unbounded recursion on both sides.

解决方案的关键是这一行:

The crux of the solution is this line:

u2v(N) --> u(N), [2], v(N).

事实上，您不需要保留 N，但我发现它对调试很有用.这里最重要的是u(N) 匹配v(N).那么 u//1 和 v//1 都具有相同的结构:首先，一个不匹配的基本情况，然后是一个匹配所需数字的归纳情况，然后递增计数，Peano-style (0, s(0), s(s(0)), s(s(s(s(0))), ...)，然后是与其他数字匹配的替代归纳案例并向前传播前一个计数.

In fact, you don't need to keep the N, but I found it useful for debugging. The essential thing here is that u(N) matches v(N). Then both u//1 and v//1 have the same structure: first, a base-case of matching nothing, then an inductive case that matches the desired number and increments the count, Peano-style (0, s(0), s(s(0)), s(s(s(0))), ...), and then an alternate inductive case that matches the other digits and propagates the previous count forward.

可能可以用 succ/2 而不是这个来做到这一点，但我担心需要将纯 Prolog 的一部分放置在哪里才能让它运行.和皮亚诺一起走这条路对我来说似乎更简单.(甚至可能有一种 clpfd 方法.)

It would probably be possible to do this with succ/2 instead of this, but I worry about where one would need to place the bit of pure Prolog to make it go. Going this route with Peano seemed simpler to me. (There's probably even a clpfd approach.)

无论如何，我希望这会有所帮助！

Anyway, I hope this helps!

这篇关于为包含相同数量的特定数字的字符串编写 DCG - Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！