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

您的问题是由于规则

n3 --> n3,d3.

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

基本上，您希望每个递归语法规则在执行递归调用之前首先匹配一些非终结符。（同样，在 "normal" 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 and left recursion

Removing left recursion in DCG - Prolog

Removing left recursion grammar using DCG

Answer 2

首先，无论何时使用 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 ;
ERROR: Out of local stack

所以顶层坚持认为除了实际成功。为了系统地缩小范围，我将使用 failure-slice 将 false 添加到常规目标和 {false}语法内。

:- set_prolog_flag(double_quotes, chars).

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.

?- phrase(g3,"(1+(1+1))"), false.

因为这个小片段在循环，所以整个程序也在循环。笔记 + 不再是程序的一部分！问题无关完全使用 +。

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

Prolog DCG: Match different symbols on a chain

recursion

prolog

left-recursion

dcg

failure-slice