Пролог Вопрос - Простая реализация грамматики

Question

Если у меня есть следующая грамматика:

S → ε

S → a S b S

Как мне реализовать ее в Прологе?

Я пробовал это:

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

Звучит как домашняя работа, поэтому я не буду пытаться сделать это для вас.

Возможно, вы захотите взглянуть на определенные грамматики предложений (DCG) в Прологе. Это в основном синтаксический сахар, который позволяет писать грамматики, которые читаются больше как грамматики, чем предикаты Пролога. Если вы понимаете, как это работает, то у вас, вероятно, будет приличное понимание того, как анализировать в Прологе.