Table-driven parsing of natural language with constraint-based grammars

In this dissertation, it is shown how efficient natural language parsing with constraint-based grammars can be achieved. In so doing, a variant of the LR-parsing algorithm is developed that deals with grammars using feature-based categories. It is shown that constraint-based grammars bring about the problems of potential nontermination and unnecessary nondeterminism with the LR parsing method, which do not arise from grammars using monadic categories. To achieve a terminating and deterministic algorithm, an extended method for constructing parsing tables is developed. The extended LR method is unable to handle schematic rules as in HPSG and CUG, however. To remedy this problem, a rule inference algorithm is developed that instantiates underspecified rules into more specified ones containing enough information to construct sets of items and parsing tables. The implementation and evaluation of the extended LR parsing method is also discussed.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Linguistics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Lee, Kang-Hyuk

Contributors dc:contributor

• Morgan, Jerry L.

• Language, Linguistics

Statement dc:rights

• Copyright 1993 Lee, Kang-Hyuk

Language dc:language

eng

Identifier

AAI9314899
(UMI)AAI9314899

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/22566