Exercise 9.1

[This may be your end project]

Implement a top-down chart recognizer in Prolog.

As we have said, you only have to adapt steps 1 (the initialization of chart and agenda) and 2d (how new hypotheses are predicted) of the general algorithm to arrive at a top-down parser.

That means that you can reuse most of the code that we wrote for the bottom-up algorithm. In fact, you only have to change the predicates initialize_chart_bottomup/2 and initialize_agenda_bottomup/1 that take care of the initialization, and the predicates make_new_arcs_bottomup/2 and predict_new_arcs_bottomup/2 that implement step 2d.

initialize chart

Let's first look at the initialization. For top-down processing, we initially write not only the words and their position into the chart but also passive arcs giving us the categories of the words. So, initialize_chart_topdown/2 has to recurse through the input list, and

1. write the approriate scan entries to the chart,

2. retrieve all categories for each word from the lexicon, and

3. assert a passive arc to the chart for each of these categories.

For step 2 and 3, you might use a failure driven loop (remember doall/1 from Section 8.4.2).

initialize agenda

In the initial agenda we want to have all possible hypotheses of how a sentence can be built. Use findall/3 to to find all rules that have s on the left hand side of the arrow and add and active arc from position 0 to position 0.

new arcs

Now, let's look at how new arcs are created. As in the bottom-up case, we apply step 2c to all arcs. But unlike there, we will apply step 2d only to active arcs. make_new_arcs_topdown/2 has to make sure that apply_fundamental_rule/2 and predict_new_arcs_topdown/2 are applied appropriately depending on whether an active or a passive arc is coming in.

The fundamental rule remains the same. But predict_new_arcs_topdown/2 differs from predict_new_arcs_bottomup/2 . The arcs that are coming in now are active: . predict_new_arcs_topdown/2 has to look for all rules that have the category CatToFind on the left hand side and create new active edges for them. These new active edges don't cover anything of the string, yet, and start in the position where the active edge ends.

That is basically it. Remember that a proper documentation is an essential part of your Endprojekt. Give a short specification of what you implemented, i.e. the use and functionality of your program. Then describe in detail (!) how you implemented it. I.e. quote parts (or all) of the code and explain how it works. Third, supply examples calls that can be used for testing your program.

Once again, if you have trouble or see that something doesn't work properly, don't mind. Document this problem and discuss your efforts to solve it. You need not be perfect, but you should show your understanding of the matter.