Bottom Up Active Chart Recognition (continued)

Continuation.

process_agenda/1 is a recursive predicate. Its argument is the list representing the agenda. It takes the first arc off that list and processes it. This may add new arguments to the agenda. In the end it recursively calls itself with the new agenda as argument. The recursion stops when the agenda is empty.

Processing of an arc works as follows. We make sure that the arc is not in the chart yet, and add it. (That's step 2b of the general algorithm.) The predicate make_new_arcs_bottomup/2 then carries out steps 2c and 2d which may create new arcs. These are appended to the front of the agenda. If the arc is already in the chart, we throw it away and look at the rest of the agenda.

process_agenda([]).

process_agenda([Arc|Agenda]) :-
        \+ Arc,!,
        assert(Arc),
        %%% nl,write('New arc on chart: '), write(Arc), nl,
        make_new_arcs_bottomup(Arc, NewArcs),
        append(NewArcs, Agenda, NewAgenda),
        %%% write('New arcs on agenda: '), write(NewArcs), nl,
        process_agenda(NewAgenda).

process_agenda([_|Agenda]) :-
        process_agenda(Agenda).

There are two steps in the general algorithm which generate new rules: steps 2c and 2d. In the bottom-up case, step 2c is applied to all edges, while step 2d is applied only to passive edges. The predicate make_new_arcs_bottomup/2 therefore has two clauses which carry out only step 2c (apply_fundamental_rule/2) or step 2c and step 2d (predict_new_arcs_bottomup/2) depending on whether the arc that's coming in is active or passive.

make_new_arcs_bottomup(Arc, NewArcs) :-
        Arc = arc(_,_,_,_,[_|_]),
        apply_fundamental_rule(Arc, NewArcs).

make_new_arcs_bottomup(Arc, NewArcs) :-
        Arc = arc(_,_,_,_,[]),
        apply_fundamental_rule(Arc, NewArcs1),
        predict_new_arcs_bottomup(Arc, NewArcs2),
        append(NewArcs1, NewArcs2, NewArcs).

apply_fundamental_rule/2 tries to apply the fundamental rule to the arc given in the first argument. There are two clauses: one for those cases where we are dealing with a passive arc and one for those cases where we are dealing with an active arc. In the first case, we have to look for an active arc which satisfies the following two conditions:

• It must end in the starting position of the passive arc.

• The next category that the active arc has to find must be what the passive arc has on its left hand side.

We again use findall/3 to collect all possible solutions.

apply_fundamental_rule(arc(I, J, Cat, Done, [SubCat|SubCats]), NewArcs) :-
        findall(arc(I, K, Cat, [SubCat|Done], SubCats),
                arc(J, K, SubCat, _, []),
                NewArcs
               ).        

In case we are dealing with an active arc, we looking for a passive arc in the chart.

apply_fundamental_rule(arc(J, K, Cat, _, []), NewArcs) :-
        findall(arc(I, K, SuperCat, [Cat|Done], Cats),
                arc(I, J, SuperCat, Done, [Cat|Cats]),
                NewArcs
            ).

When processing the chart in a bottom-up fashion we only apply step 2d to passive rules. In that case, we look for grammar rules that have the left hand side of the arc as the first symbol in the right hand side. findall/3 again gives us all possible solutions.

predict_new_arcs_bottomup(arc(J, _, Cat, _, []), NewArcs) :-
        findall(arc(J, J, SuperCat, [], [Cat|Cats]),
                SuperCat ---> [Cat|Cats],
                NewArcs
            ).