Next: A DCG Implementation Up: A Semantic-Head-Driven Generation Algorithm Previous: Source of the
The New Algorithm
Given an analysis tree for a sentence, we define the pivot node as the lowest node in the tree such that it and all higher nodes up to the root have the same semantics. Intuitively speaking, the pivot serves as the semantic head of the root node. Our traversal will proceed both top-down and bottom-up from the pivot, a sort of semantic-head-driven traversal of the tree. The choice of this traversal allows a great reduction in the search for rules used to build the analysis tree.
To be able to identify possible pivots, we distinguish a subset of the
rules of the grammar, the chain rules, in which the semantics
of some right-hand-side element is identical to the semantics
of the left-hand side. The
right-hand-side element will be called the
rule's semantic head.
The traversal, then, will work top-down from the pivot
using a non-chain rule, for if a chain rule were used, the pivot would not be
the lowest node sharing semantics with the root. Instead, the pivot's semantic
head would be. After the non-chain rule is chosen, each of its children must be
generated recursively.
The bottom-up steps to connect the pivot to the root of the analysis tree can be restricted to chain rules only, as the pivot (along with all intermediate nodes) has the same semantics as the root and must therefore be the semantic head. Again, after a chain rule is chosen to move up one node in the tree being constructed, the remaining (non-semantic-head) children must be generated recursively.
The top-down base case occurs when the non-chain-rule has no nonterminal children, i.e., it introduces lexical material only. The bottom-up base case occurs when the pivot and root are trivially connected because they are one and the same node.
Next: A DCG Implementation Up: A Semantic-Head-Driven Generation Algorithm Previous: Source of the
Gertjan van Noord
Thu Nov 24 18:39:44 MET 1994