Next: Why head driven Up: Head driven bottom-up Previous: Head driven bottom-up
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) ---> [] ).
predict_rule(Head,Mother,Others,_):-
( Mother ---> [Head|Others] ).
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.
Next: Why head driven Up: Head driven bottom-up Previous: Head driven bottom-up
Gertjan van Noord
Fri Nov 25 13:07:08 MET 1994