We'll now implement a bottom-up chart recognizer in Prolog. To do so, we first have to decide how to represent the chart. As already mentioned in the last section, we want to use the Prolog database for that. More explicitly, we will use the predicates
scan/3 and
arc/3. The predicate
scan encodes the position of the words. For example, we take
scan(2,3,loves) to mean that the word
loves is between positions 2 and 3 of the input sentence. The initial empty chart for the input sentence
vincent loves mia, which doesn't contain any arcs, yet, thus looks like this in Prolog:
scan(0,1,vincent).
scan(1,2,loves).
scan(2,3,mia).
We will represent arcs using the predicate
arc/3 in the obvious way:
arc(0,2,np) means that there is an
np-arc between 0 and 2. So, the chart
------------- s ---------------
| |
| |
| --------- vp ------
| | |
| | |
-- np -- -- np --
| | | |
| | | |
-- pn -- -- tv -- -- pn --
| | | |
| | | |
0 vincent 1 loves 2 mia 3
is represented in Prolog as
scan(0,1,vincent).
scan(1,2,loves).
scan(2,3,mia).
arc(0,1,pn).
arc(0,1,np).
arc(1,2,tv).
arc(2,3,pn).
arc(2,3,np).
arc(1,3,vp).
arc(0,3,s).