9.1.5 Looking to the Right is Enough

So far, edges from the agenda have to be combined to the left and to the right with edges from the chart. But if we impose an ordering on adding edges then it is enough to look to one side only. Suppose we want to look to the right only. Then we have to built the chart from the right to the left. This means that an edge at position is added only if the chart is complete between position P+1 and the right most position. Such an ordering can be obtained by organising the agenda as a stack.

An example has to be added here.

At the beginning, the egdes for all words such that the right most word is on top of the stack.

Then each edge in the agenda is processed as follows. Let edge(Cat,Begin,End) be the edge to be processed, then:

For each unary rule of the form Cat' --> Cat, add the edge edge(Cat',Begin,End) to the agenda.
For each edge in the chart of the form edge(RightCat,End,NewEnd) and for each rule of the form Cat' --> Cat RightCat, add the edge edge(Cat',Begin,NewEnd) to the agenda.

What this does is process the string from right-to-left, processing one word at a time and recursively adding all possible right-hand expansions of this word to the chart. In this way, all possible constituents are parsed and each constituent is only parsed once.