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，为此，必须先等等，这永远不会终止。

基本上，您希望每个递归语法规则在执行递归调用之前首先匹配一些非终止符。 （同样，在“正常”的Prolog谓词的机构，如果您有任何递归调用之前其他目标。）

如果你改变了这个规则到右递归variant

n3 --> d3,n3. 

你的语法变得很好-behaved：

?- 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, true). 

这允许使用更可读的语法。以下是该约定因该改变规则 和查询。

:- 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. 

因为这个小片段的循环，整个程序循环，太。注 即+不再是程序的一部分！这个问题根本没有与+一起 。