プロローグで書かれたRegEx Parser

Question

私は数時間、この宿題の問題で壁に頭を叩いていました。 Prologで正規表現を解析する必要があります。ほとんどの場合、私が使っている述語は、SWI-Prologのスタック領域を使い果たしてしまう正規表現と文字列コンボがあります。最初のものは動作し、二番目は、スタックが不足

star(star(char(a))), [] 
star(star(char(a))), [a] 

：ここに正規表現文字列の組み合わせの2、動作しない一対一のサンプルです。

ここで私が使用している述語です：

re_match(epsilon, []). 
re_match(char(Letter), [Letter]). 
re_match(star(_), []). 
re_match(seq(Rx1, Rx2), List) :- append(List1, List2, List), re_match(Rx2, List2), re_match(Rx1, List1). 
re_match(alt(Rx1, Rx2), List) :- re_match(Rx1, List); re_match(Rx2, List). 
re_match(star(Rx), List) :- append(List1, List2, List), re_match(Rx, List1), re_match(star(Rx), List2). 

私はそれが正しい動作させるために行うために必要なものを変更わからないんだけど、私が行うことは他に何かわかりません。

また、List：--end（List1、List2、List）を[H | T]に変更しても、いずれの例でもtrueと評価されません。

Answer 1

私は今、SWIプロローグへのアクセス権を持っているが、ここでは推測ですしないでください。

は、「何かを食べにre_matchを強制的に

re_match(star(Rx), List) :- append([H|List1], List2, List), 
          re_match(Rx, [H|List1]), 
          re_match(star(Rx), List2). 

に

re_match(star(Rx), List) :- append(List1, List2, List), 
          re_match(Rx, List1), 
          re_match(star(Rx), List2). 

を変更してみてください"それは星の構造を反復するとき。

Answer 2

は、読みやすくするためDCG表記の使用を検討して終了プロパティの詳細簡単に理由：長くますます生成する長さ/ 2を使用して

:- op(100, xf, *). 

rexp(eps)  --> []. 
rexp([T])  --> [T]. 
rexp(_*)  --> []. 
rexp(R*)  --> rexp(R), rexp(R*). 
rexp(s(R1,R2)) --> rexp(R1), rexp(R2). 
rexp((R1|R2)) --> (rexp(R1) ; rexp(R2)). 

例は、正規表現にマッチしている文字列を生成するために示しています

?- length(Ls, _), phrase(rexp(s(([a]|[b]),[c]*)), Ls). 
Ls = [a] ; 
Ls = [b] ; 
Ls = [a, c] ; 
Ls = [b, c] ; 
Ls = [a, c, c] ; 
etc.