7

私はこの宿題の問題で数時間頭を壁にぶつけていました。Prolog で正規表現を解析する必要があります。ほとんどの場合、私が持っている述語は機能しますが、いくつかの正規表現と文字列の組み合わせにより、SWI-Prolog のスタック スペースが不足してしまいます。2 つの Regex 文字列の組み合わせのサンプルを次に示します。1 つは機能し、もう 1 つは機能しません。

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 :- append(List1, List2, List) を [H|T] に変更しても、例の 1 つで true と評価されません。

4

2 に答える 2

6

可読性を高め、終了プロパティについてより簡単に推論できるように、DCG 表記を使用することを検討してください。

:- 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/2 を使用して徐々に長くなるリストを生成し、正規表現に一致する文字列を生成する例:

?- length(Ls, _), phrase(rexp(s(([a]|[b]),[c]*)), Ls).
Ls = [a] ;
Ls = [b] ;
Ls = [a, c] ;
Ls = [b, c] ;
Ls = [a, c, c] ;
etc.
于 2011-01-22T10:05:17.290 に答える
5

私は現在 SWI Prolog にアクセスできませんが、推測は次のとおりです。

変更してみる

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

に

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

re_matchスター構造を反復するときに「何かを食べる」ことを強制します。

于 2011-01-22T08:05:58.393 に答える