prolog - Prologの質問-簡単な文法の実装

Question

次の文法がある場合：

S → ε

S → a S b S

Prologに実装するにはどうすればよいですか？

私はこれを試しました：

isMatched([]).

isMatched([a,b]).

isMatched([a|[S1|[b|S2]]]) :- isMatched(S1), isMatched(S2).

ただし、リストの先頭をリストにすることはできないため、明らかに機能しません。

次に、次のように新しいバージョンを実装してみました。

conc([], R, R).

conc([H|T], L, [H|R]) :- conc(T, L, R).

isMatched([]).

isMatched([a,b]).

isMatched(List) :- conc([a], S1, List3), isMatched(S1), conc(List3, [b], List2), conc(List2, S2, List), isMatched(S2).

ただし、入力isMatched([a,b,a])の場合、スタックが不足します。

これを修正するにはどうすればよいですか？

Answer 1

宿題のように聞こえるので、私はあなたのためにそれをしようとはしません。

Prologのdefiniteclausegrammars（DCG）を確認することをお勧めします。これは基本的に構文糖衣であり、Prolog述語よりも文法に似た文法を書くことができます。これらがどのように機能するかを理解していれば、おそらくPrologで解析する方法を十分に理解しているでしょう。