4

我正在尝试匹配一些句子（例如 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,')',')']).

不会工作。

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

4

2 回答 2

5

首先，每当您使用 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

所以高层坚持认为除了实际的成功之外还有别的东西。为了以系统的方式缩小范围，我将使用一个，它增加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。

?- 短语(g3,"(1+(1+1))"),假。

因为这个小片段循环，整个程序也循环。请注意，+不再是程序的一部分！这个问题根本没有关系+。

于 2017-08-25T13:01:31.043 回答
4

你的问题是由于规则

n3 --> n3,d3.

这就是所谓的左递归规则。它说要匹配 an n3，你必须首先匹配 an ，你必须首先匹配 an 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 删除左递归语法

于 2017-08-25T11:55:59.223 回答