Bottom Up Active Chart Recognition

For representing the chart, we will again use the Prolog database. The agenda will be represented as a list. New edges are added by just appending them to the front (or the end).

For representing the chart, we will again use the Prolog database. The agenda will be represented as a list. New edges are added by just appending them to the front (or the end).

The main predicate is active_chart_recognize/1 (see active_chart_bottomup.pl ). It takes a list of words (the input sentence) as argument and succeeds if it can:

1. Initialize the chart and agenda. (step 1 of the general algorithm)

2. Build the chart while processing the agenda until it's empty. (step 2)

3. End up with a chart containing a passive s arc that leads from the first node to the last node. (step 3)

Here is the code:

active_chart_recognize(Input) :-
        cleanup,
        %%% step 1
        initialize_chart_bottomup(Input, 0),
        initialize_agenda_bottomup(Agenda),
        %%% step 2
        process_agenda(Agenda),
        %%% step 3
        length(Input, N),
        arc(0, N, s, _, []).

Now, let's look at the initialization predicates. We said that the initial chart is exactly as for the passive chart parser (see Section 8.4.1). So, initialize_chart_bottomup/2 looks exactly like the initialze_chart/2 predicate of the last chapter:

initialize_chart_bottomup([], _).

initialize_chart_bottomup([Word|Input], From) :-
        To is From + 1,
        assert(scan(From, To, Word)),
        initialize_chart_bottomup(Input, To).

The initial agenda should contain passive arcs recording the position and category of the words of the input sentence. We retrieve one word and its category using the following sequence of goals

scan(From, To, Word),
lex(Word, Cat).

To get all categories for all of the words, we simply use findall. The passive arc is constructed directly in the first argument of findall.

initialize_agenda_bottomup(Agenda) :-
        findall(arc(From, To, Cat, [Word], []),
                (
                 scan(From, To, Word),
                 lex(Word, Cat)
                ),
                Agenda
               ).

This is what we need in order to carry out steps 1 and 3 of the general algorithm in a bottom-up fashion. Now, let's look at step 2, the loop which does most of the work.