Master's thesis, University of Düsseldorf, 1997:

Parsing and Generation within uniform Architectures

Sebastian Varges

Abstract:

The thesis compares some approaches integrating parsing and generation within a uniform architecture and details a Prolog implementation of the most uniform one. Additionally, some suggestions for future research directions are made.

Uniform architectures are commonly defined as a reversible grammar combined with a single processing component. Although declarative grammars should be independent of specific processing directions, they are often only used for parsing and are not well suited for generation. In addition to issues of simplicity and elegance, the use of a uniform processing component allows for interleaving parsing and generation. Therefore, it is possible to model phenomena such as monitoring (controlling the generation process with the parser; cf. [Neumann 1994]).

After defining some basic notions such as reversibility, completeness and coherence of parsing and generation, pre-, post-, and in-order tree traversal (corresponding to top-down, bottom-up and left/head-corner analysis), control strategies (breadth-first, depth-first), and handling of alternatives (backtracking versus tabulation/chart), the thesis investigates a number of previous approaches to parsing and generation with respect to these dimensions:

Van Noord's head-driven algorithms: head-corner parsing and semantic-head-driven generation ([van Noord 1993], [Shieber et al. 1990], [van Noord 1997]);

The first proposal of [Shieber 88] to use Earley deduction for parsing and generation;

The use of a head-driven selection strategy for generation in the context of Earley deduction of [Gerdemann 1991];

The Uniform Tabular Algorithm (UTA) of [Neumann 1994], which for the first time truly integrates parsing and generation;

Bottom-up Earley deduction of [Erbach 1995].

The following table gives an overview of the approaches mentioned above:

The last row referring to the uniformity of parsing and generation should not be taken too seriously: it seems that the notion of `uniformity' has not been precisely defined yet. I propose to define it as a uniform analysis strategy, according to which a uniform architecture consists of a reversible grammar and a single processing component which performs only one kind of tree traversal. This is especially useful in case of arbitrarily underspecified input feature structures, e.g. with only parts of the input string instantiated but containing also some semantic or pragmatic information. In such cases, the task of the processing component cannot be determined as `pure generation' or `pure parsing'. If different analysis strategies are used for parsing and generation it is hard to decide which one to use. A uniform analysis strategy avoids this problem. Since head-driven algorithms perform both tasks equally efficiently, a uniform analysis strategy should select the head element of a grammar rule first. However, this imposes additional requirements on the grammar formalism.

References

@PhdThesis{erb95,
  author =       "Gregor Erbach",
  title =        "Bottom-Up Earley Deduction for Preference-Driven Natural Language Processing",
  school =       "Universit{\"a}t des Saarlandes, Saarbr{\"u}cken.
                  Draft of 31.8.1995.",
  year =         "1995"
}

@PhdThesis{gerde91,
  author =       "Dale Gerdemann",
  title =        "Parsing and Generation of Unification Grammars",
  school =       "University of Illinois",
  year =         "1991"
}

@PhdThesis{noord93,
  author =       "Gertjan van Noord",
  title =        "Reversibility in Natural Language Processing",
  school =       "University of Utrecht, 1993",
  year =         "1993"
}

@PhdThesis{neu94,
  author =       "G{\"u}nter Neumann",
  title =        "A Uniform Computational Model for Natural Language Parsing and Generation",
  school =       "Universit{\"a}t des Saarlandes, Saarbr{\"u}cken",
  year =         "1994"
}

@Article{noord97,
  author =       "Gertjan van Noord",
  title =        "An efficient {I}mplementation of the head-corner-{P}arser",
  year =         1997,
  journal =      "{\rm to appear in} Computational Linguistics"
}

@InProceedings{shieb88,
  author =       "Stuart M. Shieber",
  title =        "A {U}niform {A}rchitecture for {P}arsing and {G}eneration",
  pages =        "S.614-619",
  booktitle =    "Proceedings of the 12th International Conference on Computational Linguistics",
  year =         "1988"
}

@Article{shieb90,
  author =       "Stuart M. Shieber and Gertjan van Noord and  Fernando C.N. Pereira and R.C. Moore.",
  title =        "Semantic-head-driven {G}eneration",
  volume =       "16",
  number =       "1",
  pages =        "S.30-42",
  journal =      "Computational Linguistics",
  year =         "1990"
}