Created
March 27, 2013 05:38
-
-
Save mikebern/5251965 to your computer and use it in GitHub Desktop.
Parse trees using Prolog
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% | |
% 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). | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment