next up previous contents
Next: Solutions and Comments on Chapter 9 Up: Solutions and Comments on Chapter 8 Previous: Solutions and Comments on Chapter 8

Exercise Chapter 8.1


  1.  
     [the,clever,boy,buys,a,sweet]
    

    [the,clever,sweet,buys,a,clever,clever,boy]

    (etcetera)

    These are legitimate inputs produced by the query

     
    ?- s([the,clever,boy,buys,a,sweet],[]).
    

    ?- s([the,clever,sweet,buys,a,clever,clever,boy],[]).

    (etcetera)

    It is not so immediately apparent that this grammar can generate sentences as well. What is the order in which sentences are generated?

     
    [a,boy,buys,a,boy]
    

    [a,boy,buys,a,sweet]

    [a,boy,buys,the,boy]

    [a,boy,buys,the,sweet]

    [a,boy,buys,a,clever,boy]

    [a,boy,buys,a,clever,sweet]

    [a,boy,buys,a,clever,clever,boy]

    [a,boy,buys,a,clever,clever,sweet]

    [a,boy,buys,a,clever,clever,clever,boy]

    (and so on)

  2. Here is just one example ---there are various ways of doing this.
     
    s(sentence(NP-VP))		  --> 		 np(NP),
    

    vp(VP).

    np(nounphrase(Det-N)) --> det(Det),

    noun(N).

    np(nounphrase(Det-Adjs-N)) --> det(Det),

    adjs(Adjs),

    noun(N).

    vp(verbphrase(V-NP)) --> verb(V),

    np(NP).

    det(determiner(a)) --> [a].

    det(determiner(the)) --> [the].

    adjs(adjectives(Adj)) --> adj(Adj).

    adjs(adjectives(Adj-Adjs)) --> adj(Adj),

    adjs(Adjs).

    adj(adjective(clever)) --> [clever].

    noun(noun(boy)) --> [boy].

    noun(noun(sweet)) --> [sweet].

    verb(verb(buys)) --> [buys].

    which produces (in a much less readable form than the following):

     
    X = sentence(
    

    nounphrase(

    determiner(a)

    -

    adjectives(adjective(clever))

    -

    noun(boy))

    -

    verbphrase(

    verb(buys)

    -

    nounphrase(

    determiner(a)

    -

    adjectives(adjective(clever)-adjectives(adjective(clever)))

    -

    noun(boy))))

  3. This is very hard to do in general. The issue here is one of `robust parsing' and it is a major research topic. Consequently, there is no complete answer but a first attempt might look like:

     
    s(sentence(NP-VP))  		            --> 		 np(NP),
    

    vp(VP).

    np(nounphrase(Det-N)) --> det(Det),

    noun(N).

    np(nounphrase(Det-Adjs-N)) --> det(Det),

    adjs(Adjs),

    noun(N).

    vp(verbphrase(V-NP)) --> verb(V),

    np(NP).

    det(determiner(a)) --> [a].

    det(determiner(the)) --> [the].

    det(unknown_det(X)) --> [X],

    {\+(known(X))}.

    adjs(adjectives(Adj)) --> adj(Adj).

    adjs(adjectives(A-Adjs)) --> adj(A),

    adjs(Adjs).

    adj(adjective(clever)) --> [clever].

    adj(unknown_adj(X)) --> [X],

    {\+(known(X))}.

    noun(noun(boy)) --> [boy].

    noun(noun(sweet)) --> [sweet].

    noun(unknown_noun(X)) --> [X],

    {\+(known(X))}.

    verb(verb(buys)) --> [buys].

    verb(unknown_verb(X)) --> [X],

    {\+(known(X))}.

    known(X):-noun(noun(X),_,_).

    known(X):-verb(verb(X),_,_).

    known(X):-det(determiner(X),_,_).

    known(X):-adj(adjective(X),_,_).

    Some points to note:
    1. It cannot cope with missing words so this goal fails badly. We could try to extend it to meet this problem. For example, we might like the following query to succeed:
       
      s(X,[the,clever,buys,a,sweet],[]).
      

    2. It does cope quite well with more than one misspelling provided the sentence structure is acceptable ---as in the query:
       
      s(X,[the,clever,silly,buoy,buys,a,sweet],[]).
      

    3. The known/1 predicate is not at all clever.



next up previous contents
Next: Solutions and Comments for Chapter 9 Up: Solutions and Comments Chapter 8 Previous: Solutions and Comments Chapter 8



Paul Brna
Mon May 24 20:14:48 BST 1999