Browse Theses

The thesis discusses natural language generation with Head-Driven Phrase Structure Grammar (HPSG). A series of six implementations are described. The first three implementations are all based on the HPSG theory of the 1994 textbook by Pollard and Sag. The next three relatively experimental implementations are based on significant revisions of HPSG theory after 1994. Most of the systems use a head-driven generation algorithm, as it is argued that head-driven generation is the natural approach with a head-driven grammar such as HPSG.The first implementation, which uses the ALE typed feature system of Carpenter and Penn, is a fairly full implementation of the 1994 HPSG textbook. The textbook version of HPSG is taken as an already known starting point without detailed explanation, and the description is concerned primarily with how the theory is implemented. This first implementation follows the 1994 HPSG theory closely, but it can only perform parsing, not generation.By contrast, the second implementation can do generation as well as parsing. Three head-driven generation algorithms are compared: van Noord's head-driven bottom-up generator, Shieber et al's semantic head-driven generator and Haruno et al's chart-based semantic head-driven generator. Matsumoto's SAX parser and SGX chart-based semantic head-driven generator are introduced. An English Engine is described which uses SAX and SGX for parsing and generation with a DCG grammar which has many HPSG features and mechanisms. However the grammar does not include inheritance-based typed feature structures and therefore only approximates to HPSG theory.The third implementation combines the strengths of the first two into a single framework by using Erbach's ProFIT typed feature system. This completely revised version of English Engine performs efficient parsing and generation using SAX and SGX, but combines them with an HPSG grammar based on an inheritance-based typed feature structure representation using ProFIT. This system includes an implementation of delayed lexical choice in generation with HPSG, which exploits the monotonicity of subsumption in the sort hierarchy. This approach to delayed lexical choice, based on deliberate underspecification of features, extends and generalizes previous approaches.A number of revisions of HPSG theory have been proposed since 1994. Some of the revisions, and experimental implementations of their main ideas, are described in the second part of the thesis. The fourth implementation is based on the proposals of Sag (1997) to eliminate all empty categories from HPSG theory. This has specific importance for the implementations in this thesis, as SAX and SGX do not permit empty categories. Sag's revised analysis of English relative clauses is implemented in ProFIT using a hierarchy of construction types. Constraints on phrase types are implemented by ProFIT templates. This implementation handles all forms of English relative clauses without using empty categories, but it can only do parsing, not generation.The thesis includes a proposal for another theoretical revision in HPSG: the lexicalization of context. The proposed change strengthens the role of semantic heads in the overall organization of HPSG grammar. It is needed to solve fundamental problems with handling contextual information in head-driven generation. Theoretical, computational and linguistic justifications for the proposal are presented. These include a sketch of an analysis of register variation, proposing a lexicalist account of case assignment and register restrictions within Sag's revised analysis of English relative clauses. The fifth implementation is a basic implementation of these theoretical revisions.Another major theoretical revision is the use of Minimal Recursion Semantics (MRS) in HPSG. In order to perform generation using MRS, the sixth implementation switches to non-head-driven generation. Phillips' bag generation algorithm for categorial grammar and indexed logical form is adapted for use with HPSG and MRS. The algorithm is then modified to perform incremental generation with HPSG, using simple rules for utterance continuation and repairs. Difficulties in using HPSG for incremental generation are discussed, and a chart-based solution is proposed.