<em>BUG1</em>: a head driven bottom-up generator

## BUG1: a head driven bottom-up generator

In this section I will present a simple variant of a head driven, bottom-up generator, called BUG1, which I use as prototypical for the approaches presented in [24][30][23][5].

As a simplifying assumption I will require for the moment that rules have a head (unless of course a rule does not have any daughters). Moreover, the logical form of this head must be identical to the logical form of the mother node; i.e. the mother node and the head share their logical form. Note that for each rule in grammar 2.1 it is possible to choose a head that will fulfill this requirement.

The algorithm consists of two parts. The prediction part predicts a lexical entry. The connection part tries to build a parse tree matching the top goal and starting from this lexical entry. The algorithm BUG1 proceeds as follows. Its input will be some node with some logical form . First BUG1 tries to find the pivot, a lexical entry whose logical form unifies with (the prediction step). Note that the logical form of this lexical entry will be instantiated by the prediction step. Now BUG1 is going to build from this pivot larger entities as follows. It selects a rule whose head unifies with the pivot. The other daughters of this rule are generated recursively. For the mother node of this rule this procedure will be repeated: selecting a rule whose head unifies with the current node, generate the daughters of this rule and connect the mother node. This part of the algorithm, called the connection part, will end if a mother node has been found that unifies with the original node . In this can be defined as in:

```bug1(Node):-
predict_word(Node,Small),
connect(Small,Node).

connect(Node,Node).
connect(Small,Big) :-
predict_rule(Small,Middle,Others,Big),
gen_ds(Others),
connect(Middle,Big).

gen_ds([]).
gen_ds([Node|Nodes]):-
bug1(Node),
gen_ds(Nodes).

predict_word(node(_/LF,_),node(S/LF,P)):-
( node(S/LF,P) ---> [] ).

As an example, consider what happens if this algorithm is activated by the query

First the clause will select the pivot, a lexical entry with a logical form that can unify with . The definition for is a possible candidate. This results in a node

This node is going to be connected to the original node by the clauses. To be able to connect the to (ultimately) the a rule will be selected of which the can be the head. The rule is a possible candidate. If this rule is selected the following instantiations are obtained:

The list is generated recursively, instantiating into . Therefore the next task is to connect

This node can be unified with the head of rule , thereby instantiating the logical form of the . This again is generated recursively and the node of the rule will become:

This node can easily be connected to the by the first clause for , because it can be unified with the node; the variable in the query will be instantiated into .

As another example consider the case where the logical form is built in a semantically non-monotonic way:

The predictor step will select the lexical entry for , after which the generator will try to connect this to the node, as in the foregoing example. After the generation of the first element of the complement list, , the first entry of the complement list of the dominating is fully instantiated, so the particle can be generated without problem. In the connect step the rule can be applied after which the connect step terminates, instantiating as . In section 3.5 I will give some more interesting examples.