Parse trees using Prolog

gistfile1.prolog

%
% parses given sentence, outputs and draws all possible parse trees
% example is from Coursera NLP course by Michael Collins 
%
% tested with gprolog
% to compile: gplc --no-top-level parse_tree.pl
% ignore alignment warnings
% to run: ./parse_tree
%

%
%  based on several examples found on the interwebs
%  and on "Prolog and Natural-Language Analysis" by F. Pereira and S. Shieber
%  available at http://www.mtome.com/Publications/PNLA/prolog-digital.pdf
%  


:- initialization(main).

% entry point
% arg1 - parse tree output, arg2 - init for the recursion depth counter, 
% arg3 - max recursion depth, arg4 - sentence to parse, 
% arg5 - all words should be parsed, so the remaining words should be []
main :- noun_phrase(M, 0, 5, [the, fast, car, mechanic], []),   nl, nl, write(M), nl, nl, nl, draw_tree(M, 5),fail.

main.

% grammar description

noun_phrase(np(D, N), Cnt, Limit) --> {Cnt1 is inc(Cnt)}, determiner(D, Cnt1, Limit), noun(N, Cnt1, Limit).

% clauses with the same head should be grouped together

% prevent infinite left-term  recursion
noun(_, Cnt, Limit) -->   {Cnt > Limit}, !, {fail}.  % reached depth limit

noun(n(N1,N2), Cnt, Limit) --> {Cnt1 is inc(Cnt)}, noun(N1, Cnt1, Limit), noun(N2, Cnt1, Limit). 

noun(n(JJ,N), Cnt, Limit) --> {Cnt1 is inc(Cnt)}, adjective(JJ, Cnt1, Limit), noun(N, Cnt1, Limit).

noun(n(NN), Cnt, Limit) --> {Cnt1 is inc(Cnt)}, noun_noun(NN, Cnt1, Limit).

% keep all atoms lowercase
noun_noun(nn(car),_,_) --> [car].

noun_noun(nn(mechanic),_,_) --> [mechanic].

adjective(adj(fast),_,_) --> [fast].

determiner(d(the),_,_) --> [the].


% clauses to draw the tree
draw_tree(Sym,Tab) :- nonvar(Sym), functor(Sym,F,A), A > 0,
   tab(Tab),
   write('|-- '),
   write(Sym),
   nl,
   Sym =.. [F|ArgsX],
   Tab5 is Tab + 5,
   draw_tree_list(ArgsX,Tab5).

draw_tree(Node,Tab) :- atomic(Node),
   tab(Tab),
   write('|-- '),
   write(Node),
   nl.   
   
draw_tree_list([], _).

draw_tree_list([B | Bs],Tab) :- draw_tree(B,Tab), draw_tree_list(Bs,Tab).