Robust chart parsing with mildly inconsistent feature structures

Abstract

We introduce the formal underpinnings of our theory of nonclassical feature structures The resulting expanded universe of feature structures has direct implications for robust parsing for linguistic theories founded upon feature theory We present an implementa tion of a robust chart parser for Headdriven Phrase Structure Grammar HPSG The problem of relaxed unication is in limiting it so that arbitrarily nongrammatical in puts needn t be accepted In the worst case excessively relaxed parsers cannot provide meaningful interpretations to process However parsers which can guarantee minimally nongrammatical inconsistent interpretations provide an important tool for grammar de velopment and online robust processing of natural language Our parser prefers maximally consistent interpretations and accommodates inconsistencies by discovering the minimal set of constraints that need to be relaxed for a parse to go through without employing backtracking or post processing The system is di erent from other related relaxational techniques for unication grammars which require advanced naming of features whose constraints are allowed to be relaxed Yet it is compatible with those approaches in that there is a well dened location for preferences on sources of inconsistency to be named

as well as for resolution of inconsistent information We use a simple approach to the problem of unknown words and suggest generalization of that for coping with missing and extra elements in an input