Prolog DCG:匹配链上的不同符号

Question

我正在尝试匹配一些句子(例如 001 [0,0,1]、(1+(1/0(( [

'('，1，+，'('，1，/，0，'('，'(']，等等。我让自己跟随小型DCG。

g3 --> s3.
s3 --> e3.
e3 --> eAdd.
e3 --> eMin.
e3 --> eMul.
e3 --> eDiv.
e3 --> n3.
eAdd --> ['('],e3,['+'],e3,[')'].
eMin --> ['('],e3,['-'],e3,[')'].
eMul --> ['('],e3,['*'],e3,[')'].
eDiv --> ['('],e3,['/'],e3,[')'].

n3 --> d3.
n3 --> n3,d3.
d3 --> [0].
d3 --> [1].

现在我的问题是，它与使用 -，* 或/的句子不匹配，但它仅适用于仅使用 + 的递归句子。

例如：

phrase(g3,['(',1,'+','(',1,'+',1,')',')']).

会工作，但是

phrase(g3,['(',1,'+','(',1,'/',1,')',')']).

行不通。

任何帮助将不胜感激，谢谢！

Answer 1

首先，无论何时使用 DCG，请考虑

:- set_prolog_flag(double_quotes, chars).

这允许使用更具可读性的语法。 以下是规则 以及由于此约定而更改的查询。

:- set_prolog_flag(double_quotes, chars).
eAdd --> "(", e3, "+", e3, ")".
eMin --> "(", e3, "-", e3, ")".
eMul --> "(", e3, "*", e3, ")".
eDiv --> "(", e3, "/", e3, ")".
d3 --> "0".
d3 --> "1".
?- phrase(g3,"(1+(1+1))").
?- phrase(g3,"(1+(1/1))").

请注意，您的第一个查询已经有问题，即使它成功了。 这可以在顶层轻松看到：

?- phrase(g3,"(1+(1+1))").
true
;  resource_error(_). % ERROR: Out of local stack

所以高层坚持认为，除了 实际成功。 为了系统地缩小范围，我将使用 一个失败切片，为常规目标增加false{false}语法范围内。

：- set_prolog_flag(double_quotes，字符(。 g3 --> s3，{false}. S3 --> E3，{false}.e3 -->{false}， eAdd.e3 -->{false}， eMin.e3 -->{false}， eMul.e3 -->{false}， eDiv. e3 --> n3，{false}.n3 -->{false}， d3. n3 --> n3，{false}，d3. ？- 短语(g3，"(1+(1+1(("(，假。

因为这个微小的片段循环，整个程序也循环。 注意 该+不再是该计划的一部分！ 问题与无关 完全与+有关。

Answer 2

您的问题是由于规则造成的

n3 --> n3,d3.

这就是所谓的左递归规则。它说要匹配一个n3，你必须首先匹配一个n3，为此你必须首先匹配一个n3，为此你必须首先匹配，等等，这永远不会终止。

基本上，您希望每个递归语法规则在执行递归调用之前首先匹配一些非终端。(类似地，在"正常"Prolog谓词的主体中，在任何递归调用之前，你应该有其他目标。

如果将此规则更改为右递归变体

n3 --> d3,n3.

你的语法变得乖巧：

?- phrase(g3,['(',1,'+','(',1,'+',1,')',')']).
true ;
false.
?- phrase(g3,['(',1,'+','(',1,'/',1,')',')']).
true ;
false.
?- length(L, 6), phrase(g3, L).
L = ['(', 0, +, 0, 0, ')'] ;
L = ['(', 0, +, 0, 1, ')'] ;
L = ['(', 0, +, 1, 0, ')'] ;
L = ['(', 0, +, 1, 1, ')'] ;
L = ['(', 1, +, 0, 0, ')'] ;
L = ['(', 1, +, 0, 1, ')'] ;
L = ['(', 1, +, 1, 0, ')'] ;
L = ['(', 1, +, 1, 1, ')'] ;

等。

以下是一些关于 DCG 中左递归的老问题，它们可能会提供其他有用的信息：

DCG 和左递归

删除 DCG 中的左递归 - Prolog

使用 DCG 删除左递归语法