Representing the Arcs

Before we look at the implementation of the parser, we have to decide how to represent arcs. We are going to use the same strategy as in the last chapter.

Before we look at the implementation of the parser, we have to decide how to represent arcs. We are going to use the same strategy as in the last chapter. For that purpose we use a predicate which we call arc. In addition to the positions that the arc spans, this predicate has to encode a dotted rule. We will therefore use arc with five arguments in the following way:

arc(Start, End, LHS, FoundSoFar, ToFind)

The three last arguments represent the information contained in the `.' notation of arc labels. LHS is the left hand side of the respective rule, FoundSoFar is the list of those symbols that are to the left of the dot, and ToFind are those that are to the right of the dot. For example, the arc

is represented as

arc(2, 3, vp, [dv], [np, pp])

One important thing to notice is that we represent the categories in FoundSoFar in reversed order. So

would be

arc(2, 5, vp, [np, dv], [pp]).