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の述語の体で、あなたは、任意の再帰呼び出しの前に他の目標を持っている必要があります。）

あなたは右再帰的な変種に

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, ')'] ; 

など

は、追加の有用な情報を提供するかもしれないDCGsで左再帰についていくつかの古い質問です：

DCG and left recursion

Removing left recursion in DCG - Prolog

Removing left recursion grammar using DCG

Answer 2

まず第一に、あなたがDCGsを使用している時はいつでも、これははるかに読みやすい構文を使用することを許可

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

だからトップレベルは 実際の成功から離れて何か他のものがあることを主張しました。体系的な方法でこれを絞り込むために私は文法内で定期的に目標と {false}に falseを追加 failure-sliceを使用します。

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

このため、小さなフラグメントループ、プログラム全体は、あまりにも、ループします。 +はもはやプログラムの一部ではありません。問題には には何もなかったので、+とはまったく関係ありません。