/*-------------------------------------------------------------*/
/*         Parsing NL by DD-rules                              */
/*         (C) 1993 Lydia Sinapova, Zdravko Markov, II-BAS     */
/*-------------------------------------------------------------*/
/*
DESCRIPTION:
-----------
The program illustrates how to implement grammars by using
DD-rules. It also shows a way of combining DD-rules and
net-clauses for the purposes of semantic analysis of NL.
 
For each DD-rule the corresponding grammar rule is shown as a
comment. In a grammar rule the order of the symbols is specified
by putting them in a particular sequence. To specify the order of
the symbols processed by a DD-rule the free nodes are supplied
with two additional variables to "link" the symbols in a given
order. At the level of terminals these variables represent the
consecutive numbers of the symbols as appeared in the string to
be parsed. The structure of a non-terminal symbol in a grammar is
represented by a local parse tree rooted at that symbol. A local
tree covers a sequence of terminal symbols if the first symbol of
the sequence is the leftmost leaf of the tree and the last
one is the rightmost leaf of the tree. For example, the free node
np(NP,I,J) specifies that the tree NP has the structure of a noun
phrase and covers a sequence of terminal symbols from I to J.
The adjacency of the symbols NP and VP in the rule S -> NP VP is
expressed by using the same consecutive numbers for the rightmost
leaf of NP and for the leftmost leaf of VP (the variable J) in
the corresponding DD-rule. Following these considerations, the
problem for parsing a sentence is to find a parse tree which
covers the sequence of terminal symbols from 1 to N, where N is
the consecutive number of the last terminal. This is expressed by
the first DD-rule in the program. To activate the DD-rules we
have to provide a sequence of words terminating with a data item,
specifying the consecutive number of the last word.
 
After successful parsing, the top level DD-rule in the program
prints the parse tree and calls the semantic layer of the
program, the Prolog procedure "sem". This procedure processes the
parse tree of the verb phrase and assigns semantic roles
("action" and "object") to the syntactic categories (vp and np).
These roles are used to activate the case frames explaining the
semantics of the parsed sentence. However since the first
sentence is ambiguous the action "throw" and the object "ball"
can be included in two case frames - case_frame(propel,sphere)
and case_frame(sponsor,dance). To disambiguate the meaning of the
sentence the prepositional phrase is used. The use of "for
charity" will make it clear that the case is sponsoring a ball.
Thus the preposition "for" used in the prepositional phrase
following the verb phrase discriminates the two case frames. This
is implemented by using the variable For, which is bound when
such a "for" appears in the sentence and is included as an
excitatory input in the "sponsor-dance" case frame and as an
inhibitory input in the "propel-sphere" one. The preposition "to"
(connected to the  discriminating variable To) plays a similar
role. Note that the threshold of the first case frame,
case_frame(propel,sphere), is 2. This allows its activation
without any prepositional phrase, as shown by the first query,
i.e. this a way of specifying the default meaning of the "throw"
action.
 
REFERENCE:
---------
Sinapova, L. & Z. Markov. Grammar Representation and Parsing
in a Data-Driven Logic Programming Environment. In: B. du Boulay
and V. Sgurev (eds.), Proceedings of AIMSA'92, Artificial
Intelligence V, North-Holland, 151-159.
*/
 
/*------------------------- DD-rules --------------------------*/
s(s(X,Y),1,N):end_sent(N) => write(s(X,Y)),nl,sem(Y).
np(X,I,J):vp(Y,J,K) => s(s(X,Y),I,K).           /* S -> NP VP  */
pn(X,I,J) => np(np(X),I,J).                     /* NP -> PN    */
n(X,I,J) => np(np(X),I,J).                      /* NP -> N     */
det(X,I,J):n(Y,J,K) => np(np(X,Y),I,K).         /* NP -> Det N */
v(X,I,J):np(Y,J,K) => vp(vp(X,Y),I,K).          /* VP -> V NP  */
vp(X,I,J):pp(Y,J,K) => vp(vp(X,Y),I,K).         /* VP -> VP PP */
p(X,I,J):np(Y,J,K) => pp(pp(X,Y),I,K).          /* PP -> P NP  */
 
/*----------------------- Semantic Level ----------------------*/
sem(vp(V,np(_,N))):-action(V,V),object(N,N).
sem(vp(V,np(N))):-action(V,V),object(N,N).
sem(vp(V,pp(P,_))):-preposition(P,P),sem(V).
 
action(threw,Threw):
object(ball,Ball):
preposition(for,For):
preposition(to,To):
 
node(Threw,Ball,~For,2,write(case(propel,sphere))):
node(Threw,Ball,For,3,write(case(sponsor,dance))).
 
/*----------------- Dictionary (word categories) --------------*/
word(a,I,J,det(a,I,J)).
word(the,I,J,det(the,I,J)).
word(to,I,J,p(to,I,J)).
word(for,I,J,p(for,I,J)).
word(tom,I,J,pn(tom,I,J)).
word(dog,I,J,n(dog,I,J)).
word(ball,I,J,n(ball,I,J)).
word(charity,I,J,n(charity,I,J)).
word(threw,I,J,v(threw,I,J)).
word(gave,I,J,v(gave,I,J)).
 
/*------------------------ Top Level --------------------------*/
sent(I,[X]):-J is I+1,word(X,I,J,P),P,end_sent(J),!.
sent(I,[X|Y]):-J is I+1,word(X,I,J,P),P,sent(J,Y).
 
/*-------------------------------------------------------------*/
/* EXAMPLES:                                                   */
/*-------------------------------------------------------------*/
/*
?- sent(1,[tom,threw,a,ball]).
s(np(tom),vp(threw,np(a,ball)))
case(propel,sphere)
 
?- sent(1,[tom,threw,a,ball,for,charity]).
s(np(tom),vp(vp(threw,np(a,ball)),pp(for,np(charity))))
case(sponsor,dance)
 
?- sent(1,[tom,threw,a,ball,to,the,dog]).
s(np(tom),vp(vp(threw,np(a,ball)),pp(to,np(the,dog))))
case(propel,sphere)
 
*/