% Program 6.4, PS p. 168. % *** Changed by Eric Auer according to exercise 6.5 % *** use "runme." for demonstration :-) % A DCG interpreter written as a DCG. % *** providing a local append implementation: myAppend([],B,B). myAppend([A|As],Bs,[A|Cs]) :- myAppend(As,Bs,Cs). :- op(1200,xfx,--->). parse(NT,Tree) --> % *** creates a node with subtrees {NT ---> Body}, parse(Body,BodyList), { ( [_|_] = BodyList % *** ensure BL being a list -> BL = BodyList ; BL = [BodyList] ), Tree =.. [NT|BL] % *** functor of Tree is the NT, % *** arguments are BodyList. This is easier % *** with =.. than with functor and arg. }. parse((Body1,Body2),Tree) --> % *** combine the subtrees parse(Body1,Tree1), parse(Body2,Tree2), { myAppend([Tree1],[Tree2],Tree) }. parse([],[]) --> []. % *** this adds a terminal node/leaf to a list... parse([Word|Rest],[leaf(Word)|RestList]) --> [Word], parse(Rest,RestList). parse({Goals},[]) --> % not added in detail, alternative: {call(Goals)}. % add e.g. a prolog(Goald) leaf % *** Everything from here on is added for exercise 6.5 *** % *** small sample grammar inspired by program 3.12 of the % *** book (englishgram.pl) s ---> np, vp. np ---> det, n. np ---> pn. vp ---> tv, np. vp ---> iv. det ---> [the]. det ---> [a]. det ---> [every]. n ---> [shrdlu]. n ---> [author]. n ---> [book]. n ---> [professor]. n ---> [program]. n ---> [student]. pn ---> [bertrand]. pn ---> [gottlob]. pn ---> [shrdlu]. pn ---> [terry]. tv ---> [concerns]. tv ---> [meets]. tv ---> [writes]. iv ---> [halts]. sentence([shrdlu,halts]). sentence([shrdlu,writes,a,program]). runme :- sentence(S), phrase(parse(s,Tree),S), format('Tree of ~p is:~n~p~n~n',[S,Tree]), fail. % fail-driven loop % note: [a,b,c] = [a|[b,c]] ... [a] = [a|[]] ...