next up previous contents
Next: A Second Approach Up: Parsing in Prolog Previous: The Parse Tree

First Attempt at Parsing

We assume that we will parse sentences converted to list format. That is, the sentence ``the man ate the cake'' will be represented by the list [the,man,ate,the,cake].

We use append/3 to glue two lists together. The idea is that append/3 returns the result of gluing takes input as lists in the first and second argument positions and returns the result in the third position.

 
sentence(S):-

append(NP,VP,S),

noun_phrase(NP),

verb_phrase(VP).

noun_phrase(NP):-

append(Det,Noun,NP),

determiner(Det),

noun(Noun).

verb_phrase(VP):-

append(Verb,NP,VP),

verb(Verb),

noun_phrase(NP).

determiner([a]).

determiner([the]).

noun([man]).

noun([cake]).

verb([ate]).

Here is what happens to the query:
 
?- sentence([the,man,ate,the cake]).

append/3 succeeds with NP=[], VP=[the,man,ate,the,cake]

noun_phrase/1 fails

append/3 succeeds with NP=[the], VP=[man,ate,the,cake]

noun_phrase/1 fails

append/3 succeeds with NP=[the,man], VP=[ate,the,cake]

noun_phrase/1 succeeds

...

verb_phrase/1 succeeds

This is all very well but the process of parsing with this method is heavily non deterministic.

Also, it suffers from not being a very flexible way of expressing some situations. For example, the problem of adjectives:

 
the quick fox

is also a noun phrase.

We might try to parse this kind of noun phrase with the extra clause:

 
noun_phrase(NP):-

append(Det,Bit,NP),

determiner(Det),

append(Adj,Noun,Bit),

adjective(Adj),

noun(Noun).

A little ungainly.



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