The Psychophysics Psyber Lab




Linton Miller's Thesis

Flexible Table-Driven Parsing for Natural Language Processing

Linton Miller


Submitted for the degree of Master of Science in Computer Science
Victoria University of Wellington, New Zealand


Ambiguity is a major difficulty for natural language processing (NLP) systems. The longer that ambiguities in a sentence remain unresolved, the more work an NLP system may perform in considering alternative interpretations of the sentence. Thus, for efficiency, an NLP system should resolve ambiguities as early as possible in processing.

This thesis describes L* parsing - an algorithm for table-driven
parsing, designed to permit efficient processing of natural language by facilitating the early resolution of ambiguity. The algorithm is a generalisation of GLR parsing that allows grammar rules to be used whenever they may provide useful syntactic information to an NLP system.

L* parsing defines a general framework for specifying a variety of
parser control strategies. Different control strategies can be expressed by specifying exactly when grammar rules are to be used. This thesis presents one possible control strategy, designed to provide syntactic information that enables useful semantic and pragmatic processing, and describes a method of compiling this strategy into a parse table.


Last updated 08 Nov 2009 04:37 PM

This psyber lab webpage is maintained by Judi Lapsley Miller
Comments, suggestions, and enquires always welcome.
Generic Copyright Statement, 2000-2010. All rights reserved.