% file:     dcg5.pl
% author:   Bob Keller
% purpose:  Solution to assignment 5, problem 5 in Prolog DCG notation

% show(Height) will list all generable strings with height at most Height

show(Height) :-
    setof(Result, gen(Height, Result), Set),
    display(Set).

display([]) :- nl.

display([[_Length, Result, _Height] | X]) :- 
    atom_chars(Atom, Result),
    write(Atom), nl,
    display(X).

% gen(D, R) will generate as result R all phrases of height at most D

gen(Height, [Length, Result, Height]) :-
        x(Height, Result, []),  % x is the start symbol of the grammar
        length(Result, Length).        

% x is the start symbol of the grammar

x(H) --> {H > 1, H1 is H-1}, y(H1).
x(H) --> {H > 1, H1 is H-1}, z(H1).

y(H) --> {H > 1}, [].
y(H) --> {H > 1, H1 is H-1}, ['0'], t(H1), y(H1).

z(H) --> {H > 1, H1 is H-1}, ['0'], t(H1), z(H1).
z(H) --> {H > 1, H1 is H-1}, ['0'], u(H1), v(H1).

t(H) --> {H > 1, H1 is H-1}, ['0'], t(H1), t(H1).

u(H) --> {H > 1, H1 is H-1}, ['0'], t(H1), u(H1).
u(H) --> {H > 1, H1 is H-1}, ['0'], u(H1), w(H1).

u(H) --> {H > 1}, ['1'].

w(H) --> {H > 1}, ['1'].

v(H) --> {H > 1}, [].