prolog - Prolog program to recognize context free grammar a^n b^n

Question

Using Prolog I'm trying to write a predicate that recognizes context free grammar and returns true if the input list matches the CFG.
The alphabet of the input consists only of a,b. The CFG i'm trying to match is

S-> TT
T -> aTb | ab

I'm not quite sure how to implement this, mainly the T rule.

s(S0,S):-t(S0,S),t(S1,S).
t(S0,S):-S0 = a, t(S1,S), S1 = b; S0 = a, S1 = b.

match([H|T] :- s(H,T).

So if I query [a, a, b, b] it should return true. However, I'm just getting an infinite loop. I'm not quite sure how to implement the a^n b^n rule.

Answer 1

我会这样写CFG：

S -> T
T -> a T b | {epsilon}

直接转换为 DCG：

s --> t.
t --> [].
t --> a, t, b.

注意我交换了 epsilon 规则，以获得生成短语的能力。

手动翻译 DCG ：

s(S0,S) :- t(S0,S).
t(S0,S0).
t(S0,S) :- S0=[a|S1], t(S1,S2), S2=[b|S].

产量

?- phrase(s,L).
L = [] ;
L = [a, b] ;
L = [a, a, b, b] ;
L = [a, a, a, b, b, b] ;
...