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 中的定语子句语法 (DCG)。这基本上是语法糖，允许您编写读起来更像语法而不是 Prolog 谓词的语法。如果您了解它们是如何工作的，那么您可能会对如何在 Prolog 中进行解析有一个很好的理解。