Not fully understanding Prolog parsers. Why does this return false instead of true?

Question

I am writing some prolog to determine if a given query matches a grammar.

S → F |T N T |ε

F → if B then { S } | if B then { S } else { S }

B → (T E T )

T → x|y|0

E → > | <

N ⇒ +| − | =

Now I write out my terminals, and my rules. To me it seems like this should work, but it doesnt.

t(x).
t(y).
t(0).

e(>).
e(<).

n(+).
n(-).
n(=).

% Non Terminals
s([]).
s([T1, N, T2]) :-
    t(T1), n(N), t(T2).
s(S) :-
    f(S).
         
b(['(', T1, E, T2, ')']) :-
    t(T1), e(E), t(T2).


f([if, B, then, '{', S, '}']) :-
    write(B),
    b([B]),
    s(S).

f([if, B, then, '{', S, '}', else, '{', S2, '}']):-
    b([B]),
    s(S),
    s(S2).

parse(E1) :-
    s(E1).

When I try and test it with something like:

?-parse([if, '(', x, '>', y, ')', then, '{', x, '-', y, '}']).

I get false instead of true. Can someone explain and maybe point me in the right direction, Thank you!

Answer 1

The naive/easy way to translate the rules you have to a DCG (definite clause grammar):

s --> f | t, n, t | [].

f --> [if], b, [then, '{'], s, ['}'].
f --> [if], b, [then, '{'], s, ['}', else, '{'], s, ['}'].

b --> ['('], t, e, t, [')'].

t --> [x] | [y] | [z].

e --> [>] | [<].

n --> [+] | [-] | [=].

Note the --> instead of :- for DCG rule definition. Note also how the literals have to be put in an explicit list in the rule definitions.

When I load this and run your example, I get:

?- phrase(s, [if, '(', x, '>', y, ')', then, '{', x, '-', y, '}']).
true .

I use phrase/2 (instead of a hand-written "parse") to evaluate a DCG rule (the non-terminal s) on the input list.

If you want to get the actual parse tree you'd have to do more than this.