IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Parsing and generation of unification grammars

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/20955

Files in this item

File Description Format
PDF 9136597.pdf (11MB) Restricted to U of Illinois (no description provided) PDF
Title: Parsing and generation of unification grammars
Author(s): Gerdemann, Dale Douglas
Doctoral Committee Chair(s): Hinrichs, Erhard
Department / Program: Linguistics
Discipline: Linguistics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Language, Linguistics Computer Science
Abstract: In this dissertation, it is shown that declarative, feature-based, unification grammars can be used for efficiently both parsing and generation. It is also shown that radically different algorithms are not needed for these two modes of processing. Given this similarity between parsing and generation, it will be easier to maintain consistency between input and output in interactive natural language interfaces. A Prolog implementation of the unification-based parser and DAG unifier is provided. The DAG unifier includes extension to handle disjunction and negation.The parser presented in this thesis is based on Stuart Shieber's extensions of Earley's algorithm. This algorithm is further extended in order to incorporate traces and compound lexical items. Also, the algorithm is optimized by performing the subsumption test on restricted DAGs rather than on the full DAGs that are kept in the chart. Since the subsumption test can be very time consuming, this is a significant optimization, particularly for grammars with a considerable number of (nearly) left recursive rules. A grammar which handles quantifier scoping is presented as an example of such a grammar.For generation, the algorithm is modified in order to optimize the use of both top-down and bottom-up information. Sufficient top-down information is ensured by modifying the restriction procedure so that semantic information is not lost. Sufficient bottom-up information is ensured by making the algorithm head-driven. Generation also requires that the chart be modified so that identical phrases are not generated at different string positions. It is shown how readjustments to the chart can be made whenever a duplicate phrase is predicted. The generator in this thesis does not perform equally well with all types of grammars. Grammars employing type raising may cause the generator to go into an unconstrained search. However, given the independently motivated principles of minimal type assignment and type raising only as needed, it is shown how such unconstrained searches can be avoided.Finally, suggestions are made as to how unification grammars can be developed in order to handle difficult problems such as partially free word order, bound variables for semantic interpretation and resolving feature clashes in agreement.
Issue Date: 1991
Type: Text
Language: English
URI: http://hdl.handle.net/2142/20955
Rights Information: Copyright 1991 Gerdemann, Dale Douglas
Date Available in IDEALS: 2011-05-07
Identifier in Online Catalog: AAI9136597
OCLC Identifier: (UMI)AAI9136597
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 0
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key