8.4.1 Representing the Chart

We first have to decide how to represent the chart in Prolog.

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).