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

但是对于 input isMatched([a,b,a])，它用完了堆栈。

我该如何解决？

Answer 1

听起来像家庭作业，所以我不会尝试为你做。

您可能想看看 Prolog 中的定句语法 (DCG)。这基本上是一种语法糖，它允许您编写读起来更像语法而不是 Prolog 谓词的语法。如果您了解这些是如何工作的，那么您可能会对如何在 Prolog 中进行解析有一个不错的了解。